Leetcode时间限制
注意:
⏰表示未完成
⭐表示重要
🌟表示超级重要
😄表示我的思路并且通过了
😭表示自己尝试的方法但是通不过
🙆♂表示他人的方法通过了
🙅♂表示他人的方法但没通过
💭表示只写了想法没写代码无论自己或者其他人的.
题号.题目
描述
样例
思想1名称(self
思路
描述
代码
\\语法, 以后搜索\\语法可以学习语法
\\思想, 学习思想
复杂度
- 时间: $$
- 空间: $$
思想2名称*
思路
描述
代码
复杂度
- 时间: $$
- 空间: $$
数据结构入门
217.存在重复元素
排序后扫描
算法
排序后再扫描,有相邻两位数字相同即存在相同元素,可以用Arrays.sort()进行排序
Arrays.sort(nums); //语法
int n = nums.length;
for (int i = 0; i < n - 1; i++) {
if (nums[i] == nums[i + 1]) {
return true;
}
}
return false;
复杂度
- 时间复杂度:O(NlogN).
- 空间空咋读:O(logN),为递归调用栈的深度.
选择排序法,边比较边扫描*
for (i = 1; i < nums.length;i++) {
for (j = i-1; j >= 0; j--) {
if (nums[i] == nums[j]) {
return true;
}else if(nums[i] > nums[j]){
break;
}
}
j++; //语法,j指向的是要替换的元素
int temp = nums[i];
for (int k = i; k > j; k--) {
nums[k] = nums[k-1];
}
nums[j] = temp;
}
return false;
- 时间:O(N^2)
- 空间:O(1)
集合长度小于数组长度,则重复
Set<Integer> res = new HashSet<Integer>();//语法
for(int i:nums)
res.add(i);
return res.size()<nums.length?true:false;
- 时间:O(N)
- 空间:O(N)
哈希表,在插入的时候如存在则重复
unordered_set<int> s; //语法
for (int x: nums) { //语法
if (s.find(x) != s.end()) {//语法
return true;
}
s.insert(x);
}
- 时间:O(N)
- 空间:O(N)
53.最大子序和
求数组中连续子序列最大的一段子数组.
动态规划
思路
假设$nums$数组的长度为$0$到$n-1$.
设**$f(i)$为以下标$i$元素结尾的「连续子数组的和**[^ 1]那么,答案为
$$
\sum_{0\leq i\leq n-1}{\max \left{ f\left( i \right) \right}}
$$
而基于$f(i)$的定义的假设,我们可以得到$f(i)$的递推公式:
$$
f(i) = max(f(i-1)+a_n,a_n)
$$
注意到$f(i)$只与$f(i-1)$有关,所以可以将空间复杂度将为$O(1)$.
代码
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0;
int maxAns = nums[0];
for (int a:nums){
pre = Math.max(pre+a,a); //f(i)
maxAns = Math.max(pre,maxAns); //f(0)-f(n-1)求最大值
}
return maxAns;
}
}
复杂度
时间复杂度:$O(n)$
空间复杂度:$O(1)$
1.两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
用map(self
思路
扫描一遍, 将nums[i]为key, i为value, 如果遇到相同的存储在第二个map里面
得到答案的话用直接取key=nums[i]和key=target-nums[i]的value值即可, 需要注意当两个数字相同的这种情况.
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> m1 =new HashMap<>(); //语法, 只能用Integer
Map<Integer, Integer> m2 = new HashMap<>();
for(int i =0; i < nums.length;i++){ //语法, nums.length
int num = nums[i];
if(!m1.containsKey(num)) {
m1.put(num,i); //语法
}else{
m2.put(num,i);
}
}
// System.out.println(m1);
// System.out.println(m2);
int []result = new int[2]; //语法, 用[]而不是()
for(int num : nums){
int first = num;
int second = target-num;
if (first==second) {
if(m1.containsKey(first)&&m2.containsKey(second)) {//语法
result[0] = m1.get(first);
result[1] = m2.get(second);
}
}else if(m1.containsKey(first)&&m1.containsKey(second)) {
result[0] =m1.get(first); //语法
result[1] = m1.get(second);
break;
}
}
return result;
}
}
复杂度
- 时间: O(N)
- 空间: O(N)
暴力枚举
思路
两个for循环, 第一个for遍历所有元素nums[i], 第二个for从第一个for的当前元素向后扫描nums[j], 如果等于nums[j]= target-nums[i]的话, 返回i,j即可.
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) { //思想
return new int[]{i, j}; //语法
}
}
}
return new int[0];
}
}
复杂度
- 时间: O(N^2)
- 空间: O(1)
哈希表*
思路
扫描元素, 如果已经包含$target-nums[i]$的话, 返回当前下标和另一个数字存储在map中的下标, 否则的话把这个数字当作key, 其对应的下标当作value进行存储.
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
/*思想, 太精妙了, 如果扫描到第一个数字, 则放入, 如果扫描第二个数字, 则直接返回答案
*相等数字情况下, 正好避免了两个key相同
*不相等数字下, 直接返回答案, 不进行存储, 非常高效
*/
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};//语法
}
hashtable.put(nums[i], i);
}
return new int[0]; //语法
}
}
复杂度
时间: O(N)
空间: O(N))
88:合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
归并(自己
思路
从后往前归并排序
代码
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m-1;
int j = n-1;
int point = m+n-1;
//系统的特殊数据,不具有普适性
if (m==0) {
for (int l = 0; l < n; l++) {
nums1[l] = nums2[l];
}
}
//思想, 归并
while(i!=-1 && j!=-1) {
if(nums1[i] >nums2[j]) {
nums1[point] = nums1[i];
i--;
}else {
nums1[point] = nums2[j];
j--;
}
point--;
}
//思想,当第二个数组剩下的话需要补上去, 第一个数组自动补了(正宗归并的话都要补)
while(j!=-1) {
nums1[point] = nums2[j];
point--;
j--;
}
return;
}
}
复杂度
- 时间: O(n)
- 空间: O(1)
归并(背, 一行代码, 非常简洁精妙
思路
$m$指向第一个数组的有数字的末尾, $n$指向第二个数组的有数字的末尾, 而$n+m-1$自然是真正的$point$, 不需要单独设置$point$.
在第二个指针没有穷尽时:
如果m到第一个数组移动完 或者 第一个数组的指针的数值小于第二个数组的指针的数值的话, 将第二个数组指针指向的数值赋值给n+m-1位置, 否则将第一个数组指针指向的数值赋值给n+m-1位置.
代码
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
while(n>0) {
nums1[n+m-1] = m<1||(nums1[m-1]< nums2[n-1])?nums2[--n]:nums1[--m];
}
}
}
- $while(n>0)$和将$nums2[–-n]$配合消除了正宗归并排序的剩余的第二个数组的补齐操作.
- $m<1$和$nums1[–m]$配合消除了第一个数组的补齐操作.
- $–n$和$–m$则消除了我的需要将$i=m-1, j=n-1$作为指针.
复杂度
- 时间: O(N)
- 空间: O(1).
直接合并后调用排序(算法工具的精髓
思路
调用算法库
代码
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0; i != n; ++i) {
nums1[m + i] = nums2[i];
}
Arrays.sort(nums1);
//C++ sort(nums1.begin(), nums1.end());
//python nums1.sort()
}
}
复杂度
时间: $O((N+M)log(N+M))$
空间: $log(N+M))$
350:两个数组的交集II
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
排序+双指针(self
思路
本来想着用两个set存储两个数组, 然后求交集, 但是发现多个重复元素的话集合只能保留一个, 所以还是用人工思想转代码, 先排序, 然后双指针.
代码
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
List<Integer> l = new ArrayList<>();
Arrays.sort(nums1);
Arrays.sort(nums2);
int i = 0;
int j = 0;
while (i <nums1.length && j <nums2.length) {
if (nums1[i] == nums2[j]) {
l.add(nums1[i]);
i++;
j++;
}else if(nums1[i] < nums2[j]) { //思想,哪个小移动哪个
i++;
}else {
j++;
}
}
int[] result = new int[l.size()];
for(int k = 0; k < l.size(); k++) {
result[k] = l.get(k);
}
return result;
}
}
复杂度
- 时间: O(max{N, M}log(max{N, M}), 主要是排序, 算法本身是O(N)
- 空间: O(N+M) 结果的返回
哈希表(官方
思路
由于同一个数字在两个数组中都可能出现多次，因此需要用哈希表存储每个数字出现的次数。对于一个数字，其在交集中出现的次数等于该数字在两个数组中出现次数的最小值。
首先遍历第一个数组，并在哈希表中记录第一个数组中的每个数字以及对应出现的次数，然后遍历第二个数组，对于第二个数组中的每个数字，如果在哈希表中存在这个数字，则将该数字添加到答案，并减少哈希表中该数字出现的次数。
为了降低空间复杂度，首先遍历较短的数组并在哈希表中记录每个数字以及对应出现的次数，然后遍历较长的数组得到交集。
代码
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int num : nums1) {
int count = map.getOrDefault(num, 0) + 1;
map.put(num, count);
}
int[] intersection = new int[nums1.length];
int index = 0;
for (int num : nums2) {
int count = map.getOrDefault(num, 0);
if (count > 0) {
intersection[index++] = num;
count--;
if (count > 0) {
map.put(num, count);
} else {
map.remove(num);
}
}
}
return Arrays.copyOfRange(intersection, 0, index);
}
}
复杂度
- 时间: O(m+n)
- 空间: O(min(m,n))
121:买卖股票的最佳时机
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
示例 1：
输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
暴力双循环(self
思路
找外循环后面的比该元素大的, 计算差值,如果比max大, 则替换, 否则继续循环.
代码
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
int length = prices.length;
for (int i = 0; i < length-1; i++) {//思想, 要记得-1,因为j+1, 否则会越界
for (int j = i+1; j < length; j++){
max = prices[j]-prices[i]>max?prices[j]-prices[i]:max;
}
}
return max;
}
}
复杂度
- 时间: O(N^2)超时了
- 空间: O(1)
动态规划*
思路
动态规划 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
代码
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
int smallest = prices[0];
for (int i = 0; i < prices.length; i++) {
max = Math.max(max, prices[i]-smallest); //语法//思想
if(prices[i] < smallest) smallest = prices[i];
}
return max;
}
}
复杂度
- 时间: O(N)
- 空间: O(1)
566:重塑矩阵
在 MATLAB 中，有一个非常有用的函数 reshape ，它可以将一个 m x n 矩阵重塑为另一个大小不同（r x c）的新矩阵，但保留其原始数据。
给你一个由二维数组 mat 表示的 m x n 矩阵，以及两个正整数 r 和 c ，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的 行遍历顺序 填充。
如果具有给定参数的 reshape 操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
新建数组循环赋值(self
思路
对于一个矩阵[m,n], i个元素在数组中对应的下标是[i/n, i%n];
代码
class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
int row = mat.length; //语法
int col = mat[0].length; //语法
if (row*col == r*c) {
int [][]result = new int[r][c]; //语法
for(int i = 0; i < row*col; i++) {
result[i/c][i%c] = mat[i/col][i%col];//语法//思想, 数组的下标和总长度的关系只有列有关
}
return result;
}
return mat;
}
}
复杂度
- 时间: O(r*c)
- 空间: O(1)
118:杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行, 在杨辉三角中, 每个数是它左上方和右上方的数的和.
模拟手算(self
思路
杨辉三角递推公式:
$$
result[row][j] =\left{
\begin{align}
1(第一行为1) &&{row=0,j=0}\
1(头尾为1) &&{row!=0,j=0 ||row!=0, j=row-1} \
result[row-1][j-1]+result[row-1][j] & & row>0,j>0 \
\end{align}
\right.
$$
代码
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> firstRow = new ArrayList<>();
firstRow.add(1);
result.add(firstRow);
for(int numRow = 2; numRow <= numRows; numRow++) {
List<Integer> row = new ArrayList<>(numRow);
result.add(row);
for (int j = 0; j < numRow; j++) {
if (j==0||j==numRow-1) {
result.get(numRow-1).add(1); //语法
}
else {
Integer num = result.get(numRow-2).get(j-1)+result.get(numRow-2).get(j);//思想, 递推公式
result.get(numRow-1).add(num);
}
}
}
return result;
}
}
复杂度
- 时间: $O(N^2)$
- 空间: $O(N^2)$
36:有效的数独
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
- 一个有效的数独（部分已被填充）不一定是可解的。
- 只需要根据以上规则，验证已经填入的数字是否有效即可。
- 空白格用
'.'表示。
输入：board =
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true
Map存储是否出现(self
思路
有9行个Map来存储每一行的出现,有9列个Map存储每一列的出现, 有3*3个Map存储对应第三条3*3个九宫格的出现.
其实我用Map的原因是因为输入是Char, 其实可以将char转化为int, 然后就只需要用bool的二维数组就可以了,比如boolean[][] row=new boolean[9][9]记i行的数j是否已经摆放, i起list的作用, j起map的作用
代码
class Solution {
public boolean isValidSudoku(char[][] board) {
List<Map<Character, Boolean>> row = new ArrayList<>(); //语法, //思想, 其实用bool [][]
List<Map<Character, Boolean>> col = new ArrayList<>();
List<List<Map<Character, Boolean>>> nine_Square = new ArrayList<>();//语法//思想,
for (int k = 0; k < 9; k++) {
row.add(new HashMap<>()); //语法, 注意可以省略Key和Value的类型自行推断.
col.add(new HashMap<>());
}
for (int i = 0; i < 3; i++) {
List<Map<Character, Boolean>> temp = new ArrayList<>(3);
for(int j = 0; j < 3; j++){
temp.add(new HashMap<Character, Boolean>());
}
nine_Square.add(temp);
}
int r = board.length;
int c = board[0].length;
for (int i = 0;i < r; i++) {
for (int j = 0; j < c; j++) {
if(board[i][j] == '.') continue;
if(!row.get(i).containsKey(board[i][j])) row.get(i).put(board[i][j], true);
else return false;
if(!col.get(j).containsKey(board[i][j])) col.get(j).put(board[i][j], true);
else return false;
if(!nine_Square.get(i/3).get(j/3).containsKey(board[i][j])) nine_Square.get(i/3).get(j/3).put(board[i][j], true);
else return false;
}
}
return true;
}
}
复杂度
- 时间: $O(r*c)$
- 空间: $O(r*c)$
73:矩阵置零
给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法.
用两个set记录0所对应的行数和列数(self
思路
代码
class Solution {
public void setZeroes(int[][] matrix) {
Set<Integer> row = new HashSet<>();
Set<Integer> col = new HashSet<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if(matrix[i][j]==0) {
row.add(i); //思想
col.add(j); //思想
}
}
}
for(Integer r:row) { //语法
for(int j = 0; j < matrix[0].length; j++) {
matrix[r][j] = 0;
}
}
for(Integer c:col) {
for(int i = 0; i < matrix.length; i++) {
matrix[i][c] = 0;
}
}
}
}
复杂度
- 时间: $O(M*N)$
- 空间: $O(M+N)$
使用两个标记变量
思路
我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1)O(1)O(1) 的额外空间。但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 000。因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 000。
在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。
代码
复杂度
- 时间: $O(M*N)$
- 空间: $O(1)$
使用BigSet类
387:字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例：
s = "leetcode"
返回 0
s = "loveleetcode"
返回 2
Hash存字符-出现次数(self
思路
Hash存字符-出现次数, 第一遍遍历获取, 第二遍遍历检验
代码
class Solution {
public int firstUniqChar(String s) {
Map<Character, Integer> m = new HashMap<>();
Integer min = Integer.MAX_VALUE;
for(int i = 0; i < s.length(); i++) {
m.put(s.charAt(i), m.getOrDefault(s.charAt(i),0)+1);//语法,//思想
}
for(int i = 0; i < s.length(); i++) {
if(m.get(s.charAt(i)) == 1) {
return i;
}
}
return -1;
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(\sum)$ $\sum$是字符集的大小.
383:赎金信
给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。
如果可以，返回 true ；否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1：
输入：ransomNote = "a", magazine = "b"
输出：false
两个Map存储出现次数, 然后遍历比较(self
思路
描述
代码
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
Map<Character, Integer> ransomNoteMap = new HashMap<>();
Map<Character, Integer> magazineMap = new HashMap<>();
for(int i = 0; i < ransomNote.length(); i++) {
ransomNoteMap.put(ransomNote.charAt(i), ransomNoteMap.getOrDefault(ransomNote.charAt(i),0)+1);
}
for(int i = 0; i < magazine.length(); i++) {
magazineMap.put(magazine.charAt(i), magazineMap.getOrDefault(magazine.charAt(i),0)+1);
}
for(int i = 0; i < ransomNote.length(); i++) {
if (!magazineMap.containsKey(ransomNote.charAt(i))) {//思想
return false;
}
if (ransomNoteMap.get(ransomNote.charAt(i)) > magazineMap.get(ransomNote.charAt(i))) {//思想
return false;
}
}
return true;
}
}
复杂度
- 时间: $O(max{N,M})$
- 空间: $O(N+M)$
数组统计+变体比较*
思路
统计用int[]来做, 只不过下标由map转变了int, 利用了数组本身的特性.
将两个map和比较大小转化成了一个array和相减操作比大小.
代码
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if (ransomNote.length() > magazine.length()) {
return false;
}
int[] cnt = new int[26];
for (char c : magazine.toCharArray()) { //语法
cnt[c - 'a']++; //思想
}
for (char c : ransomNote.toCharArray()) {
cnt[c - 'a']--; //思想
if(cnt[c - 'a'] < 0) { //思想
return false;
}
}
return true;
}
}
复杂度
- 时间:
- 空间: $O(\sum)$ $\sum$是字符集的大小.
242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
排序后比较*
思路
异位词等价于排序后字符串相等
代码
class Solution {
public boolean isAnagram(String s, String t) {
if (s.length() != t.length()) {
return false;
}
char[] str1 = s.toCharArray(); //语法
char[] str2 = t.toCharArray();
Arrays.sort(str1); //语法
Arrays.sort(str2);
return Arrays.equals(str1, str2);//思想
}
}
复杂度
- 时间: O(nlogn)
- 空间: O(logn)
141:环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
快慢指针(self
思路
描述
代码
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode first = head;
ListNode second = head;
while(first!=null&&second!=null&&second.next!=null) {//重要
first = first.next;
second = second.next.next;
if (first == second) {
return true;
}
}
return false;
}
}
复杂度
- 时间: O(N)
- 空间: O(1)
哈希表*
思路
最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。
代码
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<ListNode>(); //思想, 可以把ListNode也可以放集合
while (head != null) {
if (!seen.add(head)) {
return true;
}
head = head.next;
}
return false;
}
}
复杂度
- 时间: O(N)
- 空间: O(N)
21:合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
假头指针(self
思路
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
代码
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode point = new ListNode();//语法
ListNode head = point; //语法//思想
while(list1!=null&&list2!=null) {
if (list1.val < list2.val) {
point.next = list1; //思想
point = point.next; //思想
list1 = list1.next; //思想
}else {
point.next = list2;
point = point.next;
list2 = list2.next;
}
}
if (list1==null) {
point.next = list2;
}
if (list2 ==null) {
point.next = list1;
}
//语法,上面两句可以合并成point.next = list1==null?list2:list1;
return head.next;
}
}
复杂度
- 时间: $O(N)$
- 空间: $O(1)$
递归*
思路
链表的定义否和递归, 所以常用递归来解决链表问题.
代码
/*
LeetCode官方代码, 好清晰啊
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode point = new ListNode();
ListNode head = point;
merge(head, list1, list2);
return head.next;
}
private void merge(ListNode point, ListNode list1, ListNode list2) {
if(list1 == null) {
point.next = list2;
return;
}
if(list2 == null) {
point.next = list1;
return;
}
if (list1.val < list2.val) {
point.next = list1;
merge(point.next, list1.next, list2);
}else{
point.next = list2;
merge(point.next, list1, list2.next);
}
}
}
复杂度
- 时间: O(N)
- 空间: O(N)
203:移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
递归(self
思路
考虑返回值是什么, 什么时候停止,
代码
/*
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head == null) {
return head;
}
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
}
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if (head==null) {
return head;
}
if (head.val == val) {
return removeElements(head.next, val);
}else{
head.next = removeElements(head.next, val);
return head;
}
}
}
复杂度
- 时间: O(N)
- 空间: O(N)
迭代
206:反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
假头+临时节点(self
思路
迭代,用假头节点和临时节点
代码
class Solution {
public ListNode reverseList(ListNode head) {
ListNode fake_head = new ListNode();
ListNode temp;
while(head!=null) {
temp = fake_head.next; //思想
fake_head.next = head; //思想
head = head.next; //思想,非常重要, 不能写在下一条语句的后面,前三句承上启下
fake_head.next.next = temp; //思想,temp是暂存的, 放在最后没有任何问题, 其他的都是复用
}
return fake_head.next;
}
}
复杂度
- 时间: O(N)
- 空间: O(1)
其他
思路
用栈或者反转值.
83. 删除排序链表中的重复元素
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素只出现一次 。
返回同样按升序排列的结果链表。
双指针迭代(self
思路
描述
代码
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode prev; //其实用cur也可以
ListNode follow;
if(head==null) {
return head;
}
prev = head;
follow = head.next;
while(follow!=null) {
if (prev.val == follow.val) { //思想
prev.next = follow.next; //删除相同元素
follow = follow.next; //相等只移动follow
}else{
follow = follow.next; //不相等都移动
prev = prev.next;
}
}
return head;
}
}
/*
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode cur = head; //思想, 其实不需要用follow指针
while (cur.next != null) {
if (cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
*/
复杂度
- 时间:
- 空间:
递归*(太妙了
思路
递归套路解决链表问题：
- 找终止条件：当head指向链表只剩一个元素的时候，自然是不可能重复的，因此return
- 想想应该返回什么值：应该返回的自然是已经去重的链表的头节点
- 每一步要做什么：宏观上考虑，此时head.next已经指向一个去重的链表了，而根据第二步，我应该返回一个去重的链表的头节点。因此这一步应该做的是判断当前的head和head.next是否相等，如果相等则说明重了，返回head.next，否则返回head
- 如果独立写递归函数有困难的，可以参考一下我写的一个博客，附有详细的图文介绍：博客链接
代码
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null || head.next == null){
return head;
}
head.next = deleteDuplicates(head.next); //思想,先让后面的不重复
if(head.val == head.next.val) head = head.next; //思想,解决现有头和后面的头相同的问题
return head;
}
}
/*
刚开始我也想的是递归, 但是有一点点问题, 就放弃了,问题出现在我是没有解决head和deleteDuplicates返回的节点如果相同的问题, 而原Po主解决了,就是先将后面的链表删除重复元素, 再来解决返回的链表的头和现有的头相同的问题, 另一个解决方法是我下面的注释中写的, 是在评论区找到的
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head==null||head.next==null) {
return head;
}
if (head.val==head.next.val) {
head.next = deleteDuplicates(head.next.next);
//这条语句有问题,当相等的时候应该是head = deleteDuplicates(head.next);
}else{
head.next = deleteDuplicates(head.next);
}
return head;
}
}
*/
复杂度
- 时间: 分析不出来
- 空间: O(N)
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
示例 1：
输入：s = "()"
输出：true
栈(self
思路
描述
代码
class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<>();
for(char c:s.toCharArray()) {
if (c=='('||c=='['||c=='{') {
stack.push(c);
}else{
if (stack.empty()) return false; //思想,一定在每次取栈顶前都加这种判断
char temp = stack.peek();
if(c==')'&&temp=='(') stack.pop();
else if(c==']'&&temp=='[') stack.pop();//思想, 要用else if
else if(c=='}'&&temp=='{') stack.pop();
else return false;
}
}
if(stack.empty()) return true;
return false;
}
}
复杂度
- 时间: O(N)
- 空间: O(N)
232. 用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）
模拟(self
思路
当取队头的时候, 将A栈送入B栈,然后取B栈头,取完后再入A栈, 读取队头也一样.
当入队的时候, 直接入A栈尾.
代码
class MyQueue {
private Stack<Integer> s1; //语法, 在这里声明变量
private Stack<Integer> s2;
public MyQueue() {
s1 = new Stack<>(); //语法, 初始化
s2 = new Stack<>();
}
public void push(int x) {
s1.push(x);
}
public int pop() {
if(s1.empty()) return -1;
int result;
while(!s1.empty()) {
int temp = s1.pop();
s2.push(temp);
}
result = s2.pop();
while(!s2.empty()) {
int temp = s2.pop();
s1.push(temp);
}
return result;
}
public int peek() {
int result;
while(!s1.empty()) {
int temp = s1.pop();
s2.push(temp);
}
result = s2.peek();
while(!s2.empty()) {
int temp = s2.pop();
s1.push(temp);
}
return result;
}
public boolean empty() {
return s1.empty();
}
}
144. 二叉树的前序, 中序(94), 后序(145), 层次遍历
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
输入：root = [1,null,2,3]
输出：[1,2,3]
递归(self
前序思路
因为要存储为LIst,使用一个帮助函数, 中, 后序改动少量代码即可.
前序代码
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
preorderHelp(result, root);
return result;
}
private void preorderHelp(List<Integer> l, TreeNode root) { //思想
if (root==null) {
return;
}
l.add(root.val); //思想
preorderHelp(l, root.left);
preorderHelp(l, root.right);
}
}
前序复杂度
- 时间: $O(N)$
- 空间: $O(logN)$
模拟手动模板套路
前序思路及代码
将手动求前序的过程进行模拟,
当栈不为空或者当前指针不为空的时候:
遍历左子树
先访问cur
入栈cur(父节点)
然后cur指向它的左子树继续第一步
出栈(得到父节点)
访问右子树
//记忆
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
List<Integer> result = new ArrayList<>();
if(root==null) return result; //思想
TreeNode cur = root;
while(cur!=null || !s.empty()) { //思想
while(cur!=null) { //思想, 遍历左子树
result.add(cur.val);
s.push(cur);
cur = cur.left;
}
TreeNode peek = s.pop(); //取父节点
cur = peek.right; //思想, 指向右节点
}
return result;
}
}
中序思路及代码
在前序的基础上, 取栈顶元素(父节点)后访问父节点元素(而不是入栈前),在指向右孩子.
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
List<Integer> result = new ArrayList<>();
if(root==null) return result;
TreeNode cur = root;
while(cur!=null || !s.empty()) {
while(cur!=null) {
s.push(cur);
cur = cur.left;
}
TreeNode peek = s.pop();
result.add(peek.val); //思想
cur = peek.right;
}
return result;
}
}
后序思路及代码
相当于”先访问后孩子的前序”, 对结果再进行逆序
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
List<Integer> result = new ArrayList<>();
if(root==null) return result;
TreeNode cur = root;
while(cur!=null || !s.empty()) {
while(cur!=null) {
result.add(cur.val);
s.push(cur);
cur = cur.right; //思想, 先访问右孩子的前序
}
TreeNode peek = s.pop();
cur = peek.left; //思想, 后访问左孩子的前序
}
Collections.reverse(result); //语法,//思想, 逆序
return result;
}
}
用栈迭代
下面的前序遍历代码相比于前一个更简洁一点, 也可以在这个基础上改后序, 但是需要添加标志位, 前序的话访问父节点的时候就直接访问元素, 再压栈右孩子, 左孩子(访问的话就左孩子, 右孩子了), 而后序的时候是第一次访问父节点的时候不访问元素, 而是在第二次访问父节点入栈右孩子和左孩子的时候再访问其元素.
前序遍历思路及代码
用栈来存放节点, 先入root, 然后如果栈不为空一直做一下事情:
- 出栈,
- 临时节点为空则继续
- 否则访问(前序遍历)
- 然后将临时节点的右孩子入栈
- 然后将临时节点的左孩子入栈
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
Stack<TreeNode> s = new Stack<>();
List<Integer> result = new ArrayList<>();
s.push(root);
while(!s.empty()){
TreeNode temp = s.pop(); //语法
if (temp==null) continue;
result.add(temp.val);
s.push(temp.right);
s.push(temp.left);
}
return result;
}
}
- 时间: O(N)
- 空间: O(logN)
后序遍历思路及代码
可以维护Pair的栈, 也可以维护一个标志位栈.
import java.util.AbstractMap;
//https://blog.csdn.net/allway2/article/details/117630517 java pair代替的五种方案.
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<Map.Entry<TreeNode,Boolean>> s = new Stack<>();
List<Integer> result = new ArrayList<>();
s.push(new AbstractMap.SimpleEntry<>(root, false));
while(!s.empty()){
TreeNode temp = s.peek().getKey(); //语法, 此时还不能出栈,
Boolean flag = s.peek().getValue();
s.pop();
if (temp==null) continue;
if (flag==true){ //第二次访问的时候才添加元素
result.add(temp.val);
}else{
s.push(new AbstractMap.SimpleEntry<>(temp, true));
s.push(new AbstractMap.SimpleEntry<>(temp.right, false));
s.push(new AbstractMap.SimpleEntry<>(temp.left, false));
}
}
return result;
}
}
/*
不用pair的话
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> s1 = new Stack<>();
Stack<Boolean> s2 = new Stack<>();
List<Integer> result = new ArrayList<>();
s1.push(root);
s2.push(false);
while(!s1.empty()){
TreeNode temp = s1.pop(); //语法
boolean falg = s2.pop();
if (temp==null) continue;
if (falg==true){
result.add(temp.val);
}else{
s1.push(temp);
s2.push(true);
s1.push(temp.right);
s2.push(false);
s1.push(temp.left);
s2.push(false);
}
}
return result;
}
}
*/
总结
先三种递归 => 模板(不要求递归的话) => 用栈迭代(后序不允许逆转).
102. 二叉树的层序遍历
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
奇淫巧计-用前序遍历实现(self
思路
只考虑答案的话, 只需要每次访问元素将其入到对应层数的数组中即可.
代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<List<Integer>>();//语法, 不要写成new LinkedList<LinkedList<Integer>>()
int height = getHeight(root); //思想, 目的是为了得到需要多少个内层list
for(int i = 0; i < height; i++) {
List<Integer> child_result= new LinkedList<Integer>();
result.add(child_result);
}
preOrder(root, 0, result); //思想, 前序遍历加入对应层数的list
return result;
}
private int getHeight(TreeNode node) {
if(node==null) return 0;
return Math.max(getHeight(node.left),getHeight(node.right))+1;
}
private void preOrder(TreeNode node, int i, List<List<Integer>> result) {
if (node==null) return;
result.get(i).add(node.val);
preOrder(node.left, i+1, result);
preOrder(node.right, i+1, result);
}
}
复杂度
- 时间: O(N)
- 空间: O(logN)
层次遍历*
思路
每次进入队后先得到队的长度, 用这个数字来for循环访问每一层的元素,但是是入的同一个队.
代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new LinkedList<List<Integer>>();
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(queue.size()!=0) {
int queueSize = queue.size();
LinkedList<Integer> levelResult = new LinkedList<>();
for (int i = 0; i < queueSize; i++) {
TreeNode cur = queue.poll();
if (cur!=null) {
levelResult.add(cur.val);
queue.add(cur.left);
queue.add(cur.right);
}
}
result.add(levelResult);
}
result.remove(result.size()-1);
//因为根节点为空, 再加上不加左右孩子判断空的话, 会多一个末尾的空list, 也可以在进入while循环前判断根节点不为空, 在在里面判断左右孩子不为空再入队, 这样就不用加cur!=null了, 我的是将空节点也入队了
return result;
}
}
/*
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
if (root == null) { //思想, 判空
return ret;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.offer(root);
while (!queue.isEmpty()) {
List<Integer> level = new ArrayList<Integer>();
int currentLevelSize = queue.size();
for (int i = 1; i <= currentLevelSize; ++i) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) { //思想, 不空的孩子才入
queue.offer(node.left);
}
if (node.right != null) { //思想, 不空的孩子才入
queue.offer(node.right);
}
}
ret.add(level);
}
return ret;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/er-cha-shu-de-ceng-xu-bian-li-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
复杂度
- 时间: O(N)
- 空间: O(N)
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
递归(self
思路
深度 = Max(左孩子深度, 右孩子深度) +1;
返回条件 = if (note==null) return 0;
代码
class Solution {
public int maxDepth(TreeNode root) {
if (root==null) return 0;
return Math.max(maxDepth(root.left), maxDepth(root.right))+1;
}
}
复杂度
- 时间: O(N)
- 空间: O(logN)
一行代码
思路
用了三元符
代码
class Solution {
public int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
}
复杂度
- 时间: O(N)
- 空间: O(N)
101. 对称二叉树
给定一个二叉树，检查它是否是镜像对称的。
遍历法(self, 做不出来
思路
先访问左孩子的后序遍历和先访问右孩子的后序遍历.
有些样例跑不过去, 所以应该不是等价条件.
迭代*
思路
描述
代码
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root==null) return true;
else return isSymmetricHelp(root.left, root.right);
}
private boolean isSymmetricHelp(TreeNode left, TreeNode right) {
if(left==null &&right==null) {
return true;
}else if(left==null && right!=null) { //思想, 重要的停止条件
return false;
}else if(left!=null&&right==null) { //思想, 重要的停止条件
return false;
}
return left.val==right.val&&isSymmetricHelp(left.left,right.right)&&(isSymmetricHelp(left.right, right.left));
}
}
/*
class Solution {
public boolean isSymmetric(TreeNode root) {
return check(root, root); //用了这么一个判断条件.
}
public boolean check(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}
if (p == null || q == null) { //语法, 这里简化了我上面的判断
return false;
}
return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}
}
*/
复杂度
- 时间: O(N)
- 空间: O(N)
226. 翻转二叉树
翻转一棵二叉树。
示例：
输入：
4
/ \
2 7
/ \ / \
1 3 6 9
输出：
4
/ \
7 2
/ \ / \
9 6 3 1
递归(self
思路
要注意原树左右孩子为空时, 将新树也赋值为空, 而不是新建节点, 官方的好简洁啊, 并且很清晰.
invertTree函数:
- 功能: 反转一个树并返回新树.
- 结束条件: 如果原树为空返回空.
- 其他: 原树不为空, 反转原树的左子树为新树的右子树(孩子), 反转原树的右子树为新树的左子树(孩子).
- 返回新树根节点.
代码
/*
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode left = invertTree(root.left);
TreeNode right = invertTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/invert-binary-tree/solution/fan-zhuan-er-cha-shu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
TreeNode result = new TreeNode();
if (root==null) return root;
setSymmetrix(root, result);
return result;
}
private void setSymmetrix(TreeNode left, TreeNode right) {
if (left==null) return;
right.val = left.val;
if (left.right==null) {
right.left = null; //思想
}
else {
right.left = new TreeNode();
setSymmetrix(left.right, right.left); //思想
}
if (left.left == null){
right.right = null; //思想
}
else{
right.right = new TreeNode();
setSymmetrix(left.left, right.right); //思想
}
}
}
复杂度
- 时间: O(N)
- 空间: O(N)
112. 路径总和
给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
改变原树使得节点的值为路径和(self
思路
先用改造的前序遍历使得节点的值为路径和.
然后再用前序遍历检查叶子节点的值是否为targetSum.
一开始想的时复制一条树, 使得树的节点既存储原节点的值, 也存储路径和, 但是发现需要修改TreeNode本身的结构, 所以再想着直接复制一条树, 但是这棵新树的节点值都是路径之和, 但是发现其实直接在原树上修改即可.
甚至可以不需要二次遍历, 在第一次构造的时候, 加判断叶子节点的话判断targetSum和已经构造出来的值是否相等, 相等的话就直接退出递归(这时候递归条件需要增加一个全局变量, 当满足条件时候改变全局变量之后一层一层直接退出递归).
代码
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
boolean []result = new boolean[1]; //语法, 因为直接传单个的boolean是值传递.
preOrderSum(root); //先修改树的节点为路径之和.
preOrder(root, targetSum, result); //前序遍历检查叶子节点的值是否等于targetSum
return result[0];
}
private void preOrderSum(TreeNode root) {
if(root==null) {
return;
}
if (root.left!=null) {
root.left.val += root.val;
}
if (root.right!=null) {
root.right.val+=root.val;
}
preOrderSum(root.left);
preOrderSum(root.right);
}
private void preOrder(TreeNode root, int targetSum, boolean[] result) {
if(root==null) {
return;
}
if (root.left==null&&root.right==null&&root.val == targetSum) result[0] = true;//前面的条件是为了判断叶子节点
preOrder(root.left, targetSum, result);
preOrder(root.right, targetSum, result);
}
}
/*复制一棵树, 我发现在复制一棵树的同时再修改节点的值需要多传递一个父节点的参数, 不能直接修改
private TreeNode copyTree(TreeNode root) {
if (root==null) return null;
else {
TreeNode result = new TreeNode(root.val);
result.left = copyTree(root.left);
result.right = copyTree(root.right);
return result;
}
}
*/
复杂度
- 时间: O(N)
- 空间: O(H)
递归*
思路
观察要求我们完成的函数，我们可以归纳出它的功能：询问是否存在从当前节点 root 到叶子节点的路径，满足其路径和为 sum。
假定从根节点到当前节点的值之和为 val，我们可以将这个大问题转化为一个小问题：是否存在从当前节点的子节点到叶子的路径，满足其路径和为 sum - val。
不难发现这满足递归的性质，若当前节点就是叶子节点，那么我们直接判断 sum 是否等于 val 即可（因为路径和已经确定，就是当前节点的值，我们只需要判断该路径和是否满足条件）。若当前节点不是叶子节点，我们只需要递归地询问它的子节点是否能满足条件即可。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
代码
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) {
return false;
}
if (root.left == null && root.right == null) {
return sum == root.val;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); //思想,//记忆,太妙了
}
}
复杂度
- 时间: O(N)
- 空间: O(H)
700. 二叉搜索树中的搜索
给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。
递归(self
思路
二分查找和遍历结构类似, 但是思想是极为不同的, 遍历因为要走所有一遍, 所以没有返回值. 而二分查找是找到了就不用往下找了, 所以在找到正确答案的时候直接返回即可.
代码
//记忆
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root==null) return null; //思想, 不要想太多, 这条语句只考虑空树的结果即可.
if (root.val==val) return root; //思想, 注意返回值
else if (root.val < val) return searchBST(root.right, val); //思想, 二分查找.
else return searchBST(root.left, val);
}
}
复杂度
- 时间: O(H)
- 空间: O(H)
迭代*
思路
迭代的思想太优美了, 当节点不为空(放在第一个条件)并且节点的值不等于目标值的时候, 根据二分查找将子树赋值给该节点继续判断.
代码
//记忆
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
while(root!=null&&root.val!=val){ //思想,妙啊
root = root.val<val?root.right:root.left;
}
return root;
}
}
复杂度
- 时间: O(H)
- 空间: O(1)
错误反思*
思路
用递归, 但是不是返回正确答案, 而是用返回参数,错在以下几个地方
- 空树的返回TreeNode(0)(不是重点)
result = root;这条语句不能改变在searchBST(TreeNode root, int val)中创建的result变量, 因为java中是值传递, 在preOrder中, 形参result是实参result的拷贝, 指向了root是拷贝的形参指向了root, 而不是实参result指向了result, 如果要这样使用, 那么必须改变TreeNode的结构, 增加一个setVal(val){this.val=val}方法, 然后调用该方法, 而不是赋值.
代码
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
TreeNode result = new TreeNode();
preOder(root, val, result);
return result;
}
private void preOrder(TreeNode root, int val, TreeNode result) {
if (root==null) return;
if (root.val == val) {
result = root; //错误, 这样不能改变实参的指向, 必须要用result.setVal(val)才可以
}else{
preOrder(root.left, val, result);
preOrder(root.right, val, result);
}
}
}
701. 二叉搜索树中的插入操作
给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 ，新值和原始二叉搜索树中的任意节点值都不同。
注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回 任意有效的结果 。
迭代(self
思路
要注意还得保存父节点, 另外要初始就判断是否为空, 因为根节点为空的话和后面的迭代操作不一样(直接赋值而不是将孩子赋值给父亲).
代码
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root==null) {
return new TreeNode(val); //思想
}
TreeNode node = root;
TreeNode father = root;
while(node!=null) {
father = node; //思想, 注意保存父节点
node = node.val<val?node.right:node.left;
}
node = new TreeNode(val);
if (father.val > node.val) father.left = node; //思想, 父节点大于子节点时, 左孩子为节点
else father.right = node;
return root;
}
}
复杂度
- 时间: O(H)
- 空间: O(1)
递归*
代码
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
//函数功能, 给以root节点为根节点的树插入val并返回插入后的新树
if (root==null) {
return new TreeNode(val);
}
if (root.val < val) {
root.right = insertIntoBST(root.right, val); //思想
}else{
root.left = insertIntoBST(root.left, val);
}
return root;
}
}
复杂度
- 时间: O(H)
- 空间: O(H)
98. 验证二叉搜索树
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树
错误的递归思想(self
思路
- 函数返回检验这颗树是否是二叉搜索树
- 如果根节点为空返回真
- 其他情况
- 如果左子树为空或者不为空的时候左子树小于根节点并且左子树为二叉搜索树标记为真.
- 如果右子树为空或者不为空的时候右子树大于根节点并且右子树为二叉搜索树标记为真.
- 当上面两者都为真时返回真
错误之处在于:
“二叉搜索树”的左节点小于根节点&&右节点大于根节点&&左右两棵子树都是”二叉搜素树”是 二叉搜素树 的必要条件而非充分条件. 也就是不等价, 例如
5
4 6
N N 3 7
上面的递归判断不能保证3也大于5.
代码
class Solution {
public boolean isValidBST(TreeNode root) {
boolean is_left = true;
boolean is_right = true;
if(root==null) return true;
if (root.left!=null){
is_left = root.left.val<root.val&&isValidBST(root.left);
}
if(root.right!=null) {
is_right = root.right.val>root.val&&isValidBST(root.right);
}
return is_left&&is_right;
}
}
复杂度
- 时间:
- 空间:
正确的递归*
思路
传入该节点的最大值和最小值
代码
class Solution {
public boolean isValidBST(TreeNode root) {
return isValidBSTHelp(root, Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY); //语法, 要注意无穷大常量全都是大写字母, 不能用Integer的无穷大, 因为会卡边界值
}
boolean isValidBSTHelp(TreeNode node, double max, double min) {
if (node==null) return true;
return node.val<max&&node.val>min&&isValidBSTHelp(node.left, node.val, min)&&isValidBSTHelp(node.right, max, node.val);//思想
}
}
复杂度
- 时间: O(N)
- 空间: O(H)
中序遍历的结果为递增*
思路
中序遍历存储进数组, 必然为递增序列, 此时用Integer足以
代码
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> l = new ArrayList<Integer>();
midOrder(root, l);
boolean flag = true;
for(int i = 0; i < l.size()-1; i++){
if(l.get(i) >= l.get(i+1)) {
flag = false;
return flag;
}
}
return flag;
}
void midOrder(TreeNode root, List<Integer> l) {
if(root==null) return;
midOrder(root.left, l);
l.add(root.val);
midOrder(root.right, l);
}
}
复杂度
- 时间: O(N)
- 空间: O(H)(迭代中序的话可以为O(1))
653. 两数之和 IV - 输入 BST
给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。
层次遍历进集合,进之前先判断(self
思路
层次遍历(队列方式)元素进集合,进之前先判断集合前有没有target-该元素, 有的话则找到(可以一般情况和分辨taregt-该元素=该元素值), 没有话则入set, 这个技巧我觉得挺好的.
另外遍历前中后序都可以, 核心思想是在加入set前判断是否存在target-val
代码
class Solution {
public boolean findTarget(TreeNode root, int k) {
boolean result = false;
Queue<TreeNode> q = new LinkedList<>();
Set<Integer> s = new HashSet();
TreeNode cur = root;
q.offer(root);
while(q.size()!=0) {
int size = q.size();
for(int i = 0; i < size; i++) {
cur = q.poll();
if (cur==null) continue; //思想,左右孩子前一定要判断cur是否为空
q.offer(cur.left);
q.offer(cur.right);
if(s.contains(k-cur.val)){ //思想(核心), trick
result = true;
return result;
}
s.add(cur.val);
}
}
return result;
}
}
复杂度
- 时间: O(N)
- 空间: O(N)
双指针*
思路
方法二：叉搜索树的中序遍历为递增序列，所以我们可以利用这个升序的序列寻找k。 使用双指针，分别指向头、尾。如果两数之和大于target，尾指针前移，如果两数之和小于target，首指针后移。
leetcode题目评论
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
递归(self
思路
明确以下事情:
- 函数是干什么的: 传递根节点
root, 需要搜寻的节点p,q, 返回在以根节点root为树的最近公共祖先 - 最简单返回条件: 如果root为空的话直接返回root
- 其他情况下
- 如果p和q的值都比root的大的话, 那调用该方法, 在root.right上继续寻找
- 其他如果p和q的值都比root的小的话, 那调用该方法, 在root.left上继续寻找.
- 其他情况下(p的值有一个与root相等或者其中有一个比root大并且另一个比root小的话)都返回root
可以看到, 其实, 我们做一道题就是在找问题的能用数据结构表示的等价说明(一句有用的废话)
代码
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null) return null;
if(p.val>root.val&&q.val>root.val) {
return lowestCommonAncestor(root.right, p, q);
}else if(p.val<root.val&&q.val<root.val) {
return lowestCommonAncestor(root.left, p, q);
}else {
return root;
}
}
}
复杂度
- 时间: O(H)
- 空间: O(H)
思想2名称*
思路
描述
代码
复杂度
- 时间:
- 空间:
207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
拓扑排序(self
思路
拓扑排序算法:
- 计算所有节点的入度, 将入度为0的节点加入队列
- 遍历队列, 将队列的节点出队列并且将出的节点所指向的节点的入度减1,
- 入度为0的队列遍历完之后, 还存在入度不为0的节点, 则说明存在环.
代码
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
Queue<Integer> s = new LinkedList<Integer>();
List<List<Integer>> graph = new ArrayList<>();
int[] inDegree = new int[numCourses];
//初始图
for(int i = 0; i < numCourses; i++) {
List<Integer> graph_item = new ArrayList<>();
graph.add(graph_item);
}
//计算入度和建图
for(int i = 0; i < prerequisites.length; i++) {
inDegree[prerequisites[i][1]]+=1;
graph.get(prerequisites[i][0]).add(prerequisites[i][1]);
}
//将入度为0的节点加入队列
for(int i = 0; i < numCourses; i++) {
if(inDegree[i] == 0) s.add(i);
}
while(s.size() != 0) {
int head = s.remove();
for(int i = 0; i < graph.get(head).size(); i++) {
inDegree[graph.get(head).get(i)]--;
if(inDegree[graph.get(head).get(i)]==0) {
s.add(graph.get(head).get(i));
}
}
}
//如果删除入度后还有入度不为0, 也就时存在环
for(int i = 0; i < numCourses; i++) {
if (inDegree[i] != 0) return false;
}
return true;
}
}
复杂度
- 时间: $O(n+e)$
- 空间: $O(n)$
欢迎在评论区中进行批评指正，转载请注明来源，如涉及侵权，请联系作者删除。
