63 数组中的逆序对
经典归并排序，divide+merge。在merge时，如果左半边某个元素（i）大于右半边的某个元素，那么左半边后面的元素都大于右半边该元素，逆序对增加mid-i。
class Solution {
public:
int Divide_Merge(vector<int>& nums, int left, int right){
if(left + 1 >= right)
return 0;
// divide
int mid = left + (right - left) / 2;
int left_pair = Divide_Merge(nums, left, mid);
int right_pair = Divide_Merge(nums, mid, right);
// merge
vector<int> tmp;
int i = left, j = mid, cur_pair = left_pair + right_pair;
while(i < mid && j < right){
if(nums[i] <= nums[j]){
tmp.push_back(nums[i]);
i++;
}
else{
tmp.push_back(nums[j]);
cur_pair += (mid - i);
j++;
}
}
while(i < mid)
tmp.push_back(nums[i++]);
while(j < right)
tmp.push_back(nums[j++]);
for(int k = 0; k < tmp.size(); k++)
nums[left + k] = tmp[k];
return cur_pair;
}
int reversePairs(vector<int>& nums) {
int pairs = Divide_Merge(nums, 0, nums.size());
return pairs;
}
};
64 求1+2+...+n
不能用if语句，但是可以用？来判断ns是否为0
class Solution {
public:
int sumNums(int n) {
return n ? n + sumNums(n - 1) : 0;
}
};
68 二叉搜索树的最近公共节点
因为是二叉搜索树，所以可以通过pq以及root的取值判断，如果pq都小于root，那么最近公共节点在root左子树中；都大于，在右子树中；一个小于一个大于，root就是最近公共节点。如果是面试的时候，需要多考虑一些边界条件，力扣测试数据都没有考虑边界条件。。。
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 这里第一需要判断pq以及root是否空
if((p -> val < root -> val) && (q -> val < root -> val))
return lowestCommonAncestor(root -> left, p, q);
if((p -> val > root -> val) && (q -> val > root -> val))
return lowestCommonAncestor(root -> right, p, q);
return root;
}
};
68-II 二叉树的最近公共祖先
上一题的升级版，二叉搜索树改成了普通二叉树。这种做法其实跟前面一样，如果左右返回都不为空，说明p和q分别在左右子树中，最近公共祖先就是root；如果其中一个返回为空，另一个不为空，那么pq就在不为空的子树中。对于其中一个是另一个祖先的情况，也可以包含进来，因为只要访问到其中一个节点就不会再深入了。
/**
* 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* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == nullptr || root == p || root == q)
return root;
TreeNode* left = lowestCommonAncestor(root -> left, p, q);
TreeNode* right = lowestCommonAncestor(root -> right, p, q);
if(left && right)
return root;
if(left == nullptr)
return right;
return left;
}
};
05 替换空格
原地替换。这个题目如果只是额外分配空间来做，那就没啥意思了。首先需要统计出空格的数目，将字符串后面扩充2*空格数。然后设置ij两个指针，分别指向原字符串末尾和扩充后的字符串末尾，双指针扫描替换，直到两个指针重合，此时前面就没有空格了，也不需要再替换了。
class Solution {
public:
string replaceSpace(string s) {
int space_cnt = 0, ori_len = s.size();
for(int i = 0; i < s.size(); i++){
if(s[i] == ' ')
space_cnt++;
}
for(int i = 0; i < space_cnt; i++)
s += " ";
int i = ori_len - 1, j = s.size() - 1;
while(i < j){
if(s[i] != ' ')
s[j--] = s[i--];
else{
s[j--] = '0';
s[j--] = '2';
s[j--] = '%';
i--;
}
}
return s;
}
};
3 数组中重复的数字
第一种时间O(n)且空间O(1)的解法是原地排序，将每个元素放到自己指定的地方，如果同一个位置出现第二个元素，那么该元素就是重复的。
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
for(int i = 0; i < nums.size(); i++){
int j = nums[i];
while(i != j){
int tmp = nums[j];
if(nums[j] == j)
return nums[j];
nums[j] = j;
j = tmp;
}
nums[i] = j;
}
return -1;
}
};
二分解法，1～n-1分成两个区间1～m，m～n-1分别统计两个区间的元素个数，如果左边区间元素多于m，重复元素就在左边区间中；否则在右边区间中，不断缩小区间。但是本题元素范围是0～n-1，所以这种解法不能用，对于[0,0,1,2,4,5,6,7,8,9]是找不到正确解的
class Solution {
public:
int findRepeatNumber(vector<int>& nums) {
int left = 1, right = nums.size(), left_cnt = 0, right_cnt = 0;
while(left + 1 < right){
int mid = left + (right - left) / 2;
left_cnt = 0;
right_cnt = 0;
for(int i = 0; i < nums.size(); i++){
if((nums[i] >= left) && (nums[i] < mid))
left_cnt++;
else if((nums[i] >= mid) && (nums[i] < right))
right_cnt++;
}
if(left_cnt > (mid - left))
right = mid;
else
left = mid;
}
return left;
}
};
网友评论