- 博客(550)
- 收藏
- 关注
RSS订阅原创 leetcode 172. 阶乘后的零
最终5的个数就是n / 5 + n / 25 + n / 125 ...public int trailingZeroes(int n) { int count = 0; while (n > 0) { count += n / 5; n = n / 5; } return count;}
2020-09-09 09:37:33
155
原创 leetcode 147. 对链表进行插入排序
classSolution{public:ListNode*insertionSortList(ListNode*head){autoone=newListNode(0);autotemp=one;for(autop=head;p!=NULL;p=temp){autoq=one;for(;q->next!=NULL&&a...
2020-09-09 09:27:48
172
原创 leetcode 148. 排序链表
/***Definitionforsingly-linkedlist.*publicclassListNode{*intval;*ListNodenext;*ListNode(intx){val=x;}*}*/classSolution{publicListNodesortList(ListNodehead){returnhead==null?h...
2020-09-09 09:21:06
168
原创 leetcode 最近公共祖先 235 236
235很简单，因为二叉搜索树的特性，如果一左一右则就是当前节点。 如果都左或者都右，则顺着递归往下走即可236普通的二叉树。法一：dfs遍历整棵树，记录所有的节点的父节点是什么。 之后root1开始放上遍历，vis记录经过的所有节点。之后root2开始遍历，碰到vis=1的即最近的父节点。法二：dfs往下找这两个节点。往左找A和B找到没（||一个即可），往右找找到没。如果左右都有即当前为公共，否则返回左/右。class Solution {public: unorde...
2020-09-08 21:26:34
117
原创 层次遍历！！
一定要注意这一点。for (int i = 1; i <= currentLevelSize; ++i) 这里代表这部分全部都是同一层的class Solution {public: vector<vector<int>> levelOrder(TreeNode* root) { vector <vector <int>> ret; if (!root) return ret; ...
2020-09-08 20:32:19
182
原创 lootcade 114. 二叉树展开为链表 链表
给定一个二叉树，原地将它展开为一个单链表。例如，给定二叉树 1 / \ 2 5/ \ \3 4 6将其展开为：1\ 2 \ 3 \ 4 \ 5 \ 6找到A的左子树最右边的那个节点，把A的右子树接到那里。在把整个左子树变为右子树。重复这个操作class Solution { public void flat...
2020-09-08 20:29:45
104
原创 leetcode 61. 旋转链表 头尾相连，移动找头后断开
给定一个链表，旋转链表，将链表每个节点向右移动k个位置，其中k是非负数。示例1:输入: 1->2->3->4->5->NULL, k = 2输出: 4->5->1->2->3->NULL解释:向右旋转 1 步: 5->1->2->3->4->NULL向右旋转 2 步: 4->5->1->2->3->NULL示例2:输入: 0->1->2->...
2020-09-08 16:37:43
127
原创 leetcode 4. 寻找两个正序数组的中位数 经典
求第k个。我们比较两个数组的（k+1）/2。如果A的小于B的，那么A左边的全部放弃，同时这个K要变为K=K-A左边/2 -1. 注意要记录A的边界值。反之同理。classSolution{public:intgetKthElement(constvector<int>&nums1,constvector<int>&nums2,intk){intm=nums1.size();...
2020-09-08 11:35:45
128
原创 LeetCode-32.最长有效括号 栈
保存的是下标，而且只保存(的。 当遇到)时，如果为(，则计算两者之间的差值即可。如果遇到)时，当前还是)，我们也放入其中，作为一个 -1的作用int longestValidParentheses(string s) { int len = s.length(); stack<int> st; st.push(-1);//放入起始点 int result = 0; for (int i=0;i<len;i++) { ...
2020-09-08 10:53:56
137
原创 leetcode 29. 两数相除 两倍相减
https://blog.csdn.net/Zolewit/article/details/9714311229. 两数相除这道题就是慢慢减，但是为了加快速度，一次减两倍的
2020-09-08 09:13:32
281
1
原创 leetcode 166. 分数到小数
https://leetcode-cn.com/problems/fraction-to-recurring-decimal/solution/fen-shu-dao-xiao-shu-by-leetcode/使用map<余数，出现次数>。 如果余数再次出现时，就代表着有重叠部分了。在左边(，最后加)classSolution{public://小数部分如果余数重复出现两次就表示该小数是循环小数了stringfractionToDecima...
2020-09-08 09:02:13
114
原创 leetcode 149. 直线上最多的点数 考虑点
给定一个二维平面，平面上有n个点，求最多有多少个点在同一条直线上。示例 1:输入: [[1,1],[2,2],[3,3]]输出: 3解释:^|| o| o| o +------------->0 1 2 3 4示例2:输入: [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]输出: 4解释:^|| o| o o| o| o o+----...
2020-09-07 21:20:46
109
原创 leetcode 54. 螺旋矩阵 模拟 常考
给定一个包含m x n个元素的矩阵（m 行, n 列），请按照顺时针螺旋顺序，返回矩阵中的所有元素。示例1:输入:[[ 1, 2, 3 ],[ 4, 5, 6 ],[ 7, 8, 9 ]]输出: [1,2,3,6,9,8,7,4,5]示例2:输入:[ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12]]输出: [1,2,3,4,8,12,11,10,9,5,6,7]https://leetcode-cn.com/pr...
2020-09-07 19:35:48
154
原创 leetcode 153. 寻找旋转排序数组中的最小值 二分
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组[0,1,2,4,5,6,7] 可能变为[4,5,6,7,0,1,2])。请找出其中最小的元素。你可以假设数组中不存在重复元素。示例 1:输入: [3,4,5,1,2]输出: 1示例 2:输入: [4,5,6,7,0,1,2]输出: 0比较中间值和右边的值。如果中间比右边大，说明最小的值被旋转到右边了移动l如果中间小，说明最小的值在左边，移动rclassSolution{p...
2020-09-07 11:11:49
127
原创 leetcode 95. 不同的二叉搜索树 II 树的 dfs
class Solution {public: vector<TreeNode*> generateTrees(int start, int end) { if (start > end) { return { nullptr }; } vector<TreeNode*> allTrees; // 枚举可行根节点 for (int i = start; i <...
2020-09-06 20:43:22
249
原创 leetcode 卡特兰数
https://www.cnblogs.com/linzhengmin/p/11298140.htmln对括号的合法配对方案书 n个节点的二叉树的形态数 n+1个叶子(n个非叶节点)的满二叉树的形态数, 走到左儿子+1,走到 右儿子-1,类似于括号匹配(大致同2) n个数入栈后出栈的排列总数 对凸n+2边形进行不同的三角形分割的方案数(分割线断点仅为顶点，且分割线仅在顶点上相交) n层的阶梯切割为n个矩形的切法数先背诵上述应用场景，然后记忆卡特兰数的前几项:1,1,2,5,14,..
2020-09-06 20:39:51
182
转载 leetcode 89. 格雷编码 规律
转载https://www.jianshu.com/p/f46debb8a3d6如果n = 1，那么编码为[0, 1]；n = 2，编码为[00, 10, 11, 01]；n = 3，编码为[000, 100, 110, 010, 011, 111, 101, 001]；所以，n级的编码的生成，是从n - 1编码的最后一个编码开始倒序遍历，每遍历一个编码，就将这个编码+1后的码字添加到结果列表的后面，然后再将这个编码+0。比如，n = 2，编码为[00, 10, 11, 01]，倒序遍历
2020-09-06 20:16:48
453
原创 leetcode 309. 最佳买卖股票时机含冷冻期 dp
给定一个整数数组，其中第i个元素代表了第i天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。示例:输入: [1,2,3,0,2]输出: 3解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]dp[第几天][是否持股]dp[i][0] = max(dp[i - ...
2020-09-06 17:30:05
102
原创 leetcode 123. 买卖股票的最佳时机 III dfs和dp
方法一：dfs(id,num,status) 分别代表第几天，交易几次，当前是否是持有。 会超时方法二：dfs优化。用hashmap存放之前的情况。key值为id，num，status的合体，value为结果。方法三：dpdp[第几天][状态][交易次数] 分各种情况讨论。https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/mai-mai-gu-piao-zui-jia-shi-ji-i.
2020-09-06 17:27:36
151
原创 leetcode 174. 地下城游戏 难DP
174. 地下城游戏难度困难366收藏分享切换为英文关注反馈一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为0），要么包含..
2020-09-06 17:12:49
101
原创 leetcode 97. 交错字符串 dp
给定三个字符串s1, s2, s3, 验证s3是否是由s1和s2 交错组成的。示例 1：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"输出：true示例2：输入：s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"输出：falsedp[i][j]表示s1的前i个和s2的前j个可以组成s3的前i+j个。dp[0][j]=dp[0][j-1]&&s2[...
2020-09-06 11:50:21
100
原创 leetcode 51. N 皇后 DFS记录状体
n皇后问题研究的是如何将 n个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。上图为 8 皇后问题的一种解法。给定一个整数 n，返回所有不同的n皇后问题的解决方案。每一种解法包含一个明确的n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。示例：输入：4输出：[[".Q..", // 解法 1 "...Q", "Q...", "..Q."],["..Q.", // 解法 2 "Q...", "....
2020-09-06 10:31:27
102
原创 leetcode 72. 编辑距离 dp
72. 编辑距离难度困难1120收藏分享切换为英文关注反馈给你两个单词word1和word2，请你计算出将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作：插入一个字符 删除一个字符 替换一个字符示例1：输入：word1 = "horse", word2 = "ros"输出：3解释：horse -> rorse (将 'h' 替换为 'r')rorse -> rose (删除 'r')rose ->...
2020-09-06 10:09:13
125
原创 leetcode 132. 分割回文串 II dp
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回符合要求的最少分割次数。示例:输入:"aab"输出: 1解释: 进行一次分割就可将s 分割成 ["aa","b"] 这样两个回文子串。dp[i]表示0-i为回文串的最小切割次数。初始化：dp[i]=i。 每个都是独立的一个。for(int i=0;i<n;i++){ for(int j=0;j<i;j++) ｛ ｉｆ（ａ［ｊ］＝＝ａ［ｉ］＆＆ｚ［ｊ＋１］［ｉ－１...
2020-09-05 21:36:12
117
原创 leetcode 120. 三角形最小路径和 经典DP O（N）
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。例如，给定三角形：[ [2], [3,4], [6,5,7], [4,1,8,3]]自顶向下的最小路径和为11（即，2+3+5+1= 11）。class Solution {public: int minimumTotal(vector<...
2020-09-05 21:05:38
82
原创 leetcode 131. 分割回文串 使用dp对回文串进行预处理！！！
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。示例:输入:"aab"输出:[ ["aa","b"], ["a","a","b"]]就是简单的dfs即可。但是有个优化的地方，那就是i到j是否为回文串。可以先用dp来预处理。if(a[i]==a[j]&&dp[i+1][j-1]) dp[i][j]=true;boolean[][] dp = new boolean[le...
2020-09-05 20:42:17
126
原创 leetcode 140. 单词拆分 II DP+DFS
140. 单词拆分 II难度困难224收藏分享切换为英文关注反馈给定一个非空字符串s和一个包含非空单词列表的字典wordDict，在字符串中增加空格来构建一个句子，使得句子中所有的单词都在词典中。返回所有这些可能的句子。说明：分隔时可以重复使用字典中的单词。 你可以假设字典中没有重复的单词。示例 1：输入:s = "catsanddog"wordDict = ["cat", "cats", "and", "sand", "dog"]输出:[ "cats and d...
2020-09-05 20:33:54
136
原创 leetcoe 139. 单词拆分 dp
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入: s = "leetcode", wordDict = ["leet", "code"]输出: true解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。示例 2：输入: s = "applepenapple", wordDic.
2020-09-05 17:22:45
143
原创 leetcode 115. 不同的子序 dp
给定一个字符串S和一个字符串T，计算在 S 的子序列中 T 出现的个数。一个字符串的一个子序列是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE"是"ABCDE"的一个子序列，而"AEC"不是）题目数据保证答案符合 32 位带符号整数范围。示例1：输入：S = "rabbbit", T = "rabbit"输出：3解释：如下图所示, 有 3 种可以从 S 中得到 "rabbit" 的方案。(上箭头符号 ^ 表示选...
2020-09-05 16:21:18
91
原创 leetcode 33. 搜索旋转排序数组 分情况二分
假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回-1。你可以假设数组中不存在重复的元素。你的算法时间复杂度必须是O(logn) 级别。示例 1:输入: nums = [4,5,6,7,0,1,2], target = 0输出: 4示例2:输入: nums = [4,5,6,7,0,1,2], ta...
2020-09-05 11:33:08
125
原创 leetcode 38. 外观数列
给定一个正整数 n（1 ≤n≤ 30），输出外观数列的第 n 项。注意：整数序列中的每一项将表示为一个字符串。「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：1. 12. 113. 214. 12115. 111221第一项是数字 1描述前一项，这个数是 1 即 “一个 1 ”，记作 11描述前一项，这个数是 11 即 “两个 1 ” ，记作 21描述前一项，这个数是 21 即 “一个 ...
2020-09-05 09:55:02
78
原创 ｌｅｅｔｃｏｄｅ 14. 最长公共前缀 多个思路的合计。二分／分治
14. 最长公共前缀难度简单1244收藏分享切换为英文关注反馈编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串""。示例1:输入: ["flower","flow","flight"]输出: "fl"示例2:输入: ["dog","racecar","car"]输出: ""解释: 输入不存在公共前缀。方法１： 那第一个单词和第二个单词求前缀，返回前缀和。 再拿前缀和第三个求。重复方法２：遍历第一个单词，拿字符和所有其他的进行...
2020-09-04 20:34:10
144
原创 ｌｅｅｔｃｏｄｅ 40. 组合总和 II 必须学会的的横向剪枝法
给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。说明：所有数字（包括目标数）都是正整数。解集不能包含重复的组合。示例1:输入: candidates =[10,1,2,7,6,1,5], target =8,所求解集为:[ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6]]这道...
2020-09-04 17:53:40
173
原创 ｌｅｅｔｃｏｄｅ 数字和系列题目 １ １５ １６ “ｆｏｒ＋双指针”
１：两数之和这道题三种做法：暴力法；两次哈希法。ｍａｐ＜ｉｎｔ，ｉｎｔ＞。ｋｅｙ为值，ｖａｌｕｅ为ｉｄ。 全部放入后。从０开始遍历，如果存在ｓｕｍ－ｎｕｍ【ｉ】，并且value的ｉ不是用一个，则可以一次哈希法。每次放入值前，检测一下之前的是否有满足条件的15. 三数之和ｆｏｒ第一个数字，如果第一个数字重复，则跳过。之后我们确定好ｔａｒｇｅｔ＝－ｎｕｍｓ［第一个数字］。第三个数字从ｎ找ｆｏｒ第二个数字，如果重复则跳过。如果第二个＋第三个大于ｔａｒｇｅｔ了，说明第三个大.
2020-09-04 17:25:52
162
原创 ｌｅｅｔｃｏｄｅ 118. 杨辉三角 容器的相关事情
不难，但是容器操作的确很麻烦。ｖｅｃｔｏｒ加入内容后是可以通过［］［］来获取元素的，但是加入元素只能通过ｐｕｓｈｂａｃｋ。classSolution{public:vector<vector<int>>generate(intnumRows){vector<vector<int>>vec; if(numRows==0)returnvec;v...
2020-09-04 15:43:34
86
原创 ｌｅｅｔｃｏｄｅ 162. 寻找峰值 二分查找确定峰值
峰值元素是指其值大于左右相邻值的元素。给定一个输入数组nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设nums[-1] = nums[n] = -∞。示例 1:输入: nums = [1,2,3,1]输出: 2解释: 3 是峰值元素，你的函数应该返回其索引 2。示例2:输入: nums = [1,2,1,3,5,6,4]输出: 1 或 5解释: 你的函数可以...
2020-09-04 15:30:21
271
原创 leetcode 189. 旋转数组 三次反转
给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。示例 1:输入: [1,2,3,4,5,6,7] 和 k = 3输出: [5,6,7,1,2,3,4]解释:向右旋转 1 步: [7,1,2,3,4,5,6]向右旋转 2 步: [6,7,1,2,3,4,5]向右旋转 3 步: [5,6,7,1,2,3,4]示例2:输入: [-1,-100,3,99] 和 k = 2输出: [3,99,-1,-100]解释:向右旋转 1 步: [99,-1,-100,3]...
2020-09-04 15:03:06
163
原创 leetcode 88. 合并两个有序数组
给你两个有序整数数组nums1 和 nums2，请你将 nums2 合并到nums1中，使 nums1 成为一个有序数组。说明:初始化nums1 和 nums2 的元素数量分别为m 和 n 。你可以假设nums1有足够的空间（空间大小大于或等于m + n）来保存 nums2 中的元素。示例:输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出:[1,2,2,3,5,6]...
2020-09-04 11:06:06
81
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人