DP When it comes to even numbers, i.e, 2,4,6,8, their binary should be like ‘10’, ‘100’, ‘110’, ‘1000’ so one notable difference is their unit digit is always 0, which means when you call >> 1- shift one bit rightwards and also means dividing by 2- would cause no change to the count of ‘1’ in the binary string.
Vice versa, when you meet odd numbers, shifting one bit rightwards always eliminates one ‘1’ digit from original binary string, that is why we should “compensate” one ‘1’ character to the count.
To sum up, when you meet even number the count of ‘1’s is always the same as its half number, on the other hand, remember to plus one to the odds’ half number.
1 2 3
int[] f = newint[num + 1]; for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1); return f;
public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>() for(int i = 0; i < nums.length - 2; i++) { if(i == 0 || nums[i] != nums[i - 1]) { int low = i + 1; int high = nums.length - 1; int remain = 0 - nums[i]; while(low < high) { if(nums[low] + nums[high] == remain) { res.add(Arrays.asList(nums[i], nums[low], nums[high])); while(low < high && nums[low + 1] == nums[low]) low++; while(low < high && nums[high - 1] == nums[high]) high--; low++; high--; }elseif(nums[low] + nums[high] < remain) low++; else high--; } } } return res; }
3Sum closest
找最接近的sum（也可能相等）
增加判断条件Math.abs小的话，就要更新。
3Sum With Multiplicity
每一中情况都要考虑到–排列组合
1 2 3 4 5 6 7 8 9 10 11 12
if (A[j] == A[k]) { // If A[j...k] are all equal, then there are C(k - j + 1, 2) // combinations that meet the requirement.取两个 res = (res + (k - j + 1) * (k - j) / 2) % m; break; } int l = 1, r = 1; while (j + l < k && A[j + l] == A[j]) { ++l; } // l: number of elements equal to A[j]. while (j < k - r && A[k - r] == A[k]) { ++r; } // r: number of elements equal to A[k]. res = (res + l * r) % m; // found l * r cases that meet the requirement. j += l; // forward j by l steps. k -= r; // backward k by r steps.
Sum of Square Numbers
c = a^2 + b^2
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
publicbooleanjudgeSquareSum(int c){ int limit = (int)Math.sqrt(c); int low = 0; while(low<=limit){ int sum = low*low + limit*limit; if(c==sum){ returntrue; } if(sum<c){ low++; } else { limit--; } } returnfalse; }
基础字符串操作
reverse
1 2 3 4 5 6
public String reverse(String s){ StringBuilder res=new StringBuilder(); for (int i = 0; i < s.length(); i++) res.insert(0,s.charAt(i)); return res.toString(); }
split 对应API public String[] split(String regex, int limit)
1 2 3 4 5 6 7 8 9 10 11 12 13
public String[] split(String s) { ArrayList < String > words = new ArrayList < > (); StringBuilder word = new StringBuilder(); for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ' ') { words.add(word.toString()); word = new StringBuilder(); } else word.append( s.charAt(i)); } words.add(word.toString()); return words.toArray(new String[words.size()]); }
indexOf（int，ch）：先看第一个indexOf它返回值是int，在看它的参数（int，ch）意思就是使用者可以给参数一个‘char’字符所代表的int值，然后去从前向后找到该字符在字符串中第一次出现处的索引，当然了我们不可能记得住每一个char的值所以我们在使用时直接用String s=abcdef; int i=s.indexOf(‘d’) 这种方式就可以了，char类型会自动提升为int类型，还有就是要注意如果返回值为-1，就说明索引越界了；
* I have seen many variants using Binary Search, the key difference is the search range. It seems easy to do it but actually there are some traps we need to take care. I made this just for a note for me.
Search range summary:
* [1, Integer.MAX_VALUE](easy but not recommend)
* [1, x](recommended)
* [1, x/2](you need to do math to prove it)
* For case 2 and case 3, we need to take care of the corner case by making sure right >= left for [left, right], so:
2. x >= 1 for [1, x] => so we need to take care of the corner case: x < 1
3. x/2 >= 1 for [1, x/2]=> x >= 2 => so we need to take care of the corner case: x < 2
1 2 3 4 5 6 7 8 9 10 11
classSolution{ publicintmySqrt(int x){ long l=0,r=x; //in case of overflow while(l<r){ long mid=l+(r-l)/2+1; if(mid*mid>x) r=mid-1; else l=mid; } return (int)l; } }
public List<Integer> findDuplicates(int[] nums){ List<Integer> res = new ArrayList<>(); for (int i = 0; i < nums.length; ++i) { int index = Math.abs(nums[i])-1;//要去绝对值 索引 if (nums[index] < 0)//是负的说明，之前遇到过 res.add(Math.abs(index+1)); nums[index] = -nums[index]; } return res; }