Recently, I am brushing leetcode, and I want to record some code skills and ideas, so I wrote this blog. Because LeetCode will continue to brush, so whenever there are notes, I will keep updating here.

* bit operation:

  • N & n-1: Changes the last 1 in the binary representation of n to 0
// Check if there is only one 1 in n
return n & (n-1) = =0
Copy the code
  • N >> 1: The logical move to the right is equivalent to dividing n by 2
  • I >> j&1: Shift I arithmeatically to the right by j bits, and then check if the lowest digit is 1. This operation can be used to determine how many 1’s there are in the binary representation of a number, for example:
// The sum of this code is the number of 1 bits in the binary representation of TMP
int sum = 0;
while(tmp ! =0) {if ((tmp & 1) = =1)
      sum ++;
  tmp = tmp >> 1;
}
return sum;
Copy the code

* Convert a numeric string to an int number:

String str = "25578"
int num = 0;
for(int i=0; i<str.length(); i++){
 num = num*10 + str.charAt(i)-'0';
}
Copy the code

* Check whether it is a palindrome string:

public boolean isPalindrome(String sb, int start, int end){   
for (int i=start,j=end; i<j; i++,j--){       
    if(sb.charAt(i) ! = sb.charAt(j))return false;   
}    
return true;
}
Copy the code

* Two ways of writing dichotomy

Pass an array nums, query the target value, and return the subscript of target

  • Method 1:
public int search(int[] nums, int target){
        if (nums.length == 0)
            return -1;
        int left = 0, right = nums.length;
        while (left < right){
            int mid = (left+right)/2;
            if (nums[mid] == target){
                return mid;
            }else if (nums[mid] > target){
                right = mid;
            }else
                left = mid+1;
        }
        return -1;
    }
Copy the code
  • Method 2:
public int search(int[] nums, int target){
        if (nums.length == 0)
            return -1;
        int left = 0, right = nums.length-1;
        while (left <= right){
            int mid = (left+right)/2;
            if (nums[mid] == target){
                return mid;
            }else if (nums[mid] > target){
                right = mid-1;
            }else
                left = mid+1;
        }
        return -1;
    }
Copy the code

Notice the difference between the two, there are three things that are different when it comes to cyclic invariants. It’s not hard to think about dichotomies, but to write them right you have to think about boundary conditions, and using loop invariants to control boundary conditions helps you understand how to write code, right

To understand cyclic invariants, see this post on “cyclic invariants for binary lookup.” You don’t need to memorize boundary conditions

* Determines whether a string of lowercase letters has duplicate letters

private boolean match(StringBuilder builder) {
        String s = builder.toString();
        int[] counter = new int[26];
        for (int i = 0; i < s.length(); i++) {
            int ch = s.charAt(i)-'a';
            counter[ch]++;
            if (counter[ch] > 1) {
                return false; }}return true;
    }
Copy the code