Notes

tags: In-place WikiPedia: https://en.wikipedia.org/wiki/In-place%5Falgorithm Let see two examples before we go further: As above we can see, to reverse a array in-place, we just need swap each two elements in the array from both side to middle. The pseudo code from WikiPedia: function reverse_in_place(a[0..n-1]) for i from 0 to floor((n-2)/2) tmp := a[i] a[i] := a[n − 1 − i] a[n − 1 − i] := tmp The loop travels the array to the middle and swap each other in the list, two points we must be noticed: We stop the element at(not before): floor((n - 2) / 2), It’s both 1 of the two above figures. We swap current element with n - 1 - i.

tags: Algorithm

tags: In-place,LeetCode101,In-place Reverse class Solution { public: void reverseString(vector<char>& s) { if (s.size() == 1) { return; } for (int i = 0; i <= (s.size() - 2) / 2; ++i) { swap(s[s.size() - 1 - i], s[i]); } } };

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; } };