53-I 在排序数组中查找数字 I
利用二分查找法，可以定位到第一个或者最后一个查找元素。
查找第一个时，如果中间元素小于或大于查找元素，都可以将区间缩小一半；而中间元素等于查找元素时，需要判断中间元素是不是第一个出现的元素，判断方式为查看前一个元素，如果前一个元素等于查找元素，第一个元素则出现在前一半区间中；如果前一个元素不等于查找元素，第一个元素就是当前元素，可以返回。
查找最后一个出现的元素位置也是类似的做法。
class Solution {
public:
int search_first(vector<int> &nums, int target, int left, int right){
if(left > right)
return -1;
int mid = left + (right - left) / 2;
if(nums[mid] > target)
return search_first(nums, target, left, mid - 1);
if(nums[mid] < target)
return search_first(nums, target, mid + 1, right);
// nums[mid] == target
// 这里利用了短路的做法
if(mid == left || nums[mid - 1] != target)
return mid;
return search_first(nums, target, left, mid - 1);
}
int search_last(vector<int> &nums, int target, int left, int right){
if(left > right)
return -1;
int mid = left + (right - left) / 2;
if(nums[mid] > target)
return search_last(nums, target, left, mid - 1);
if(nums[mid] < target)
return search_last(nums, target, mid + 1, right);
// nums[mid] == target
if(mid == right || nums[mid + 1] != target)
return mid;
return search_last(nums, target, mid + 1, right);
}
int search(vector<int>& nums, int target) {
int first = search_first(nums, target, 0, nums.size() - 1);
if(first < 0)
return 0;
int last = search_last(nums, target, 0, nums.size() - 1);
return last - first + 1;
}
};
53 - II. 0～n-1中缺失的数字
二分查找法，如果中间数字等于下标数，缺失的数字就在右半边；否则，查看左边的数字是不是等于下标，等于的话，中间下标就是缺失的数字，否则在左半边。
实现用了递归和迭代两种实现方法：
迭代
class Solution {
public:
int missingNumber(vector<int>& nums) {
int left = 0, right = nums.size();
int mid, ret;
while(left < right){
mid = left + (right - left) / 2;
if(nums[mid] == mid){
left = mid + 1;
}
else{
if(mid == 0 || (mid > 0 && nums[mid - 1] == mid - 1))
return mid;
else
right = mid;
}
}
return left;
}
};
递归
public:
int binary_search(vector<int>& nums, int left, int right){
if(left >= right)
return left;
int mid = left + (right - left) / 2;
if(nums[mid] == mid)
return binary_search(nums, mid + 1, right);
if(mid == 0 || (mid > 0 && nums[mid - 1] == mid - 1))
return mid;
return binary_search(nums, left, mid);
}
int missingNumber(vector<int>& nums) {
return binary_search(nums, 0, nums.size());
}
};
54 二叉搜索树的第k大节点
二叉搜索树的中序遍历是有序的。因此对二叉搜索树进行逆中序遍历，返回值为TreeNode指针，未找到第k个节点之前，返回空指针，找到后返回该节点指针。每次右孩子遍历完，将k减一，k减到1时，找到了第k大的节点。
这个题目的代码逻辑比较难写，需要重点学习下。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* kthLargestCore(TreeNode* root, int &k){
if(root == nullptr)
return nullptr;
TreeNode* target = kthLargestCore(root -> right, k);
if(target == nullptr){
if(k == 1)
target = root;
k--;
}
if(target == nullptr)
target = kthLargestCore(root -> left, k);
return target;
}
int kthLargest(TreeNode* root, int k) {
TreeNode* target = kthLargestCore(root, k);
return target -> val;
}
};
55-II 平衡二叉树
该问题可以用二叉树的后序遍历解决，首先判断左右子树分别是否平衡，如果左右子树平衡，再根据左右子树的高度，判断该树是否平衡，并且返回树高度。这样只需要遍历一次即可。
另一个技巧，如果有多个需要返回的值，可以将其中某些值的引用作为参数传回来。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced_Depth(TreeNode* root, int &depth){
if(root == nullptr){
depth = 0;
return true;
}
int left_depth = 0, right_depth = 0;
if(isBalanced_Depth(root -> left, left_depth) && isBalanced_Depth(root -> right, right_depth)){
if(abs(left_depth - right_depth) <= 1){
depth = max(left_depth, right_depth) + 1;
return true;
}
else return false;
}
else return false;
}
bool isBalanced(TreeNode* root) {
int depth = 0;
return isBalanced_Depth(root, depth);
}
};
56-I 数组中只出现一次的两个数字
这个题目有点难，如果只有一个数字只出现一次，那么我们可以利用同一个数异或两次是0，将所有数字进行异或操作，最后的结果就是只出现一次的数字。
如果有两个数字只出现一次，那么将所有数字异或一次，得到的结果是这两个数字的异或结果，这个数字一定不为0。找到这个数字中出现1的某一位，则这两个只出现一次的数中，一个是这一位等于1，一个是不等于1.通过这一位是否为1，可以将这两个数字分到两个数组中，之后，分别在这两个数组中进行异或，就可以得到这两个数字。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int EORresult = 0;
for(int i = 0; i < nums.size(); i++)
EORresult ^= nums[i];
// find first 1
int k = 0;
while(EORresult % 2 == 0){
EORresult = EORresult >> 1;
k++;
}
int check_mod = 1 << k;
// divide nums into two parts
int num1 = 0, num2 = 0;
for(int i = 0; i < nums.size(); i++){
if(nums[i] & check_mod)
num1 ^= nums[i];
else
num2 ^= nums[i];
}
vector<int> ret = {num1, num2};
return ret;
}
};
56-II 数组中唯一只出现一次的数字
其他数字都出现3次，因此，这个题目就不能用异或来做了，但还是可以用位运算的思路。每个数字的每一位相加三次，这一位的和一定可以整除3.那么将所有数字的每一位求和，如果某一位的和可以整除3，那么这个只出现一次的数字在这一位上一定为0，否则为1。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int bit_sum[32] = {0};
for(int i = 0; i < nums.size(); i++){
int tmp = nums[i], j = 0;
while(tmp){
if(tmp & 1)
bit_sum[j]++;
tmp = tmp >> 1;
j++;
}
}
for(int i = 0; i < 32; i++)
bit_sum[i] = bit_sum[i] % 3;
int num = 0;
for(int i = 31; i >= 0; i--)
num = (num << 1) + bit_sum[i];
return num;
}
};
57-II 和为s的连续正数序列
还是用双指针，left和right，当前和小于target时，right++，大雨target时，left++，等于时，记录下当前的序列。
class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> ret;
int left = 1, right = 2, sum = 3;
while(2 * left < target){
if(sum == target){
vector<int> tmp;
for(int i = left; i <= right; i++)
tmp.push_back(i);
ret.push_back(tmp);
}
if(sum <= target){
right++;
sum += right;
}
else{
sum -= left;
left++;
}
}
return ret;
}
};
58 翻转单词顺序
先翻转整句话，再翻转每个单词。比较麻烦的就是空格的处理，所以开辟了额外空间，如果空格没问题，就可以原地翻转了。
class Solution {
public:
string reverse_string(string s, int begin, int end){
string rev_s = "";
for(int i = end; i >= begin; i--)
rev_s += s[i];
return rev_s;
}
string reverseWords(string s) {
// remove extra spaces
s = reverse_string(s, 0, s.size() - 1);
string ret_s = "";
int begin = 0, end = 0, str_len = s.size();
while(end < str_len){
while(begin < str_len && s[begin] == ' ')
begin++;
if(begin == str_len)
break;
end = begin;
while(end < str_len && s[end] != ' ')
end++;
if(ret_s.size())
ret_s += ' ';
ret_s += reverse_string(s, begin, end - 1);
begin = end;
}
return ret_s;
}
};
58-II 左旋转字符串
还是两次旋转，第一次旋转0-k，k-strlen，第二次旋转整个字符串。
class Solution {
public:
void reverse_string(string &s, int begin, int end){
while(begin < end){
char tmp = s[begin];
s[begin] = s[end];
s[end] = tmp;
begin++;
end--;
}
}
string reverseLeftWords(string s, int n) {
reverse_string(s, 0, n - 1);
reverse_string(s, n, s.size() - 1);
reverse_string(s, 0, s.size() - 1);
return s;
}
};
59-I 滑动窗口的最大值
用双向队列，存放所有可能成为滑动窗口最大值的元素的下标。如果当前队列中的每个元素小于新加进来的元素，那么这个元素就不可能成为后面的滑动窗口的最大值，应该出队列，此时是从队尾出队列。另一方面，如果当前队列中某个元素的下标已经在滑动窗口之外，那么这个元素也应该出队列，此时从队首出队列。每次，当前最大元素就在队头。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> binary_queue;
vector<int> maxes;
for(int i = 0; i < nums.size(); i++){
while(binary_queue.size() && binary_queue.front() + k <= i)
binary_queue.pop_front();
while(binary_queue.size() && nums[binary_queue.back()] < nums[i])
binary_queue.pop_back();
binary_queue.push_back(i);
if(i >= k - 1)
maxes.push_back(nums[binary_queue.front()]);
}
return maxes;
}
};
59-II 队列的最大值
实现一个最大队列，pop，push，max都是常数时间。跟滑动窗口类似，用一个双向队列存放当前最大值。每次push的时候，双向队列中存入可能成为最大值的值，也就是说，如果队列中的某些元素比push进来的元素小，那么他们不可能成为最大值了，就应该先出队列。pop时，需要判断一下当前队头的元素是否要pop的元素，如果是，就出队列。
一个需要注意的地方是如果队列中有相同的元素，这两个元素都会进入双向队列，这样pop的时候不会出错。
class MaxQueue {
public:
MaxQueue():q_size(0){}
int max_value() {
if(q_size == 0)
return -1;
return max_q.front();
}
void push_back(int value) {
q.push(value);
while(!max_q.empty() && max_q.back() < value)
max_q.pop_back();
max_q.push_back(value);
q_size++;
}
int pop_front() {
if(q_size == 0)
return -1;
int ret = q.front();
q.pop();
if(ret == max_q.front())
max_q.pop_front();
q_size--;
return ret;
}
private:
deque<int> max_q;
queue<int> q;
int q_size;
};
网友评论