算法苦手
二叉树剪枝
来源： https://leetcode.cn/problems/pOCWxh/
想法：
后序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* pruneTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
TreeNode* left = pruneTree(root->left);
TreeNode* right = pruneTree(root->right);
if (root->val == 0 && left == nullptr && right == nullptr) {
return nullptr;
}
root->left = left;
root->right = right;
return root;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
从根节点到叶节点的路径数字之和
来源： https://leetcode.cn/problems/3Etpl5/
想法：
遍历树即可
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int sum = 0;
void run(TreeNode* node, int val) {
if (node->left != nullptr) run(node->left,val * 10 + node->val);
if (node->right != nullptr) run(node->right,val * 10 + node->val);
if (node->left == nullptr && node->right == nullptr) sum += val * 10 + node->val;
}
int sumNumbers(TreeNode* root) {
run(root,0);
return sum;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
向下的路径节点之和
来源： https://leetcode.cn/problems/6eUYwP/
想法：
遍历树的同时维护节点路径
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int res = 0;
int target;
void preorder(TreeNode* node, vector<int>& road) {
road.push_back(node->val);
if (node->left != nullptr) preorder(node->left,road);
if (node->right != nullptr) preorder(node->right,road);
int tmp = 0;
for (int i = road.size() - 1 ; i >= 0 ; i--) {
tmp += road[i];
if (tmp == target) {
res++;
}
}
road.pop_back();
}
int pathSum(TreeNode* root, int targetSum) {
if (root == nullptr) return 0;
vector<int> v;
target = targetSum;
preorder(root,v);
return res;
}
};
时间复杂度： O(n²)
空间复杂度： **O(n) **
展平二叉搜索树
来源： https://leetcode.cn/problems/NYBBNL/
想法：
前序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode *res = nullptr;
TreeNode *head;
void midorder(TreeNode *node) {
if (node->left != nullptr) midorder(node->left);
if (res == nullptr) {
res = new TreeNode(node->val);
head = res;
}
else {
res->right = new TreeNode(node->val);
res = res->right;
}
if (node->right != nullptr) midorder(node->right);
}
TreeNode* increasingBST(TreeNode* root) {
midorder(root);
return head;
}
};
时间复杂度： O(n²)
空间复杂度： **O(n) **
二叉搜索树中的中序后继
来源： https://leetcode.cn/problems/P5rCT8/
想法：
中序遍历
/**
* 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* inorderSuccessor(TreeNode* root, TreeNode* p) {
stack<TreeNode*> s;
bool sign = false;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (sign) break;
if (root == p) sign = true;
root = root->right;
}
return root;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
所有大于等于节点的值之和
来源： https://leetcode.cn/problems/w6cpku/
想法：
中序遍历
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
TreeNode* convertBST(TreeNode* root) {
TreeNode *tmp1 = root, *tmp2 = root;
stack<TreeNode*> s;
int sum = 0;
int prev = 0;
while (tmp1 != nullptr || !s.empty()) {
while (tmp1 != nullptr) {
s.push(tmp1);
tmp1 = tmp1->left;
}
tmp1 = s.top();
s.pop();
sum += tmp1->val;
tmp1 = tmp1->right;
}
while (tmp2 != nullptr || !s.empty()) {
while (tmp2 != nullptr) {
s.push(tmp2);
tmp2 = tmp2->left;
}
tmp2 = s.top();
s.pop();
int tmp = tmp2->val;
tmp2->val = sum - prev;
prev += tmp;
tmp2 = tmp2->right;
}
return root;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
二叉搜索树中两个节点之和
来源： https://leetcode.cn/problems/opLdQZ/
想法：
中序遍历,用哈希表存储已经遍历到的节点的值，然后每遍历一个节点，只需要找哈希表里是否存在 k - val 即可
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool findTarget(TreeNode* root, int k) {
stack<TreeNode*> s;
set<int> base;
while (root != nullptr || !s.empty()) {
while (root != nullptr) {
s.push(root);
root = root->left;
}
root = s.top();
s.pop();
if (base.find(k - root->val) != base.end()) return true;
base.insert(root->val);
root = root->right;
}
return false;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
日程表
来源： https://leetcode.cn/problems/opLdQZ/
想法：
线段树，left存储日程在节点之前的，right存储日程在节点之后的
class MyCalendar {
public:
struct TreeNode{
TreeNode* left;
TreeNode* right;
int start;
int end;
TreeNode(int x, int y) : start(x), end(y), left(nullptr), right(nullptr) {}
};
TreeNode *root = nullptr;
MyCalendar() {
}
bool book(int start, int end) {
if (root == nullptr) {
root = new TreeNode(start,end);
return true;
}
TreeNode *tmp = root;
while (tmp != nullptr) {
if (end <= tmp->start) {
if (tmp->left == nullptr) {
tmp->left = new TreeNode(start,end);
return true;
}
tmp = tmp->left;
}else if (start >= tmp->end){
if (tmp->right == nullptr) {
tmp->right = new TreeNode(start,end);
return true;
}
tmp = tmp->right;
}else return false;
}
return true;
}
};
时间复杂度： O(logn)
空间复杂度： **O(n) **
实现前缀树
来源： https://leetcode.cn/problems/QC3q1f/
想法：
字典树
class Trie {
public:
vector<Trie*> children;
bool isEnd;
/** Initialize your data structure here. */
Trie() : children(26), isEnd(false){}
/** Inserts a word into the trie. */
void insert(string word) {
Trie* node = this;
for (char c : word) {
if (node->children[c - 'a'] == nullptr) {
node->children[c - 'a'] = new Trie();
}
node = node->children[c - 'a'];
}
node->isEnd = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
Trie* node = this;
for (char c : word) {
if (node->children[c - 'a'] == nullptr) {
return false;
}
node = node->children[c - 'a'];
}
return node != nullptr && node->isEnd;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
Trie* node = this;
for (char c : prefix) {
if (node->children[c - 'a'] == nullptr) {
return false;
}
node = node->children[c - 'a'];
}
return node != nullptr;
}
};
| 时间复杂度： **初始化为 O(1)，其余操作为 O( | S | )，其中 | S | 是每次插入或查询的字符串的长度。** |
| 空间复杂度： **O(∣T∣⋅Σ)，其中 | T | 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。** |
替换单词
来源： https://leetcode.cn/problems/QC3q1f/
想法：
哈希表
class Solution {
public:
string replaceWords(vector<string>& dictionary, string sentence) {
string res = "";
string temp = sentence + " ";
vector<string> strs;
size_t pos = temp.find(" ");
while (pos != temp.npos) {
string tmp = temp.substr(0, pos);
strs.push_back(tmp);
temp = temp.substr(pos + 1, temp.size());
pos = temp.find(" ");
}
set<string> roots;
for (string i : dictionary) {
roots.insert(i);
}
for (string i : strs) {
bool flag = false;
for (int j = 1 ; j < i.length() ; j++) {
string tmp = i.substr(0,j);
if (roots.find(tmp) != roots.end()) {
res.append(tmp).append(" ");
flag = true;
break;
}
}
if (!flag) res.append(i).append(" ");
}
res = res.substr(0,res.size() - 1);
return res;
}
};
时间复杂度： O(n)
空间复杂度： O(n)
神奇的字典
来源： https://leetcode.cn/problems/US1pGT/
想法：
前缀树，遍历字符串，对每个字符存在25种替换，如果遍历其后面的子串可以遍历到尾，就返回true，否则返回false。
class MagicDictionary {
public:
vector<MagicDictionary*> children;
bool isEnd;
/** Initialize your data structure here. */
MagicDictionary() : children(26), isEnd(false){}
void buildDict(vector<string> dictionary) {
for (string str : dictionary) {
MagicDictionary* node = this;
for (char c : str) {
if (node->children[c - 'a'] == nullptr) {
node->children[c - 'a'] = new MagicDictionary();
}
node = node->children[c - 'a'];
}
node->isEnd = true;
}
}
bool search(string searchWord) {
MagicDictionary* node = this;
int n = searchWord.length();
for (int i = 0 ; i < n ; i++) {
int num = searchWord[i] - 'a';
for (int x = 0 ; x < 26 ; x++) {
if (x == num || node->children[x] == nullptr) continue;
string tmp_str = searchWord.substr(i + 1);
auto tmp_node = node->children[x];
bool flag = true;
for (int j = 0 ; j < tmp_str.length() ; j++) {
if (tmp_node->children[tmp_str[j] - 'a'] == nullptr) {
flag = false;
break;
}
tmp_node = tmp_node->children[tmp_str[j] - 'a'];
}
if (flag) flag = tmp_node->isEnd;
if (flag) return true;
}
if (node->children[num] == nullptr) return false;
node = node->children[num];
}
return false;
}
};
| 时间复杂度： **O( | S | ⋅ Σ)，其中 | S | 是每次插入或查询的字符串的长度, Σ 为字符集的大小，本题 Σ=26。** |
| 空间复杂度： **O( | T | ⋅Σ)，其中 | T | 为所有插入字符串的长度之和，Σ 为字符集的大小，本题 Σ=26。** |
单词之和
来源： https://leetcode.cn/problems/z1R5dt/
想法：
前缀树加深度遍历
class MapSum {
public:
vector<MapSum*> child;
bool isEnd;
map<string,int> table;
int res = 0;
/** Initialize your data structure here. */
MapSum() : child(26), isEnd(false){}
void insert(string key, int val) {
table[key] = val;
MapSum *node = this;
for (char c : key) {
if (node->child[c - 'a'] == nullptr) {
node->child[c - 'a'] = new MapSum();
}
node = node->child[c - 'a'];
}
node->isEnd = true;
}
void dst(MapSum* node, string str) {
for (int i = 0 ; i < 26 ; i++) {
if (node->child[i] != nullptr) {
char c = 'a' + i;
dst(node->child[i],str + c);
}
}
if (node->isEnd) res += table[str];
}
int sum(string prefix) {
MapSum* tmp = this;
bool flag = true;
for (char c : prefix) {
if (tmp->child[c - 'a'] == nullptr) {
flag = false;
break;
}
tmp = tmp->child[c - 'a'];
}
if (!flag) return 0;
else dst(tmp,prefix);
int v = res;
res = 0;
return v;
}
};
最大的异或
来源： https://leetcode.cn/problems/ms70jA/
想法：
将每个数字都化为32位的二进制数，然后生成一个前缀树，再对每个数进行遍历前缀树，对于每个节点，如果当前数的位为0，就走右子树，如果为0就走左子树（因为如果能保证当前位异或的结果为1一定是最大的）。
class Solution {
struct tree{
tree* left;
tree* right;
};
public:
int findMaximumXOR(vector<int>& nums) {
int res = -1;
auto root = new tree();
for (int num : nums) {
tree* node = root;
for (int i = 30 ; i >= 0 ; i--) {
int bit = (num >> i ) & 1;
if (bit == 0) {
if (node->left == nullptr) node->left = new tree();
node = node->left;
}
else{
if (node->right == nullptr) node->right = new tree();
node = node->right;
}
}
}
for (int num : nums) {
tree* node = root;
int tmp_res = 0;
bool flag = false;
for (int i = 30 ; i >= 0 ; i--) {
int bit = (num >> i ) & 1;
if (flag) tmp_res *= 2;
if (bit == 0) {
if (node->right != nullptr) {
tmp_res++;
node = node->right;
}else node = node->left;
}else {
flag = true;
if (node->left != nullptr) {
tmp_res++;
node = node->left;
}else node = node->right;
}
}
res = max(res,tmp_res);
}
return res;
}
};
时间复杂度：O(nlogC)，其中 n是数组 nums 的长度，C 是数组中的元素范围，在本题中 C < 2^{31}。
空间复杂度：O(nlogC)，其中 n是数组 nums 的长度，C 是数组中的元素范围，在本题中 C < 2^{31}。
查找插入位置
来源： https://leetcode.cn/problems/N6YdxV/
想法：
二分查找
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int n = nums.size();
int left = 0, right = n - 1, ans = n;
while (left <= right) {
int mid = ((right - left) >> 1) + left;
if (target <= nums[mid]) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return ans;
}
};
时间复杂度：O(logn)
空间复杂度：O(1)
山峰数组的顶部
来源： https://leetcode.cn/problems/N6YdxV/
想法：
二分查找
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int n = arr.size();
int left = 1, right = n - 2, ans = 0;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > arr[mid + 1]) {
ans = mid;
right = mid - 1;
}
else {
left = mid + 1;
}
}
return ans;
}
};
时间复杂度：O(logn)
空间复杂度：O(1)
排序数组中只出现一次的数字
来源： https://leetcode.cn/problems/skFtm2/
想法：
二分查找，在查找时，判断当前数字是否和前一个或者后一个相等，如果都不相等，则返回；如果相等，则判断这两个数字中索引较小的那一个的索引是奇数还是偶数，如果是奇数说明要找的结果在左边，否则在右边。
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int n = nums.size();
if (n == 1) return nums[0];
int left = 0, right = n - 1;
while (left != right - 1) {
int mid = ((right - left) / 2) + left;
if (nums[mid] == nums[mid - 1]) {
if ((mid - 1) % 2 == 0) left = mid;
else right = mid;
}else if (nums[mid] == nums[mid + 1]){
if (mid % 2 == 0) left = mid;
else right = mid;
}else {
return nums[mid];
}
}
if (left == 0) return nums[left];
if (right == n - 1) return nums[right];
return 0;
}
};
时间复杂度：O(logn)
空间复杂度：O(1)
狒狒吃香蕉
来源： https://leetcode.cn/problems/skFtm2/
想法：
二分答案
class Solution {
public:
int minEatingSpeed(vector<int>& piles, int h) {
int n = piles.size();
int max_i = -1;
for (int i : piles) max_i = max(max_i,i);
int l = 1, r = max_i;
while (l != r - 1) {
int mid = (l + r) / 2;
int tmp = 0;
for (int i : piles) {
int d = i / mid;
if (d * mid == i) tmp += d;
else tmp += (d + 1);
}
if (tmp > h) l = mid;
if (tmp <= h) r = mid;
}
int tmp = 0;
for (int i : piles) {
int d = i / l;
if (d * l == i) tmp += d;
else tmp += (d + 1);
}
if (tmp <= h) return l;
else return r;
}
};
时间复杂度：O(logn)
空间复杂度：O(1)
合并区间
来源： https://leetcode.cn/problems/SsGoHC/
想法：
按照左边界建了一个BST，然后中序遍历，分类讨论即可。
class Solution {
struct tree{
tree* left;
tree* right;
int l;
int r;
tree(int x, int y) : l(x), r(y), left(nullptr),right(nullptr) {}
};
public:
vector<vector<int>> res;
void midorder(tree* node) {
if (node->left != nullptr) midorder(node->left);
if (res.empty()) {
res.push_back({node->l,node->r});
}else {
vector<int> &tmp = res.back();
if (node->l <= tmp[1] && node->r >= tmp[1]) tmp[1] = node->r;
else if (node->l > tmp[1]) {
res.push_back({node->l,node->r});
}
}
if (node->right != nullptr) midorder(node->right);
}
vector<vector<int>> merge(vector<vector<int>>& intervals) {
tree *root = new tree(intervals[0][0],intervals[0][1]);
for (int i = 1 ; i < intervals.size() ; i++) {
tree *tmp = root;
int l = intervals[i][0];
int r = intervals[i][1];
while (tmp != nullptr) {
if (l <= tmp->l) {
if (tmp->left == nullptr) {
tmp->left = new tree(l,r);
break;
}
tmp = tmp->left;
}else if (l > tmp->l) {
if (tmp->right == nullptr) {
tmp->right = new tree(l,r);
break;
}
tmp = tmp->right;
}
}
}
midorder(root);
return res;
}
};
时间复杂度：O(nlogn)
空间复杂度：O(n)
数组中的第k大的数字
来源： https://leetcode.cn/problems/xx4gT2/
想法：
快排
class Solution {
public:
int res;
int k;
int getPivot(vector<int> &nums, int left, int right) {
int random = rand() % (right - left + 1) + left;
swap(nums[random], nums[right]);
int index = left;
for (int i = left; i < right; i++) {
if (nums[i] > nums[right]) {
swap(nums[i], nums[index++]);
}
}
swap(nums[index], nums[right]);
return index;
}
void qsort(vector<int> &nums, int left, int right) {
int pivot = getPivot(nums,left,right);
if (pivot == k - 1) {
res = nums[pivot];
return;
}else if (pivot < k) qsort(nums,pivot + 1, right);
else qsort(nums,left, pivot - 1);
}
int findKthLargest(vector<int>& nums, int k) {
this->k = k;
qsort(nums,0,nums.size() - 1);
return res;
}
};
时间复杂度：O(n)
空间复杂度：O(logn)
生成匹配的括号
来源： https://leetcode.cn/problems/IDBivT/
想法：
回溯
class Solution {
public:
void run(int left,int right, int unpaired, vector<string> &ans, string & now, int n) {
if (left == n && right == n && unpaired == 0) {
ans.emplace_back(now);
return;
}
if (left < n) {
now += "(";
run(left + 1,right,unpaired + 1,ans,now,n);
now.pop_back();
}
if (unpaired != 0) {
now += ")";
run(left, right + 1, unpaired - 1, ans, now, n);
now.pop_back();
}
}
vector<string> generateParenthesis(int n) {
vector<string> ans;
string now = "(";
run(1,0,1,ans,now,n);
return ans;
}
};
时间复杂度：？（算不来）
空间复杂度：？（算不来）
分割回文子字符串
来源： https://leetcode.cn/problems/M99OJA/
想法：
回溯
class Solution {
public:
bool judge(string s) {
int l = 0, r = s.length() - 1;
while (l <= r) {
if (s[l] != s[r]) return false;
l++,r--;
}
return true;
}
void run(vector<vector<string>>& ans, vector<string> &now, int idx, string s) {
if (idx == s.length()) {
bool flag = true;
for (string &i : now) {
if (!judge(i)) {
flag = false;
break;
}
}
if (flag) ans.emplace_back(now);
return;
}
int now_index = now.size() - 1;
string now_str = now[now_index];
now_str += s[idx];
now[now_index] = now_str;
run(ans,now,idx + 1,s);
now_str.pop_back();
now[now_index] = now_str;
string tmp;
tmp = s.substr(idx,1);
now.emplace_back(tmp);
run(ans,now,idx + 1,s);
now.pop_back();
}
vector<vector<string>> partition(string s) {
vector<vector<string>> ans;
vector<string> now;
string first = s.substr(0,1);
now.emplace_back(first);
if (s.length() == 1) {
ans.emplace_back(now);
return ans;
}
run(ans,now,1,s);
return ans;
}
};
时间复杂度：？（算不来）
空间复杂度：？（算不来）
PREVIOUS算法练习