- 博客(143)
- 收藏
- 关注
RSS订阅原创 leetcode, LC79:爬楼梯
1 题目描述你在爬楼梯，需要n步才能爬到楼梯顶部每次你只能向上爬1步或者2步。有多少种方法可以爬到楼梯顶部？2 解题思路斐波那契3 代码实现class Solution {public: /** * * @param n int整型 * @return int整型 */ int climbStairs(int n) { // write code here int f = 1; int
2020-12-28 22:05:58
121
原创 leetcode, LC78:简化路径
1 题目描述请简化给出的Unix样式的文件绝对路径，也就是转换成规范路径在Unix样式的文件系统中， .代表当前目录，… 表示将目录向上移动一级，更多的介绍可以查看 Absolute path vs relative path in Linux/Unix请注意，返回的规范路径必须以斜杠“/”开头，并且两个目录名之间只能有一个斜杠“/”开头。如果存在的最后一级目录的话不能以“/”结尾。另外，转化出的规范路径必须是能表示给出的绝对路径的最短字符串。例如：文件路径 = “/web/”, =>"/w
2020-12-28 21:45:24
187
原创 leetcode, LC77:编辑距离
1 题目描述2 解题思路最小编辑距离dp[i][j]表示由word1的前i个字符转换为word2的前j个字符的最小编辑距离。状态公式：如果word1[i-1] = word2[j-1]，dp[i][j] = dp[i-1][j-1]如果word1[i-1] != word2[j-1], dp[i][j] = min(dp[i-1][j-1]+1, dp[i][j-1]+1, dp[i-1][j] + 1)基准1: dp[0][k] = k基准2: dp[k][0] = k状态公式的解释如
2020-12-28 21:38:15
135
原创 leetcode, LC76:矩阵置零
1 题目描述给定一个m*n的矩阵，如果有一个元素是0，就把该元素所在的行和列上的元素全置为0，要求使用原地算法。拓展：你的算法有使用额外的空间吗？一种比较直接的算法是利用O(m,n)的空间，但是这不是一个好的解法使用简单的改进可以在O(m+n)的空间解决这个问题，但是还不是最佳的解法你能在常量级的空间复杂度内解决这个问题吗？2 解题思路见代码3 代码实现class Solution {public: void setZeroes(vector<vector<int&
2020-12-28 20:33:58
96
原创 leetcode, LC75:矩阵查找
1 题目描述请写出一个高效的在m*n矩阵中判断目标值是否存在的算法，矩阵具有如下特征：每一行的数字都从左到右排序每一行的第一个数字都比上一行最后一个数字大2 解题思路首先选取右上角数字，如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数字，去掉此数字所在列；如果该数字小于要查找的数字，则去掉该数字所在行。重复上述过程直到找到要查找的数字，或者查找范围为空。3 代码实现class Solution {public: /** * * @param m
2020-12-28 20:13:21
99
原创 leetcode, LC74:排列颜色
1 题目描述现在有一个包含n个物体的数组，其中物体颜色为颜色为红色、白色或蓝色，请对这个数组进行排序，让相同颜色的物体相邻，颜色的顺序为红色，白色，蓝色。我们用0,1,2分别代表颜色红，白，蓝注意：本题要求你不能使用排序库函数扩展：一个非常直接的解法是两步的计数排序的算法首先：遍历一遍数组，记录0,1,2的数量，然后重写这个数组，先将0写入，再将1写入，再将2写入你能给出一个只用一步，并且能在常数级空间复杂度解决这个问题的算法吗？2 解题思路设置3个变量，分别代表数组前部zeroinde
2020-12-28 20:07:12
147
原创 leetcode, LC73:最小覆盖子串
1 题目描述给出两个字符串 S 和 T，要求在O(n)的时间复杂度内在 S 中找出最短的包含 T 中所有字符的子串。例如：S=“XDOYEZODEYXNZ”T=“XYZ”找出的最短子串为"YXNZ".注意：如果 S 中没有包含 T 中所有字符的子串，返回空字符串 “”；满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。2 解题思路这道题的思路是：begin开始指向0， end一直后移，直到begin - end区间包含T中所有字符。记录窗口长度d然后begin开始后
2020-12-23 19:55:18
139
原创 leetcode, LC72:组合
1 题目描述给出两个整数n和k，返回从1到n中取k个数字的所有可能的组合2 解题思路dfs3 代码实现class Solution {public: /** * * @param n int整型 * @param k int整型 * @return int整型vector<vector<>> */ vector<vector<int> > combine(int n, int
2020-12-23 19:25:35
95
原创 leetcode, LC71:集合的所有子集
1 题目描述现在有一个没有重复元素的整数集合S，求S的所有子集注意：你给出的子集中的元素必须按升序排列给出的解集中不能出现重复的元素2 解题思路dfs3 代码实现class Solution {public: vector<vector<int> > subsets(vector<int> &S) { vector<vector<int>> subset_list; vector&l
2020-12-23 19:15:56
134
原创 leetcode, LC70:单词搜搜
1 题目描述给出一个二维字符数组和一个单词，判断单词是否在数组中出现，单词由相邻单元格的字母连接而成，相邻单元指的是上下左右相邻。同一单元格的字母不能多次使用。例如：给出的字符数组=[[“XYZE”],[“SFZS”],[“XDEE”]]单词 =“XYZZED”, -> 返回 true,单词 =“SEE”, ->返回 true,单词 =“XYZY”, -> 返回 fXlse.2 解题思路dfs3 代码实现class Solution {public:
2020-12-23 19:00:01
502
原创 leetcode, LC69:删除有序数组中重复的元素 ii
1 题目描述继续思考题目"Remove Duplicates":如果数组中元素最多允许重复两次呢？例如：给出有序数组 A =[1,1,1,2,2,3],你给出的函数应该返回length =5, A 变为[1,1,2,2,3].2 解题思路暴力法3 代码实现class Solution {public: int removeDuplicates(int A[], int n) { int index = 0; for(int i = 0; i &l
2020-12-23 17:52:10
82
原创 leetcode, LC68:旋转排序数组搜索
1 题目描述继续思考题目 “旋转排序数组搜索”:如果数组种允许有重复元素怎么办？会影响时间复杂度吗？是怎样影响时间复杂度的，为什么？编写一个函数判断给定目标值是否在数组中。2 解题思路暴力法3 代码实现class Solution {public: /** * * @param A int整型一维数组 * @param n int A数组长度 * @param target int整型 * @return bool布尔型
2020-12-23 17:45:22
118
原创 leetcode, LC67:删除有序链表中重复的元素
1 题目描述删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次例如：给出的链表为1→1→2,返回1→2.给出的链表为1→1→2→3→3,返回1→2→3.2 解题思路见代码3 代码实现ListNode* deleteDuplicates(ListNode* head) { ListNode* cur = head; while(cur != NULL){ while(cur->next != NULL &&
2020-12-20 22:26:02
148
原创 leetcode, LC66:删除有序链表中重复出现的元素
1 题目描述给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。例如：给出的链表为1→2→3→3→4→4→5, 返回1→2→5.给出的链表为1→1→1→2→3, 返回2→3.2 解题思路见代码3 代码实现/** * struct ListNode { * int val; * struct ListNode *next; * }; */class Solution {public: /** * * @param
2020-12-20 22:13:45
240
原创 leetcode, LC65:直方图中的最大矩形
1 题目描述给出n个数字，代表直方图的条高，直方图每一条的宽度为1，请计算直方图中最大矩形的面积例如：给出的高度 =[2,1,5,6,2,3],返回10.2 解题思路目的：用height[]构造一个升序栈,构造过程中计算面积；如果当前height[i]大于栈顶元素，则入栈；若小于栈顶元素，则将栈顶元素弹出并做记录弹出几次，并计算以弹出元素作为高度的面积，留下最大值ret，直到满足height[i]大于栈顶元素，再将弹出的元素以height[i]重新入栈；过程为 ：2入栈；目前栈为{2
2020-12-17 17:31:42
129
原创 leetcode, LC64:最大的长方形
1 题目描述给出一个只包含0和1的二维矩阵，找出最大的全部元素都是1的长方形区域，返回该区域的面积。2 解题思路https://blog.csdn.net/qq_41855420/article/details/874595493 代码实现class Solution {public: int maximalRectangle(vector<vector<char> > &matrix) { int n_rows = matrix.size
2020-12-17 17:31:21
355
原创 leetcode, LC63: 划分链表
1 题目描述给出一个链表和一个值 x，以 x为参照将链表划分成两部分，使所有小于 x的节点都位于大于或等于 x的节点之前。两个部分之内的节点之间要保持的原始相对顺序。例如：给出 1→4→3→2→5→2和 x=3,返回 1→2→2→4→3→5.2 解题思路新建两个节点lt_x与gtet_x，分别为指向两个链表的头结点。把节点值小于x的节点链接到链表lt_x上，节点值大等于x的节点链接到链表gtet_x上。最后把两个链表相连即可3 代码实现class Solution {public
2020-12-16 16:12:50
110
原创 leetcode, LC62:搅乱字符串
1 题目描述https://www.nowcoder.com/practice/2bdc44bb0186468b8d8c13ea5d3a9e58?tpId=46&&tqId=29091&rp=1&ru=/ta/classic-code&qru=/ta/classic-code/question-ranking2 解题思路见代码3 代码实现#include<unordered_map>class Solution {public: b
2020-12-16 16:12:31
113
1
原创 leetcode, LC61: 合并两个有序的数组
1 题目描述给出两个有序的整数数组 A和 B，请将数组 B合并到数组 A中，变成一个有序的数组注意：可以假设 A数组有足够的空间存放 B数组的元素， A和 B中初始的元素数目分别为 m和 n2 解题思路最优解：从后往前处理,不需要开辟额外空间3 代码实现class Solution {public: void merge(int A[], int m, int B[], int n) { int idx1 = m - 1; int idx2 = n -
2020-12-15 14:29:29
73
原创 leetcode, LC60:格雷码
1 题目描述格雷码是一种二进制编码系统，如果任意两个相邻的代码只有一位二进制数不同，则称这种编码为格雷码（Gray Code）。给定一个非负整数n，表示代码的位数，打印格雷码的序列。格雷码序列必须以0开头。例如：给定n=2，返回[0,1,3,2]. 格雷码的序列为：00 - 001 - 111 - 310 - 2注意：对于一个给定的n，格雷码的序列不一定是唯一的，例如：根据题目描述，[0,2,3,1]也是一个有效的格雷码序列2 解题思路3 代码实现class Soluti
2020-12-15 14:19:47
79
原创 leetcode, LC59: 解密
1 题目描述一条仅包含字母‘A’-‘Z’的消息用下列的方式加密成数字‘A’ -> 1‘B’ -> 2…‘Z’ -> 26现在给出加密成数字的密文，请判断有多少种解密的方法例如：给出的密文为“13”，可以解密为"AC"(1 3) 或者"M"(13).所以密文"13"的解密方法是2种.2 解题思路dp3 代码实现class Solution {public: /** * * @param s string字符串 * @r
2020-12-14 13:59:34
109
原创 leetcode, LC58: 子集ii
1 题目描述给出一个可能包含重复元素的整数集合S，返回该整数集合的所有子集。注意：你给出的子集中的元素要按非递减的顺序排列给出的解集中不能包含重复的子集例如：如果S =[1,2,2], 给出的解集应该是：[[2],[1],[1,2,2],[2,2],[1,2],[]]2 解题思路dfs3 代码实现class Solution {public: // params vector<vector<int>> subset_list;
2020-12-14 13:56:34
89
原创 leetcode, LC57: 链表内指定区间反转
1 题目描述将一个链表m 位置到n 位置之间的区间反转2 解题思路见代码3 代码实现/** * struct ListNode { * int val; * struct ListNode *next; * }; */class Solution {public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return Lis
2020-11-25 11:09:23
153
原创 leetcode, LC56: 数字字符串转化成IP地址
1 题目描述现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。例如：给出的字符串为"25525522135",返回[“255.255.22.135”, “255.255.221.35”]. (顺序没有关系)3 代码实现class Solution {public: /** * * @param s string字符串 * @return string字符串vector */ vector<stri
2020-11-25 11:09:20
1124
原创 leetcode, LC55: 二叉树的中序遍历
1 题目描述给出一棵二叉树，返回这棵树的中序遍历2 解题思路见代码。3 代码实现class Solution {public: vector<int> inorderTraversal(TreeNode* root) { stack<TreeNode*> leftSubtreeList; vector<int> inorderTraversalResult; TreeNode* curNode = roo
2020-11-24 10:26:43
63
原创 leetcode, LC54: 不同的二叉搜索树
1 题目描述给定一个值n，能构建出多少不同的值包含1…n的二叉搜索树（BST）？例如给定 n = 3, 有五种不同的二叉搜索树（BST）2 解题思路动态规划。3 代码实现class Solution {public: int numTrees(int n) { // Note that dp[k] represents the number of BST trees built from 1...k if(n <= 0) return 0;
2020-11-24 10:17:50
62
原创 leetcode, LC53: 不同的二叉搜索树 ii
1 题目描述给定一个值n,请生成所有的存储值1…n.的二叉搜索树（BST）的结构2 解题思路见代码3 代码实现class Solution {public: vector<TreeNode*> generateTrees(int n) { return generateTreesHelper(1, n); } vector<TreeNode*> generateTreesHelper(int small, int large){
2020-11-23 11:00:19
68
原创 leetcode, LC52: 判交织的字符串
1 题目描述2 解题思路动态规划3 代码实现class Solution {public: bool isInterleave(string s1, string s2, string s3) { int len1 = s1.length(); int len2 = s2.length(); int len3 = s3.length(); if(len1 + len2 != len3) return false;
2020-11-23 10:43:59
57
原创 leetcode, LC51: 判断二叉搜索树
1 题目描述判断给出的二叉树是否是一个二叉搜索树（BST）二叉搜索树的定义如下一个节点的左子树上节点的值都小于自身的节点值一个节点的右子树上节点的值都大于自身的节点值所有节点的左右子树都必须是二叉搜索树如果你不清楚“{1,#,2,3}"的含义的话，请继续阅读我们用如下方法将二叉树序列化：二叉树的序列化遵循层序遍历的原则，”#“代表该位置是一条路径的终结，下面不再存在结点。2 解题思路老实说，这一题我也不太明白。3 代码实现/** * struct TreeNode { * i
2020-11-20 16:04:37
62
原创 leetcode, LC50: 恢复二叉搜索树
1 题目描述二叉搜索树（BST）中的两个节点被错误地交换了，请在不改变树的结构的情况下恢复这棵树。备注；用O(n)的空间解决这个问题的方法太暴力了，你能设计一个常数级空间复杂度的算法么？2 代码实现老实说我没太明白。3 解题思路/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(
2020-11-20 15:54:33
81
原创 leetcode, LC49: 判断二叉树是否相等
1 题目描述给出两个二叉树，请写出一个判断两个二叉树是否相等的函数。判断两个二叉树相等的条件是：两个二叉树的结构相同，并且相同的节点上具有相同的值。2 解题思路和48题类似。3 代码实现/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** * * @param p
2020-11-20 15:31:51
70
原创 leetcode, LC48: 判断二叉树是否对称
1 题目描述给定一棵二叉树，判断琪是否是自身的镜像（即：是否对称）2 解题思路见代码3 代码实现class Solution {public: /** * * @param root TreeNode类 * @return bool布尔型 */ bool isSymmetric(TreeNode* root) { return isSymmetricHelper(root, root); } bool i
2020-11-20 10:24:44
68
原创 leetcode, LC47: 求二叉树的层序遍历
1 题目描述给定一个二叉树，返回该二叉树层序遍历的结果，（从左到右，一层一层地遍历）2 解题思路会做z型这题肯定会做了。3 代码实现class Solution {public: /** * * @param root TreeNode类 * @return int整型vector<vector<>> */ vector<vector<int> > levelOrder(TreeNode*
2020-11-19 10:08:58
87
原创 leetcode, LC46: 二叉树的之字形层序遍历
1 题目描述给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）2 解题思路与普通的层序遍历不同的是，我们设置了一个left2right的flag，当left2right == true时，当前层从左到右遍历（pushback），当left2right == false时，当前层从右到左遍历（insert(0, )）3 代码实现class Solution {public: /** * * @param root TreeN
2020-11-19 10:06:53
140
原创 leetcode, LC45: 二叉树的最大深度
1 题目描述求给定二叉树的最大深度，最大深度是指树的根结点到最远叶子结点的最长路径上结点的数量。2 解题思路递归，当前结点的最大深度为其左子树深度和右子树深度较大的那个加1。3 代码实现class Solution {public: /** * * @param root TreeNode类 * @return int整型 */ int maxDepth(TreeNode* root) { if(root == NUL
2020-11-19 09:51:37
76
原创 leetcode, LC44: 从前序和中序遍历构造二叉树
1 题目描述给出一棵树的前序遍历和中序遍历，请构造这颗二叉树注意：可以假设树中不存在重复的节点2 解题思路和 从中序和后序遍历构造二叉树 一致。3 代码实现/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** * * @param preorder int整型v
2020-11-19 09:47:47
73
原创 leetcode, LC43: 从中序和后序遍历构造二叉树
1 题目描述给出一棵树的中序遍历和后序遍历，请构造这颗二叉树注意：保证给出的树中不存在重复的节点2 解题思路就是数据结构课本里图示方法的代码版。3 代码实现/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** * * @param inorder int整型ve
2020-11-18 16:48:13
60
原创 leetcode, LC42: 二叉树程序遍历 ii
1 题目描述给定一个二叉树，返回该二叉树由底层到顶层的层序遍历，（从左向右，从叶子节点到根节点，一层一层的遍历）2 解题思路bfs3 代码实现/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** * * @param root TreeNode类 * @
2020-11-18 16:31:08
68
原创 leetcode, LC41: 将升序数组转化为平衡二叉搜索树
1 题目描述给出一个升序排序的数组，将其转化为平衡二叉搜索树（BST）.2 解题思路和上题一样。3 代码实现/** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */class Solution {public: /** * * @param num int整型vector * @return TreeNode类
2020-11-18 16:11:37
179
原创 leetcode, LC40: 有序链表变成二叉搜索树
1 题目描述给定一个单链表，其中的元素按升序排序，请将它转化成平衡二叉搜索树（BST）2 解题思路思路：这道题是要求把有序链表转为二叉搜索树，和之前那道Convert Sorted Array to Binary Search Tree思路完全一样，只不过是操作的数据类型有所差别，一个是数组，一个是链表。数组方便就方便在可以通过index直接访问任意一个元素，而链表不行。由于二分查找法每次需要找到中点，而链表的查找中间点可以通过快慢指针来操作。找到中点后，要以中点的值建立一个数的根节点，然后需要把原
2020-11-18 15:53:58
96
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人