everlasting_lxy-CSDN博客

原创 leetcode131. 分割回文串

1、题目 https://leetcode-cn.com/problems/palindrome-partitioning/submissions/ 2、题意题解1：爆搜+特判 class Solution { public: vector<vector<string>> res; vector<string> t; void dfs(string &s,int cnt) { if(cnt==s.size())

2020-11-30 21:19:09 121

原创 leetcode283移动零

1、题目 https://leetcode-cn.com/problems/peeking-iterator/ 2、题意题解1：将非0的数放在数组前面后面的数全部置于0即可 class Solution { public: void moveZeroes(vector<int>& nums) { int j = 0; for(auto &x:nums) if(x) nums[j+

2020-11-19 23:18:10 97

原创第七届蓝桥杯决赛真题凑平方数

把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。比如：0, 36, 5948721 再比如： 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等… 注意，0可以作为独立的数字，但不能作为多位数字的开始。分组时，必须用完所有的数字，不能重复，不能遗漏。如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？注意：需要提交的是一个整数，不要填写多余内容。思路:全排列+dfs dfs按升序记录结果(pre记录上一个数) 出现0的情况表

2020-11-09 01:37:52 146

原创第六届蓝桥杯决赛真题 -居民集会

蓝桥村的居民都生活在一条公路的边上，公路的长度为L，每户家庭的位置都用这户家庭到公路的起点的距离来计算，第i户家庭距起点的距离为di。每年，蓝桥村都要举行一次集会。今年，由于村里的人口太多，村委会决定要在4个地方举行集会，其中3个位于公路中间，1个位最公路的终点。已知每户家庭都会向着远离公路起点的方向去参加集会，参加集会的路程开销为家庭内的人数ti与距离的乘积。给定每户家庭的位置di和人数ti，请为村委会寻找最好的集会举办地：p1, p2, p3, p4 (p1<=p2<=p3<=p4=L

2020-11-09 01:09:11 389

原创 leetcode108. 将有序数组转换为二叉搜索树

1、题目 https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/submissions/ 2、题意题解1：dfs /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x)

2020-09-24 18:52:42 47

原创 leetcode684. 冗余连接

1、题目 https://leetcode-cn.com/problems/redundant-connection/submissions/ 2、题意题解1：并查集当前两个节点为一个集合时说明有环返回这两个结果，否则合并p[a] = b; class Solution { public: vector<int> p; int find(int x) { return x==p[x]?x:p[x] = find(p[x]); } ve

2020-09-23 20:32:55 46

原创 leetcode990. 等式方程的可满足性

1、题目 https://leetcode-cn.com/problems/satisfiability-of-equality-equations/ 2、题意题解1：并查集将a-z当做0-25表示; 将相等的合并为一个集合; 将不相等的判断时否为一个集合即find(a)==find(b);相等则等式不成立 class Solution { public: vector<int> p; int find(int x) { return x==p[x]

2020-09-23 20:01:58 51

原创 leetcode547. 朋友圈

1、题目 https://leetcode-cn.com/problems/friend-circles/ 2、题意题解1：dfs 当前这个同学不在一个朋友圈内的话,将这一行与他为朋友的和与他朋友的朋友标记为一个朋友圈;res++; 返回res即可。 class Solution { public: vector<bool> st; int findCircleNum(vector<vector<int>>& M) { int m

2020-09-23 19:42:38 230

原创 leetcode974. 和可被 K 整除的子数组

1、题目 https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/ 2、题意题解1：前缀和+哈希表和leetcode560类似 class Solution { public: int subarraysDivByK(vector<int>& A, int k) { unordered_map<int, int> m; m[0] = 1; long

2020-09-22 18:54:38 50

原创 leetcode560. 和为K的子数组

1、题目 https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/dai-ni-da-tong-qian-zhui-he-cong-zui-ben-fang-fa-y/ 2、题意题解1：前缀和+哈希表 class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int,int&gt

2020-09-22 18:27:15 53

原创 leetcode637. 二叉树的层平均值

1、题目 https://leetcode-cn.com/problems/average-of-levels-in-binary-tree/submissions/ 2、题意题解1：bfs /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x),

2020-09-12 20:19:04 61

原创 leetcode136. 只出现一次的数字

1、题目 https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/ 2、题意题解1:异或所有数字最后剩下的就是结果 class Solution { public: int singleNumber(vector<int>& nums) { int res=0; for(auto x : nums) res^=x; return res; } }; ...

2020-09-11 00:28:44 40

原创 leetcode216. 组合总和 III

1、题目 https://leetcode-cn.com/problems/combination-sum-iii/ 2、题意题解1：递归回溯和组合总和12类似 class Solution { public: vector<vector<int>> res; vector<int> path; void dfs(int start,int k,int tar) { if(k==0&&tar==0)

2020-09-11 00:20:56 57

原创 leetcode129. 求根到叶子节点数字之和

1、题目 https://leetcode-cn.com/problems/sum-root-to-leaf-numbers/ 2、题意题解1:递归每次到底层更新结果 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL),

2020-09-10 15:38:34 55

原创 leetcode128. 最长连续序列

1、题目 https://leetcode-cn.com/problems/longest-consecutive-sequence/ 2、题意题解1:hash表当当前该数前面没有元素时判断从这个数开始往后连续的最大个数每一次删除在set中的这一段连续的数 class Solution { public: int longestConsecutive(vector<int>& nums) { int res = 0; unordered_s

2020-09-10 15:25:46 50

原创 leetcode124. 二叉树中的最大路径和

1、题目 https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/submissions/ 2、题意题解1：递归 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(

2020-09-10 15:04:51 40

原创 leetcode123. 买卖股票的最佳时机 III

1、题目 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/ 2、题意题解1：线性扫描(On) 维护f[i]数组表示购买一次所能组成的最大值； res初始化为f[n-1](表示只买一次的最大值)；从后往前遍历维护一个从后往前的最大值maxv 当当前数值<maxv更新res = res = max(res,maxv-prices[i]+f[i-1]);（表示只买卖一次且是第天买入的最大值); /* */ cla

2020-09-09 00:13:35 58

原创 leetcode257. 二叉树的所有路径

1、题目 https://leetcode-cn.com/problems/binary-tree-paths/ 2、题意题解1：dfs /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {}

2020-09-04 10:26:40 46

原创 leetcode841. 钥匙和房间

1、题目 https://leetcode-cn.com/problems/keys-and-rooms/ 2、题意题解1：dfs class Solution { public: void dfs(vector<vector<int>>& rooms,int house,vector<bool>&st) { st[house] = true; for(int j=0;j<rooms[house

2020-08-31 07:32:14 101

原创 leetcode459. 重复的子字符串

1、题目 https://leetcode-cn.com/problems/repeated-substring-pattern/ 2、题意题解1：枚举 class Solution { public: bool repeatedSubstringPattern(string s) { int n = s.size(),j; s = " "+s; for(int i=1;i<=n/2;i++) { if(

2020-08-24 05:58:19 124 1

原创 leetcode122. 买卖股票的最佳时机 II

1、题目 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/ 2、题意题解1：贪心 class Solution { public: int maxProfit(vector<int>& prices) { int res = 0; for(int i=1;i<prices.size();i++) res+=max(0,prices

2020-08-23 06:53:23 67

原创 leetcode201. 数字范围按位与

1、题目 https://leetcode-cn.com/problems/bitwise-and-of-numbers-range/ 2、题意题解1：位运算二进制从最高位开始相等并且为1 将当前这位加到结果，不相等说明从这一位开始往后无法增加结果 break； class Solution { public: int rangeBitwiseAnd(int m, int n) { int res = 0; for (int i = 30; i >= 0;

2020-08-23 06:18:25 52

原创 leetcode679. 24 点游戏

1、题目 https://leetcode-cn.com/problems/24-game/submissions/ 2、题意题解1：dfs+回溯除法有可能为小数每次选两个数nums[i]和nums[j]，枚举所有情况(除法的时候要保证被除数不为0),遍历所有情况(删除nums[i]和nums[j]并加上一个这两个数能构成的一种情况); 当nums.size()=1时判断nums[0]-24的绝对值是否<1e-5 是的话则有解; class Solution { public: boo

2020-08-22 17:34:37 91

原创 leetcode529. 扫雷游戏

1、题目 https://leetcode-cn.com/problems/minesweeper/ 2、题意题解1：dfs 当前这个格子’E’若为’B’说明周围8个格子没有雷,继续搜索它其它八个格子为’E’的格子 (若为数字则说明有雷则不用扩散) class Solution { public: vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<

2020-08-20 02:40:32 92

原创 leetcode121. 买卖股票的最佳时机

1、题目 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/ 2、题意题解1：维护最小买入的价格更新结果的最大值 class Solution { public: int maxProfit(vector<int>& prices) { int res = 0,start = INT_MAX; for(int i =0;i<prices.size();i++)

2020-08-17 17:35:31 44

原创 leetcode120. 三角形最小路径和

1、题目 https://leetcode-cn.com/problems/triangle/ 2、题意题解1： class Solution { public: int minimumTotal(vector<vector<int>>& f) { for (int i = f.size() - 2; i >= 0; i -- ) for (int j = 0; j <= i; j ++ )

2020-08-17 17:26:13 34

原创 leetcode119. 杨辉三角 II

1、题目 https://leetcode-cn.com/problems/pascals-triangle-ii/submissions/ 2、题意题解1： class Solution { public: vector<int> getRow(int rowIndex) { vector<vector<int>> f; for (int i = 0; i <=rowIndex; i ++ ) {

2020-08-17 17:23:47 54

原创 leetcode118. 杨辉三角

1、题目 https://leetcode-cn.com/problems/pascals-triangle/ 2、题意题解1： class Solution { public: vector<vector<int>> generate(int n) { vector<vector<int>> f; for (int i = 0; i < n; i ++ ) { vector<int

2020-08-17 17:19:03 45

原创 leetcode98. 验证二叉搜索树

1、题目 https://leetcode-cn.com/problems/validate-binary-search-tree/submissions/ 2、题意题解1：中序遍历为升序若当前节点为>min并且<max则符合情况若递归左子树说明左边树要val则将max更新为root->val; 右子树>root->val min更新为root->val /** * Definition for a binary tree node. * struct Tree

2020-08-17 17:08:28 48

原创 leetcode96. 不同的二叉搜索树

1、题目 https://leetcode-cn.com/problems/unique-binary-search-trees/ 2、题意题解1： f[n]表示以n为跟节点二叉搜索树的个数左子树有0-(n-1)个节点右子树有(n-1)-0个节点 f[n]为所有的总合 class Solution { public: int numTrees(int n) { vector<int> f(n + 1); f[0] = 1; for

2020-08-17 16:49:49 46

原创 leetcode97. 交错字符串

1、题目 https://leetcode-cn.com/problems/interleaving-string/ 2、题意题解1：dp 做法和10正则表达式匹配 72. 编辑距离类似 f[i][j]表示s1前i个字符和s2前j个字符是否可以交错形成s3前i+j个字符 1:s1[i] == s3[i + j] f[i][j] = f[i - 1][j]; 2:s2[j] == s3[i + j] f[i][j] = f[i][j-1]; 两种情况一种为true则f[i][j] = true; c

2020-08-13 15:54:16 58

空空如也

空空如也