LeetCode100题持续更新中

1、动态规划

1.1 爬楼梯 (70)

题目：

分析：f[i] 表示从第1层爬到第i层阶梯有多少种方法，i = 1…n。
状态转移方程：f[i] = f[i-1] + f[i-2]
理解：最后一步有两种可能，可能爬 1 阶，也可能爬 2阶，如果爬1阶，子问题为 f[i-1]；如果爬2阶，子问题为 f[i-2]; 都有可能，所以加起来。
初始化： f[0] = 1, f[1] = 1；要凑 f[2] = 2，所以 f[0] = 1

class Solution {
    public int climbStairs(int n) {

        int[] ans = new int[n+1];
        ans[0]  = 1;
        ans[1]  = 1;
        for(int i = 2;i<= n;i++)
        {
            ans[i] = ans[i-1] +ans[i-2];
        }
        return ans[n];

    }
}

1.2 杨辉三角 (118)

题目：

注意：numRows>=1；

分析：
List<List<Integer>> 这是返回类型，选取数据结构很重要，要遍历输出，选取HashMap<Integer,<List<Integer>>> 作为存储结构。其中List<Integer> 选取ArrayList<>()作为存储结构。然后，注意到边缘位置全是1，然后非边缘位置 l[i] 是上一层 l[i-1] + l[i]。
代码：

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[2] = le[1]+le[2]
                l.add(le.get(j-1)+le.get(j));
            }
        }
        hp.put(i,l);// 只是为记忆上一层
        ans.add(l);

      }
      return ans;

    }
}

1.3 打家劫舍 (198)

题目：

分析：
非负，这是一个很关键信息，因为这样表示状态时可以用前 i 个元素的最大目标值作为状态；不难分析到这是一个选与不选问题,状态转移方程如下：
$$\mathrm{dp}[\mathrm{i}]=\max (\mathrm{dp}[\mathrm{i}-2]+\mathrm{nums}[\mathrm{i}],\mathrm{dp}[\mathrm{i}-1])$$
其中$\mathrm{dp}[\mathrm{i}]$ 表示的是下标为 0 - i 元素的最大目标值；$\mathrm{dp}[0]=\mathrm{nums}[0]$。

代码：

class Solution {
    public int rob(int[] nums) {
        
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        if(nums.length>1)// 原因 从2开始，防止越界
        dp[1] = Math.max(nums[0],nums[1]);

        for(int i =2;i<nums.length;i++)
        {
            dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i]);
                                                                                                    
        }
        return dp[nums.length-1];

   


        
    }
}

1.4 完全平方数 (279)

题目：

分析：关键是如何确定一个数可以被平方数+数来表示，进而转换为子问题，状态转移方程有：
$$\mathrm{dp}[\mathrm{i}]=\min (\mathrm{dp}[\mathrm{i}],\mathrm{dp}[\mathrm{i}-\mathrm{j}\ast \mathrm{j}]+1)$$
其中$\mathrm{dp}[\mathrm{i}]$表示的是数字 i 最少可以用几个平方数来表示，$\mathrm{i}-\mathrm{j}\ast \mathrm{j}\ge 0$, dp[0] = 0。
代码：

class Solution {
    public int numSquares(int n) {
        

        // dp[0] = 0，是因为如果一个数据本身就是平方数 dp[i-j*j]=0, 即 dp[i-j*j]+1 = 1
        int[] dp = new int[n+1];
        dp[0] = 0;

        for(int i = 1;i<=n;i++ )
        {
            dp[i] = i;//最大值，尽量避免使用Integer.MAX_VALUE
            for(int j = 0;j*j<=i;j++)
            {
                dp[i] = Math.min(dp[i],dp[i-j*j]+1); 
            }

        }
        return dp[n];

    }
}

1.5 零钱兑换 (322)

题目：
分析：
如何定义状态变量，转换成子问题，才是关键，要想计算 dp[amount] ，不难想到其子问题是 dp[amount-coin] ,当然，对于每一个硬币coin都要进行相减，所以状态转移方程有：
$$\mathrm{dp}[\mathrm{i}]=\min (\mathrm{dp}[\mathrm{i}],\mathrm{dp}[\mathrm{i}-\mathrm{coin}]+1)$$
其中 dp[i] 表示能组成金额i的最小硬币数量，dp[0] = 0.
代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        
        int[] dp  = new int[amount+1];
        dp[0] =  0;// 表示金额0肯定是0 个硬币数量
        
        for(int i =1;i<=amount;i++)
        {
            dp[i] = amount+1;// 这是一个不可能的最大值
            for(int coin: coins)
            {
                if(i>=coin)
                {
                    dp[i] = Math.min(dp[i],dp[i-coin]+1);
                }
            }

        }
        if(dp[amount] == amount+1)
        {
            return  -1;
        }
        else
        {
            return dp[amount];
        }
        
    }
}

1.6 单词划分 (139)

题目：
分析：
要转换为子问题，先定义好一个状态变量（父问题），再找子问题，dp[i] 表示的是 s[0] - s[i-1] 能否被字典划分 , i = 1,2,3…s.length(), 对于每一个状态定义都要严丝合缝; 寻找子问题, 对于字典中的每一个单词, 都要看 s[i-word.length()] - s[i-1] 是否满足是该单词, 而且dp[i-word.length()]为true, 也就是说 s[0] - s[i-word.length()-1] 可以被划分; 都满足, OK 令 dp[i] = true. 状态转移方程为:
$$\mathrm{dp}[\mathrm{i}]=\mathrm{i}-word.length()\ge 0\wedge \mathrm{dp}[\mathrm{i}-word.length()]\wedge \mathrm{word}==\mathrm{sub}(\mathrm{s})$$

其中 dp[ 0] = true, 原因就是如果sub(s)本来就是从头开始, dp[0] = true 可以不影响我们对该字串的判断.
代码:

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {

        // 从 i=1 开始判断  dp[i] 表示 s[0]-s[i-1] 能否 被划分
        // dp[0] = true;

        // dp[1] 表示 s[0] 能否划分

        // dp[i] =  [dp[i-word.length] &&  s(i-word.length: i-1) == word] or (nextword)
  
        int s_len = s.length();
        boolean[] dp = new boolean[s_len+1];
        dp[0] = true;
        for(int i = 1;i<=s_len;i++)
        {
            for(String word : wordDict)
            {
                // l e e t c ode  dp[4] 为例
                // 0 1 2 3 4      dp
                int leftIndex = i - word.length();// 当前可能匹配单词的起始左下标
                if(leftIndex>=0 && dp[leftIndex] && word.equals(s.substring(leftIndex,i)))
                {
                    dp[i] = true;
                    break;//  只要找到一个就可以       
                }
            }
        }

        return dp[s_len];



        
    }
}

1.7 最长递增子序列 (300)

题目：

分析：
定义状态变量dp[i] 表示 以 下标 i 为结尾的最长子序列长度， 子问题就是，如果当前 nums[i] 大于 nums[j] , j = 0…i-1 , dp[i] = max( dp[i] , dp[j] + 1)
代码：

class Solution {
    public int lengthOfLIS(int[] nums) {

        //i    0  1 2 3 4 5
        //num  4,10,4,3,8,9
        //dp   1  2 2 2 3 4 
        //  如果dp[i] 0-i元素的最大值子序列长度，我们会发现会出错，dp[4] = 3，因为8虽然大于3，dp[3] = 2，
        //  但是dp[4]显然等于2，因为dp[3] = 2,不是以3结尾的最长长度，所以不能用dp[i]表示0-i元素的最大值子序列长度
        
        // dp[i] 表示 以 i 为结尾的最长子序列长度

        int[] dp = new int[nums.length];
        dp[0] = 1;
        int maxlen = 1;
        for(int i = 1;i<nums.length;i++)
        {
            dp[i] = 1; // 如果nums[i] 无法和之前元素构成更长子序列，那么dp[i] = 1
           
            for(int j = 0;j<i;j++)// 因为它可能和所有0-----i-1 构成更长子序列
            {
                if(nums[i]>nums[j])
                {
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }

            }
            if(dp[i]>maxlen)
            maxlen = dp[i];
        }
        return maxlen;
  
    }
}

1.8 乘积最大子数组 (152)

题目：

分析：
最大从哪里来，这是化解为子问题的关键，当然，题目变为最小也一样。审题：非空连续。 maxdp[i] 代表以下标i为结尾的最大值,只和nums[i],maxdp[i-1],mindp[i-1] 有关。
例如： -2 1 -3 dp[2] = 6 要用到mindp[1] = -2，所以要记录最小也要记录下来。
状态转移方程为：
$$\mathrm{maxdp}[\mathrm{i}]=\max (\mathrm{d}[\mathrm{i}],\mathrm{maxdp}[\mathrm{i}-1]\ast \mathrm{nums}[\mathrm{i}],\mathrm{mindp}[\mathrm{i}-1]\ast \mathrm{nums}[\mathrm{i}])$$
代码：

class Solution {
    public int maxProduct(int[] nums) {
        
 

    int n = nums.length;
    int[] maxdp = new int[n];
    int[] mindp = new int[n];
    
    maxdp[0] = nums[0];   
    mindp[0] = nums[0];
    int max  = nums[0];
    for(int i =1;i<n;i++)
    {
        maxdp[i] = Math.max(Math.max(nums[i]*mindp[i-1],nums[i]*maxdp[i-1]),nums[i]);
        mindp[i] = Math.min(Math.min(nums[i]*mindp[i-1],nums[i]*maxdp[i-1]),nums[i]);
        if(maxdp[i]>max)
        {
            max = maxdp[i];
        }
    }
    return max;
    }
}

1.9 分割等和子集 (416)

题目：

分析：

和不是偶数，无解；和为偶数，转换为0-1背包问题

现在变成了恰好型背包问题 其实就是0-1背包问题，就是要求我们装满而已。

我们把其想成nums[i]想成体积,背包容量为sum, 每一个价值对应为nums[i]。

有人就可能问了，背包问题不是解决的是 不超过容量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[i]想成体积,背包容量为sum, 每一个价值对应为nums[i],
        // 有人就可能问了，背包问题不是解决的是 不超过容量s的最大价值，和这个装满s能一样吗
        // 当然是一样的，因为我们设定所有物品单位体积的价值都为1，能转满就说明价值也是最大的
        // 不同在于，背包问题使价值最大的解(不一定为s)，我们的问题是在此基础上能否找到使最大价值为s的解，也就是能装满的解

        int n = nums.length;

        int[][] dp = new int[n+1][s+1]; 
         // dp[i][j] 代表把第i个物品(i=1---n 对应的物品是num[0] - nums[n-1])放到体积为j的最大值,
         // dp[0][j] 与dp[i][0] 代表边界，初始化为0

         for(int i =1;i<=n;i++)
         {
            for(int j=1;j<=s;j++)
            {
                dp[i][j] = dp[i-1][j];// 第i件物品不装
                if(j-nums[i-1]>=0)// 第i件物品能装得下
                {
                    dp[i][j] = Math.max(dp[i][j],dp[i-1][j-nums[i-1]]+nums[i-1]);
                }
            }
         }
         if(dp[n][s]==s)  // 把n件物品放入到体积为s的恰好装满，true
         {
            return true;
         }
         else
         {
            return false;
         }
    }
}

1.10 最大子数组和 (53)

题目：

分析:
dp[i] 表示以下标i为结尾最大值，dp[0]=nums[0],递推关系为：
$\mathrm{dp}[\mathrm{i}]=\max (\mathrm{nums}[\mathrm{i}],\mathrm{nums}[\mathrm{i}]+\mathrm{dp}[\mathrm{i}-1])$
代码：

class Solution {
    public int maxSubArray(int[] nums) {

        // 100 -1 -1 2 2 90 dp[i] 不能表示前0-i最大值了,没法构造子问题
        // 连续
        // 动态规划   dp[i] 表示以i为结尾最大值
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int max = nums[0];
        for(int i = 1;i<nums.length;i++)
        {
            dp[i] = Math.max(nums[i],nums[i]+dp[i-1]);//没有dp[i-1]
            if(dp[i]>max)
            {
                max = dp[i];
            }
        }

        return max;

    }
}

2、位运算

2.1 只出现一次的数字（136）

题目：

分析：常量空间，要么是双指针，要么是位运算；本题使用异或。
知识储备：
任何整数^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）

问题：
分析：
如果知道值直接获得下标的话，省去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[i])) // containsKey
            {
                return new int[]{hp.get(target-nums[i]),i};
            }
            else
            {
                hp.put(nums[i],i);
            }
        }
        return new int[0];
    }
}

3.2 字母异位词 (49)

问题:

分析:
键是关键，小写字母是关键，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)

问题：

分析:一开始我是想着用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)

问题:

分析：
主要是要满足时间复杂度和空间复杂度要求，使用投票抵消算法。只要不同就抵消！
以 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[0];
     for(int num:nums)
     {
        if(vote == 0)
        {
            candidate = num;
            vote++;
        }
        else
        {
            if(num == candidate)
            {
                vote++;
            }
            else
            {
                vote--;
            }
        }

     }
     return candidate;

    }
}

4.2 轮转数组（189）

问题：

分析：
关键是时间复杂度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[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;
            r--;
        }
    }
}

4.3 合并区间 （56）

问题：

分析：思路很简单，先根据二维数组中每一个一维数组的首元素从小到大排序，数据结构选取也很重要，先把第一个放进去，然后从第个开始判断，若能合并，合并；不能合并，把它放进去，每一次比较是刚刚放进去的那个。
代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        
        // 长度未知  每一个元素是数组

        List<int[]> l = new ArrayList<>();

        // 按照左端点排序
        Arrays.sort(intervals,(p,q)->p[0]-q[0]);

        // 思路：
        l.add(intervals[0]);

       int k = 0;
        for(int i = 1;i<intervals.length;i++)
        {
            if(intervals[i][0]<=l.get(k)[1])
            {
                l.get(k)[1] = Math.max(intervals[i][1],l.get(k)[1]);
            }
            else
            {
                l.add(intervals[i]);
                k++;
            }
        }

        return  l.toArray(new int[l.size()][]);  
    }
}

4.4 除自身以外数组的乘积 （238）

问题：

分析：

以 1 2 3 4 为例
1    2   3   4
1    1   3   4
1    2   1   4
1    2   3   1

想要的结果是  每一行连乘
 ans[0]  2  3  4 
 ans[1]  1  3  4
 ans[2]  1  2  4
 ans[3]  1  2  3
 
 先算左下三角(从上往下算)：
ans[1]  1
ans[2]  1×2
ans[3]  1×2×3

再算右下三角(从下往上算)：再和之前ans[i]相乘
ans[0]   4×3×2
ans[1]   4×3          
ans[2]   4    

代码：

class Solution {
    public int[] productExceptSelf(int[] nums) {

        int[] ans = new int[nums.length];
        ans[0]  = 1;
        for(int i =1;i<nums.length;i++)
        {
            ans[i] = ans[i-1]*nums[i-1];
        }

        int temp =1;
        for(int j =nums.length-2;j>=0;j--)
        {
            temp = temp*nums[j+1];
            ans[j] = temp*ans[j];
        }

        return ans;

        
        
    }
}

4.5 矩阵置零（73）

问题：

分析：分别用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[0].length;j++)
            {
                if(matrix[i][j] == 0)
                {
                    r.add(i);
                    c.add(j);
                }
            }
        }
       
        for(int i:r)
        {
            for(int j =0;j<matrix[0].length;j++)
            {
                matrix[i][j] = 0;
            }

        }

        for(int j:c)
        {
            for(int i =0;i<matrix.length;i++)
            {
                matrix[i][j] = 0;
            }

        }

    }
}

// O(1)
class Solution {
    public void setZeroes(int[][] matrix) {
        
        int m = matrix.length;
        int n = matrix[0].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[i][j]==0)
            {
                iz = i;
                jz = j;
                break;
            }
        }
        // 没找到，就不用找了
        if(iz == m+1) return;

       // 假设 iz = 1 jz = 2

       // 先把其所在行列都变为0   如果一开始为0，变为-1,当然也包含matrix[iz][jz]

       
       for(int j = 0;j<n;j++)
       {
            if(matrix[iz][j]==0)
            {
                matrix[iz][j] = -1;
            }
            else
                matrix[iz][j] = 0;
       }
   
        for(int i = 0;i<m;i++)
       {
            if(matrix[i][jz]==0)
            {
                matrix[i][jz] = -1;
            }
            else
                matrix[i][jz] = 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[i][j]==0)
                    {
                        matrix[iz][j] = -1;
                        matrix[i][jz] = -1;
                        
                    }
                }
            }
           }
       }
       // 除了iz,jz所在行和列  根据结果 分别置为0

       // 所有行置为0
      for(int i = 0;i<m;i++)
      {
         if(i!=iz&&matrix[i][jz]==-1)
         {
            for(int j = 0;j<n;j++)
            {
                if(j!=jz)
                {
                    matrix[i][j] = 0;
                }
            }
         }
      }

      
       // 所有列置为0
      for(int j = 0;j<n;j++)
      {
         if(j!=jz&&matrix[iz][j]==-1)
         {
            for(int i = 0;i<m;i++)
            {
                if(i!=iz)
                {
                    matrix[i][j] = 0;
                }
            }
         }
      }

      // iz jz行列置0
         // 行为 0
       for(int j = 0;j<n;j++)
       {
        matrix[iz][j] = 0;      
       }
       // 列为 0
        for(int i = 0;i<m;i++)
       {
           
         matrix[i][jz] = 0;
            
       }      

}}

4.6 螺旋矩阵（54）

问题：

分析：每一圈递归一次，出口是一行，一列，或者没有
代码：

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[i][co_1]);
            }
            return;

        }
        
        if(row_1==row_2)
        {
             for(int j = co_1;j<=co_2;j++)
            {
                list.add(matrix[row_1][j]);
            }
            return;
        }

        for(int j = co_1;j<=co_2;j++)
        {
            list.add(matrix[row_1][j]);
        }
        for(int i = row_1+1;i<row_2;i++)
        {
            list.add(matrix[i][co_2]);
        }

      
        
        for(int j = co_2;j>=co_1;j--)
        {
            list.add(matrix[row_2][j]);
         }
        
    
        for(int i = row_2-1;i>row_1;i--)
        {
            list.add(matrix[i][co_1]);
        }
        cycle(matrix,list,row_1+1,row_2-1,co_1+1,co_2-1);

    }
    public List<Integer> spiralOrder(int[][] matrix) {
       // row_1  row_2  co_1 co_2
       List<Integer> list = new ArrayList<>();
       cycle(matrix,list,0,matrix.length-1,0,matrix[0].length-1);
       return list;

    }
}

4.7 旋转图像（48）

题目：

分析：
矩阵知识，旋转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[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }

        }
        for(int i = 0; i<n; i++)
        {
            int l = 0;
            int r = n-1;
            while(l<r)
            {
                int temp = matrix[i][l];
                matrix[i][l] = matrix[i][r];
                matrix[i][r] =temp; 
                l++;
                r--;
            }

        }


    }
}

5、 双指针

5.1 移动零

问题：

分析：
第一个指针之前为已经ok的，先找到这个位置，放数即可。
代码：

class Solution {
    public void moveZeroes(int[] nums) {
        int firstZero = -1;// 
       // 先找到第一个为0 的位置
        for(int i = 0;i<nums.length;i++)
        {   
            if(nums[i]==0)
            {
                firstZero = i;
                break;
            }
        }
        if(firstZero==-1) return;
        int i = firstZero;// 第一个为0的位置,前面为ok的
        for(int j = firstZero+1;j<nums.length;j++)
        {
            if(nums[j]!=0)
            { 
                nums[i] = nums[j];
                nums[j] = 0;
                i++;
            }
        }

    }
}

6、链表

6.1 相交链表 (160)

问题：

分析：
我走过你来时的路，要么相遇，要么同时走到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）

问题：

分析：
两种方式，模板，最常见，必须快准稳
代码：

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)

问题描述：

代码:
转换成求高度

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）

题目：

分析和代码: 和二叉树直径，有同工异曲之妙，它那个是借助左高度，右高度更新max;咱这个是左节点最大路径和以及右节点的最大路径和更新max,只不过如果为小于0，就不加入。

class Solution {
   
    int  max = 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[mid],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) {
        
      return  isBST(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],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[firstPre],null,null);
        int index = hp.get(preorder[firstPre]);
        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[i];

            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;
    
    }
}