算法苦手
整数除法
来源： https://leetcode.cn/problems/xoh6Oh/
想法：
每次通过位运算获得当前比a最小的b的最大倍数，然后记录该倍数，再让a与b相减，重复该过程即可。
class Solution {
public:
int divide(int a, int b) {
int sign = a > 0 ^ b > 0 ? -1 : 1;
int res = 0;
if (a == -1 * pow(2,31) && b == -1) return pow(2,31) - 1;
else {
a = a > 0 ? -a : a;
b = b > 0 ? -b : b;
while (a <= b) {
bool flag = false;
if (a == b) {
res++;
break;
}
int temp1 = a, temp2 = b, temp3 = 0;
while (temp1 < temp2 && temp2 >= -1 * pow(2,30)) {
flag = true;
temp2 *= 2;
temp3 = temp3 == 0 ? 1 : temp3 << 1;
}
if (flag) {
if (temp2 != temp1) temp2 /= 2;
else temp3 <<= 1;
} else {
temp3 = 1;
}
res += temp3;
a -= temp2;
}
}
if (res == -1 * pow(2,31)) return res;
return abs(res) * sign;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
优化：
写法有待优化
前 n 个数字二进制中 1 的个数
来源： https://leetcode.cn/problems/w3tCBm/
想法：
以当前索引为2的幂次为一次轮换，每次轮换都从vector的头开始计算，结果加1
class Solution {
public:
vector<int> countBits(int n) {
vector<int> res;
res.push_back(0);
if (n == 0) return res;
res.push_back(1);
if (n == 1) return res;
int j;
for (int i = 2 ; i <= n; i++) {
if ((i & (i - 1)) == 0) {
j = 0;
}
res.push_back(res[j++] + 1);
}
return res;
}
};
时间复杂度： O(n)
空间复杂度： O(n)
二进制加法
来源： https://leetcode.cn/problems/xoh6Oh/
想法：
实现二进制加法
class Solution {
public:
string addBinary(string a, string b) {
string res;
int l1 = a.length(), l2 = b.length();
int sign = 0;
for (int i = l1 - 1 ,j = l2 - 1; i >= 0 || j >= 0; i--,j--) {
int tmp;
if (i >= 0 && j >= 0) tmp = a[i] - '0' + b[j] - '0' + sign;
else if (i >= 0) tmp = a[i] - '0' + sign;
else tmp = b[j] - '0' + sign;
if (tmp == 0) {
res += "0";
sign = 0;
}
else if (tmp == 1) {
res += "1";
sign = 0;
}
else if (tmp == 2) {
res += "0";
sign = 1;
}
else {
res += "1";
sign = 1;
}
}
if (sign == 1) res += "1";
std::reverse(res.begin(), res.end());
return res;
}
};
只出现一次的数字
来源： https://leetcode.cn/problems/WGki4K/
想法：
本人的想法就是使用hashset，看完了题解中他人的想法后，改进为O(1)的空间复杂度。
想法即为：出现三次的元素每一位相加得到的结果都为3的倍数，只要将数组中每一个元素每一位分别相加的到的结果模3，即得到了仅出现一次的那个元素的那一位。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int i = 0; i < 32; ++i) {
int total = 0;
for (int num: nums) {
total += ((num >> i) & 1);
}
if (total % 3) {
ans |= (1 << i);
}
}
return ans;
}
};
时间复杂度： O(nlgC) C为数字位数长度
空间复杂度： O(1)
单词长度的最大乘积
来源： https://leetcode.cn/problems/aseY1I/
想法：
将字符串映射为一个26位的数，这样判断字符串是否有相同字符时，就只需要判断与的结果是否为0即可
class Solution {
public:
int maxProduct(vector<string>& words) {
vector<int> masks(words.size());
int res = 0;
for (int i = 0 ; i < words.size(); i++) {
for (char c : words[i]) {
masks[i] |= 1 << (c - 'a');
}
}
for (int i = 0 ; i < words.size(); i++) {
for (int j = i + 1 ; j < words.size(); j++) {
if ((masks[i] & masks[j]) == 0) {
res = max(res,(int)(words[i].length() * words[j].length()));
}
}
}
return res;
}
};
时间复杂度： O(L + n²) C为数字位数长度 L为数组中所有单词长度之和
空间复杂度： O(n)
排序数组中两个数字之和
来源： https://leetcode.cn/problems/kLl5u1/
想法：
固定一个数，在另一边找另一个数是否满足要求。
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> res(2);
bool flag = false;
for (int i = 0 ; i < numbers.size() % 2 == 0 ? numbers.size() / 2 : numbers.size() / 2 + 1; i++) {
for (int j = numbers.size() - 1 ; j >= 0 ; j--) {
if (target == numbers[i] + numbers[j]) {
flag = true;
res[0] = i;
res[1] = j;
break;
}
if (target > numbers[i] + numbers[j]) break;
}
if (flag) break;
}
return res;
}
};
时间复杂度： O(n²)
空间复杂度： O(1)
数组中和为0的三个数
来源： https://leetcode.cn/problems/1fGaJU/
想法：
先通过排序，确保找到的三个数不会因为遍历而造成重复。
然后固定第一个数，使用双指针从第一个数右边开始遍历，如果三个数之和结果大于0，就将右指针左移，如果三个数之和小于0，就将左指针右移，同时在找到满足的结果时，要保证下一次遍历的开始的数与上一次的结果不同。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int first = 0; first < n; ++first) {
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
int third = n - 1;
int target = -nums[first];
for (int second = first + 1; second < n; ++second) {
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
while (second < third && nums[second] + nums[third] > target) {
--third;
}
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
ans.push_back({nums[first], nums[second], nums[third]});
}
}
}
return ans;
}
};
时间复杂度： O(n²)
空间复杂度： O(n)
和大于等于target的最短子数组
来源： https://leetcode.cn/problems/2VG8Kg/
想法：
滑动窗口实现
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
if (n == 0) {
return 0;
}
int ans = INT_MAX;
int start = 0, end = 0;
int sum = 0;
while (end < n) {
sum += nums[end];
while (sum >= target) {
ans = min(ans, end - start + 1);
sum -= nums[start];
start++;
}
end++;
}
return ans == INT_MAX ? 0 : ans;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
乘积小于k的子数组
来源： https://leetcode.cn/problems/ZVAVXX/
想法：
滑动窗口实现
class Solution {
public:
int numSubarrayProductLessThanK(vector<int>& nums, int k) {
int len = nums.size();
int ans = 0 ;
int sum = 1 ;
int l=0, r=0;
while(r<len){
sum = sum * nums[r];
while(sum>=k&&l<=r){
sum/=nums[l++];
}
ans = ans + r-l+1;
r++;
}
return ans;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
字符串中的变位词
来源： https://leetcode.cn/problems/MPnaiL/
想法：
滑动窗口实现，通过diff变量记录窗口中s2的子串与s1的字符数量差距，通过cnt数组记录差值，移动窗口时，如果插值从0变为正负1时，diff++，如果插值变为0时，diff–。
class Solution {
public:
bool checkInclusion(string s1, string s2) {
bool ans = false;
if (s1.length() > s2.length() ) return false;
int cnt[26] = {0};
for (char c : s1){
cnt[c - 'a']++;
}
for (int i = 0 ; i < s1.length(); i++) {
cnt[s2[i] - 'a']--;
}
int diff = 0;
for (int i : cnt) {
if (i != 0) diff++;
}
for (int l = 0, r = s1.length(); r < s2.length();l++,r++) {
if (diff == 0) {
ans = true;
break;
}else {
int sign1 = cnt[s2[l] - 'a'];
cnt[s2[l] - 'a']++;
if (cnt[s2[l] - 'a'] == 0) diff--;
else if (sign1 == 0)diff++;
int sign2 = cnt[s2[r] - 'a'];
cnt[s2[r] - 'a']--;
if (cnt[s2[r] - 'a'] == 0) diff--;
else if (sign2 == 0)diff++;
}
}
if (diff == 0) return true;
return ans;
}
};
时间复杂度： O(n + m + C) ,C为字符集大小
空间复杂度： O(C)， C为字符集大小
字符串中的所有变位词
来源： https://leetcode.cn/problems/VabMRr/
想法：
与上题一致。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ans;
if (s.length() < p.length()) return ans;
int cnt[26] = {0};
for (char c : p){
cnt[c - 'a']++;
}
for (int i = 0 ; i < p.length(); i++) {
cnt[s[i] - 'a']--;
}
int diff = 0;
for (int i : cnt) {
if (i != 0) diff++;
}
for (int l = 0, r = p.length(); r < s.length();l++,r++) {
if (diff == 0) {
ans.push_back(l);
}
int sign1 = cnt[s[l] - 'a'];
cnt[s[l] - 'a']++;
if (cnt[s[l] - 'a'] == 0) diff--;
else if (sign1 == 0)diff++;
int sign2 = cnt[s[r] - 'a'];
cnt[s[r] - 'a']--;
if (cnt[s[r] - 'a'] == 0) diff--;
else if (sign2 == 0)diff++;
}
if (diff == 0) ans.push_back(s.length() - p.length());
return ans;
}
};
时间复杂度： O(n + m + C) ,C为字符集大小
空间复杂度： O(C)， C为字符集大小
不含重复字符的最长子字符串
来源： https://leetcode.cn/problems/wtcaE1/
想法：
使用滑动窗口，滑动时先判断：
右窗口是否与其左边字符相同，如果相同则一直向右移动直到不相同，然后左窗口移动到右窗口的左边
如果不与其左边字符相同，则根据记录的字符数量数组判断：
如果当前右窗口的字符数大于1，则将左窗口一直移动到与右窗口字符相同的位置的右边一位
如果不大于1，则计算窗口大小，与ans取max
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length();
if (n == 0) return 0;
int ans = 1;
int cnt[128] = {0};
int l = 0,r = 1;
cnt[s[0]]++;
while (r < n) {
cnt[s[r]]++;
if (s[r] == s[r - 1]) {
while(r < n && s[r] == s[r - 1]) {
r++;
cnt[s[r]]++;
}
cnt[s[r]]--;
while (l < r - 1) {
cnt[s[l]]--;
l++;
}
}else {
if (cnt[s[r]] > 1) {
while (s[l] != s[r]) {
cnt[s[l]]--;
l++;
}
cnt[s[l]]--;
l++;
}else ans = max(ans,r - l + 1);
r++;
}
}
return ans;
}
};
时间复杂度： O(n)
空间复杂度： O(C)， C为字符集大小
有效的回文
来源： https://leetcode.cn/problems/XltzEq/
想法：
双指针实现。
class Solution {
public:
bool isPalindrome(string s) {
int n = (int)s.length();
if (n == 0) return true;
bool ans = true;
int l = 0, r = n - 1;
while (l < r) {
while (l < n && !isalnum(s[l])) l++;
while (r > 0 && !isalnum(s[r])) r--;
if (l == n && r == 0) break;
if (tolower(s[l]) != tolower(s[r])) {
ans = false;
break;
}
l++,r--;
}
return ans;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
最多删除一个字符得到回文
来源： https://leetcode.cn/problems/RQku0D/
想法：
贪心+双指针，如果左右指针的字符不同时，判断删除最左边字符或者删除最右边字符，如果有一种满足回文，则成立。
class Solution {
public:
bool validPalindrome(string s) {
int n = s.length();
int l = 0, r = n - 1;
bool sign = false;
while (l < r) {
if (s[l] != s[r]) {
sign = true;
break;
}
l++,r--;
}
if (!sign) return true;
if (l == r - 1) return true;
else {
int l1 = l, r1 = r - 1, l2 = l + 1, r2 = r;
bool flag1 = true, flag2 = true;
while (l1 < r1) {
if (s[l1] != s[r1]) {
flag1 = false;
break;
}
l1++,r1--;
}
while (l2 < r2) {
if (s[l2] != s[r2]) {
flag2 = false;
break;
}
l2++,r2--;
}
return flag1 || flag2;
}
}
};
时间复杂度： O(n)
空间复杂度： O(1)
回文子字符串的个数
来源： https://leetcode.cn/problems/a7VOhD/
想法：
枚举回文子串的中心，然后使用双指针向两边拓展。
class Solution {
public:
int countSubstrings(string s) {
int n = s.size(), ans = 0;
for (int i = 0; i < 2 * n - 1; ++i) {
int l = i / 2, r = i / 2 + i % 2;
while (l >= 0 && r < n && s[l] == s[r]) {
--l;
++r;
++ans;
}
}
return ans;
}
};
时间复杂度： O(n²)
空间复杂度： O(1)
删除链表的倒数第n个结点
来源： https://leetcode.cn/problems/SLwz0R/
想法：
双指针，保持间距为n即可
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* res = head;
ListNode* first = head;
ListNode* second = head;
for (int i = 0 ; i < n ; i++) {
first = first->next;
}
if (first == nullptr) return head->next;
while (first->next != nullptr) {
first = first->next;
second = second->next;
}
second->next = second->next->next;
return res;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
链表中环的入口节点
来源： https://leetcode.cn/problems/c32eOV/
想法：
双指针，一个指针以1为步长移动，一个指针以2为步长移动，如果两个指针能够相遇，那么就存在环
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head, *fast = head;
while (fast != nullptr) {
slow = slow->next;
if (fast->next == nullptr) {
return nullptr;
}
fast = fast->next->next;
if (fast == slow) {
ListNode *ptr = head;
while (ptr != slow) {
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
return nullptr;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
两个链表的第一个重合节点
来源： https://leetcode.cn/problems/3u1WK4/
想法：
双指针，一个指针从链表一开始，遍历完后从链表二开始，另一个相反，输出它们相遇时的节点即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode *pA = headA, *pB = headB;
while (pA != pB) {
pA = pA == nullptr ? headB : pA->next;
pB = pB == nullptr ? headA : pB->next;
}
return pA;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
反转链表
来源： https://leetcode.cn/problems/UHnkqh/
想法：
反转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
if (head->next->next == nullptr) {
ListNode *res = head->next;
head->next->next = head;
head->next = nullptr;
return res;
}
ListNode *p1 = head, *p2 = head->next, *p3 = head->next->next;
head->next = nullptr;
while (p3 != nullptr) {
p2->next = p1;
p1 = p2;
p2 = p3;
p3 = p3->next;
}
p2->next = p1;
return p2;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
链表中的两数相加
来源： https://leetcode.cn/problems/lMSNwu/
想法：
使用栈实现逆序
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1, s2;
while (l1) {
s1.push(l1 -> val);
l1 = l1 -> next;
}
while (l2) {
s2.push(l2 -> val);
l2 = l2 -> next;
}
int carry = 0;
ListNode* ans = nullptr;
while (!s1.empty() or !s2.empty() or carry != 0) {
int a = s1.empty() ? 0 : s1.top();
int b = s2.empty() ? 0 : s2.top();
if (!s1.empty()) s1.pop();
if (!s2.empty()) s2.pop();
int cur = a + b + carry;
carry = cur / 10;
cur %= 10;
auto curnode = new ListNode(cur);
curnode -> next = ans;
ans = curnode;
}
return ans;
}
};
时间复杂度： O(n)
空间复杂度： O(1)
回文链表
来源： https://leetcode.cn/problems/aMhZSa/
想法：
使用数组存放链表。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> list;
while (head != nullptr) {
list.push_back(head->val);
head = head->next;
}
for (int i = 0, j = list.size() - 1; i <= j ; i++,j--) {
if (list[i] != list[j]) return false;
}
return true;
}
};
时间复杂度： O(n)
空间复杂度： O(n)
展平多级双向链表
来源： https://leetcode.cn/problems/Qv1Da2/
想法：
深度遍历
/*
// Definition for a Node.
class Node {
public:
int val;
Node* prev;
Node* next;
Node* child;
};
*/
class Solution {
public:
Node* flatten(Node* head) {
function<Node*(Node*)> dfs = [&](Node* node) {
Node* cur = node;
Node* last = nullptr;
while (cur) {
Node* next = cur->next;
if (cur->child) {
Node* child_last = dfs(cur->child);
next = cur->next;
cur->next = cur->child;
cur->child->prev = cur;
if (next) {
child_last->next = next;
next->prev = child_last;
}
cur->child = nullptr;
last = child_last;
}
else {
last = cur;
}
cur = next;
}
return last;
};
dfs(head);
return head;
}
};
时间复杂度： O(n)
空间复杂度： O(n)
排序的循环链表
来源： https://leetcode.cn/problems/4ueAj6/
想法：
找到循环列表中最后一个比插入值小的节点，插入在其后面即可。
如果循环列表中所有元素都比插入值小或者大，就插入在节点值最大的节点后面，可保证列表性质仍然成立。
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node() {}
Node(int _val) {
val = _val;
next = NULL;
}
Node(int _val, Node* _next) {
val = _val;
next = _next;
}
};
*/
class Solution {
public:
Node* insert(Node* head, int insertVal) {
if (head == nullptr) {
Node *tmp = new Node(insertVal);
tmp->next = tmp;
return tmp;
}else if (head->next == head) {
head->next = new Node(insertVal,head);
return head;
}else {
Node *prev = nullptr, *res = head, *max = head, *min = head;
int cnt = 0;
while (1) {
if (head->val >= max->val) max = head;
if (head->val >= insertVal && prev != nullptr) {
Node* tmp = new Node(insertVal);
prev->next = tmp;
tmp->next = head;
break;
}
if (head->val <= insertVal) prev = head;
if (head == res) {
cnt++;
if (cnt == 2){
Node *p = max->next;
max->next = new Node(insertVal,p);
break;
}
}
head = head->next;
}
return res;
}
}
};
时间复杂度： O(n)
空间复杂度： O(1)
变位词组
来源： https://leetcode.cn/problems/sfvd7V/
想法：
将每个字符串排序后的结果作为key，那么变位词的key都会是一样的。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for (string& str: strs) {
string key = str;
sort(key.begin(), key.end());
mp[key].emplace_back(str);
}
vector<vector<string>> ans;
for (auto it = mp.begin(); it != mp.end(); ++it) {
ans.emplace_back(it->second);
}
return ans;
}
};
时间复杂度： O(nklogk) n为strs中字符串的数量，k为strs中字符串的最大长度
空间复杂度： **O(nk) **n为strs中字符串的数量，k为strs中字符串的最大长度
外星语言是否排序
来源： https://leetcode.cn/problems/lwyVBB/
想法：
通过数组记录单词表每个字符的顺序，然后对于两个字符串的头开始对每个字符进行判断。如果后面一个字符串的字符在字母表中顺序在前一个字符串对应位置的字符的前面，就结束判断输出 false ；如果在后面，就结束判断输出 true ；如果等于就继续判断下一个，如果到结束都等于，那么就根据字符串长度判断，如果后一个字符串长度 $≥$ 前一个字符串的长度，就输出 true ，反之输出 false 。
class Solution {
public:
bool isAlienSorted(vector<string>& words, string order) {
if (words.size() == 1) return true;
int index[26] = {0};
for (int i = 0 ; i < order.length() ; i++) {
index[order[i] - 'a'] = i;
}
bool flag = false;
for (int i = 1 ; i < words.size() ; i++){
flag = false;
int n = min(words[i].length(),words[i - 1].length());
bool flag2 = true;
for (int j = 0 ; j < n ; j++) {
if(index[words[i][j] - 'a'] > index[words[i - 1][j] - 'a']) {
flag = true;
flag2 = false;
break;
}else if (index[words[i][j] - 'a'] < index[words[i - 1][j] - 'a']) {
flag = false;
flag2 = false;
break;
}
}
if (flag2 && words[i].length() >= words[i - 1].length()) flag = true;
if (!flag) break;
}
return flag;
}
};
时间复杂度： O(nk) n为字符串数量，k为最长的字符串长度
空间复杂度： **O(m) ** m为字母表大小
最小时间差
来源： https://leetcode.cn/problems/569nqc/
想法：
将所有时间先化为整数分钟，同时将早于12点的字符串计算两次，一次为第一天，一次为第二天。
得到结果数组后进行排序，然后遍历最小差。
class Solution {
public:
int findMinDifference(vector<string>& timePoints) {
vector<int> time;
for (int i = 0 ; i < timePoints.size(); i++) {
int hour = (timePoints[i][0] - '0') * 10 + (timePoints[i][1] - '0');
int min = (timePoints[i][3] - '0') * 10 + (timePoints[i][4] - '0');
if (hour < 12) {
time.push_back(1440 + hour * 60 + min);
}
time.push_back(hour * 60 + min);
}
std::sort(time.begin(),time.end());
int res = 9999;
for (int i = 1 ; i < time.size() ; i++) {
res = min(res,time[i] - time[i - 1]);
}
return res;
}
};
时间复杂度： O(nlogn)
空间复杂度： **O(n) **
后缀表达式
来源： https://leetcode.cn/problems/8Zf90G/
想法：
逆波兰
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> num;
for (string s : tokens) {
int temp = 300;
temp = atoi(s.c_str());
if (temp != 0) num.push(temp);
else if (s[0] == '0') num.push(temp);
else {
int num1 = num.top();
num.pop();
int num2 = num.top();
num.pop();
int tmp;
switch(s[0]) {
case '+' :
tmp = num2 + num1;
break;
case '-' :
tmp = num2 - num1;
break;
case '*' :
tmp = num2 * num1;
break;
case '/' :
tmp = num2 / num1;
break;
}
num.push(tmp);
}
}
return num.top();
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
小行星碰撞
来源： https://leetcode.cn/problems/XagZNi/
想法：
根据规则遍历，删除不符合的节点
class Solution {
public:
vector<int> asteroidCollision(vector<int>& asteroids) {
int i = 0;
int j = (int)asteroids.size() - 1;
auto it = asteroids.begin();
while (i < j && asteroids[i] < 0) {
i++;
it++;
}
while (j >= 0 && asteroids[j] > 0) j--;
while (i < j) {
if (asteroids[i + 1] * asteroids[i] < 0) {
if (abs(asteroids[i + 1]) > abs(asteroids[i])) {
it = asteroids.erase(it);
j--;
if (i != 0 && asteroids[i - 1] > 0) i--,it--;
else {
while (i < j && asteroids[i] < 0) {
i++;
it++;
}
}
}else if (abs(asteroids[i + 1]) == abs(asteroids[i])) {
it = asteroids.erase(it);
it = asteroids.erase(it);
if(i != 0 && asteroids[i - 1] > 0)i--,it--;
j-=2;
}else {
it++;
it = asteroids.erase(it);
it--;
j--;
}
}else {
i++;
it++;
}
}
return asteroids;
}
};
时间复杂度： O(n)
空间复杂度： **O(1) **
每日温度
来源： https://leetcode.cn/problems/iIQa4I/
想法：
遍历数组，用一个栈储存还没找到比它温度高的气温和索引，然后遍历每个元素时，与栈中元素进行比较然后存储索引差值即可。
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<pair<int,int>> s;
vector<int> res(temperatures.size());
for (int i = 0 ; i < temperatures.size() ; i++) {
if(!s.empty()) {
while (!s.empty() && s.top().first < temperatures[i]) {
res[s.top().second] = i - s.top().second;
s.pop();
}
}
s.push(pair<int,int>(temperatures[i],i));
}
return res;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
滑动窗口的平均值
来源： https://leetcode.cn/problems/qIsx9U/
想法：
队列
class MovingAverage {
public:
/** Initialize your data structure here. */
queue<int> q;
int self_size;
int sum = 0;
MovingAverage(int size) {
self_size = size;
}
double next(int val) {
if (q.size() == self_size) {
sum -= q.front();
q.pop();
q.push(val);
sum += val;
return sum * 1.0 / q.size();
}else {
q.push(val);
sum += val;
return sum * 1.0 / q.size();
}
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
最近请求次数
来源： https://leetcode.cn/problems/H8086Q/
想法：
队列
class RecentCounter {
public:
queue<int> q;
RecentCounter() {
}
int ping(int t) {
while (!q.empty() && t - 3000 > q.front()) q.pop();
q.push(t);
return q.size();
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
往完全二叉树添加节点
来源： https://leetcode.cn/problems/NaqhDT/
想法：
层序遍历
/**
* 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 CBTInserter {
public:
TreeNode* self_root;
queue<TreeNode*> q;
CBTInserter(TreeNode* root) {
self_root = root;
q.push(root);
}
int insert(int v) {
TreeNode *tmp = q.front();
while (tmp && tmp->left != nullptr && tmp->right != nullptr) {
q.push(tmp->left);
q.push(tmp->right);
q.pop();
tmp = q.front();
}
if (tmp->left == nullptr) {
tmp->left = new TreeNode(v);
}else {
tmp->right = new TreeNode(v);
}
return tmp->val;
}
TreeNode* get_root() {
return self_root;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
二叉树每层最大值
来源： https://leetcode.cn/problems/hPov7L/
想法：
层序遍历
/**
* 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:
vector<int> largestValues(TreeNode* root) {
vector<int> ans;
if (root == nullptr) return ans;
queue<TreeNode*> q;
ans.push_back(root->val);
q.push(root);
while(!q.empty()) {
int size = q.size();
int max_val = -pow(2,31);
bool sign = false;
while (size--) {
TreeNode *tmp = q.front();
if (tmp->left != nullptr) {
q.push(tmp->left);
max_val = max(max_val,tmp->left->val);
if (max_val == -pow(2,31)) sign = true;
else sign = false;
}
if (tmp->right != nullptr){
q.push(tmp->right);
max_val = max(max_val,tmp->right->val);
if (max_val == -pow(2,31)) sign = true;
else sign = false;
}
q.pop();
}
if (max_val != -pow(2,31) || sign)ans.push_back(max_val);
}
return ans;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
二叉树最底层最左边的值
来源： https://leetcode.cn/problems/LwUNpT/
想法：
层序遍历
/**
* 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 findBottomLeftValue(TreeNode* root) {
queue<TreeNode*> q;
q.push(root);
TreeNode *first = q.front();
while (!q.empty()) {
int size = q.size();
first = q.front();
while (size--) {
TreeNode *tmp = q.front();
if (tmp->left != nullptr) q.push(tmp->left);
if (tmp->right != nullptr) q.push(tmp->right);
q.pop();
}
}
return first->val;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
二叉树的右侧视图
来源： https://leetcode.cn/problems/WNC0Lk/
想法：
层序遍历
/**
* 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:
vector<int> rightSideView(TreeNode* root) {
vector<int> ans;
if (root == nullptr) return ans;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
TreeNode *tmp = q.front();
while (size--) {
tmp = q.front();
if (tmp->left != nullptr) q.push(tmp->left);
if (tmp->right != nullptr) q.push(tmp->right);
q.pop();
}
ans.push_back(tmp->val);
}
return ans;
}
};
时间复杂度： O(n)
空间复杂度： **O(n) **
所有子集
来源： https://leetcode.cn/problems/WNC0Lk/
想法：
对数组进行遍历，对每一个元素进行如下操作：
遍历已经在结果数组中的每一个集合，在其基础上加上当前元素，在加入到结果数组中即可。
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> res;
vector<int> first;
res.emplace_back(first);
for (int i : nums) {
int n = res.size();
for (int j = 0 ; j < n ; j++) {
vector<int> tmp;
if (!res[j].empty()) tmp = res[j];
tmp.emplace_back(i);
res.emplace_back(tmp);
}
}
return res;
}
};
时间复杂度： O(n × $2^n$)
空间复杂度： **O(n) **
含有重复元素的集合的组合
来源： https://leetcode.cn/problems/4sjJUc/
想法：
递归回溯，为了避免重复先将数组排序，在不选择当前数字的情况下，直接跳到下一个不同的数字。
class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& combine, int idx){
if (target == 0) {
ans.emplace_back(combine);
return;
}
if (idx == candidates.size()) return;
if (candidates[idx] > target) return;
int tmp = idx;
while (tmp < candidates.size() - 1 && candidates[tmp + 1] == candidates[tmp]) tmp++;
tmp++;
dfs(candidates,target,ans,combine,tmp);
if (target - candidates[idx] >= 0) {
combine.emplace_back(candidates[idx]);
dfs(candidates,target - candidates[idx], ans, combine, idx + 1);
combine.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
std::sort(candidates.begin(),candidates.end());
vector<vector<int>> ans;
vector<int> combine;
if (candidates.size() == 1) {
if (candidates[0] == target) {
combine.emplace_back(candidates[0]);
ans.emplace_back(combine);
return ans;
}
}else dfs(candidates,target,ans,combine,0);
return ans;
}
};
时间复杂度： O(n × $2^n$)
空间复杂度： **O(n) **