- 博客(107)
- 收藏
- 关注
RSS订阅原创 从头做leetcode之leetcode 108 将有序数组转换为二叉搜索树
108.将有序数组转换为二叉搜索树将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), l
2020-07-04 23:30:34
141
原创 从头做leetcode之leetcode 104 二叉树的最大深度
104.二叉树的最大深度给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。递归/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), r
2020-06-30 22:16:21
154
原创 从头做leetcode之leetcode 103 二叉树的锯齿形层次遍历
103.二叉树的锯齿形层次遍历给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。用一个变量记录层数，奇数尾插，偶数头插。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x
2020-06-30 22:13:11
159
原创 从头做leetcode之leetcode 102 二叉树的层序遍历
102.二叉树的层序遍历给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。队列，把每层的结点放入后进入循环输出。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), rig
2020-06-30 22:07:50
97
原创 从头做leetcode之leetcode 101 对称二叉树
101.对称二叉树给定一个二叉树，检查它是否是镜像对称的。用递归的方法/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {pub
2020-06-28 16:22:44
103
原创 从头做leetcode之leetcode 100 相同的树
100.相同的树给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。递归/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL)
2020-06-14 14:57:36
82
原创 从头做leetcode之leetcode 98 验证二叉搜索树
98.验证二叉搜索树给定一个二叉树，判断其是否是一个有效的二叉搜索树。假设一个二叉搜索树具有如下特征：节点的左子树只包含小于当前节点的数。节点的右子树只包含大于当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。二叉搜索树的性质是中序遍历可以得到一个递增的序列/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNo
2020-06-13 15:27:59
93
原创 从头做leetcode之leetcode 97 交错字符串
97.交错字符串给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。动态规划class Solution {public: bool isInterleave(string s1, string s2, string s3) { int m = s1.size(),n = s2.size(); if(m + n != s3.size()) return false; vector<vector&l
2020-06-13 15:09:39
123
原创 从头做leetcode之leetcode 96 不同的二叉搜索树
96.不同的二叉搜索树给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？有n个结点的二叉搜索树的个数为每一个数为根节点时，左边结点能形成的二叉搜索树个数与右边结点能形成的二叉搜索树个数之积的和。class Solution {public: int numTrees(int n) { if(n <= 1) return n; int res = 0; vector<int> dp(n+1,0);
2020-06-12 11:34:14
106
原创 从头做leetcode之leetcode 96 不同的二叉搜索树II
96.不同的二叉搜索树II给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。对于每个结点的所有二叉搜索树在于要遍历左边的结点能形成的所有二叉搜索树和右边的结点形成的所有二叉搜索树。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(
2020-06-12 11:26:17
93
原创 从头做leetcode之leetcode 94 二叉树的中序遍历
94.二叉树的中序遍历给定一个二叉树，返回它的中序 遍历。示例:输入: [1,null,2,3]12/3输出: [1,3,2]进阶: 递归算法很简单，你可以通过迭代算法完成吗？栈/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : va
2020-06-11 17:19:48
118
原创 从头做leetcode之leetcode 92 反转链表II
92.反转链表II反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。说明:1 ≤ m ≤ n ≤ 链表长度。注意链表从第一位就开始反转的情况，要把start结点定义为一个空结点。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; *
2020-06-11 16:46:03
123
原创 从头做leetcode之leetcode 91 解码方法
91.解码方法一条包含字母 A-Z 的消息通过以下方式进行了编码：‘A’ -> 1‘B’ -> 2…‘Z’ -> 26给定一个只包含数字的非空字符串，请计算解码方法的总数。动态规划class Solution {public: int numDecodings(string s) { if(s.size() == 0 || s == "0") return 0; if(s.size() == 1) return 1;
2020-06-10 23:40:24
92
1
原创 从头做leetcode之leetcode 90 子集II
90.子集II给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。DFS回溯class Solution {public: vector<vector<int>> subsetsWithDup(vector<int>& nums) { if(nums.size() == 0) return {}; sort(nums.begin(),nums.end()
2020-06-10 23:23:59
100
原创 从头做leetcod之leetcode 89 格雷编码
89.格雷编码格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。格雷编码序列必须以 0 开头。用异或class Solution {public: vector<int> grayCode(int n) { vector<int> res; int size = pow(2,n); fo
2020-06-09 11:13:46
139
原创 从头做leetcode之leetcode 88 合并两个有序数组
88.合并两个有序数组给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。class Solution {public: void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int pos = m+n-1; int n1 = m-1,n2 = n-1;
2020-06-09 11:06:28
80
原创 从头做leetcode之leetcode 87 扰乱字符串
87.扰乱字符串给定一个字符串 s1，我们可以把它递归地分割成两个非空子字符串，从而将其表示为二叉树。下图是字符串 s1 = “great” 的一种可能的表示形式。great/ gr eat/ \ / g r e at/ a t在扰乱这个字符串的过程中，我们可以挑选任何一个非叶节点，然后交换它的两个子节点。例如，如果我们挑选非叶节点 “gr” ，交换它的两个子节点，将会产生扰乱字符串 “rgeat” 。rgeat/ rg eat
2020-06-08 14:46:28
120
原创 从头做leetcode之leetcode 86 分割链表
86.分隔链表给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。你应当保留两个分区中每个节点的初始相对位置。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution
2020-06-08 14:32:58
81
原创 从头做leetcode之leetcode 83 删除排序链表中的重复元素II
83.删除排序链表中的重复元素给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* deleteDupl
2020-06-07 15:33:00
90
原创 从头做leetcode之leetcode 82 删除排序链表中的重复元素
82.删除排序链表中的重复元素给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字要注意开头就重复的情况/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:
2020-06-07 15:26:00
96
1
原创 从头做leetcode之leetcode 81 搜索旋转排序数组
81.搜索旋转排序数组假设按照升序排序的数组在预先未知的某个点上进行了旋转。( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。二分查找，多一步判断哪边有序。class Solution {public: bool search(vector<int>& nums, int target) { int right =
2020-06-06 18:05:31
97
原创 从头做leetcode 80 删除排序数组中的重复项
80 删除排序数组中的重复项给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。双指针，一个指针遍历原数组，一个指针位于新数组末尾class Solution {public: int removeDuplicates(vector<int>& nums) { if(nums.size() <= 2){
2020-06-06 17:40:50
70
原创 从头做leetcode之leetcode 79 单词搜索
79.单词搜索给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。DFS的思想class Solution {public: bool exist(vector<vector<char>>& board, string word) { for(int i = 0;i < board.siz
2020-06-05 14:50:54
83
原创 从头做leetcode之leetcode 78 子集
78.子集给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。说明：解集不能包含重复的子集。DFS回溯class Solution {public: vector<vector<int>> subsets(vector<int>& nums) { vector<vector<int> > res; vector<int> tmp; DF
2020-06-05 13:59:11
106
原创 从头做leetcode之leetcode 77 组合
77.组合给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。DFSclass Solution {public: vector<vector<int>> combine(int n, int k) { if(k == 0) return {}; vector<vector<int> > res; vector<int> tmp; DFS(re
2020-06-04 16:34:39
108
原创 从头做leetcode之leetcode 76 最小覆盖子串
76.最小覆盖子串给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入: S = “ADOBECODEBANC”, T = “ABC”输出: “BANC”说明：如果 S 中不存这样的子串，则返回空字符串 “”。如果 S 中存在这样的子串，我们保证它是唯一的答案。class Solution {public: string minWindow(string s, string t) { if(t.size() >
2020-06-04 16:20:21
104
原创 从头做leetcode之leetcode 75 颜色分类
75.颜色分类两遍扫描一遍扫描给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。注意:不能使用代码库中的排序函数来解决这道题。两遍扫描用三个变量记录三个颜色的数量，时间复杂度O(2n)class Solution {public: void sortColors(vector<int>& nums) {
2020-06-03 11:26:22
78
原创 从头做leetcode之leetcode 74 搜索二维矩阵
74.搜索二维矩阵编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。对行和列分别执行二分查找class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if(matrix.size() == 0 || matrix[0]
2020-06-03 11:06:18
96
原创 从头做leetcode 73 矩阵置0
73 矩阵置0给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。用每行每列的首个元素表示此行是否置0要额外处理首行首列的情况class Solution {public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(),n = matrix[0].size(); int lflag=
2020-06-02 12:20:10
100
原创 从头做leetcode之leetcode 72 编辑距离
72.编辑距离给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。你可以对一个单词进行如下三种操作：插入一个字符删除一个字符替换一个字符用动态规划的方法使得word1[0]-word1[i]与word2[0]-word2[j]匹配的情况：word1[0]-word1[i-1]与word2[0]-word2[j-1]已经匹配且word1[i] == word2[j]word1[0]-word1[i-1]与word2[0]-wo
2020-06-02 11:58:44
121
原创 从头做leetcode之leetcode 71 简化路径
71.简化路径以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （…） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串
2020-06-01 14:22:17
88
原创 从头做leetcode之leetcode70 爬楼梯
70.爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。由于一次只能爬1-2层，所以第n层的楼梯只能从第n-1或第n-2层爬上去。所以 dp[n] = dp[n-1]+dp[n-2](n > 2)class Solution {public: int climbStairs(int n) { if(n <= 2) return n; in
2020-06-01 13:53:38
154
原创 从头做leetcode之leetcode 69 x的平方根
69.x的平方根实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。用二分查找的思想，由于是取整数位，不存在四舍五入，所以在down > up-1 时退出循环class Solution {public: int mySqrt(int x) { if(x <= 1) return x; int up = x; int down
2020-05-31 14:50:52
158
原创 从头做leetcode之leetcode 68 文本左右对齐
68.文本左右对齐给定一个单词数组和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。你应该使用“贪心算法”来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。文本的最后一行应为左对齐，且单词之间不插入额外的空格。说明:单词是指由非空格字符组成的字符序列
2020-05-31 14:36:49
135
原创 从头做leetcode之leetcode 67 二进制求和
67.二进制求和给你两个二进制字符串，返回它们的和（用二进制表示）。输入为 非空 字符串且只包含数字 1 和 0。先将短的字符串前面填充0，使得字符串长度一样，便于运算。class Solution {public: string addBinary(string a, string b) { string res; int flag=0,tmp=0; if(a.size() > b.size()) b.insert(0,a.siz
2020-05-31 14:18:23
113
原创 从头做leetcode之leetcode 65 有效数字
65.有效数字验证给定的字符串是否可以解释为十进制数字。例如:“0” => true" 0.1 " => true“abc” => false“1 a” => false“2e10” => true" -90e3 " => true" 1e" => false“e3” => false" 6e-1" => true" 99e2.5 " => false“53.5e93” => true" --6 " =>
2020-05-30 18:02:26
124
原创 从头做leectcode之leetcode 66 加一
66.加一给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。你可以假设除了整数 0 之外，这个整数不会以零开头。没什么好说的，找到进位的结束就好了class Solution {public: vector<int> plusOne(vector<int>& digits) { for(int i = digits.size()-1;i >= 0;i--)
2020-05-30 16:59:40
113
1
原创 从头做leetcode之leetcode 64 最小路径和
64.最小路径和给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。说明：每次只能向下或者向右移动一步。动态规划class Solution {public: int minPathSum(vector<vector<int>>& grid) { int m = grid.size(); int n = grid[0].size(); vector<
2020-05-30 16:25:23
92
原创 从头做leetcode之leetcode 63 不同路径II
63.不同路径II一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。和上一题一样，遇到障碍物，当前位置路径变为0。class Solution {public: int uniquePathsWithObstacles(vector
2020-05-29 10:28:58
80
原创 从头做leetcode之leetcode 62 不同路径
62.不同路径一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？动态规划：除了最左边和最上边的两排，其他的每一个位置只有上边和左边两条路可以到。到达一个位置的路径数就等于到达上边的路径数加上到达左边的路径数即dp[i][j] = dp[i][j-1] + dp [i-1][j]class Solution {public:
2020-05-29 10:21:16
114
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人