LeetCode100题持续更新中
1、动态规划1.1 爬楼梯 (70)
标题：
https://i-blog.csdnimg.cn/direct/3c30785182ce4bbc928a6b0b6f371ed1.png
分析：f 表示从第1层爬到第i层阶梯有多少种方法，i = 1…n。
状态转移方程：f = f + f
明白：末了一步有两种可能，可能爬 1 阶，也可能爬 2阶，假如爬1阶，子问题为 f；假如爬2阶，子问题为 f; 都有可能，以是加起来。
初始化： f = 1, f = 1；要凑 f = 2，以是 f = 1
class Solution {
public int climbStairs(int n) {
int[] ans = new int;
ans= 1;
ans= 1;
for(int i = 2;i<= n;i++)
{
ans = ans +ans;
}
return ans;
}
}
1.2 杨辉三角 (118)
标题：
https://i-blog.csdnimg.cn/direct/bd9f4b0b53ad4424bd0a2a425e1695a5.png
留意：numRows>=1；
分析：
List<List<Integer>> 这是返回类型，选取数据结构很重要，要遍历输出，选取HashMap<Integer,<List<Integer>>> 作为存储结构。此中List<Integer> 选取ArrayList<>()作为存储结构。然后，留意到边缘位置全是1，然后非边缘位置 l 是上一层 l + l。
代码：
class Solution {
public List<List<Integer>> generate(int numRows) {
Map<Integer,List<Integer>> hp = new HashMap<>();
List<List<Integer>> ans = new ArrayList<>();
for(int i = 1;i<=numRows;i++)
{
List<Integer> l = new ArrayList<>();
for(int j = 0;j<i;j++)// 第i行恰好有i个元素，开始赋值
{
if(j == 0 || j == i-1)
l.add(1);
else
{
// 拿到上一层的list
List<Integer> le = hp.get(i-1);
// 例如：l = le+le
l.add(le.get(j-1)+le.get(j));
}
}
hp.put(i,l);// 只是为记忆上一层
ans.add(l);
}
return ans;
}
}
1.3 打家劫舍 (198)
标题：
https://i-blog.csdnimg.cn/direct/627a307c1abb4493a354630716fb4eaa.png
分析：
非负，这是一个很关键信息，因为如许表示状态时可以用前 i 个元素的最大目标值作为状态；不难分析到这是一个选与不选问题,状态转移方程如下：
d p [ i ] = m a x ( d p [ i − 2 ] + n u m s [ i ] , d p [ i − 1 ] ) \mathrm{ dp = max(dp+nums,dp)} dp=max(dp+nums,dp)
此中 d p [ i ] \mathrm{dp} dp 表示的是下标为 0 - i 元素的最大目标值； d p [ 0 ] = n u m s [ 0 ] \mathrm{dp = nums} dp=nums。
代码：
class Solution {
public int rob(int[] nums) {
int[] dp = new int;
dp = nums;
if(nums.length>1)// 原因 从2开始，防止越界
dp = Math.max(nums,nums);
for(int i =2;i<nums.length;i++)
{
dp = Math.max(dp,dp+nums);
}
return dp;
}
}
1.4 完全平方数 (279)
标题：
https://i-blog.csdnimg.cn/direct/688bd31735784c52af8cdd5e9e16eb5e.png
分析：关键是怎样确定一个数可以被平方数+数来表示，进而转换为子问题，状态转移方程有：
d p [ i ] = m i n ( d p [ i ] , d p [ i − j ∗ j ] + 1 ) \mathrm{dp=min(dp,dp+1)} dp=min(dp,dp+1)
此中 d p [ i ] \mathrm{dp} dp表示的是数字 i 最少可以用几个平方数来表示， i − j ∗ j ≥ 0 \mathrm{i-j*j\ge0} i−j∗j≥0, dp = 0。
代码：
class Solution {
public int numSquares(int n) {
// dp = 0，是因为如果一个数据本身就是平方数 dp=0, 即 dp+1 = 1
int[] dp = new int;
dp = 0;
for(int i = 1;i<=n;i++ )
{
dp = i;//最大值，尽量避免使用Integer.MAX_VALUE
for(int j = 0;j*j<=i;j++)
{
dp = Math.min(dp,dp+1);
}
}
return dp;
}
}
1.5 零钱兑换 (322)
标题：https://i-blog.csdnimg.cn/direct/ed656bcf29034d3b967e1d38b00b54ad.png
分析：
怎样定义状态变量，转换成子问题，才是关键，要想计算 dp ，不难想到其子问题是 dp ,当然，对于每一个硬币coin都要进行相减，以是状态转移方程有：
d p [ i ] = m i n ( d p [ i ] , d p [ i − c o i n ] + 1 ) \mathrm{dp = min(dp,dp+1)} dp=min(dp,dp+1)
此中 dp 表示能构成金额i的最小硬币数量，dp = 0.
代码：
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp= new int;
dp =0;// 表示金额0肯定是0 个硬币数量
for(int i =1;i<=amount;i++)
{
dp = amount+1;// 这是一个不可能的最大值
for(int coin: coins)
{
if(i>=coin)
{
dp = Math.min(dp,dp+1);
}
}
}
if(dp == amount+1)
{
return-1;
}
else
{
return dp;
}
}
}
1.6 单词划分 (139)
标题：https://i-blog.csdnimg.cn/direct/cd700c8c516a4bc0b56b12d81b32a9ad.png
分析：
要转换为子问题，先定义好一个状态变量（父问题），再找子问题，dp 表示的是 s - s 能否被字典划分 , i = 1,2,3…s.length(), 对于每一个状态定义都要严丝合缝; 寻找子问题, 对于字典中的每一个单词, 都要看 s - s 是否满足是该单词, 而且dp为true, 也就是说 s - s 可以被划分; 都满足, OK 令 dp = true. 状态转移方程为:
d p [ i ] = i − w o r d . l e n g t h ( ) ≥ 0 ∧ d p [ i − w o r d . l e n g t h ( ) ] ∧ w o r d = = s u b ( s ) \mathrm{dp = i-word.length()\ge0 \wedge dp \wedge word == sub(s) } dp=i−word.length()≥0∧dp∧word==sub(s)
此中 dp[ 0] = true, 缘故原由就是假如sub(s)本来就是从头开始, dp = true 可以不影响我们对该字串的判定.
代码:
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
// 从 i=1 开始判断dp 表示 s-s 能否 被划分
// dp = true;
// dp 表示 s 能否划分
// dp = &&s(i-word.length: i-1) == word] or (nextword)
int s_len = s.length();
boolean[] dp = new boolean;
dp = true;
for(int i = 1;i<=s_len;i++)
{
for(String word : wordDict)
{
// l e e t c odedp 为例
// 0 1 2 3 4 dp
int leftIndex = i - word.length();// 当前可能匹配单词的起始左下标
if(leftIndex>=0 && dp && word.equals(s.substring(leftIndex,i)))
{
dp = true;
break;//只要找到一个就可以
}
}
}
return dp;
}
}
1.7 最长递增子序列 (300)
标题：
https://i-blog.csdnimg.cn/direct/4a656565e57d410c8cd859eba3acf24d.png
分析：
定义状态变量dp 表示 以 下标 i 为结尾的最长子序列长度， 子问题就是，假如当前 nums 大于 nums , j = 0…i-1 , dp = max( dp , dp + 1)
代码：
class Solution {
public int lengthOfLIS(int[] nums) {
//i 01 2 3 4 5
//num4,10,4,3,8,9
//dp 12 2 2 3 4
//如果dp 0-i元素的最大值子序列长度，我们会发现会出错，dp = 3，因为8虽然大于3，dp = 2，
//但是dp显然等于2，因为dp = 2,不是以3结尾的最长长度，所以不能用dp表示0-i元素的最大值子序列长度
// dp 表示 以 i 为结尾的最长子序列长度
int[] dp = new int;
dp = 1;
int maxlen = 1;
for(int i = 1;i<nums.length;i++)
{
dp = 1; // 如果nums 无法和之前元素构成更长子序列，那么dp = 1
for(int j = 0;j<i;j++)// 因为它可能和所有0-----i-1 构成更长子序列
{
if(nums>nums)
{
dp = Math.max(dp,dp+1);
}
}
if(dp>maxlen)
maxlen = dp;
}
return maxlen;
}
}
1.8 乘积最大子数组 (152)
标题：
https://i-blog.csdnimg.cn/direct/47ebdb611cb34a2eb1bfc7059a3b71c2.png
分析：
最大从哪里来，这是化解为子问题的关键，当然，标题变为最小也一样。审题：非空一连。 maxdp 代表以下标i为结尾的最大值,只和nums,maxdp,mindp 有关。
例如： -2 1 -3 dp = 6 要用到mindp = -2，以是要记载最小也要记载下来。
状态转移方程为：
m a x d p [ i ] = m a x ( d [ i ] , m a x d p [ i − 1 ] ∗ n u m s [ i ] , m i n d p [ i − 1 ] ∗ n u m s [ i ] ) \mathrm{maxdp = max(d,maxdp*nums,mindp*nums)} maxdp=max(d,maxdp∗nums,mindp∗nums)
代码：
class Solution {
public int maxProduct(int[] nums) {
int n = nums.length;
int[] maxdp = new int;
int[] mindp = new int;
maxdp = nums;
mindp = nums;
int max= nums;
for(int i =1;i<n;i++)
{
maxdp = Math.max(Math.max(nums*mindp,nums*maxdp),nums);
mindp = Math.min(Math.min(nums*mindp,nums*maxdp),nums);
if(maxdp>max)
{
max = maxdp;
}
}
return max;
}
}
1.9 分割等和子集 (416)
标题：
https://i-blog.csdnimg.cn/direct/22be215b72c24f89bff5d559e263613e.png
分析：
和不是偶数，无解；和为偶数，转换为0-1背包问题
现在变成了恰恰型背包问题 实在就是0-1背包问题，就是要求我们装满而已。
我们把其想成nums想成体积,背包涵量为sum, 每一个价值对应为nums。
有人就可能问了，背包问题不是解决的是 不凌驾容量s的最大价值，和这个装满s能一样吗？
答：当然是一样的，因为我们设定所有物品单位体积的价值都为1，能装满就说明价值也是最大的。
不同在于，背包问题找到使价值最大的解(不一定为s)，我们的问题是在此基础上能否找到使最大价值为s的解，也就是能装满的解。
代码：
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int num:nums)
{
sum += num;
}
if(sum%2 == 1) return false; // 奇数就肯定不能分成了，因为都是正整数
int s = sum/2; // 背包容量
// 现在变成了恰好型背包问题其实就是0-1背包问题，就是要求我们装满而已，
// 我们把其想成nums想成体积,背包容量为sum, 每一个价值对应为nums,
// 有人就可能问了，背包问题不是解决的是 不超过容量s的最大价值，和这个装满s能一样吗
// 当然是一样的，因为我们设定所有物品单位体积的价值都为1，能转满就说明价值也是最大的
// 不同在于，背包问题使价值最大的解(不一定为s)，我们的问题是在此基础上能否找到使最大价值为s的解，也就是能装满的解
int n = nums.length;
int[][] dp = new int;
// dp 代表把第i个物品(i=1---n 对应的物品是num - nums)放到体积为j的最大值,
// dp 与dp 代表边界，初始化为0
for(int i =1;i<=n;i++)
{
for(int j=1;j<=s;j++)
{
dp = dp;// 第i件物品不装
if(j-nums>=0)// 第i件物品能装得下
{
dp = Math.max(dp,dp]+nums);
}
}
}
if(dp==s)// 把n件物品放入到体积为s的恰好装满，true
{
return true;
}
else
{
return false;
}
}
}
1.10 最大子数组和 (53)
标题：
https://i-blog.csdnimg.cn/direct/ebbb0aa5d0e941f8a689de32d1b0e723.png
分析:
dp 表示以下标i为结尾最大值，dp=nums,递推关系为：
d p [ i ] = m a x ( n u m s [ i ] , n u m s [ i ] + d p [ i − 1 ] ) \mathrm{dp = max(nums,nums+dp)} dp=max(nums,nums+dp)
代码：
class Solution {
public int maxSubArray(int[] nums) {
// 100 -1 -1 2 2 90 dp 不能表示前0-i最大值了,没法构造子问题
// 连续
// 动态规划 dp 表示以i为结尾最大值
int[] dp = new int;
dp = nums;
int max = nums;
for(int i = 1;i<nums.length;i++)
{
dp = Math.max(nums,nums+dp);//没有dp
if(dp>max)
{
max = dp;
}
}
return max;
}
}
2、位运算
2.1 只出现一次的数字（136）
标题：
https://i-blog.csdnimg.cn/direct/9e32be3eaa4c4b4290c2ef68df5f26f3.png
分析：常量空间，要么是双指针，要么是位运算；本题使用异或。
知识储备：
任何整数^0 = 该任何整数
任何整数^该任何整数 = 0
由于异或和次序没关系，直接异或解决。
代码：
class Solution {
public int singleNumber(int[] nums) {
// 常量
// 非二进制也能位运算 太强大了1^1为0 0^任何数 = 任何数
// 1^2 = 3我们用不到
int ans = 0;
for(int num:nums)
{
ans = ans^num;
}
return ans;
}
}
3、哈希
3.1 两数之和（1）
问题：https://i-blog.csdnimg.cn/direct/669f35e677cf479aab056bbfc36aa9f1.png
分析：
假如知道值直接获得下标的话，省去O（n）判定，以是遐想到哈希表。
代码:
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> hp = new HashMap<>();
for(int i = 0;i<nums.length;i++)
{
if(hp.containsKey(target-nums)) // containsKey
{
return new int[]{hp.get(target-nums),i};
}
else
{
hp.put(nums,i);
}
}
return new int;
}
}
3.2 字母异位词 (49)
问题:
https://i-blog.csdnimg.cn/direct/8aa10e4770c14bee81daef48b5ae2ef9.png
分析:
键是关键，小写字母是关键，String 当键
代码:
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
// 键:
// API:
HashMap<String,List<String>> hp = new HashMap<>();
for(String s: strs)
{
char[]ch = s.toCharArray(); //String 转 字符数组
Arrays.sort(ch);// 原地排序
String sKey = new String(ch);// 字符数组转字符串
if(hp.containsKey(sKey))//如果hashmap有同类
{
List<String> l = hp.get(sKey);
l.add(s);
hp.put(sKey,l);
}
else// 如果HashMap不存在同类
{
List<String> le = new ArrayList<>();
le.add(s);
hp.put(sKey,le);
}
/*
List<String> li = hp.getOrDefault(sKey,new ArrayList<>());
li.add(str);
ht.put(sKey,li);可以用这个替换 if else
*/
}
//第一种方式
List<List<String>> valuesList2 = hp.values().stream().collect(Collectors.toList());
//第二种方式
List<List<String>> valuesList = new ArrayList<>(hp.values());
return valuesList;
}
}
3.3 最长一连序列 (128)
问题：
https://i-blog.csdnimg.cn/direct/a29d39a25ec8418780374e21ba7902c4.png
分析:一开始我是想着用HashMap,但是什么是键，什么是值，比力难搞。 HashSet 唯一好处是什么呢，唯一性和查找O(1)。去重后，遍历每一个值，找最大长度。
代码：
class Solution {
public int longestConsecutive(int[] nums) {
// 一看就是面试高频题目 确实忘了
// O(n)
HashSet<Integer> hs = new HashSet<>();
for(int num : nums)
{
hs.add(num);
}// 去重
int L=0;
for(int num :hs)
{
int l=0;
int n=num;
while(!hs.contains(num-1)&&hs.contains(n))
{
l++;
n++;
}
L=Math.max(l,L);
}
return L;
}
}
4、技巧类
4.1 多数元素 (169)
问题:
https://i-blog.csdnimg.cn/direct/1c7f1f45f0c4437ab56e5a1f494a1949.png
分析：
重要是要满足时间复杂度和空间复杂度要求，使用投票抵消算法。只要不同就抵消！
以 2 3 1 1 1 4 2为例
初始化vote = 0
遍历序列
假如vote = 0, 令当前元素选为当前候选人，vote++ ，记载候选人 candidate
假如vote > 0, 当前元素不等于候选人元素，vote–;
当前元素不等于候选人元素，vote++;
代码:
class Solution {
public int majorityElement(int[] nums) {
int vote = 0;
int candidate = nums;
for(int num:nums)
{
if(vote == 0)
{
candidate = num;
vote++;
}
else
{
if(num == candidate)
{
vote++;
}
else
{
vote--;
}
}
}
return candidate;
}
}
4.2 轮转数组（189）
问题：
https://i-blog.csdnimg.cn/direct/3e7346815114467aada14cbcd4a28790.png
分析：
关键是时间复杂度O(n),空间复杂度O(1)
思路还是比力难想的
reverse(0,n-1) // 反转全部
reverse(0,k-1) // 反转前k个
reverse(k,n-1) // 反转后n-k个
留意要把k = k%n,保证正确性
代码：
class Solution {
public void rotate(int[] nums, int k) {
// 如果有原地操作
// 全部反转
// 反转前k个
// 反转后n-k个
k= k % nums.length;// 关键点
// O(1)空间
reverse(nums,0,nums.length-1);
reverse(nums,0,k-1);
reverse(nums,k,nums.length-1);
}
private void reverse(int[] nums,int l,int r)
{
int temp =0;
while(l<r)
{
temp = nums;
nums = nums;
nums = temp;
l++;
r--;
}
}
}
4.3 合并区间 （56）
问题：
https://i-blog.csdnimg.cn/direct/58249d61081d41e4a5a7f2f2eb32fab8.png
分析：思路很简朴，先根据二维数组中每一个一维数组的首元素从小到大排序，数据结构选取也很重要，先把第一个放进去，然后从第个开始判定，若能合并，合并；不能合并，把它放进去，每一次比力是刚刚放进去的那个。
代码：
class Solution {
public int[][] merge(int[][] intervals) {
// 长度未知每一个元素是数组
List<int[]> l = new ArrayList<>();
// 按照左端点排序
Arrays.sort(intervals,(p,q)->p-q);
// 思路：
l.add(intervals);
int k = 0;
for(int i = 1;i<intervals.length;i++)
{
if(intervals<=l.get(k))
{
l.get(k) = Math.max(intervals,l.get(k));
}
else
{
l.add(intervals);
k++;
}
}
returnl.toArray(new int[]);
}
}
4.4 除自身以外数组的乘积 （238）
问题：
https://i-blog.csdnimg.cn/direct/1b44e02d26054ed6ae26b986eba0405c.png
分析：
以 1 2 3 4 为例
1 2 3 4
1 1 3 4
1 2 1 4
1 2 3 1
想要的结果是每一行连乘
ans234
ans134
ans124
ans123
先算左下三角(从上往下算)：
ans1
ans1×2
ans1×2×3
再算右下三角(从下往上算)：再和之前ans相乘
ans 4×3×2
ans 4×3
ans 4
代码：
class Solution {
public int[] productExceptSelf(int[] nums) {
int[] ans = new int;
ans= 1;
for(int i =1;i<nums.length;i++)
{
ans = ans*nums;
}
int temp =1;
for(int j =nums.length-2;j>=0;j--)
{
temp = temp*nums;
ans = temp*ans;
}
return ans;
}
}
4.5 矩阵置零（73）
问题：
https://i-blog.csdnimg.cn/direct/d24f2df9c38b4346b45df4f9c2c1b1eb.png
分析：分别用O(m+n)和O(1)空间复杂度实现,第一种用集合记载为0的行和列，第二种先找到为0的行和列，让那一行和列来做标志位。
代码：
// O(m+n)
class Solution {
public void setZeroes(int[][] matrix) {
// API要熟悉
HashSet<Integer> r = new HashSet<>();
HashSet<Integer> c = new HashSet<>();
for(int i = 0;i<matrix.length;i++)
{
for(int j =0;j<matrix.length;j++)
{
if(matrix == 0)
{
r.add(i);
c.add(j);
}
}
}
for(int i:r)
{
for(int j =0;j<matrix.length;j++)
{
matrix = 0;
}
}
for(int j:c)
{
for(int i =0;i<matrix.length;i++)
{
matrix = 0;
}
}
}
}
// O(1)
class Solution {
public void setZeroes(int[][] matrix) {
int m = matrix.length;
int n = matrix.length;
int iz = m+1;
int jz = n+1;
// 找首次出现0的位置
for(int i = 0;i<m;i++)
for(int j =0;j<n;j++)
{
if(matrix==0)
{
iz = i;
jz = j;
break;
}
}
// 没找到，就不用找了
if(iz == m+1) return;
// 假设 iz = 1 jz = 2
// 先把其所在行列都变为0 如果一开始为0，变为-1,当然也包含matrix
for(int j = 0;j<n;j++)
{
if(matrix==0)
{
matrix = -1;
}
else
matrix = 0;
}
for(int i = 0;i<m;i++)
{
if(matrix==0)
{
matrix = -1;
}
else
matrix = 0;
}
// 遍历全部（除了那一行和那一列），若发现0,变为-1
for(int i = 0;i<m;i++)
{
if(i!=iz)
{
for(int j =0;j<n;j++)
{
if(j!=jz)
{
if(matrix==0)
{
matrix = -1;
matrix = -1;
}
}
}
}
}
// 除了iz,jz所在行和列根据结果 分别置为0
// 所有行置为0
for(int i = 0;i<m;i++)
{
if(i!=iz&&matrix==-1)
{
for(int j = 0;j<n;j++)
{
if(j!=jz)
{
matrix = 0;
}
}
}
}
// 所有列置为0
for(int j = 0;j<n;j++)
{
if(j!=jz&&matrix==-1)
{
for(int i = 0;i<m;i++)
{
if(i!=iz)
{
matrix = 0;
}
}
}
}
// iz jz行列置0
// 行为 0
for(int j = 0;j<n;j++)
{
matrix = 0;
}
// 列为 0
for(int i = 0;i<m;i++)
{
matrix = 0;
}
}}
4.6 螺旋矩阵（54）
问题：
https://i-blog.csdnimg.cn/direct/e369a19369c04cc08094d86b49235fe9.png
分析：每一圈递归一次，出口是一行，一列，或者没有
代码：
class Solution {
void cycle(int[][] matrix,List<Integer> list,int row_1,int row_2,int co_1,int co_2)
{
if(co_1>co_2||row_1>row_2)
{
return ;
}
if(co_1==co_2)
{
for(int i = row_1;i<=row_2;i++)
{
list.add(matrix);
}
return;
}
if(row_1==row_2)
{
for(int j = co_1;j<=co_2;j++)
{
list.add(matrix);
}
return;
}
for(int j = co_1;j<=co_2;j++)
{
list.add(matrix);
}
for(int i = row_1+1;i<row_2;i++)
{
list.add(matrix);
}
for(int j = co_2;j>=co_1;j--)
{
list.add(matrix);
}
for(int i = row_2-1;i>row_1;i--)
{
list.add(matrix);
}
cycle(matrix,list,row_1+1,row_2-1,co_1+1,co_2-1);
}
public List<Integer> spiralOrder(int[][] matrix) {
// row_1row_2co_1 co_2
List<Integer> list = new ArrayList<>();
cycle(matrix,list,0,matrix.length-1,0,matrix.length-1);
return list;
}
}
4.7 旋转图像（48）
标题：
https://i-blog.csdnimg.cn/direct/1ff9cc37f73d4cec84629ccdd78108ae.png
分析：
矩阵知识，旋转90°，要转置+每行反转
代码:
class Solution {
public void rotate(int[][] matrix) {
// 字节面试题
// 原地
// 转置+反转
int n = matrix.length;
for(int i = 0; i<n ; i++)
{
for(int j = 0;j<i;j++)
{
int temp = matrix;
matrix = matrix;
matrix = temp;
}
}
for(int i = 0; i<n; i++)
{
int l = 0;
int r = n-1;
while(l<r)
{
int temp = matrix;
matrix = matrix;
matrix =temp;
l++;
r--;
}
}
}
}
5、 双指针
5.1 移动零
问题：
https://i-blog.csdnimg.cn/direct/fb42fa4d21434eb7bedfec4b6f8d89e5.png
分析：
第一个指针之前为已经ok的，先找到这个位置，放数即可。
代码：
class Solution {
public void moveZeroes(int[] nums) {
int firstZero = -1;//
// 先找到第一个为0 的位置
for(int i = 0;i<nums.length;i++)
{
if(nums==0)
{
firstZero = i;
break;
}
}
if(firstZero==-1) return;
int i = firstZero;// 第一个为0的位置,前面为ok的
for(int j = firstZero+1;j<nums.length;j++)
{
if(nums!=0)
{
nums = nums;
nums = 0;
i++;
}
}
}
}
6、链表
6.1 相交链表 (160)
问题：
https://i-blog.csdnimg.cn/direct/92e41ebf94324195a4017788c22ccfa6.png
分析：
我走过你来时的路，要么相遇，要么同时走到null。
代码：
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 双指针，我走过的你走过的路
// 各至少一个节点
ListNode pNode = headA;
ListNode qNode = headB;
// 如果
while(pNode!=qNode)
{
if(pNode!=null)
{
pNode = pNode.next;
}
else
{
pNode = headB;
}
if(qNode!=null)
{
qNode = qNode.next;
}
else
{
qNode = headA;
}
}
return pNode;
}
}
6.2 反转链表（206）
问题：
https://i-blog.csdnimg.cn/direct/788688c8fb4f49dd8cc7fc24c2d065bd.png
分析：
两种方式，模板，最常见，必须快准稳
代码：
class Solution {
public ListNode reverseList(ListNode head) {
// 头插法模板一样，必须快准稳
// 1.先尝试不带头节点
/*
ListNode pNode = head;
ListNode newHead = null;
ListNode qNode = null;
while(pNode!=null)
{
qNode = pNode.next;
pNode.next = newHead;
newHead = pNode;
pNode = qNode;
}
return newHead;*/
// 2、虚拟头节点 可能更好理解
ListNode dummy = new ListNode(0,null);
ListNode pNode = head;
ListNode qNode = null;
while(pNode!=null)
{
qNode = pNode.next;
pNode.next = dummy.next;
dummy.next = pNode;
pNode = qNode;
}
return dummy.next;
}
}
6.3 回文链表 （234）
问题：
判定链表是否为回文序列
分析：
双指针+链表反转，面试的时候一定要翻转过来
代码：
class Solution {
public boolean isPalindrome(ListNode head) {
//用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题
if(head.next==null) return true;
// 找node的方法优化一下 前后指针 双指针找中间节点 奇数就是中间那个，偶数就是1234中的2
ListNode node = head;
ListNode node2 = head;
while(node2!=null&&node2.next!=null&&node2.next.next!=null)
{
node = node.next;
node2 = node2.next.next;
}
ListNode qNode = node.next;
node.next = null;
// node 就当作dummy节点
// 反转node后面的节点
ListNode pNode =null;
while(qNode!=null)
{
pNode = qNode.next;
qNode.next = node.next;
node.next = qNode;
qNode =pNode;
}
pNode = node.next;
qNode = head;
boolean ans = true;
while(pNode!=null)
{
if(pNode.val!=qNode.val)
{
ans = false;
}
pNode = pNode.next;
qNode = qNode.next;
}
// 再反转过来
qNode = node.next;
node.next = null;
while(qNode!=null)
{
pNode = qNode.next;
qNode.next = node.next;
node.next = qNode;
qNode = pNode;
}
// 现在
return ans;
}
}
7、二叉树
7.1 二叉树的中序遍历 (94)
代码：
class Solution {
/*
List<Integer> list = new ArrayList<>();
public List<Integer> inorderTraversal(TreeNode root) {
if(root!=null)
{
inorderTraversal(root.left);
list.add(root.val);
inorderTraversal(root.right);
}
return list;
}} */
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
// 注意啦，这里是Deque
Deque<TreeNode> stack = new ArrayDeque<>();// 双端队列 模拟栈的操作
TreeNode cur = root;
while(!stack.isEmpty()||cur!=null)
{
// 若 存在左边一直入栈
while(cur!=null)
{
stack.push(cur);
cur = cur.left;
}
// 出栈
cur = stack.pop();
list.add(cur.val);
// 指向右子树
cur = cur.right;
}
return list;
}
}
7.2 二叉树的最大深度（104）
代码：
class Solution {
public int maxDepth(TreeNode root) {
if(root==null) return 0;
int lh = maxDepth(root.left);
int rh = maxDepth(root.right);
return Math.max(lh,rh)+1;
}
}
7.3 反转二叉树（226）
class Solution {
public TreeNode invertTree(TreeNode root) {
if(root == null)
{
return null;
}
TreeNode left =invertTree(root.left);
TreeNode right = invertTree(root.right);
TreeNode temp = left;
root.left =right;
root.right = temp;
return root;
}
}
7.4 对称二叉树（101）
代码：
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root==null)
{
return true;
}
return dfs(root.left,root.right);
}
//判断左右子树是否对称
boolean dfs(TreeNode left,TreeNode right)
{
// 左右子树都为空 对称
if(left==null&&right==null) return true;
// 左(右)子树为空且右(左)子树不为空不对称
if(left==null&&right!=null||left!=null&&right==null)
{
return false;
}
// 都不为空 只有这三个条件同时成立才对称
// 1.左右子树的节点值相同
boolean a = left.val==right.val;
// 2.左子树的左子树和右子树的右子树相同
boolean b = dfs(left.left,right.right);
// 3.左子树的右子树和左子树的右子树相同
boolean c = dfs(left.right,right.left);
return a&&b&&c;
}
}
7.5 二叉树的直径(543)
问题形貌：
https://i-blog.csdnimg.cn/direct/2e231b501b384fa4b94706bcf87bb1ad.png
代码:
转换成求高度
class Solution {
int ans = 0;
public int diameterOfBinaryTree(TreeNode root) {
height(root);
return ans;
}
// height 代表高度
// 节点个数为1 高度为1
int height(TreeNode root)
{
if(root == null) return 0;
int leftHeight = height(root.left);
int rightHeight = height(root.right);
ans = Math.max(ans,leftHeight+rightHeight);
return 1+(leftHeight>rightHeight?leftHeight:rightHeight);
}
}
7.6 二叉树最大路径和 （124）
标题：
https://i-blog.csdnimg.cn/direct/4e791643fa0a451ba9f088e0305b53e0.png
分析和代码: 和二叉树直径，有同工异曲之妙，它那个是借助左高度，右高度更新max;咱这个是左节点最大路径和以及右节点的最大路径和更新max,只不外假如为小于0，就不到场。
class Solution {
intmax = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
dfs(root);
return max;
}
// 返回以当前节点为起点（向下走一条路径）能得到的最大路径和 往下走的1条的
int dfs(TreeNode node)
{
if(node==null) return 0;
int l =dfs(node.left);
int r =dfs(node.right);
// 一定要 把少于 0的变为0 ，也就是说，如果说哪一分支小于0，不要啦
l = Math.max(l,0);
r = Math.max(r,0);
max = Math.max(max,l+r+node.val);
return node.val+(l>r?l:r);
}
}
7.7 二叉树层序遍历（102）
代码:
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Deque<TreeNode> deque = new ArrayDeque<>();
List<List<Integer>> list = new ArrayList<>();
if(root==null) return list;
// offer poll
deque.offer(root);
while(!deque.isEmpty())
{
// 就是.size()
int level = deque.size();
List<Integer> l = new ArrayList<>();
// poll
for(int i = 0;i<level;i++)
{
TreeNode node = deque.poll();
if(node.left!=null) deque.offer(node.left);
if(node.right!=null) deque.offer(node.right);
l.add(node.val);
}
list.add(l);
}
return list;
}
}
7.8 将有序数组转换为二叉搜索树（108）
分析：二分法递归建立树
代码:
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums,0,nums.length-1);
}
TreeNode dfs(int nums[],int left,int right)
{
if(right<left)
{
return null;
}
int mid = (left+right)/2;
TreeNode node = new TreeNode(nums,null,null);
node.left = dfs(nums,left,mid-1);
node.right = dfs(nums,mid+1,right);
return node;
}
7.9 验证二叉搜索树 (98)
分析： 传入一个左右区间判定，或者中序遍历判定上一个一定小于下一个
代码：
class Solution {
public boolean isValidBST(TreeNode root) {
returnisBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
}
boolean isBST(TreeNode node,long left,long right){
if(node==null) return true;
if(node.val<=left||node.val>=right)
{
return false;
}
boolean l = isBST(node.left,left,node.val);
boolean r = isBST(node.right,node.val,right);
return l&&r;
}
}
7.10 二叉搜索树中的第k小元素(230)
class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack = new ArrayDeque<>();
int ans =0;
while(root!=null||!stack.isEmpty())
{
while(root!=null)
{
stack.push(root);
root = root.left;
}
root = stack.pop();
k--;
if(k==0)
{
ans=root.val;
}
root = root.right;
}
return ans;
}
}
7.11 二叉树的右视图（199）
分析：层次遍历
代码:
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null ) return list;
Deque<TreeNode> deque= new ArrayDeque<>();
deque.offer(root);
while(!deque.isEmpty())
{
int levelCount = deque.size();
for(int i = 0;i<levelCount;i++)
{
TreeNode node = deque.poll();
if(node.left!=null)
{
deque.offer(node.left);
}
if(node.right!=null)
{
deque.offer(node.right);
}
if(i == levelCount-1)
{
list.add(node.val);
}
}
}
return list;
}
}
7.12 二叉树展开为链表（114）
分析:
把右子树放到左子树的最右面，然后把左子树移动右子树上，再遍历下一个。
代码:
class Solution {
public void flatten(TreeNode root) {
TreeNode cur = root;
while(cur!=null)
{
TreeNode curLeft = cur.left;
if(curLeft!=null)
{
while(curLeft.right!=null)
{
curLeft = curLeft.right;
}
// 此时curLeft就是左子树的最右边那个
curLeft.right = cur.right;
cur.right = cur.left;
cur.left = null;
}
cur = cur.right;
}
}
}
7.13 前序和中序序列构造二叉树（105）
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
HashMap<Integer,Integer> hp = new HashMap<>();
for(int i = 0;i<inorder.length;i++)
{
hp.put(inorder,i);
}
return build(preorder,inorder,0,preorder.length-1,0,inorder.length-1,hp);
}
TreeNode build(int[] preorder,int[] inorder,int firstPre,int endPre,int firstIn,int endIn,HashMap<Integer,Integer> hp)
{
if(firstPre>endPre || firstIn > endIn)
{
return null;
}
TreeNode root = new TreeNode(preorder,null,null);
int index = hp.get(preorder);
int leftSize = index-firstIn;
root.left = build(preorder,inorder,firstPre+1,firstPre+leftSize,firstIn,index-1,hp);
root.right = build(preorder,inorder,firstPre+leftSize+1,endPre,index+1,endIn,hp);
return root;
}
}
7.14 路径总和III （437）
// 前缀和 + 递归 +哈希
class Solution {
public int pathSum(TreeNode root, int targetSum) {
Map<Long,Integer> prefixMap = new HashMap<>();
prefixMap.put(0L,1);
return dfs(root,0,targetSum,prefixMap);
}
int dfs(TreeNode node,long currSum,int target,Map<Long,Integer> prefixMap )
{
if(node==null ) return 0;
currSum += node.val;
int count = prefixMap.getOrDefault(currSum-target,0);
// 更新前缀和
prefixMap.put(currSum,prefixMap.getOrDefault(currSum,0)+1);
count+=dfs(node.left,currSum,target,prefixMap);
count+=dfs(node.right,currSum,target,prefixMap);
// 回溯：撤销当前前缀和，防止影响其他分支
prefixMap.put(currSum, prefixMap.get(currSum) - 1);
return count;
}
}
7.15 和为k的子数组（560）以及拓展（523）
代码： 前缀和 与 HashMap
class Solution {
public int subarraySum(int[] nums, int k) {
HashMap<Integer,Integer> hp = new HashMap<>();
int preSum = 0;
int count = 0;
hp.put(0,1);
for(int num:nums)
{
preSum+=num;
if(hp.containsKey(preSum-k))
{
count+=hp.get(preSum-k);
}
hp.put(preSum,hp.getOrDefault(preSum,0)+1);
}
return count;
}
}
扩展：标题修改 ，求是否存在一个子数组的和是k的整数倍，而且子数组长度大于等于2。
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
if(k==0) return true;
HashMap<Integer,Integer> hp = new HashMap<>(); // 前缀和%k下标
hp.put(0,-1);
int preSum = 0;
boolean b = false;
for(int i = 0; i<nums.length; i++)
{
preSum += nums;
int mod = preSum % k;
if(hp.containsKey(mod))
{
int preIndex = hp.get(mod);
if(i-preIndex>=2)
{
b = true;
break;
}
}
else
{
hp.put(mod,i);
}
}
return b;
}
}
7.16 二叉树的最近公共祖先（236）
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// 如果我就是 p 或 q，我就返回我自己
if(root==null||root==p||root==q)
{
return root;
}
// 我去左边看看有没有 p 或 q（返回 left）
TreeNode left = lowestCommonAncestor(root.left,p,q);
// 我去右边看看有没有 p 或 q（返回 right）
TreeNode right = lowestCommonAncestor(root.right,p,q);
// 如果 left 和 right 都不为空，说明左右都找到了，那我就是最近公共祖先
if(left!=null&&right!=null)
{
return root;
}
//
return left!=null?left:right;
}
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]