leetcode solution

532 K-diff Pairs in an Array     Two pointers, O(NlgN) time and O(1) space (a) sort the array (b) Use the first pointer (the rear pointer) to iterate each element in the array. Set the second pointer (the front pointer) to first pointer plus one. (c) while the second pointer is still valid (index within range) and the diff between two pointer is less than k. increase the front pointer. (d) check whether the diff is exactly equal to k, if so increase the counter. (e) while next of rear pointer is still valid and the pointee value is equal to the next pointee, increase rear pointer (f) return the counter in the end. 826 Most Profit Assigning Work   (a) zip difficulty and profit as jobs. (b) sort jobs and sort 'worker'. (c) 2 pointers idea, for each worker, find his maximum profit he can make under his ability. Because we have sorted jobs and worker, we will go through two lists only once. It will be only O(M+N). Time Complexity O(NlogN + ...

344 Reverse String      Use two pointers i, j. keep switching elements at position i, j while i < j.     string reverseString(string s) {        for (int i = 0, j = s.size() - 1; i < j; i++, j--)            swap(s[i], s[j]);                  return s;     } 345 Reverse Vowels of a String      Similar with 344  Reverse String ,  except we need to guard the swap operation conditionally based on whether the current two chars are vowels or not. 283 Move Zeroes      Use two pointers, the front iterates the elements in the array. while the tail one keeps the current store position. If front is not zero, store it to the tail position and increase tail pointer. After the loop, set all the remaining with zero. 349 Intersection of Two Arrays      ...

(1) Standard BS:   在有序（非降序）数组中查找一个target值，数组中元素没有重复，找到target则返回该元素对应的index，找不到则返回-1  注意1：如果是start < end，那么当target等于num[num.length-1]时，会找不到该值。  注意2：因为num[mid] > target, 所以如果有num[index] == target, index一定小于mid，能不能写成end = mid呢？举例来说：num = {1, 2, 5, 7, 9}; 如果写成end = mid，当循环到start = 0, end = 0时（即num[start] = 1, num[end] = 1时），mid将永远等于0，此时end也将永远等于0，陷入死循环。也就是说寻找target = -2时，程序将死循环。 注意3：因为num[mid] < target, 所以如果有num[index] == target, index一定大于mid，能不能写成start = mid呢？举例来说：num = {1, 2, 5, 7, 9}; 如果写成start = mid，当循环到start = 3, end = 4时（即num[start] = 7, num[end] = 9时），mid将永远等于3，此时start也将永远等于3，陷入死循环。也就是说寻找target = 9时，程序将死循环。 int binarySearchStandard(vector<int> &num, int target){ int start = 0; int end = num.length - 1; while(start <= end){ // 注意1 int mid = start + ((end - start) >> 1); if(num[mid] == target) return mid; else if(num[mid] > target){ end = mid - 1; //注意2 } ...