二刷代码随想录¶
数组¶
2. 二分查找¶
二分查找只要记住分别二分左边界和右边界的代码即可
int searchLeft(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
// 寻找左边界（即大于等于），对于r来说就是糊涂账，但是l非常清楚，就是当小于时，l必定需要+1
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
return l;
}
int searchRight(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
// 寻找右边界（小于等于），那么直接看大于的情况
if (nums[mid] > target) r = mid - 1;
else l = mid;
}
return l;
}
704. Binary Search¶
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() -1;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (nums[mid] > target) r = mid - 1;
else l = mid;
}
if (nums[l] == target) return l;
else return -1;
}
};
35. Search Insert Position¶
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] >= target) r = mid;
else l = mid + 1;
}
printf("%d %d", l, r);
if (nums[l] == target) return l;
else if (l == nums.size() - 1 && target > nums[l]) return l + 1;
else return l;
}
};
34. Find First and Last Position of Element in Sorted Array¶
class Solution {
public:
int searchLeft(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
// 寻找左边界（即大于等于），对于r来说就是糊涂账，但是l非常清楚，就是当小于时，l必定需要+1
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] < target) l = mid + 1;
else r = mid;
}
return l;
}
int searchRight(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = (l + r + 1) >> 1;
// 寻找右边界（小于等于），那么直接看大于的情况
if (nums[mid] > target) r = mid - 1;
else l = mid;
}
return l;
}
vector<int> searchRange(vector<int>& nums, int target) {
if (!nums.size()) return {-1, -1};
int l = searchLeft(nums, target);
int r = searchRight(nums, target);
if (nums[l] == target && nums[r] == target) return {l, r};
else return {-1, -1};
}
};
69. Sqrt(x)¶
class Solution {
public:
int mySqrt(int x) {
if (x == 0) return 0;
long l = 1, r = x;
while (l < r) {
long long mid = (l + r + 1) >> 1;
if (mid * mid > x) r = mid - 1;
else l = mid;
}
return l;
}
};
367. Valid Perfect Square¶
class Solution {
public:
bool isPerfectSquare(int num) {
long long l = 0, r = num;
while (l < r) {
long long mid = (l + r + 1) >> 1;
if (mid * mid > num) r = mid - 1;
else l = mid;
}
return l * l == num;
}
};
3. 移除元素¶
移动元素到后面去或者只需要让前面的数组保持某种性质，那么就会用到nums[j++] = nums[i]
27. Remove Element¶
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int j = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != val) {
nums[j++] = nums[i];
}
}
return j;
}
};
26. Remove Duplicates from Sorted Array¶
思路同上
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int j = 1;
for (int i = 1; i < nums.size(); i++) {
if (nums[i] != nums[i - 1]) nums[j++] = nums[i];
}
return j;
}
};
283. Move Zeroes¶
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int j = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] != 0) nums[j++] = nums[i];
}
for (; j < nums.size(); j++) nums[j] = 0;
}
};
844. Backspace String Compare¶
第一种解法：空间复杂度为O(1)，推荐！
class Solution {
public:
void getString(string& s) {
int slow = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != '#') {
s[slow++] = s[i];
} else if (slow > 0) {
slow--;
};
}
s.resize(slow);
}
bool backspaceCompare(string s, string t) {
getString(s);
getString(t);
return s == t;
}
};
第二种解法：
class Solution {
public:
string getString(string& s) {
string res;
for (auto c : s) {
if (c == '#') {
if (res.size()) res.pop_back();
} else {
res += c;
}
}
return res;
}
bool backspaceCompare(string s, string t) {
return getString(s) == getString(t);
}
};
977. Squares of a Sorted Array¶
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
int pos = n - 1;
for (int i = 0, j = nums.size() - 1; i <= j; ) {
int left = nums[i] * nums[i];
int right = nums[j] * nums[j];
if (left > right) {
ans[pos] = left;
i++;
}
else {
ans[pos] = right;
j--;
}
pos--;
}
return ans;
}
};
或者直接sort，sort的时间复杂度时nlogn
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
for (int i = 0; i < nums.size(); i++) {
nums[i] = pow(nums[i], 2);
}
sort(nums.begin(), nums.end());
return nums;
}
};
4. 有序数组的平方¶
977. Squares of a Sorted Array¶
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n);
int pos = n - 1;
for (int i = 0, j = nums.size() - 1; i <= j; ) {
int left = nums[i] * nums[i];
int right = nums[j] * nums[j];
if (left > right) {
ans[pos] = left;
i++;
}
else {
ans[pos] = right;
j--;
}
pos--;
}
return ans;
}
};
5. 长度最小的子数组¶
滑动窗口希望得到的是以右端点结尾的符合某一条件的窗口，并且需要遍历整个数组
因此体会for (;r < nums.size(); r++)的巧妙！
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int l = 0, r = 0, sum = 0;
int res = 1e9 + 10;
for (;r < nums.size(); r++) {
sum += nums[r];
while (l <= r && sum >= target) {
res = min(res, r - l + 1);
sum -= nums[l];
l++;
}
}
if (res > 1e9) return 0;
return res;
}
};
76. Minimum Window Substring¶
class Solution {
public:
string minWindow(string s, string t) {
// 需要使用total 来记录还需要匹配的字符种类数
// vector<int> c1(60), c2(60);
// 同样的字母只要c1中的比c2中的大，那么指针就可以更新
// a-z对应0-25，A-Z对应26-51
int m = s.size(), n = t.size();
vector<int> c1(60), c2(60);
int total = 0;
int min = INT_MAX;
string ans;
for (char ch : t) {
if (++c2[getId(ch)] == 1) {
total++;
}
}
for (int i = 0, j = 0; i < m; i++) {
if (++c1[getId(s[i])] == c2[getId(s[i])]) {
total--;
}
while (j < i) {
int idx2 = getId(s[j]);
if (c1[idx2] > c2[idx2] && --c1[idx2] >= 0) j++;
else break;
}
if (total == 0 && (ans.empty() || ans.length() > i - j + 1)) ans = s.substr(j, i - j + 1);
}
return ans;
}
int getId(char ch) {
return ch >= 'A' && ch <= 'Z' ? ch - 'A' + 26 : ch - 'a';
}
};
904. Fruit Into Baskets¶
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> hash;
int ans = 0;
int n = fruits.size();
for (int i = 0, j = 0; i < n; i++) {
hash[fruits[i]]++;
while (hash.size() > 2) {
if (--hash[fruits[j]] == 0) {
hash.erase(fruits[j]);
}
j++;
}
ans = max(i - j + 1, ans);
cout << hash.size() << endl;
}
return ans;
}
};
6. 螺旋矩阵¶
class Solution {
public:
vector<vector<int>> generateMatrix(int l) {
vector<vector<int>> ans(l, vector<int>(l));
vector<int> dx = {0, 1, 0, -1};
vector<int> dy = {1, 0, -1, 0};
for (int i = 1, x = 0, y = 0, n = 0; i <= l * l; i++) {
ans[x][y] = i;
cout << "check";
int checkX = x + dx[n % 4];
int checkY = y + dy[n % 4];
if (checkX >= 0 && checkX < l && checkY >= 0 && checkY < l && ans[checkX][checkY] == 0) {
x = checkX;
y = checkY;
}
else {
cout << "check1";
n++;
x = x + dx[n % 4];
y = y + dy[n % 4];
}
}
return ans;
}
};
链表¶
2. 移除链表元素¶
203. Remove Linked List Elements¶
使用递归的方法：
/**
* 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* removeElements(ListNode* head, int val) {
// 先处理特殊情况和到头了的情况
if (head == nullptr) return head;
// 再处理之后的情况
head->next = removeElements(head->next, val);
// 最后处理自身的情况
if (head->val == val) return head->next;
else return head;
}
};
不推荐的迭代方法：
/**
* 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* removeElements(ListNode* head, int val) {
ListNode* dummy = new ListNode(-1, head);
ListNode* temp = dummy;
while (temp->next != nullptr) {
if (temp->next->val == val) {
temp->next = temp->next->next;
} else temp = temp->next;
}
return dummy->next;
}
};
3. 设计链表¶
4. 翻转链表¶
206. Reverse Linked List¶
/**
* 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) {
ListNode* prev = NULL;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* tmp = curr->next;
curr->next = prev;
prev = curr;
curr = tmp;
}
return prev;
}
};
5. 两两交换链表中的节点¶
24. Swap Nodes in Pairs¶
/**
* 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* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(-1, head);
ListNode* curr = dummy;
while (curr && curr->next && curr->next->next) {
ListNode* tmp = curr->next->next;
curr->next->next = tmp->next;
tmp->next = curr->next;
curr->next = tmp;
curr = curr->next->next;
}
return dummy->next;
}
};
6. 删除链表的倒数第N个节点¶
19. Remove Nth Node From End of List¶
/**
* 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* dummy = new ListNode(-1, head);
ListNode *right = dummy, *left = dummy;
for (int i = 0; i < n; i++) {
right = right->next;
}
while (right->next != nullptr) {
right = right->next;
left = left->next;
}
left->next = left->next->next;
return dummy->next;
}
};
7. 链表相交¶
面试题 02.07. Intersection of Two Linked Lists LCCI
使用哈希表¶
/**
* 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) {
unordered_set<ListNode *> hash;
ListNode *tmp = headA;
while (tmp != nullptr) {
hash.insert(tmp);
tmp = tmp->next;
}
tmp = headB;
while (tmp != nullptr) {
if (hash.count(tmp)) {
return tmp;
}
tmp = tmp->next;
}
return nullptr;
}
};
通过链表的长度特性来做¶
相交代表的是后面有一段长度相同的部分完全跟相同
a + c = m
b + c = n
A 和B分别经过a + c + b和b + c +a之后会到达相同的节点
否则就会抵达相同的null
/**
* 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 *a = headA, *b = headB;
while (a != b) {
if (a == nullptr) a = headB;
else a = a->next;
if (b == nullptr) b = headA;
else b = b->next;
}
return a;
}
};
通过链表的长度特性来做2¶
可以求出两条的长度
然后求出差值
然后长的那条先到差值处
然后a和b同时往后面走必然能走到相同的节点
8. 环形链表II¶
142. Linked List Cycle II¶
/**
* 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) {
// 如果只有一个环，那么快指针是慢指针两倍的话，会相遇在最初的起点
// 而有了非环的部分，会相遇在慢指针还没走完一圈的时候
// 快指针走过的路= a + n(b + c) +b
// 慢指针走过的路= a + b
// 2a + 2b = a + (n + 1) b + nc
// a = (n - 1)b + (n - 1)c + c
// 如果head和慢指针同时走a的路，那么head会到入环点，而慢指针会在转了(k - 1)圈之后到入环点
ListNode *fast = head, *slow = head;
while (true) {
if (fast == nullptr || fast->next == nullptr) return nullptr;
fast = fast->next->next;
slow = slow->next;
if (fast == slow) break;
}
ListNode *curr = head;
while (curr != fast) {
fast = fast->next;
curr = curr->next;
}
return curr;
}
};
哈希表¶
2. 有效的字母异位词¶
242. Valid Anagram¶
class Solution {
public:
bool isAnagram(string s, string t) {
vector<int> count(26);
for (char ch : s) count[ch - 'a']++;
for (char ch : t) count[ch - 'a']--;
for (int i = 0; i < 26; i++) {
if (count[i]) return false;
}
return true;
}
};
3. 两个数组的交集¶
349. Intersection of Two Arrays¶
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
// 如果记录个数没有意义，而且需要用到唯一元素或者不重复元素，就可以考虑使用unordered_set
unordered_set<int> result_set;
unordered_set<int> nums1_set(nums1.begin(), nums1.end());
for (auto num : nums2) {
if (nums1_set.find(num) != nums1_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
4. 快乐数¶
202. Happy Number¶
推荐使用快慢双指针¶
class Solution {
public:
int getNext(int n) {
int sum = 0;
while (n) {
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n, fast = n;
do {
slow = getNext(slow);
fast = getNext(getNext(fast));
} while(slow != fast);
return slow == 1;
}
};
不推荐使用unordered_set¶
class Solution {
public:
bool isHappy(int n) {
unordered_set<int> hash_set;
return isHappyHelper(n, hash_set);
}
private:
bool isHappyHelper(int n, unordered_set<int>& hash_set) {
if (n == 1) return true;
if (hash_set.find(n) != hash_set.end()) return false;
hash_set.insert(n);
int next = 0;
while (n) {
next += pow(n % 10, 2);
n /= 10;
}
return isHappyHelper(next, hash_set);
}
};
5. 两数之和¶
1. Two Sum¶
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash;
for (int i = 0; i < nums.size(); i++) {
if (hash.count(target - nums[i])) {
return {i, hash[target - nums[i]]};
}
else {
hash[nums[i]] = i;
}
}
return {};
}
};
6. 四数相加II¶
454. 4Sum II¶
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
// 正常来说就是三重循环加上哈希查表，相当于n^3 + n
// 如果想要降到n^2，那么就是num1, nums2两重循环
// 需要nums3 + nums4 = -(num1 + nums2)
// 观察最后实际上需要查找的是nums3 + nums4的和
// 所以开nums3 + nums4和的哈希表
unordered_map<int, int> count;
for (auto c : nums3) {
for (auto d : nums4) {
count[c + d]++;
}
}
int res = 0;
for (auto a : nums1) {
for (auto b : nums2) {
res += count[- (a + b)];
}
}
return res;
}
};
7. 赎金信¶
383. Ransom Note¶
用数组在空间上会更好一些
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
if (ransomNote.size() > magazine.size()) return false;
vector<int> cnt(26);
// reference saves both time and space
for (char& c : magazine) cnt[c - 'a']++;
for (char& c : ransomNote) {
if (--cnt[c - 'a'] < 0) return false;
}
return true;
}
};
8. 三数之和¶
15. 3Sum¶
双指针法（推荐）¶
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int j = i + 1, k = nums.size() - 1;
for (; j < nums.size() - 1 && j < k; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int sum = nums[i] + nums[j];
while (nums[k] > -sum && k > j + 1) k--;
if (nums[k] == -sum) ans.push_back({nums[i], nums[j], nums[k]});
}
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
int l = i + 1, r = nums.size() - 1;
if (i && nums[i - 1] == nums[i]) continue;
while (l < r) {
int s = nums[i] + nums[l] + nums[r];
if (s == 0) {
res.push_back({nums[i], nums[l], nums[r]});
r--;
while (r < nums.size() - 1 && nums[r] == nums[r + 1]) r--;
}
else if (s > 0) r--;
else l++;
}
}
return res;
}
};
哈希法（不是非常推荐）¶
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
unordered_map<int, int> hash;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i++) hash[nums[i]] = i;
for (int i = 0; i < nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size() - 1; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int sum = nums[i] + nums[j];
if (hash.count(-sum) && hash[-sum] > i && hash[-sum] > j) {
ans.push_back({nums[i], nums[j], -sum});
}
}
}
return ans;
}
};
9. 四数之和¶
18. 4Sum¶
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
if (nums.size() < 4) return res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 3; i++) {
if (i && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size() - 2; j++) {
if (j >= i + 2 && nums[j - 1] == nums[j]) continue;
for (int m = j + 1, n = nums.size() -1; m < n; m++) {
if (m >= j + 2 && nums[m - 1] == nums[m]) continue;
while (m < n - 1 && (long long)nums[i] + nums[j] + nums[m] + nums[n -1] >= target) n--;
if ((long long)nums[i] + nums[j] + nums[m] + nums[n] == target) {
res.push_back({nums[i], nums[j], nums[m], nums[n]});
}
}
}
}
return res;
}
};
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// 小于四个的个数，必须要排除
if (nums.size() < 4) return {};
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.size() - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = nums.size() - 1;
for (; l < r && l < nums.size() - 1; l++) {
if (l > j + 1 && nums[l] == nums[l - 1]) continue;
long long sum = (long long)nums[i] + nums[j] + nums[l];
long long aim = target - sum;
while (nums[r] > aim && r > l + 1) r--;
if (nums[r] == aim) ans.push_back({nums[i], nums[j], nums[l], nums[r]});
}
}
}
return ans;
}
};
字符串¶
1. 反转字符串¶
344. Reverse String¶
class Solution {
public:
void reverseString(vector<char>& s) {
if (!s.size()) return;
int i = 0, j = s.size() - 1;
while (i < j) {
swap(s[i], s[j]);
i++;
j--;
}
}
};
2. 反转字符串II¶
541. Reverse String II¶
class Solution {
public:
string reverseStr(string s, int k) {
for (int i = 0; i < s.size(); i += 2 * k) {
if (i + k <= s.size()) {
reverse(s.begin() + i, s.begin() + i + k);
}
else {
reverse(s.begin() + i, s.end());
}
}
return s;
}
};
3. 替换数字¶
#include<iostream>
using namespace std;
int main() {
string s;
while (cin >> s) {
int count = 0; // 统计数字的个数
int sOldSize = s.size();
for (int i = 0; i < s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') {
count++;
}
}
// 扩充字符串s的大小，也就是每个空格替换成"number"之后的大小
s.resize(s.size() + count * 5);
int sNewSize = s.size();
// 从后先前将空格替换为"number"
for (int i = sNewSize - 1, j = sOldSize - 1; j < i; i--, j--) {
if (s[j] > '9' || s[j] < '0') {
s[i] = s[j];
} else {
s[i] = 'r';
s[i - 1] = 'e';
s[i - 2] = 'b';
s[i - 3] = 'm';
s[i - 4] = 'u';
s[i - 5] = 'n';
i -= 5;
}
}
cout << s << endl;
}
}
4. 翻转字符串里的单词¶
151. Reverse Words in a String¶
想将去除空格
然后将整个字符串翻转
最后一个一个单词翻转
class Solution {
public:
void manageSpaces (string& s) {
int slow = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ') {
while (i < s.size() && s[i] != ' ') {
s[slow++] = s[i++];
}
s[slow++] = ' ';
}
}
s.resize(slow - 1);
}
string reverseWords(string s) {
manageSpaces(s);
reverse(s.begin(), s.end());
cout << s << endl;
for (int i = 0; i < s.size(); i++) {
cout << "i: " << i << endl;
if (s[i] != ' ') {
int j = i;
while (j < s.size() && s[j] != ' ') j++;
cout << "j: " << j << endl;
reverse(s.begin() + i, s.begin() + j);
i = j;
}
}
return s;
}
};
5. 右旋转字符串¶
右旋两个 = 整体翻转+前后各自翻转: de abc
#include <iostream>
#include <algorithm>
#include <string>
int main () {
int n;
std::string a;
std::cin >> n >> a;
reverse(a.begin(), a.end());
reverse(a.begin(), a.begin() + n);
reverse(a.begin() + n, a.end());
std::cout << a << std::endl;
return 0;
}
6. 实现strStr()¶
28. Find the Index of the First Occurrence in a String¶
推荐使用的kmp
class Solution {
public:
int strStr(string haystack, string needle) {
int n = needle.size(), m = haystack.size();
vector<int> next(n, -1);
int j = -1;
for (int i = 1; i < n; i++) {
while (j != -1 && needle[i] != needle[j + 1]) {
j = next[j];
}
if (needle[i] == needle[j + 1]) j++;
next[i] = j;
}
for (int i = 0, j = -1; i < m; i++) {
while (j != -1 && haystack[i] != needle[j + 1]) {
j = next[j];
}
if (haystack[i] == needle[j + 1]) j++;
if (j == n - 1) {
return i - n + 1;
}
}
return -1;
}
};
class Solution {
public:
int strStr(string haystack, string needle) {
int n = haystack.size(), m = needle.size();
haystack = ' ' + haystack, needle = ' ' + needle;
vector<int> ne(m + 1);
// 为什么从i = 2开始?
// abc现在是_abc，而needle[1]就是'a'必然是0，所以从2开始
// j代表在第i个字母之前已经匹配了的字符个数
// "_aba" "00"
for (int i = 2, j = 0; i <= m; i++) {
// while的意思是，在第i个字母之前有匹配的字符，但是第i个字符和前j个字符对不上
while (j && needle[i] != needle[j + 1]) {
j = ne[j];
}
if (needle[i] == needle[j + 1]) {
j++;
}
ne[i] = j;
}
for (int i = 1, j = 0; i <= n; i++) {
while (j && haystack[i] != needle[j + 1]) {
j = ne[j];
}
if (haystack[i] == needle[j + 1]) {
j++;
}
//因为右移过了，所以还得减一
if (j == m) return i - m + 1 - 1;
}
return -1;
}
};
7. 重复的子字符串¶
459. Repeated Substring Pattern¶
暴力做法：
class Solution {
public:
bool repeatedSubstringPattern(string s) {
int n = s.size();
for (int i = 1; i * 2 <= n; i++) {
if (n % i == 0) {
bool match = true;
for (int j = i; j < n; j++) {
if (s[j] != s[j - i]) {
match = false;
break;
}
}
if (match)
return true;
}
}
return false;
}
};
字符串匹配做法
class Solution {
public:
bool repeatedSubstringPattern(string s) {
return (s + s).find(s, 1) != s.size();
}
};
kmp代替find的做法
class Solution {
public:
bool kmp(const string& s, const string& t) {
int n = s.size(), m = t.size();
vector<int> next(m, -1);
for (int i = 1, j = -1; i < m; i++) {
while (j != -1 && t[i] != t[j + 1]) {
j = next[j];
}
if (t[i] == t[j + 1]) j++;
next[i] = j;
}
for (int i = 1, j = -1; i < n - 1; i++) {
while (j != -1 && s[i] != t[j + 1]) {
j = next[j];
}
if (s[i] == t[j + 1]) j++;
if (j == m - 1 ) return true;
}
return false;
}
bool repeatedSubstringPattern(string s) {
return kmp(s + s, s);
}
};
kmp优化做法
class Solution {
public:
bool kmp(const string& t) {
int m = t.size();
vector<int> next(m, -1);
for (int i = 1, j = -1; i < m; i++) {
while (j != -1 && t[i] != t[j + 1]) {
j = next[j];
}
if (t[i] == t[j + 1]) j++;
next[i] = j;
}
return next[m - 1] != -1 && m % (m - next[m - 1] - 1) == 0;
}
bool repeatedSubstringPattern(string s) {
return kmp(s);
}
};
双指针法（暂时跳过）¶
1. 移除元素¶
2. 反转字符串¶
3. 替换数字¶
4. 翻转字符串里的单词¶
5. 翻转链表¶
6. 删除链表的倒数第N个节点¶
7. 链表相交¶
栈与队列¶
栈是先进后出，像一个单口的罐子，所以先放进去的后拿出来
队列是先进先出，像双口的罐子，从下面接着
栈提供push 和 pop 等等接口，所有元素必须符合先进后出规则，所以栈不提供走访功能，也不提供迭代器(iterator)。 不像是set 或者map 提供迭代器iterator来遍历所有元素。
栈是stack
queue, 队列，先进先出，没有clear
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
q = queue<int>(); 能够直接清空q，而不需要用到clear
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆可以向里面插入-x
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
2. 用栈实现队列¶
232. Implement Queue using Stacks¶
class MyQueue {
private:
stack<int> inStack, outStack;
void inToOut() {
while (!inStack.empty()) {
outStack.push(inStack.top());
inStack.pop();
}
}
public:
MyQueue() {}
void push(int x) {
inStack.push(x);
}
int pop() {
if (outStack.empty()) {
inToOut();
}
int x = outStack.top();
outStack.pop();
return x;
}
int peek() {
if (outStack.empty()) {
inToOut();
}
return outStack.top();
}
bool empty() {
return inStack.empty() && outStack.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
3. 用队列实现栈¶
225. Implement Stack using Queues¶
// 只要保证入栈的时候每个元素都在队列1的最前面即可
class MyStack {
private:
queue<int> q1, q2;
public:
MyStack() {}
void push(int x) {
q2.push(x);
while (!q1.empty()) {
q2.push(q1.front());
q1.pop();
}
swap(q1, q2);
}
int pop() {
int x = q1.front();
q1.pop();
return x;
}
int top() {
return q1.front();
}
bool empty() {
return q1.empty();
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
4. 有效的括号¶
20. Valid Parentheses¶
class Solution {
public:
bool isValid(string s) {
stack<char> stk;
for (auto c : s) {
if (c == '(' || c == '[' || c == '{') stk.push(c);
else {
if (stk.size() && abs(stk.top() - c) <= 2) stk.pop();
else return false;
}
}
return stk.empty();
}
};
### 5. 删除字符串中的所有相邻重复项
1047. Remove All Adjacent Duplicates In String¶
class Solution {
public:
string removeDuplicates(string s) {
string stack;
for (auto ch : s) {
if (stack.size() && stack.back() == ch) {
stack.pop_back();
}
else {
stack.push_back(ch);
}
}
return stack;
}
};
6. 逆波兰表达式求值¶
7. 滑动窗口最大值¶
8. 前k个高频元素¶
动态规划¶
基础题目¶
2. 斐波那契数¶
509. Fibonacci Number¶
class Solution {
public:
int fib(int n) {
// f[i] = f[i - 1] + f[i - 2]
if (n == 0) return 0;
if (n == 1) return 1;
int f0 = 0;
int f1 = 1;
for (int i = 0; i < n - 1; i++) {
int new_f = f0 + f1;
f0 = f1;
f1 = new_f;
}
return f1;
}
};
3. 爬楼梯¶
70. Climbing Stairs¶
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
// f[i] = f[i - 1] + f[i - 2]
int f[n + 1];
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= n; i++) {
f[i] = f[i - 1] + f[i - 2];
}
return f[n];
}
};
优化一下空间：
class Solution {
public:
int climbStairs(int n) {
if (n <= 2) return n;
// f[i] = f[i - 1] + f[i - 2]
// int f[n + 1];
int f1 = 1;
int f2 = 2;
for (int i = 3; i <= n; i++) {
int f3 = f2 + f1;
f1 = f2;
f2 = f3;
}
return f2;
}
};
4. 使用最小花费爬楼梯¶
746. Min Cost Climbing Stairs¶
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
// f[i]代表的是最小花费
// f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
// 需要到达的是cost.size() + 1
int f[n + 1];
f[0] = 0;
f[1] = 0;
for (int i = 2; i < n + 1; i++) {
f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
}
return f[n];
}
};
优化一下空间：
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
// f[i]代表的是最小花费
// f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2]);
// 需要到达的是cost.size() + 1
// int f[n + 1];
int f0 = 0;
int f1 = 0;
for (int i = 2; i < n + 1; i++) {
int new_f = min(f1 + cost[i - 1], f0 + cost[i - 2]);
f0 = f1;
f1 = new_f;
}
return f1;
}
};
6. 不同路径¶
62. Unique Paths¶
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> f(m, vector<int>(n));
// f[i][j] = f[i - 1]f[j] + f[i][j - 1]
f[0][0] = 1;
for (int i = 0; i < m; i++) f[i][0] = 1;
for (int i = 0; i < n; i++) f[0][i] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
return f[m - 1][n - 1];
}
};
优化空间：
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> f(n);
// f[i][j] = f[i - 1]f[j] + f[i][j - 1]
// 将[i]优化掉因为对于每个循环来说f[i][j] = f[i - 1][j]
f[0] = 1;
// for (int i = 0; i < m; i++) f[i][0] = 1;
for (int i = 0; i < n; i++) f[i] = 1;
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
f[j] = f[j] + f[j - 1];
}
}
return f[n - 1];
}
};
7. 不同路径II¶
63. Unique Paths II¶
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> f(m, vector<int>(n));
if (obstacleGrid[0][0] == 1) return 0;
f[0][0] = 1;
for (int i = 1; i < n; i++) f[0][i] = obstacleGrid[0][i] == 1 ? 0 : f[0][i - 1];
for (int i = 1; i < m; i++) f[i][0] = obstacleGrid[i][0] == 1 ? 0 : f[i - 1][0];
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
if (obstacleGrid[i][j] == 1) f[i][j] = 0;
}
}
return f[m - 1][n - 1];
}
};
用滚动数组优化一下空间：
一定一定注意对f[0]的处理！！！
在空间优化版本中j 应该从0开始处理！！
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
// vector<vector<int>> f(m, vector<int>(n));
vector<int> f(n);
if (obstacleGrid[0][0] == 1) return 0;
f[0] = 1;
// for (int i = 1; i < n; i++) f[0][i] = obstacleGrid[0][i] == 1 ? 0 : f[0][i - 1];
for (int i = 1; i < n; i++) f[i] = obstacleGrid[0][i] == 1 ? 0 : f[i - 1];
// for (int i = 1; i < m; i++) f[i][0] = obstacleGrid[i][0] == 1 ? 0 : f[i - 1][0];
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
if (j != 0) f[j] = f[j] + f[j - 1];
if (obstacleGrid[i][j] == 1) f[j] = 0;
}
}
return f[n - 1];
}
};
8. 整数拆分¶
343. Integer Break¶
class Solution {
public:
int integerBreak(int n) {
// k是大于0小于i的数
// f[i]表示的是i能得到的最大乘积
// f[i] = max(f[i - k] * (k))
vector<int> f(59);
f[1] = 1;
for (int i = 2; i < 59; i++) {
int tmp = 0;
for (int j = 1; j < i; j++) {
tmp = max(f[j] * (i - j), tmp);
tmp = max(j * (i - j), tmp);
}
f[i] = tmp;
}
return f[n];
}
};
9. 不同的二叉搜索树¶
96. Unique Binary Search Trees¶
class Solution {
public:
int numTrees(int n) {
// 利用二叉搜索树的性质：在任意子树的顶点左边的数必然小于顶点，在任意子树顶点右边的数必然大于顶点
// 直接分割整数数段进行分割
// f[k] = f[n - k] * f[0 - k - 1]
vector<int> f(20);
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= 19; i++) {
int sum = 0;
for (int j = 1; j <= i; j++) {
sum += f[j - 1] * f[i - j];
}
f[i] = sum;
}
return f[n];
}
};
01背包¶
13. 分割等和子集¶
416. Partition Equal Subset Sum¶
class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = 0, size = nums.size();
for (int n : nums) sum += n;
if (sum % 2 == 1) return false;
else sum /= 2;
vector<int> f(sum + 1);
for (int i = 0; i < sum + 1; i++) f[i] = 0;
// for (int i = 0; i < size + 1; i++) f[i][0] = 0;
for (int i = 1; i <= size; i++) {
for (int j = sum; j >= nums[i - 1]; j--) {
// f[i][j] = f[i - 1][j];
f[j] = max(f[j], f[j - nums[i - 1]] + nums[i - 1]);
}
}
if (f[sum] == sum) return true;
else return false;
}
};
14. 最后一块石头的重量II¶
1049. Last Stone Weight II¶
class Solution {
public:
int lastStoneWeightII(vector<int>& stones) {
// 做完之后的合法性证明：实际上是最后两堆石头的差值最小，所以2225这个情况，需要看的是差的绝对值最小即可abs(5-2-2-2) = 1就行
// 所有的方案最后都能被化简为(x + x + x) - (y + y + y)
// 证明：只要左边大于等于右边，就可以做到；如果右边大于左边，那么互换位置即可；
// 如果左边的数量大于右边，比如2, 2, 2, 5，最小值是2+2+2-5，三个2不能融合怎么办？——左右互换答案一致的
// 所以最后只要找到所有数中最接近总和一般的组合即可
int sum = 0, n = stones.size();
for (auto stone : stones) sum += stone;
int ans = sum;
sum /= 2;
vector<vector<int>> f(n + 1, vector<int>(sum + 1));
// vector自动是0，就不设置了
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < sum + 1; j++) {
f[i][j] = f[i - 1][j];
if (j >= stones[i - 1]) f[i][j] = max(f[i][j], f[i - 1][j - stones[i - 1]] + stones[i - 1]);
}
}
cout << "sum: " << sum << endl;
cout << "ans: " << ans << endl;
cout << "f[n][sum]: " << f[n][sum] << endl;
return ans - f[n][sum] * 2;
}
};
16. 目标和¶
494. Target Sum¶
1. 二维直观写法¶
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// if (target < -1000 || target > 1000) return 0;
// 对于每一个数相当于对应两个状态，一个是加一个是减，对应到原始01背包中一个是选一个是不选
// f[i][j]表示的是加或减第i个数，得到的和为j的集合，以及集合的数量
// f[i][j] = f[i - 1][j - nums[i]] + f[i - 1][j + nums[i]]
// 注意到sum的取值范围和target的取值范围，那么j的取值范围其实是-sum ~ sum
// j >= -1000 && j <= 1000
int n = nums.size();
vector<vector<int>> f(n + 1, vector<int>(2001));
// -1000 + 1000 = 0
int Offset = 1000;
f[0][0 + Offset] = 1;
for (int i = 1; i < n + 1; i++) {
for (int j = -1000; j <= 1000 ; j++) {
if (j - nums[i - 1] >= -1000) {
f[i][j + Offset] += f[i - 1][j - nums[i - 1] + Offset];
}
if (j + nums[i - 1] <= 1000) {
f[i][j + Offset] += f[i - 1][j + nums[i - 1] + Offset];
}
}
}
return f[n][target + Offset];
}
};
2. 一维推导做法¶
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 总和为s，正数和为p，负数和-(s - p)
// p - (s - p) = target
// 2p = target + s
// p = (target + s) / 2
// f[i][j]就是前i个数中，和等于j的方案，属性是方案的数量
// p >= 0 && p <= 1000
int sum = target, n = nums.size();
for (int num : nums) sum += num;
if (sum % 2 == 1 || sum < 0) return 0;
sum /= 2;
vector<vector<int>> f(n + 1, vector<int>(sum + 1));
f[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < sum + 1; j++) {
f[i][j] += f[i - 1][j];
if (j >= nums[i - 1]) f[i][j] += f[i - 1][j - nums[i - 1]];
}
}
return f[n][sum];
}
};
3. dfs做法¶
class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
// 所有的正数和为p，所有的负数和为s - p，那么p - (s- p) = target
// 所以所有正数的和p = (target + s) / 2
target += accumulate(nums.begin(), nums.end(), 0);
if (target < 0 || target % 2 == 1) return 0;
target /= 2;
int n = nums.size();
// n的原因是只要在碰到横坐标小于0的时候，如果target只剩下0了那么就返回1，如果剩下还有多余，那么返回0
// c++中true是1，false是0
// target + 1的原因是需要计算的时从0到target的所有方案个数
vector<vector<int>> f(n, vector<int>(target + 1, -1));
function<int(int, int)> dfs = [&] (int i, int c) -> int{
if (i < 0) return c == 0;
int &res = f[i][c];
if (res != -1) return res;
if (nums[i] > c) return res = dfs(i - 1, c);
else return res = dfs(i - 1, c) + dfs(i - 1, c - nums[i]);
};
return dfs(n - 1, target);
}
};
17. 一和零 （二维费用的背包问题）¶
474. Ones and Zeroes¶
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
vector<vector<int>> f(m + 1, vector<int>(n + 1));
for (auto str : strs) {
int zeros = 0, ones = 0;
for (auto c : str) {
if (c == '0') zeros++;
else ones++;
}
for (int i = m; i >= zeros; i--) {
for (int j = n; j >= ones; j--) {
f[i][j] = max(f[i][j], f[i - zeros][j - ones] + 1);
}
}
}
return f[m][n];
}
};
二维背包问题的代码模板¶
#include <iostream>
using namespace std;
const int N = 110;
int n, V, M;
int f[N][N];
int main () {
cin >> n >> V >> M;
for (int i = 0; i < n; i++) {
int v, m, w;
cin >> v >> m >> w;
for (int j = V; j >= v; j--) {
for (int k = M; k >= m; k--) {
f[j][k] = max(f[j][k], f[j - v][k - m] + w);
}
}
}
cout << f[V][M] << endl;
return 0;
}