type
Post
status
Published
date
Apr 18, 2023
slug
leetcode
summary
tags
算法
category
技术分享
icon
password
数组
二分查找
704.二分查找
class Solution { public: int search(vector<int>& nums, int target) { int left = 0; int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right) while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 < int middle = left + ((right - left) >> 1); if (nums[middle] > target) { right = middle; // target 在左区间,在[left, middle)中 } else if (nums[middle] < target) { left = middle + 1; // target 在右区间,在[middle + 1, right)中 } else { // nums[middle] == target return middle; // 数组中找到目标值,直接返回下标 } } // 未找到目标值 return -1; } };
快慢指针
27. 移除元素
class Solution { public: int removeElement(vector<int>& nums, int val) { int slowIndex = 0; for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) { if (val != nums[fastIndex]) { nums[slowIndex++] = nums[fastIndex]; } } return slowIndex; } };
滑动窗口
209.长度最小的子数组
class Solution { public: int minSubArrayLen(int s, vector<int>& nums) { int result = INT32_MAX; int sum = 0; // 滑动窗口数值之和 int i = 0; // 滑动窗口起始位置 int subLength = 0; // 滑动窗口的长度 for (int j = 0; j < nums.size(); j++) { sum += nums[j]; // 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件 while (sum >= s) { subLength = (j - i + 1); // 取子序列的长度 result = result < subLength ? result : subLength; sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置) } } // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列 return result == INT32_MAX ? 0 : result; } };
链表
虚拟头结点
203.移除链表元素
class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点 dummyHead->next = head; // 将虚拟头结点指向head,这样方面后面做删除操作 ListNode* cur = dummyHead; while (cur->next != NULL) { if(cur->next->val == val) { ListNode* tmp = cur->next; cur->next = cur->next->next; delete tmp; } else { cur = cur->next; } } head = dummyHead->next; delete dummyHead; return head; } };
哈希表
map
1. 两数之和
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> res; unordered_map<int, int> hash; for (int i = 0; i < nums.size(); i++) { if(hash.find(target-nums[i]!=hash.end()){ res.push_back(hash[target - nums[i]])); res.push_back(i); return res; } hash[nums[i]]=i; } return res; } };
字符串
KMP
28. 实现 strStr()
class Solution { public: void getNext(int* next, const string& s) { int j = -1; next[0] = j; for(int i = 1; i < s.size(); i++) { // 注意i从1开始 while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了 j = next[j]; // 向前回退 } if (s[i] == s[j + 1]) { // 找到相同的前后缀 j++; } next[i] = j; // 将j(前缀的长度)赋给next[i] } } int strStr(string haystack, string needle) { if (needle.size() == 0) { return 0; } int next[needle.size()]; getNext(next, needle); int j = -1; // // 因为next数组里记录的起始位置为-1 for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始 while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配 j = next[j]; // j 寻找之前匹配的位置 } if (haystack[i] == needle[j + 1]) { // 匹配,j和i同时向后移动 j++; // i的增加在for循环里 } if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t return (i - needle.size() + 1); } } return -1; } };
栈与队列
堆
347.前 K 个高频元素
// 时间复杂度:O(nlogk) // 空间复杂度:O(n) class Solution { public: // 小顶堆 class mycomparison { public: bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) { return lhs.second > rhs.second; } }; vector<int> topKFrequent(vector<int>& nums, int k) { // 要统计元素出现频率 unordered_map<int, int> map; // map<nums[i],对应出现的次数> for (int i = 0; i < nums.size(); i++) { map[nums[i]]++; } // 对频率排序 // 定义一个小顶堆,大小为k priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pri_que; // 用固定大小为k的小顶堆,扫面所有频率的数值 for (unordered_map<int, int>::iterator it = map.begin(); it != map.end(); it++) { pri_que.push(*it); if (pri_que.size() > k) { // 如果堆的大小大于了K,则队列弹出,保证堆的大小一直为k pri_que.pop(); } } // 找出前K个高频元素,因为小顶堆先弹出的是最小的,所以倒序来输出到数组 vector<int> result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pri_que.top().first; pri_que.pop(); } return result; } };
二叉树
递归
class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root == NULL) return root; swap(root->left, root->right); // 中 invertTree(root->left); // 左 invertTree(root->right); // 右 return root; } };
回溯算法
排列问题
46.全排列
class Solution { public: vector<vector<int>> result; vector<int> path; void backtracking (vector<int>& nums, vector<bool>& used) { // 此时说明找到了一组 if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i] == true) continue; // path里已经收录的元素,直接跳过 used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } vector<vector<int>> permute(vector<int>& nums) { result.clear(); path.clear(); vector<bool> used(nums.size(), false); backtracking(nums, used); return result; } };
贪心算法
最大和连续子数组
53. 最大子序和
class Solution { public: int maxSubArray(vector<int>& nums) { int result = INT32_MIN; int count = 0; for (int i = 0; i < nums.size(); i++) { count += nums[i]; if (count > result) { // 取区间累计的最大值(相当于不断确定最大子序终止位置) result = count; } if (count <= 0) count = 0; // 相当于重置最大子序起始位置,因为遇到负数一定是拉低总和 } return result; } };
动态规划
递推公式
122.买卖股票的最佳时机II
class Solution { public: int maxProfit(vector<int>& prices) { int len = prices.size(); vector<vector<int>> dp(len, vector<int>(2, 0)); dp[0][0] -= prices[0]; dp[0][1] = 0; for (int i = 1; i < len; i++) { dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。 dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]); } return dp[len - 1][1]; } };
单调栈
栈头到栈底递增
739. 每日温度
class Solution { public: vector<int> dailyTemperatures(vector<int>& T) { // 递增栈 stack<int> st; vector<int> result(T.size(), 0); st.push(0); for (int i = 1; i < T.size(); i++) { if (T[i] < T[st.top()]) { // 情况一 st.push(i); } else if (T[i] == T[st.top()]) { // 情况二 st.push(i); } else { while (!st.empty() && T[i] > T[st.top()]) { // 情况三 result[st.top()] = i - st.top(); st.pop(); } st.push(i); } } return result; } };
图论
深度优先遍历
200. 岛屿数量
- Author:Francis
- URL:https://deqiang.wang/article/leetcode
- Copyright:All articles in this blog, except for special statements, adopt BY-NC-SA agreement. Please indicate the source!