53-I 在排序數(shù)組中查找數(shù)字 I
利用二分查找法，可以定位到第一個或者最后一個查找元素隐砸。
查找第一個時之碗，如果中間元素小于或大于查找元素，都可以將區(qū)間縮小一半季希；而中間元素等于查找元素時褪那，需要判斷中間元素是不是第一個出現(xiàn)的元素，判斷方式為查看前一個元素式塌，如果前一個元素等于查找元素博敬，第一個元素則出現(xiàn)在前一半?yún)^(qū)間中；如果前一個元素不等于查找元素峰尝，第一個元素就是當(dāng)前元素偏窝，可以返回。
查找最后一個出現(xiàn)的元素位置也是類似的做法境析。
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中缺失的數(shù)字
二分查找法囚枪，如果中間數(shù)字等于下標(biāo)數(shù)，缺失的數(shù)字就在右半邊劳淆；否則，查看左邊的數(shù)字是不是等于下標(biāo)默赂，等于的話沛鸵，中間下標(biāo)就是缺失的數(shù)字，否則在左半邊缆八。
實現(xiàn)用了遞歸和迭代兩種實現(xiàn)方法：
迭代
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大節(jié)點
二叉搜索樹的中序遍歷是有序的曲掰。因此對二叉搜索樹進(jìn)行逆中序遍歷，返回值為TreeNode指針奈辰，未找到第k個節(jié)點之前栏妖，返回空指針，找到后返回該節(jié)點指針奖恰。每次右孩子遍歷完吊趾，將k減一，k減到1時瑟啃，找到了第k大的節(jié)點论泛。
這個題目的代碼邏輯比較難寫，需要重點學(xué)習(xí)下蛹屿。
/**
* 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 平衡二叉樹
該問題可以用二叉樹的后序遍歷解決屁奏，首先判斷左右子樹分別是否平衡，如果左右子樹平衡错负，再根據(jù)左右子樹的高度坟瓢，判斷該樹是否平衡勇边，并且返回樹高度。這樣只需要遍歷一次即可折联。
另一個技巧粒褒，如果有多個需要返回的值，可以將其中某些值的引用作為參數(shù)傳回來崭庸。
/**
* 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 數(shù)組中只出現(xiàn)一次的兩個數(shù)字
這個題目有點難怀浆，如果只有一個數(shù)字只出現(xiàn)一次，那么我們可以利用同一個數(shù)異或兩次是0怕享，將所有數(shù)字進(jìn)行異或操作执赡，最后的結(jié)果就是只出現(xiàn)一次的數(shù)字。
如果有兩個數(shù)字只出現(xiàn)一次函筋，那么將所有數(shù)字異或一次沙合，得到的結(jié)果是這兩個數(shù)字的異或結(jié)果，這個數(shù)字一定不為0跌帐。找到這個數(shù)字中出現(xiàn)1的某一位首懈，則這兩個只出現(xiàn)一次的數(shù)中，一個是這一位等于1谨敛，一個是不等于1.通過這一位是否為1究履，可以將這兩個數(shù)字分到兩個數(shù)組中，之后脸狸，分別在這兩個數(shù)組中進(jìn)行異或最仑，就可以得到這兩個數(shù)字。
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 數(shù)組中唯一只出現(xiàn)一次的數(shù)字
其他數(shù)字都出現(xiàn)3次炊甲，因此泥彤，這個題目就不能用異或來做了，但還是可以用位運(yùn)算的思路卿啡。每個數(shù)字的每一位相加三次吟吝，這一位的和一定可以整除3.那么將所有數(shù)字的每一位求和，如果某一位的和可以整除3颈娜，那么這個只出現(xiàn)一次的數(shù)字在這一位上一定為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的連續(xù)正數(shù)序列
還是用雙指針揭鳞，left和right炕贵，當(dāng)前和小于target時，right++野崇，大雨target時称开，left++，等于時，記錄下當(dāng)前的序列鳖轰。
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 翻轉(zhuǎn)單詞順序
先翻轉(zhuǎn)整句話清酥，再翻轉(zhuǎn)每個單詞。比較麻煩的就是空格的處理蕴侣，所以開辟了額外空間焰轻，如果空格沒問題，就可以原地翻轉(zhuǎn)了昆雀。
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 左旋轉(zhuǎn)字符串
還是兩次旋轉(zhuǎn)辱志，第一次旋轉(zhuǎn)0-k，k-strlen狞膘，第二次旋轉(zhuǎn)整個字符串揩懒。
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 滑動窗口的最大值
用雙向隊列，存放所有可能成為滑動窗口最大值的元素的下標(biāo)挽封。如果當(dāng)前隊列中的每個元素小于新加進(jìn)來的元素已球，那么這個元素就不可能成為后面的滑動窗口的最大值，應(yīng)該出隊列辅愿，此時是從隊尾出隊列智亮。另一方面，如果當(dāng)前隊列中某個元素的下標(biāo)已經(jīng)在滑動窗口之外点待，那么這個元素也應(yīng)該出隊列阔蛉，此時從隊首出隊列。每次癞埠，當(dāng)前最大元素就在隊頭馍忽。
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 隊列的最大值
實現(xiàn)一個最大隊列，pop燕差，push，max都是常數(shù)時間坝冕。跟滑動窗口類似徒探，用一個雙向隊列存放當(dāng)前最大值。每次push的時候喂窟，雙向隊列中存入可能成為最大值的值测暗，也就是說，如果隊列中的某些元素比push進(jìn)來的元素小磨澡，那么他們不可能成為最大值了碗啄，就應(yīng)該先出隊列。pop時稳摄，需要判斷一下當(dāng)前隊頭的元素是否要pop的元素稚字，如果是，就出隊列。
一個需要注意的地方是如果隊列中有相同的元素胆描，這兩個元素都會進(jìn)入雙向隊列瘫想，這樣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;
};
