共 29 篇文章
传送门 思路 往位运算想就是想复杂了。根据题目意思，perm[i]的范围是[1,n]，且每个perm[i]不重复。这就意味着perm[0]^perm[1]^...^perm[n]是已知的。 假设： perm=[a,b,c,d,e]，encoded=[f,g,h,i]; 显然有： f = a^b; g = b^c; h = c^d; i = d^e; 我们再设已知的perm[0]^perm[1]^...^perm[n]=k，根据异或的性质：一个数异或自己得到0，任意一个数异或0等于它自己。所以我们可以用k去异或g = b^c与i = d^e来让k==a，这样我们就算出了perm[0]。再根据递推关系perm[i+1] = perm[i]^encoded[i]就可以算出整个perm。 代码 class Solution { public: vector<int> decode(vector<int>& encoded) { vector<int> perm; int a = 0; const …
传送门 思路 题目是很标准的“找到最大或最小”，也就是说假设正解为ans，(-∞,ans)范围内都无法满足题设条件，而[ans,+∞)都能满足要求，且ans是满足要求的值中最小的那个，这样ans就是一个“合法与非法”的分割点。对于形如这样的题设，就可以对答案序列进行二分来在一个较优的复杂度内枚举到答案。 就本体内容具体地看，天数显然就是我们二分的目标。枚举的左边界是0，右边界是bloomDay中最大值，这是显然地。 每次获取一个mid，然后去检查这个天数mid能否满足要求。如果可以的话，说明mid落在了[ans,+∞)范围内，令r=mid，继续； 如果不可以满足要求，那么说明mid落在了(-∞,ans) 范围内，令l=mid+1，缩小范围继续查找。 值得一提的是，与传统的二分不同，我们在缩小右边界时并非是r=mid-1，这是因为答案区间[ans,+∞)是左闭右开的，是可能存在r==ans的，如果这时还去-1，就会导致答案错误。 代码 ```cpp class Solution { public: int minDays(vector& bloomDay, int m, int k) { const int n = bloomDay.size(); if (m * k > n) return -1; vector flag(n); int l = 0, r = *max_element(bloomDay.begin(), bloomDay.end()); …
传送门 思路 题目读完，很容易想到DFS的思路，很快就可以撸一个标准的dfs解法： ```cpp class Solution { public: int ans = INT_MAX; int minimumTimeRequired(vector& jobs, int k) { vector works(k); const int n = jobs.size(); dfs(0, works, jobs, 0, n, k); return ans; } void dfs(int now, vector& w, vector& j, int maxn, int n, …
传送门 思路 记录这道题主要是为了记录二位前缀和的做题思路，毕竟CSP都遇见现题了，当时还只过了8个点... 其实前缀和也是一种形式的dp，这里借用LeetCode-304官方题解的图片，它画得很清晰了 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2021/04/1614650837-SAIiWg-1-1024x576.png 我们设dp[i][j]表示从矩阵左上角(0,0)到当前位置(i,j)的所有值之和，则不难得出图中的转移方程。减去dp[i-1][j-1]的原因是它在计算dp[i][j-1]+dp[i-1][j]中被计算了两次，要减掉多余的那一次。 这种思路在LeetCode周赛#225的T3中也有体现。 当我们对所有的(i,j)都算出前缀和后，用四重循环去依次枚举每一对左上角与右下角就行了。虽然纸面复杂度有O(n²* m²)，但每一个右下角一定在左下角后面，所以对右下角的枚举并没有严格的平方级复杂度，所以还是能把题混过去的。 代码 ```cpp int sum[110][110]; class Solution { public: int maxSumSubmatrix(vector>& mat, int k) { int m = mat.size(), n = mat[0].size(); for(int i = 1; i <= m; …
传送门 拿到这题第一思路肯定是n³直接暴，但肯定会超时，事实上定一动二的n²都能超，那么根据传统优化思路，只枚举一个就行。 根据枚举位置的不同，有两种不一样的思路。 方法一：有序集合(枚举k) 思路 枚举j，即寻找一个满足“i<j<k且nums[i]<nums[k]<nums[j]”的j。因为最左侧的i同时满足下标最小与值最小，所以可以用一个变量来记录当前最小值，也就省去了枚举i的开销。 在这同时，用一个有序集合来维护自当前枚举的位置到nums尾部的序列，它的作用是从其中找k。 在枚举时，没枚举到一个j，就从该有序集合中找到“第一个大于nums[i](也就是上文提到过的'当前最小值')的值”，根据贪心思想，它就最可能是满足条件的k。如果此时的nums[j]大于该值，则可以直接返回true；否则维护nums[i]的最小性，维护该有序集合的长度，再进行下一轮枚举，直到尾部。 代码 ```cpp class Solution { public: bool find132pattern(vector& nums) { // 左区间最小值 int left = nums[0]; // 右区间序列 multiset right; const int n = nums.size(); if (n < 3) { return false; } // 右维护 for …
传送门 思路 这题其实挺基础的，开这篇博文也只是为了记录一下该类“异型遍历”题型的套路，主要就是突出一个代码清晰逻辑明确。 代码 ```cpp class Solution { public: vector spiralOrder(vector>& matrix) { vector ans; int left = 0; int right = matrix[0].size() - 1; int top = 0; int bottom = matrix.size() - 1; int area = matrix.size() * matrix[0].size(); // 一圈一圈向内收 while (area …
传送门 思路 最粗暴的方法就是O(n²)，这题也没卡暴力，可以击败5%混过去，但可以用单调栈来优化。 众所周知，单调栈致力于解决“寻找首个大于(小于)当前位置的值”，要明白单调栈的优势，就要搞清楚它的原理。 常规方法慢在挨个枚举，对每个元素都去一个个的找满足条件的值，那自然是慢的。如果说暴力的思路是“用每个值去找答案”，那单调栈的思路可以形象地理解为“让答案自己去找值”。 就本题而言，单调栈中存的是还没有找到答案的下标，他们自底向上严格上升。在遍历中，如果当前栈顶下标对应的值比nums[i]小，那么nums[i]就是当前值答案，将nums[i]计入ans中并弹出当前下标即完成一次操作。 这样做的正确性是显然地，因为有栈的后入先出特性做保证，当前nums[i]一定最有可能是栈顶元素的答案。 更具体地，因为这题是循环数组，所以需要遍历两次，初始化ans数组为全-1就可以避免最后再来为栈内未出栈的元素赋-1的操作。 代码 ```cpp class Solution { public: vector nextGreaterElements(vector& nums) { const int n = nums.size(); stack stk; vector ans(n, -1); stk.push(0); for (int i = 0; i < n; i++) { while(!stk.empty() && nums[stk.top()] < nums[i]) { …
传送门 思路 这是一道hard题，但感觉并不是很hard。 题目要求一个无向图在保证其连通性下能删除的最大边数。那么用并查集的思想，可以理解为“给一个n个节点的图添加数量最少的无向边使其连通。” 为Alice和Bob两人各单独维护一个并查集，挨个加入每条边。如果当前边的两个顶点已经连通了，那么这个边就是一个多余边，直接计数器++。 值得注意的是，添加边的时候应该优先考虑type3的边，即公共边。因为公共边是共用的，考虑一种极端情况：对于同一个图，图中仅有type1、2边与仅有type3边。 因为对于每一个人，都要确保图的连通性，所以前者情况下，边数需要2*n=2n条，因为私有边不能公用；而后者情况下仅需要n条边，因为type3的边可以共用。以这个极端例子可以讨论在添加边的时候公有边优先级更高。 考虑非法状态，如果题目所给图对于二人中至少一人是非连通的，那么显然应该返回-1。 代码 ```cpp class Disjoint { private: unordered_map father; unordered_map rank; public: int cnt; void init(int n) { cnt = n; for (int i = 0; i < n; i++) { rank[i] = 1; father[i] = …
传送门 思路 力扣这个月的daily哟，已经变成了并查集的形状了。 题意很裸，本质上就是求联通分量的个数，和LeetCode每日一题：移除最多的同行或同列石头很像。两个连通分量相接通需要1条边，n个就需要n-1条边，求这个n并返回n-1作为答案就行了。 根据题设，显然有connections.size() < n-1时，返回-1. 代码 ```cpp class Solution { private: unordered_map father; unordered_map rank; public: int cnt; void init(int n) { cnt = n; for (int i = 0; i < n; i++) { rank[i] …
传送门 思路 题意挺简单的，就是在一个直角坐标系内给出若干点，求一个最小生成树，可以用prim直接写，也可以建图用 并查集维护边集再Kruskal。二者的介绍详见博客：最小生成树--Prim算法&Kruskal算法。 代码 prim ```cpp class Solution { public: int minCostConnectPoints(vector>& points) { const int n = points.size(); int ans = 0, mp[1005][1005], dis[1005]; bool flag[1005]={0}; memset(dis, 0x3f, sizeof(dis)); for (int i = 0; i < n; i++){ for (int j = …
传送门 思路 可以把所有在同一行和同一列的石子连起来，这样就能构成若干个连通分量。而根据题意，不难想到每一个连通分量最后都能删到只剩一颗石子，所以答案显然就是石子总数减去连通分量的个数。 用并查集来维护连通关系。 代码 第一种是最直接的O(n²)连图。 ```cpp class Solution { private: unordered_map father; unordered_map rank; public: int cnt; void init(int n) { cnt = n; for(int i = 0; i < n; i++) { father[i] = i; rank[i] = 1; } } int …
法1：hash 思路 很简单的思路，用一个hash表，键为字符，值为一个pair，pair的first成员存字符的出现次数，second成员为该字符的下标，维护一个下标最小值为答案即可。 代码 ```cpp class Solution { public: int firstUniqChar(string s) { unordered_map> mp; for(int i = 0; i < s.size(); i++) { mp[s[i]].first++; mp[s[i]].second = i; } int pos = INT_MAX; for(auto el: mp) { if((el.second).first == 1) { pos = min(pos, (el.second).second); } } return …
传送门 思路 很标准的dp。设dp[i]为当前状态下最小花费，因为可以一次爬一步或者一次爬两步，所以dp[i]=min(dp[i-1], dp[i-2])+cost[i]。又因为可以从第0级或第1级台阶开始爬，所以初始状态为dp[0]=cost[0],dp[1]=cost[1]。 值得注意的是，这题判断到达终点的条件并不是走到最后一级(cost.size()-1)，你直接跨过去也算，也就是说在倒数第二级台阶上时你直接上两级也算为上到顶(或者理解为最后一级台阶之后还有一级无消耗的台阶)，即第一组样例给出的情况。对于这种特殊情况，我们手动给cost数组pushback一个0就行了。 代码 ```cpp class Solution { public: int minCostClimbingStairs(vector& cost) { int dp[1010]; cost.push_back(0); dp[0] = cost[0], dp[1] = cost[1]; for(int i = 2; i < cost.size(); i++) { dp[i] = min(dp[i-1], dp[i-2]) + cost[i]; } return dp[cost.size() - 1]; } …
传送门 题目意思很好理解，就是维护一个单调栈。 ```cpp class Solution { public: vector mostCompetitive(vector& nums, int k) { int n = nums.size(); if(k == n) return nums; stack st; for(int i = 0; i < n; i++) { while(!st.empty() && st.top() > nums[i] && k - st.size() < n - …
传送门 题目描述 给定一个起始单词，一个目标单词与一个备选字典，通过以下规则将起始单词变到目标单词去： 每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。 求最短变化步数。 思路 看到最短步数，首先想到BFS。但使用BFS的前提是有一个可以用来搜索的图或者树，于是思维转向如何建立图/树。 思路还是很清晰的：任何两个只差一个字母的单词之间可以连成一条无向边，所有的边共同构成整张单词图。建成图后再判断endWord是否在图中就行了。真正复杂的地方在实现。 单个的字符串并不好节点化，我们可以把每个单词映射为一个id值，然后用一个int的邻接矩阵来存储整个词图。 对于添加边的操作，朴素思路枚举每一对单词，判断它们之间是否可以存在一条边，如果是，则将其加入词图，但这样显然太慢了。 可以考虑构造间接节点。假设当前单词为hit，那么显然地，_it、h_t、hi_三个长相的单词都可以与hit连成一条边。那么我们只需要构造出这三个间接节点，然后将当前单词连在间接节点上就行了。不难得知，每一个可以与hit连边的单词都一定会连向这三个间接节点。 值得注意的是，这样的操作虽然节省了时间，但人为的增加了一些“不需要的边”。假设有两个相邻单词，他们原来可以直达彼此，现在需要通过间接节点来访问，所以说真实的步数应该等于当前步数/2。又因为初始化时会将beginWord也加入词图，所以最后的总步数还得额外的+1。 代码 ```cpp class Solution { public: unordered_map wordId; vector> mp; int idNum = 0; void addWord(string& str) { if(!wordId.count(str)) { wordId[str] = idNum++; mp.emplace_back(); } } void addEdge(string& …
传送门 二叉搜索树是一颗特殊的二叉树，它满足以下条件： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左右子树也都是二叉搜索树 显然这是一个递归定义，而且不难想到，对于同样一组数据，它们转化得到的二叉搜索树是不唯一的。树的长相取决于根节点的值以及左右子树的取值。 但是一颗太过于畸形的二叉搜索树会给查找带来很高的时间复杂度，所以我们定义了平衡二叉搜索树。它的定义与二叉搜索树稍有不同： 若左子树非空，则左子树所有节点的值一定小于根节点若右子树非空，则右子树所有节点的值一定大于等于根节点左子树与右子树的高度差的绝对值小于等于1左右子树也都是平衡二叉搜索树 同时定义平衡因子为节点左子树与右子树深度之差。 那么看回这道题。题目要求构建一颗高度平衡的二叉搜索树，那么不难想到做法：取序列的中间值为根，其左右两边的数据为左右子，递归执行上述操作。这种做法的正确性是显然地，详见这里。那么代码就不难写了。 ```cpp /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), …
传送门 一个栈作为数据存储空间，另建一个辅助栈。每个入队的新元素就插入在存储栈的栈尾。每次删除就将存储栈里的元素依次弹出并压入辅助栈，操作结束后返回辅助栈栈顶元素作为答案，然后再依次将元素弹回存储栈。 ```cpp class CQueue { public: stack s1; stack s2; CQueue() { while (!s1.empty()) s1.pop(); while (!s2.empty()) s2.pop(); } void appendTail(int value) { s1.push(value); } int deleteHead() { if(s1.empty()) return -1; while(!s1.empty()) { s2.push(s1.top()); s1.pop(); } int tmp = s2.top(); s2.pop(); while(!s2.empty()) { s1.push(s2.top()); …
传送门 题目要求在一个无序数组中找到第K大的元素，不能使用排序。 最开始的想法是借用冒泡的思想两重循环去枚举，但是显然会超时，于是想到了二叉堆。 题目要求输出第K大，那么只需要在原数组上构建一个二叉堆，然后执行k-1次删除操作，堆顶即使答案。 ```cpp class Solution { public: void update(vector& arr, int i, int maxSize) { int maxn = i; int left = i * 2 + 1; int right = i * 2 + 2; if (left < …
传送门 这题很巧妙的。 题意是这样的：一个长度为n的nums数组，在自然状态下这个数组内的成员应该是(1,2,3,...,n)，但现在这个数组被打乱并拿走了一些数，我们要做的就是找出nums中缺失的第一个正数。 题目要求时间复杂度O(n)，空间复杂度O(1)。 这是一道hard，刚刚拿到手的时候挺懵的，在查阅大佬题解后了解到了一种“hash碰撞法”，以下做思路转述。 首先，合法的元素应该∈[1,n]，所以非正数成员直接标记为非法。第一次遍历，对于每个合法的成员，我们把它与自己位置上当前的元素做交换。第二次遍历去找出第一个与自己下标不相等的成员，答案就是这个下标。如果遍历到尾都没找到这样的成员，则答案为n+1。 上述思路的正确性是显然地，因为它严谨地把每一个成员放到自己应该在的下标上了，如果出现下标与值不等的情况，说明数组中缺失了这个成员。那么我们所找到的第一个缺失的成员自然就是符合题意的答案。 不难分析出这个算法的时间复杂度是线性的，也符合要求。 ```cpp class Solution { public: int firstMissingPositive(vector& nums) { for (int i = 0; i < nums.size(); i++) { if (nums[i] != i+1) { while (0 < nums[i] && nums[i] <= nums.size() && nums[nums[i]-1] …
传送门 思路：简单的链表去重，用一个set保存已有数据，每一步检测当前val是否出现过，未出现过就入集合，出现过就删除它。 ```cpp class Solution { public: ListNode* removeDuplicateNodes(ListNode* head) { if (head == nullptr) return head; unordered_set s = {head->val}; ListNode* p = head; while (p->next != nullptr) { ListNode* cur = p->next; if (!s.count(cur->val)) { s.insert(cur->val); p = p->next; } else { p->next …
传送门 LC的daily真是越来越骚了，本来打算写一个O(n3)T了后再来优化，结果居然过了，虽然击败感人... ```cpp //时间击败6.58% //空间击败7.14% class Solution { public: int threeSumClosest(vector& nums, int target) { int n = nums.size(); int minn = INT_MAX; int ans; for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) for(int k = 0; …
传送门 给出一个英文句子，要求判断它是否是回文串。判断时忽略大小写、标点以及空格，同时空字符串视为回文串。 我的思路是O(n)扫过去清掉标点和空格并统一大小写，然后翻转字符串判断它与初始字符串是否相等。确实可以A但是时间复杂度惨不忍睹，感觉可以优化到O(1)，学习后会更新。 ```cpp class Solution { public: bool isPalindrome(string s) { string str = ""; int n = s.size(); for(int i = 0; i < n; i++) if(isalpha(s[i])) str += tolower(s[i]); else if(isdigit(s[i])) str += s[i]; string str1 = str; reverse(str1.begin(), str1.end()); return str1 …
传送门 题目要求要从一组数据中找出两个值之和减去下标差最大的数。 看到这个题目，瞟一下范围，50000的范围可以尝试一下暴力： ```cpp class Solution { public: int maxScoreSightseeingPair(vector& A) { int n = A.size(); int ans = -1; for(int i = 0; i < n-1; i++) for(int j = i+1; j < n; j++) { int tmp = A[i] + A[j] + i …
传送门→ 很经典的DP。设dp[i]为走到第i级台阶的总方案数，那么显然可以得到状态转移方程：dp[i]=dp[i-1]+dp[i-2]。因为每一步能走一级或者两级台阶。 初始化dp[1]=1,dp[2]=2，然后跑循环就行了。 ```cpp class Solution { public: int climbStairs(int n) { int dp[100]; dp[1] = 1; dp[2] = 2; for(int i = 3; i <= n; i++) dp[i] = dp[i-1] + dp[i-2]; return dp[n]; } }; ```
传送门→ 很经典的题目，这里贴出一个简单地通用思路。 考虑折半这个串，比较折半后的两个串是否相等即可。 ```cpp class Solution { public: bool isPalindrome(int x) { if(x < 0 || (x % 10 == 0 && x != 0)) return false; int p = 0; while(x > p) { p = p * 10 + x % 10; x …
传送门 题面挺直接的，让人第一眼看到就想用hash。但它有不让开额外的空间，所以第一时间还硬是没想出来这么做。后来看了讨论，发觉还是自己知识学的不够活啊。 这里的解法是利用位运算中的异或运算。异或具有以下特性：任意一个数与0异或还是原来的数、任意一个数与自己异或得到的一定是0。并且异或满足常规的计算率，即存在交换律。 那么对于题目给出的一串数字nums，只需要计算整个数组的异或，最后得到的就一定是那个单独的数。 ```cpp class Solution { public: int singleNumber(vector& nums) { int res = 0; for(int i : nums) res ^= i; return res; } }; ```
传送门→ 就是实现一个能在常数时间内返回最小值的栈。根据常规思维，减少时间开销的代价一般都是增大空间开销，所以往这个方向去思考。因为栈可能随时都在弹出元素，所以单纯的用一个变量去维护最小值是不够的，这里可以用另一个栈来辅助。 单独设置一个栈mini用以保存当前栈顶元素进栈时的最小值，即每一个新元素进站时从此元素与当前mini栈顶元素中得到较小值，在x进栈的同时将这个最小值压入mini栈。这样mini栈顶就一定是当前栈内的最小值。 ```cpp class MinStack { protected: vector data; vector mini; public: /** initialize your data structure here. */ MinStack() { mini.push_back(INT_MAX); } void push(int x) { int tmp = min(mini.back(), x); data.push_back(x); mini.push_back(tmp); } void pop() { if(data.empty()) return; data.pop_back(); mini.pop_back(); } int …
传送门→ 据说是高频面试题。 大意是不用sqrt去实现开平方根计算，小数向下取整。 pow做法 第一想法是用pow函数，众所周知开平方＝½次方： ```cpp class Solution { public: int mySqrt(int x) { int ans = pow(x, 1.0/2); return ans; } }; ``` 过是过了，但是时间复杂度很高，仅击败36%。于是开始学习更先进的算法。 对数做法 还有一种算法是利用自然对数的换底公式来计算。 $$ \sqrt{x} = x^ \frac{1}{2} = e^ \ln x \frac{1}{2} $$ ```cpp class Solution { public: …
传送门 这题还是一道贪心。（最近LC很喜欢出贪心啊）因为nums[i]表示在第i个位置时每一步能向前走0~nums[i]的长度，所以若每一步都走的尽量远，最后到达终点时消耗的步数一定最短。（如果这题改成在i位置时只能走nums[i]长度那就变成一道dp了）所以对于每一步，我们都去选择能够到的最远位置。 在具体实现的时候选择一个循环从左向右遍历。维护一个maxpos值表示当前这个位置能走到的最远位置，并把它更新为边界。当走到边界的时候step++表示走了一步，然后继续更新边界。 值得一提的是，遍历过程仅访问0~n-1个元素，因为在跳到最后一个位置前，border值肯定是大于等于n的，不然就不符合题中“ 总是可以到达数组的最后一个位置”的设定了。如果border==n，step会多加一次。 ```cpp class Solution { public: int jump(vector& nums) { int maxpos = 0, border = 0, step = 0; int n = nums.size(); for (int i = 0; i < n - 1; i++) { if (maxpos >= i)//还没走到边界 { …