Notes

tags: Binary Search,LeetCode101 There is three corner cases must be handled if we don’t find target in nums: Return r + 1 if target is greater than right. Or return mid + 1 if target is greater than mid. Otherwise return mid. class Solution { public: int searchInsert(vector<int>& nums, int target) { int l = 0, r = nums.size() - 1; int mid = r / 2; while (l != r) { mid = l + (r - l) / 2; if (target == nums[mid]) { return mid; } if (target < nums[mid]) { r = mid; } else { l = mid + 1; } } if (target > nums[r]) { return r + 1; } if (target > nums[mid]) { return mid + 1; } return mid; } };

tags: Divide-and-Conquer,LeetCode101,Binary Search class Solution { public: bool searchMatrix(vector<vector<int> > &matrix, int target) { int n = matrix.size(); int m = matrix[0].size(); int l = 0, r = m * n - 1; while (l != r){ int mid = l + (r - l) / 2; if (matrix[mid / m][mid % m] < target) l = mid + 1; else r = mid; } return matrix[r / m][r % m] == target; } };

tags: Algorithm WIKIEPEDIA: https://en.wikipedia.org/wiki/Divide-and-conquer%5Falgorithm The points should been noted: The middle position is not (right - left) / 2, it must be left + ((right - left) / 2).

tags: Bit Manipulation,Bitwise Operator: XOR According to bitwise operator XOR: x ^ x = 0 y ^ 0 = y We apply the XOR operator to all the nums, all the same numbers will apply x ^ x = 0, and then y ^ 0 = y will result the single number. class Solution { public: int singleNumber(vector<int>& nums) { int xorN = 0; for (auto iter = nums.begin(); iter != nums.end(); ++iter) { xorN ^= *iter; } return xorN; } };

tags: Algorithm