- 博客(148)
- 收藏
- 关注
RSS订阅原创 leetcode：1788.Maximize the Beauty of the Garden
链接：https://leetcode-cn.com/problems/maximize-the-beauty-of-the-garden/先计算一下除去负数后的前缀和，使用map记录索引即可。C++代码：class Solution {public: int maximumBeauty(vector<int>& flowers) { int n = flowers.size(); vector<int>pre_sum(n+1,
2021-04-03 10:39:10
243
原创 leetcode：10. 正则表达式匹配（动态规划）
链接：https://leetcode-cn.com/problems/regular-expression-matching/创建二维数组dpdpdp，dp[i][j]dp[i][j]dp[i][j]代表字符串s的前iii个字符和字符串p的前jjj个字符能否匹配。考虑dp[i][j]dp[i][j]dp[i][j]的状态转移方程：当p[j]p[j]p[j]为字母时，它必须等于s[i]s[i]s[i]，且dp[i−1][j−1]dp[i-1][j-1]dp[i−1][j−1]为truetruetrue
2021-02-17 22:34:41
154
原创 leetcode: 37. 解数独（回溯）
链接：https://leetcode-cn.com/problems/sudoku-solver/对于每一个空白格，判断1−91-91−9是否能填入，若有一个能填入则先填上进入下一层递归（填下一个空格），若都不能填入则回溯到上一格重新填。C++代码：class Solution {public: bool check(vector<vector<char>>& board,int row,int col, char num) { //检查能
2021-02-17 22:22:48
148
原创 leetcode: 1035. 不相交的线（动态规划）
链接：https://leetcode-cn.com/problems/uncrossed-lines/可以看做最长公共子序列问题，动态规划解决。dp[i][j]dp[i][j]dp[i][j]表示A[0,...,i]A[0,...,i]A[0,...,i]和B[0,...,j]B[0,...,j]B[0,...,j]子问题的答案。C++代码：class Solution {public: int maxUncrossedLines(vector<int>& A, vec
2021-02-07 21:56:27
157
原创 leetcode：137. 只出现一次的数字 II
链接：https://leetcode-cn.com/problems/single-number-ii/位操作，相当精妙。C++代码：class Solution {public: int singleNumber(vector<int>& nums) { int once = 0; int twice = 0; for(int i = 0;i<nums.size();i++) {
2021-02-02 21:14:23
40
原创 leetcode: 116. 填充每个节点的下一个右侧节点指针
链接：https://leetcode-cn.com/problems/populating-next-right-pointers-in-each-node/在每个节点时，更新它左右子节点的nextnextnext，充分利用已经有的nextnextnext信息。C++代码：class Solution {public: Node* connect(Node* root) { if(root==NULL||root->left == NULL)
2021-02-01 21:38:43
65
原创 leetcode: 40. 组合总和 II（回溯）
链接：https://leetcode-cn.com/problems/combination-sum-ii/这道题和全排列II类似，都是有重复元素的回溯题。比如原数组为[1,1,6,7][1,1,6,7][1,1,6,7]，目标数为8，我们要保证结果中只有一个[1,7][1,7][1,7]且含有数组[1,1,6][1,1,6][1,1,6]。因此不能简单地跳过重复元素。使用一个标志数组来表示重复元素的使用情况，若为1则表示此元素已被选中，并且进入了下一层递归，此时我们可以选用与它重复的元素（保证[1,1
2021-01-30 21:24:57
108
原创 leetcode：31. 下一个排列
链接：https://leetcode-cn.com/problems/next-permutation/这道题的重点是搞清楚如何生成下一个排列：从右至左遍历数组，找到第一个满足 a[i]<a[i+1]a[i]<a[i+1]a[i]<a[i+1]的下标iii在a[i]a[i]a[i]的右边找到比它大的最小元素，互换这两个元素将数组下标i+1i+1i+1至末尾元素倒置java代码：class Solution { public void nextPermutation
2021-01-11 21:40:44
79
原创 leetcode: 22. 括号生成（回溯）
链接：https://leetcode-cn.com/problems/generate-parentheses/使用回溯（DFS）枚举所有可能生成的情况，剪去所有左括号数量小于右括号数量的子过程。java代码：class Solution { List<String>ans = new ArrayList(); public List<String> generateParenthesis(int n) { backtrack("",0,0,n
2021-01-11 21:37:09
136
1
原创 leetcode: 925. 长按键入
链接：https://leetcode-cn.com/problems/long-pressed-name/typed 字符串中的字符共有两种情况：与 name 字符串中的字符匹配为长按键入，即与typed字符串中上一个字符相同遍历typed字符串，判断每个字符是否都是这两种情况，最后判断 name字符串中是否所有字符均已匹配。C++代码：class Solution {public: bool isLongPressedName(string name, string typed
2021-01-09 23:10:42
85
原创 leetcode: 482. 密钥格式化
链接：https://leetcode-cn.com/problems/license-key-formatting/C++代码：class Solution {public: string licenseKeyFormatting(string S, int K) { string str = ""; for(int i = 0;i<S.size();i++) { if(S[i]!='-')
2020-12-22 19:33:27
96
原创 leetcode：58. 最后一个单词的长度
链接：https://leetcode-cn.com/problems/length-of-last-word/注意题目中“不存在最后一个单词”是指字符串中没有字母。这道题的思路是先过滤字符串尾部的空格，在从后往前遍历最后一个单词直至空格（或字符串首部）。C++代码：class Solution {public: int lengthOfLastWord(string s) { int n = s.size()-1; while(n>=0&&am
2020-12-19 21:44:09
104
1
原创 leetcode: 1400. 构造 K 个回文字符串
链接：https://leetcode-cn.com/problems/construct-k-palindrome-strings/统计字符串中字母总数为奇数的字母个数，小于kkk即可。C++代码：class Solution {public: bool canConstruct(string s, int k) { if(s.size()<k) return false; vector<int> record(26
2020-08-29 12:15:04
102
原创 leetcode：1358. 包含所有三种字符的子字符串数目（滑动窗口）
链接：https://leetcode-cn.com/problems/number-of-substrings-containing-all-three-characters/滑动窗口法，保持窗口内的子串有a,b,ca,b,ca,b,c，累加滑动窗口尾部到字符串尾部的距离即可。C++代码：class Solution {public: int numberOfSubstrings(string s) { int res = 0; vector<int&
2020-08-22 12:49:53
140
原创 leetcode：1319. 连通网络的操作次数（dfs）
链接：https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/用数组记录下连通关系（注意是双向的），然后用dfs检查共有几个连通图，答案即为连通图的数量减1.C++代码：class Solution { vector<vector<int>> edges; vector<bool> used;public: int makeConnect
2020-08-15 12:18:12
138
原创 leetcode：1312. 让字符串成为回文串的最少插入次数（动态规划）
链接：https://leetcode-cn.com/problems/minimum-insertion-steps-to-make-a-string-palindrome/找出字符串中的最长回文子序列（不是子串），再用字符串长度减去这个长度就是最终结果。C++代码：class Solution {public: int minInsertions(string s) { vector<vector<int>> dp(s.size(),vector&
2020-08-15 12:16:24
181
原创 leetcode: 1310. 子数组异或查询
链接：https://leetcode-cn.com/problems/xor-queries-of-a-subarray/先计算异或前缀和，这样查询时就可以在O(1)O(1)O(1)时间复杂度得出答案。C++代码:class Solution {public: vector<int> xorQueries(vector<int>& arr, vector<vector<int>>& queries) { vec
2020-08-15 12:14:53
126
原创 leetcode：1254. 统计封闭岛屿的数目
链接：https://leetcode-cn.com/problems/number-of-closed-islands/只有在边界的岛屿才不是封闭的，用深度优先搜索解题，其中一个参数标识是否为封闭的岛屿，只有到达边界时才更新。C++代码：class Solution {public: int closedIsland(vector<vector<int>>& grid) { int res = 0; for(int i = 0
2020-08-14 15:18:00
227
原创 leetcode：1260. 二维网格迁移
链接：https://leetcode-cn.com/problems/shift-2d-grid/模拟即可。C++代码：class Solution {public: vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) { int m = grid.size(); int n = grid[0].size();
2020-08-14 12:25:22
88
原创 leetcode：1252. 奇数值单元格的数目
链接：https://leetcode-cn.com/problems/cells-with-odd-values-in-a-matrix/记录每个行与列被增加的次数，最终为奇数的个数为增加奇数次的行数∗m+增加奇数次的列数∗n−重叠的部分增加奇数次的行数*m+增加奇数次的列数*n-重叠的部分增加奇数次的行数∗m+增加奇数次的列数∗n−重叠的部分C++代码：class Solution {public: int oddCells(int n, int m, vector<vector
2020-08-13 12:07:06
95
原创 leetcode：1250. 检查「好数组」
链接：https://leetcode-cn.com/problems/check-if-it-is-a-good-array/数学题，子集的最大公约数为1即可。C++代码：class Solution {public: bool isGoodArray(vector<int>& nums) { sort(nums.begin(),nums.end()); int g = nums[0]; for(int i = 0;i&l
2020-08-13 12:04:07
114
原创 leetcode：1247. 交换字符使得字符串相同
链接：https://leetcode-cn.com/problems/minimum-swaps-to-make-strings-equal/字符串在某一位置不匹配仅有两种情况，s1s_1s1中为yyy，s2s_2s2中为xxx，或者反过来。分别记录yxyxyx与xyxyxy的出现次数，两个同类的不匹配可以通过一次交换解决，两个不同类的不匹配可以通过两次交换解决。C++代码：class Solution {public: int minimumSwap(string s1, strin
2020-08-13 12:02:12
246
原创 leetcode：1238. 循环码排列
链接：https://leetcode-cn.com/problems/circular-permutation-in-binary-representation/格雷码，即为任意两个相邻数的二进制位中仅有一位不同的编码。构造出n位的格雷码，然后做旋转使得start在数组顶部即可。C++代码：class Solution {public: vector<int> circularPermutation(int n, int start) { vector<i
2020-08-12 11:57:26
106
原创 leetcode：1221. 分割平衡字符串
链接：https://leetcode-cn.com/problems/split-a-string-in-balanced-strings/记录字符串R与L的差值，为0时即可分割。C++代码：class Solution {public: int balancedStringSplit(string s) { int temp = 0; int res = 0; for(int i = 0;i<s.size();i++)
2020-08-12 11:54:59
68
原创 leetcode：1220. 统计元音字母序列的数目
链接：https://leetcode-cn.com/problems/count-vowels-permutation/这是一道比较简单的hard题，考虑各个元音结尾时前一位可能的情况，递推即可。class Solution { public int countVowelPermutation(int n) { int dp[] = new int [5]; for(int i = 0;i<5;i++) dp[i] = 1; /
2020-08-12 11:53:50
152
原创 leetcode：1155. 掷骰子的N种方法（dp）
链接：https://leetcode-cn.com/problems/number-of-dice-rolls-with-target-sum/dp数组用于记录使用iii个骰子掷出jjj的方法数，下一层只需在上一层的基础上累加。java代码：class Solution { public int numRollsToTarget(int d, int f, int target) { int dp[][] = new int [d+1][target+1];
2020-08-11 12:11:27
187
原创 leetcode：1219. 黄金矿工（dfs）
链接：https://leetcode-cn.com/problems/path-with-maximum-gold/dfs即可，注意dfs时不能重复进入一个矿洞。C++代码：class Solution {public: int getMaximumGold(vector<vector<int>>& grid) { int res = 0; for(int i = 0;i<grid.size();i++)
2020-08-11 12:04:29
146
原创 leetcode：1190. 反转每对括号间的子串
链接：https://leetcode-cn.com/problems/reverse-substrings-between-each-pair-of-parentheses/记录左右括号的位置，使用c++的reverse函数即可。C++代码：class Solution {public: string reverseParentheses(string s) { stack<int>s1; //存放左括号的位置 string result;
2020-08-11 12:01:21
350
原创 leetcode：1147. 段式回文
链接：https://leetcode-cn.com/problems/longest-chunked-palindrome-decomposition/此题比较简单，之间暴利递归就可以了。也有双指针的解法可能更加快一点。C++代码:class Solution {public: int longestDecomposition(string text) { if(text == "") return 0; for(int i = 1;
2020-08-10 11:33:12
249
原创 leetcode：1145. 二叉树着色游戏
链接：https://leetcode-cn.com/problems/binary-tree-coloring-game/对于第一个玩家选择的xxx,第二个玩家只要三种最优选择，xxx的左右孩子与xxx的父亲，分别计算这三种选择能不能使第二个玩家必赢即可。java代码：class Solution { int leftnum = 0; int rightnum = 0; public boolean btreeGameWinningMove(TreeNode root, in
2020-08-10 11:24:06
183
原创 leetcode：1144. 递减元素使数组呈锯齿状
链接：https://leetcode-cn.com/problems/decrease-elements-to-make-array-zigzag/此题比较简单，因为只能递减元素，分两类讨论即可，选择较小的一种情况。java代码：class Solution { public int movesToMakeZigzag(int[] nums) { int sum1 = 0; for(int i = 0;i<nums.length;i+=2)
2020-08-10 11:19:12
125
原创 leetcode：1124. 表现良好的最长时间段
链接：https://leetcode-cn.com/problems/longest-well-performing-interval/将大于8的元素看做1，小于等于8的看做-1。遍历数组计算前缀和，若当前前缀和大于0，则最长时间段必为当前全部时间；若小于0，则为最前一个 当前前缀和-1 到现在。java代码：class Solution { public int longestWPI(int[] hours) { Map<Integer,Integer>map
2020-08-08 16:04:57
333
原创 leetcode：1123. 最深叶节点的最近公共祖先
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-deepest-leaves/每当到达一个节点时，计算其左右子树的深度。若相等则说明其左右子树中均存在最深叶节点，则最近公共祖先即为此节点；若不等则可直接进入较深子树。java代码：/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode
2020-08-08 15:54:19
212
原创 leetcode：1143.最长公共子序列（动态规划）
链接：https://leetcode-cn.com/problems/longest-common-subsequence/比较经典的DP问题。创建二维数组dpdpdp，dp[i][j]dp[i][j]dp[i][j]表示text(0,i)text(0,i)text(0,i)与text2(0,j)text2(0,j)text2(0,j)的最长公共子序列。转移方程为：1. 当text1[i]==text2[j]text1[i] == text2[j]text1[i]==text2[j]时，dp[i+1
2020-08-08 15:51:20
98
原创 leetcode: 1111.有效括号的嵌套深度
链接：https://leetcode-cn.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/首先理解一个小括号字符串的嵌套深度应该如何得出。假设用栈去遍历这样一个字符串，左括号直接压入栈，右括号则弹出栈顶左括号。这样这个字符串的嵌套深度实际就是所有时刻栈中元素的最大值。对于这道题，我们用贪心的方法划分字符串即可。可以记录两个子字符串当前的“栈中元素”个数，左括号划分给小的，右括号划分给大的。C++代码：clas
2020-07-30 21:10:43
84
原创 leetcode：208. 实现 Trie (前缀树)
链接：https://leetcode-cn.com/problems/implement-trie-prefix-tree/实现一个前缀树（节点），一个前缀树节点需要保存它可能的26个孩子的信息，以及这个节点是不是一个单词的结尾。C++代码：class Trie { Trie * children[26]; bool isWord = false;public: /** Initialize your data structure here. */ Trie
2020-07-01 11:46:52
104
原创 并查集博客
python版本：https://blog.csdn.net/guoziqing506/article/details/78752557C++版本：https://blog.csdn.net/qq_41593380/article/details/81146850https://zhuanlan.zhihu.com/p/93647900例题：https://blog.csdn.net/guo15331092/article/details/78702686?tdsourcetag=s_pctim
2020-06-30 17:38:30
111
原创 leetcode：547. 朋友圈（dfs）
链接：https://leetcode-cn.com/problems/friend-circles/本来想用并查集写的，但感觉dfs还是简单点。创建一个集合标记已经访问过的人，然后挨个深度搜索访问没被访问过的人。注意count++的位置。C++代码：class Solution {public: int n; set<int> s; int findCircleNum(vector<vector<int>>& M) {
2020-06-30 17:31:39
158
原创 leetcode：1090. 受标签影响的最大值（贪心）
链接：https://leetcode-cn.com/problems/largest-values-from-labels/submissions/贪心问题，label和value都按value从大到小排序，然后取满足条件的尽可能大的即可。C++代码：class Solution {public: struct pair{ int value; int label; }; int largestValsFromLabels(vector<
2020-06-29 21:29:43
128
原创 leetcode : 1072. 按列翻转得到最大值等行数
链接：https://leetcode-cn.com/problems/flip-columns-for-maximum-number-of-equal-rows/经过若干次列翻转后，如果两行能同时满足行上所有值都相等，那么在翻转之前这两行要么相等要么互反（0-1）。因此统计最多的相等或互反的行数即可。可以借助把数组转为字符串的函数以及hashmap来求解。java代码：class Solution { public int maxEqualRowsAfterFlips(int[][] mat
2020-06-28 12:11:37
162
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人