LeetCode Top Likes 100

2019/10/22 Prolems

目录

41 第一个丢失的正数 难

  • 题目描述

    Given an unsorted integer array, find the smallest missing positive integer.

    Example:

    Input: [3,4,-1,1]
    Output: 2

  • 解法

    以 nums 本身作为辅助,依次遍历,让每个数到他对应的位置,如果再次遍历时对应位置数字不对,证明丢了整个正数。

  • 代码

      class Solution {
          public int firstMissingPositive(int[] nums) {
              //把nums作为辅助数组,让每个值放到nums对应值的位置
              for(int i=0;i<nums.length;i++){
                  int swap = nums[i];
                  while(swap>0 && swap<=nums.length && nums[swap-1]!=swap){
                      int temp = nums[swap-1];
                      nums[swap-1] = swap;
                      swap = temp;
                  }
              }
              for(int i=0;i<nums.length;i++){
                  if(nums[i]!=i+1){
                      return i+1;
                  }
              }
              return nums.length+1;
          }
      }
    

42 能装多少雨水 难

  • 题目描述

    Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

    leetcode42

    Example:

    Input: [0,1,0,2,1,0,1,3,2,1,2,1]
    Output: 6

  • 解法

    找到中间最高的分别往两边看,最左边和最右边分别往中间最高的走,这样每次两边都是最高的一定能把中间围起来一个面积。这样时间复杂度也只是O(2n)

  • 代码

      class Solution {
          //找到中间最高了,
          public int trap(int[] height) {
              if(height.length==0) return 0;
              int maxHeight = height[0];
              int maxIndex = 0;
              int res = 0;
              for(int i=0;i<height.length;i++){
                  if(height[i]>maxHeight){
                      maxHeight = height[i];
                      maxIndex = i;
                  }
              }
              //从左边开始
              int maxLeft = height[0];
              for(int i=1;i<maxIndex;i++){
                  if(maxLeft>height[i]){
                      res+=maxLeft-height[i];
                  }else{
                      maxLeft = height[i];
                  }
              }
              //从右边开始
              int maxRight = height[height.length-1];
              for(int i=height.length-2;i>maxIndex;i--){
                  if(maxRight>height[i]){
                      res+=maxRight-height[i];
                  }else{
                      maxRight = height[i];
                  }
              }
              return res;
          }
      }
    

46 数组的全排列 中

  • 题目描述

    Given a collection of distinct integers, return all possible permutations.

    Example:

    Input: [1,2,3]
    Output: [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]

  • 解法

    回溯法,将整组数中的所有的数分别与第一个数交换,继续处理后n-1,同样在都与第二个数交换。 具体在这段代码里指的是,j是实时的第一个数,然后每个数都跟第j个交换。 交换完了记着在变回原来样子。

  • 代码

      class Solution {
          public List<List<Integer>> permute(int[] nums) {
              List<List<Integer>> lists = new ArrayList<>();
              helper(lists,nums,0);
              return lists;
          }
          public void helper(List<List<Integer>> lists, int[] nums, int index){
              if(index == nums.length){
                  // List<Integer> list = Arrays.asList(nums); 这样不行的,因为里面范型是T,不能是int
                  // lists.add(list);
                  List<Integer> list = new ArrayList<>();
                  for(int num:nums) list.add(num);
                  lists.add(list);
                  return;
              }
              for(int i=index;i<nums.length;i++){
                  swap(nums,i,index);
                  helper(lists,nums,index+1);
                  swap(nums,index,i);
              }
          }
          public void swap(int[] nums,int i,int j){
              int temp = nums[i];
              nums[i] = nums[j];
              nums[j] = temp;
          }
      }
    

48 矩阵的旋转 中

  • 题目描述

    You are given an n x n 2D matrix representing an image.

    Rotate the image by 90 degrees (clockwise).

    NOTE:

    You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

    Example:

    Given input matrix =
    [
    [1,2,3],
    [4,5,6],
    [7,8,9]
    ],

    rotate the input matrix in-place such that it becomes:
    [
    [7,4,1],
    [8,5,2],
    [9,6,3]
    ]

  • 解法

    核心如下图,找到旋转规律就很容易了。 在遍历二维数组的时候要对正方形从最外圈向最里圈走 leetcode42

  • 代码

      class Solution {
          public void rotate(int[][] matrix) {
              int length = matrix.length;
              for(int i=0;i<length/2;i++){ //想象i就是第一行的index,所以走一半就到中间了,中间过后就由另一列旋转出来的
                  for(int j=i;j<length-i-1;j++){ //j的起始是i,j=i即是对角线,结束的时候走到少i个的地方,并且最后一个格是上一溜转出来的所以还要在减1
                      int temp = matrix[i][j];
                      matrix[i][j] = matrix[length-j-1][i];
                      matrix[length-j-1][i] = matrix[length-i-1][length-j-1];
                      matrix[length-i-1][length-j-1] = matrix[j][length-i-1];
                      matrix[j][length-i-1] = temp;
                  }
              }
          }
      }
    

49 按照字典序分组 中

  • 题目描述

    Given an array of strings, group anagrams together.

    Example:

    Input: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
    Output: [
    [“ate”,”eat”,”tea”],
    [“nat”,”tan”],
    [“bat”]
    ]

  • 解法

    思路很简单了,创一个map,把数组中每个字符串排序,放到map中就可以了。

  • 代码

      class Solution {
          public List<List<String>> groupAnagrams(String[] strs) {
              HashMap<String,List<String>> map = new HashMap<>();
              for(int i=0;i<strs.length;i++){
                  char[] cs = strs[i].toCharArray();
                  Arrays.sort(cs);
                  String s = String.valueOf(cs);
                  List<String> list = map.get(s);
                  if(list!=null){
                      list.add(strs[i]);
                  }else{
                      list = new LinkedList<>();
                      list.add(strs[i]);
                      map.put(s,list);
                  }
              }
              return new ArrayList<>(map.values());
          }
      }
    

55 弹跳游戏 中

  • 题目描述

    Given an array of non-negative integers, you are initially positioned at the first index of the array.
    Each element in the array represents your maximum jump length at that position.
    Determine if you are able to reach the last index.

    Example:

    Input: [2,3,1,1,4]
    Output: true
    Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

  • 解法

    最早的直观想法:每个位置跳到它能跳的位置,一直到有一个能跳到尽头就结束,结果在最后几个例子中超时了。

    动态规划,先创建一个数组标记全为未知,之后从后往前,走挨个标记

    贪心算法,从0开始计算能到的最远的点,只要在能到和数组长度内,就一直网上算最远能到的点。

  • 代码

      //最早的超时代码
      // class Solution {
      //     public boolean canJump(int[] nums) {
      //         if(nums.length == 1) return true;
      //         return jump(nums, 0);
      //     }
      //     public boolean jump(int[] nums, int position){
      //         if(position+nums[position]>=nums.length-1) return true;
      //         if(nums[position]==0) return false;
      //         for(int i=nums[position];i>0;i--){
      //             if(jump(nums, position+i)) return true;
      //         }
      //         return false;
      //     }
      // }
    
      //动态规划 O(n2)
    
      // class Solution {
      //     public boolean canJump(int[] nums) {
      //         int[] dp = new int[nums.length]; // 认为值为0,则未知,每个点表示从这个点能不能到终点
      //         dp[dp.length-1] = 1;// 值为1就是能到
      //         for(int i=dp.length-2;i>=0;i--){
      //             int maxJump = Math.min(i+nums[i],nums.length);
      //             for(int j=i+1;j<=maxJump;j++){
      //                 if(dp[j]==1){
      //                     dp[i]=1;
      //                     break;
      //                 }
      //             }
      //             if(dp[i]==0) dp[i]=-1;
      //         }
      //         return dp[0]==1?true:false;
      //     }
      // }
    
      // 贪心算法 O(n)
    
      class Solution {
          public boolean canJump(int[] nums) {
              int reach = nums[0];
              for(int i=1;reach>=i&&i<nums.length;i++){ //i是当前的位置
                  reach = Math.max(reach,i+nums[i]);
              }
              return reach>=(nums.length-1)?true:false;
          }
      }
    

56 区间的融合 中

  • 题目描述

    Given a collection of intervals, merge all overlapping intervals.

    Example:

    Input: [[1,3],[2,6],[8,10],[15,18]]
    Output: [[1,6],[8,10],[15,18]]
    Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

  • 解法

    O(n),挨着比就是了,就是要注意细节,比如先要排序,[1,10]是包含[2,5]这种情况。

  • 代码

      class Solution {
          public int[][] merge(int[][] intervals) {
              if (intervals.length <= 1) {
                  return intervals;
              }
              Arrays.sort(intervals, new Comparator<int[]>(){
                  public int compare(int[] i1,int[]i2){
                      return i1[0]-i2[0];
                  }
              });
              //Arrays.sort(intervals, Comparator.comparingInt(o -> o[0])); 函数式接口速度远慢于原始的比较器
              List<int[]> list = new ArrayList<>();
              int i = 0;
              while(i < intervals.length){
                  int[] in = new int[2];
                  in[0] = intervals[i][0];
                  in[1] = intervals[i][1];
                  while(i<intervals.length-1 && in[1]>=intervals[i+1][0]){
                      in[1] = Math.max(intervals[i+1][1],in[1]);
                      i++;
                  }
                  i++;
                  list.add(in);
              }
              return list.toArray(new int[0][]);
          }
      }
    

62 机器人唯一的路径 中

  • 题目描述

    A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).
    The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).
    How many possible unique paths are there? robot example
    Above is a 7 x 3 grid. How many possible unique paths are there?

    Example:

    Input: m = 3, n = 2
    Output: 3
    Explanation:
    From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
    1.Right -> Right -> Down
    2.Right -> Down -> Right
    3.Down -> Right -> Right

  • 解法

    最简单不用想的动态规划很容易了,数值含义是从起点到这个点的方法数,递推公式是左边值+上边值

    第二种是对空间的优惠,每个点的值是它上面点+他左边点,由此可以想到数组是不清空的,那么dp[n]其实就是它上面点的路线值,dp[n-1]就是他左边的值。于是dp[n] = dp[n]+dp[n-1]

  • 代码

      class Solution {
          // 动态规划的核心是找我的动态规划的数字代表什么,像本题这个数字就是从[0,0]到这个点的路径数量
          // 第二个重点就是递推公式,他的递推公式就是左边+上边
          public int uniquePaths(int m, int n) {
              int[][] dp = new int[m][n];
              for(int i=0;i<m;i++){
                  for(int j=0;j<n;j++){
                      if(i==0||j==0) {
                          dp[i][j] = 1;
                      }else{
                          dp[i][j] = dp[i-1][j]+dp[i][j-1];
                      }
                  }
              }
              return dp[m-1][n-1];
          }
    
          public int uniquePaths2(int m, int n) {
          int[] dp = new int[n];
          for(int i=0;i<m;i++){
              for(int j=0;j<n;j++){
                  if(i==0||j==0) {
                      dp[j] = 1;
                  }else{
                      dp[j] = dp[j]+dp[j-1]; // 上面+左边
                  }
              }
          }
          return dp[n-1];
      }
      }
    

64 最短路径和 中

  • 题目描述

    Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
    Note: You can only move either down or right at any point in time.

    Example:

    Input:
    [
    [1,3,1],
    [1,5,1],
    [4,2,1]
    ]
    Output: 7
    Explanation: Because the path 1→3→1→1→1 minimizes the sum.

  • 解法

    依然是动态规划,数值是到这个点的最短路径,这样递推公式就是上下的最短路径+这个点的路径

  • 代码

      class Solution {
          public int minPathSum(int[][] grid) {
              int m = grid.length;
              int n = grid[0].length;
              //同样动态规划,每个点的值是到这个点的最短路径值
              int[][] dp = new int[grid.length][grid[0].length];
              for(int i=0;i<m;i++){
                  for(int j=0;j<n;j++){
                      if(i==0&&j==0) dp[0][0] = grid[0][0];
                      else if(i==0){
                          dp[0][j] = dp[0][j-1] + grid[0][j];
                      }
                      else if(j==0){
                          dp[i][0] = dp[i-1][0] + grid[i][0];
                      }else{
                          dp[i][j] = Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
                      }
                  }
              }
              return dp[m-1][n-1];
          }
      }
    

70 爬梯子 简单

  • 题目描述

    You are climbing a stair case. It takes n steps to reach to the top.
    Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

    Note: Given n will be a positive integer.

    Example:

    Input: 3
    Output: 3
    Explanation: There are three ways to climb to the top.
    1.1 step + 1 step + 1 step
    2.1 step + 2 steps
    3.2 steps + 1 step

  • 解法

    最简单的思想就是每一步可以看作是减一步的数量加上1(这次再走一步),或是减两部的数量加上一(相当于一次再走两步),最后也就是斐波那契数列了。

  • 代码

      class Solution {
          //最直观的递归写法,但每次都要从头算,太慢了。
          public int climbStairs(int n) {
              if(n<=1) return 1;
              return climbStairs(n-1) + climbStairs(n-2);
          }
          //可以说算是动态规划,但其实就是找了个数组存一下中间结果罢了
          public int climbStairs2(int n) {
              int[] dp = new int[n+1];
              dp[0]=1; // 可以省略
              dp[1]=1;
              for(int i=2;i<=n;i++){
                  dp[i] = dp[i-1]+dp[i-2];
              }
              return dp[n];
          }
      }
    

72 替换单词最小编辑距离 难

  • 题目描述

    Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2.

    You have the following 3 operations permitted on a word:

    Insert a character
    Delete a character
    Replace a character

    Example:

    Input: word1 = “horse”, word2 = “ros”
    Output: 3
    Explanation:
    horse -> rorse (replace ‘h’ with ‘r’)
    rorse -> rose (remove ‘r’)
    rose -> ros (remove ‘e’)

  • 解法

    动态规划,dp[i][j]代表从0到i,j的这个两个词需要多少步能变成相同。所以dp[0][j]和dp[i][0]的值均为j或i(纯删除)。之后如果字母相同,证明无需调整,dp[i+1][j+1]=dp[i][j]。如果字母不相同会分三种情况:

    • i的删掉一个
    • j的删掉一个
    • i和j的作替换

      所以dp[i+1][j+1]就变成了取dp[i][j+1],dp[i+1][j],dp[i][j]的最小值。

  • 代码

      class Solution {
          public int minDistance(String word1, String word2) {
              int[][] dp = new int[word1.length()+1][word2.length()+1];
              if(word1.length()==0) return word2.length();
              if(word2.length()==0) return word1.length();
              for(int i = 0;i<=word1.length();i++){
                  dp[i][0] = i;
              }
              for(int i = 0;i<=word2.length();i++){
                  dp[0][i] = i;
              }
              for(int i =1;i<=word1.length();i++){
                  for(int j=1;j<=word2.length();j++){
                      if(word1.charAt(i-1)==word2.charAt(j-1)){
                          dp[i][j] = dp[i-1][j-1];
                      }else{
                          dp[i][j] = 1+Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]));
                      }
                  }
              }
              return dp[word1.length()][word2.length()];
          }
      }
    

75 数组中相同数字分组 中

  • 题目描述

    Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

    Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

    Note: You are not suppose to use the library’s sort function for this problem.

    Example:

    Input: [2,0,2,1,1,0]
    Output: [0,0,1,1,2,2]

    Follow up:

    A rather straight forward solution is a two-pass algorithm using counting sort.
    First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
    Could you come up with a one-pass algorithm using only constant space?

  • 解法

    要利用好他就0 1 2三个数排序的特点,也就证明2个指针足以分隔开三个数。第一个指针分割0,1,指针指名的是第一个非0的数。第二个指针分割1,0,指针指的是最后一个分2的数。

  • 代码

      class Solution {
          public void sortColors(int[] nums) {
              int left = 0;// 这是第一个非0的位置
              int right = nums.length - 1;// 这是最后一个非2的位置
              int i = 0;
              while(i<=right){
                  if(nums[i]==0){
                      swap(nums, i,left);
                      left++;
                      i++;
                  }else if(nums[i]==1){
                      i++;
                  }else{
                      swap(nums,i,right);
                      right--;
                      //这块不i++,因为后面的数字没有整理过,过来的可能是0或1
                  }
              }
          }
          public void swap(int[] nums,int i1, int i2){
              int temp = nums[i1];
              nums[i1] = nums[i2];
              nums[i2] = temp;
          }
      }
    

76 含有字符串的最小序列 难

  • 题目描述

    Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

    Example:

    Input: S = “ADOBECODEBANC”, T = “ABC”
    Output: “BANC”

  • 解法

    使用一个map来保存带找的字符串,并用一个count记录总长度。先将带找字符串全部输入到map中然后遍历长字符串。遇到一个map中有的数便-1。但注意count在map减到小于0后就不再减了,因为证明已经全部减完了,之后的是重复的。当count归0后,证明已经全部匹配到了,从头开始搜索。同理map大于0时才开始计数。在长度中比较选最短的即可。

  • 代码

      class Solution {
          public String minWindow(String s, String t) {
              char[] ss=s.toCharArray();
              char[] ts=t.toCharArray();
              String result="";
              int count = ts.length;
              HashMap<Character,Integer> map=new HashMap<Character,Integer>();
              for(int i=0;i<ts.length;i++){
                  if(!map.containsKey(ts[i])){
                      map.put(ts[i],0);
                  }
                  map.put(ts[i],map.get(ts[i])+1);
              }
              int left=0;
              for(int i=0;i<ss.length;i++){
                  Character temp = ss[i];
                  if(map.containsKey(temp)){
                      int num = map.get(temp);
                      if(num > 0){ //只有当map里这个字母还有没匹配的时候,就减,防止重复太多多减,如果是小于等于0时,则这个字母之前已经匹配完了,但还有重复字母,因为只取最后一个,底下的会加回来,当底下再加回0时,证明到了最后一个了
                          count--;
                      }
                      map.put(temp,num-1);
                  }
                  if(count==0){ //所有的都匹配到了
                      while(left<=i && count == 0){//一直找到最左边,如果有一个出现了字符,证明从这个地方字符就是最左边了,就跳出循环,等着再次匹配
                          Character tempLeft = ss[left];
                          if(map.containsKey(tempLeft)){
                              int num = map.get(tempLeft);
                              if(num>=0){
                                  count++;
                                  if(result.equals("")||i-left+1<result.length())
                                  result = s.substring(left,i+1);
                              }
                              map.put(tempLeft,num+1); // +1时都会进行的,而count++不是,因为对于前面一大堆重复数字这种情况,一直加到1的那个才是最近的
                          }
                          left++;
                      }
                  }
              }
              return result;
          }
      }
    

78 子集 中

  • 题目描述

    Given a set of distinct integers, nums, return all possible subsets (the power set).

    Note: The solution set must not contain duplicate subsets.

    Example:

    Input: nums = [1,2,3]
    Output:
    [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
    ]

  • 解法

    最经典样式的回溯法,每次加一个元素,加入返回结果,再继续递归套进去。当里面的输出完之后,删除这个元素,继续递归

  • 代码

      class Solution {
          public List<List<Integer>> subsets(int[] nums) {
              List<List<Integer>> lists = new LinkedList<>();
              List<Integer> list = new LinkedList<>();
              lists.add(list);
              helper(lists, list, nums, 0);
              return lists;
          }
    
          public void helper(List<List<Integer>> lists, List<Integer> list, int[] nums, int index){
              if(index == nums.length) return;
              for(int i=index;i<nums.length;i++){
                  list.add(nums[i]);
                  lists.add(new LinkedList<Integer>(list));//不能直接加list,因为list是地址引用,未来会被删掉的
                  helper(lists, list, nums, i+1);
                  list.remove(new Integer(nums[i]));
              }
          }
      }
    

79 单词搜索 中

  • 题目描述

    Given a 2D board and a word, find if the word exists in the grid.

    The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

    Example:

    board =
    [
    [‘A’,’B’,’C’,’E’],
    [‘S’,’F’,’C’,’S’],
    [‘A’,’D’,’E’,’E’]
    ]
    Given word = “ABCCED”, return true.
    Given word = “SEE”, return true.
    Given word = “ABCB”, return false.

  • 解法

    也是拿回溯法来解,挨个单元格匹配,如果相同匹配他上下左右四个单元格。需要记录一个是否来过此点。

  • 代码

      class Solution {
          public boolean exist(char[][] board, String word) {
              char[] words = word.toCharArray();
              int rows = board.length;
              int cols = board[0].length;
              boolean[][] enters = new boolean[rows][cols];
              for(int i=0;i<rows;i++){
                  for(int j=0;j<cols;j++){
                      if(helper(board, words, rows, cols, 0, i, j, enters)){
                          return true;
                      }
                  }
              }
              return false;
          }
          public boolean helper(char[][] board, char[] words, int rows, int cols, int index, int row, int column, boolean[][] enters){
              if(words[index] == board[row][column] && enters[row][column] == false){
                  enters[row][column] = true;
                  if(index == words.length-1) return true;
                  if(column>0){
                      if(helper(board, words, rows, cols, index+1, row, column-1, enters)) return true;
                  }
                  if(column<cols-1){
                      if(helper(board, words, rows, cols, index+1, row, column+1, enters)) return true;
                  }
                  if(row<rows-1){
                      if(helper(board, words, rows, cols, index+1, row+1, column, enters)) return true;
                  }
                  if(row>0){
                      if(helper(board, words, rows, cols, index+1, row-1, column, enters)) return true;
                  }
                  enters[row][column] = false;
              }
              return false;
          }
      }
    

84 直方图中的最大矩形 难

  • 题目描述

    Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

    直方图最大矩形
    The largest rectangle is shown in the shaded area, which has area = 10 unit.

    Example:

    Input: [2,1,5,6,2,3]
    Output: 10

  • 解法

    用一个栈来做,栈中存储高度,由低到高排列。当新的高度到来时,如果新的高度大于栈顶,直接加进去,如果小于栈顶,依此和栈顶比较。每次比较就可以求一次栈顶层和此时的位置(i)的最大面积。(因为可以保证中间元素的高都比两边大(已经弹出去了))。直到新的高大于了栈顶,就停止。在最后如果栈里还有元素,也要求一次面积。这次会直接求到栈为空,也会覆盖此时栈的最里层(即整个数组中的最低点)乘总共的长度的面积。

  • 代码

      class Solution {
          public int largestRectangleArea(int[] heights) {
              //链表存地址,对应的数字从小到大,因为面积是取短边。
              //当新的数字大于栈顶,直接加进去
              //当新的数字小于栈顶,依次将数字弹出栈,每弹一次计算一次最大面积,直到遇到比他小的
              //最后不要忘记在比较一轮
              Stack<Integer> stack = new Stack<>();
              int area = 0;
              for(int i=0;i<heights.length;i++){
                  while(!stack.isEmpty()&&heights[i]<=heights[stack.peek()]){ //这块小于还是小于等于不重要
                      int heightIndex = stack.pop();
                      int height = heights[heightIndex];
                      int beginIndex = stack.size()==0?-1:stack.peek();//-1指的是开头
                      area = Math.max(area,height*(i-beginIndex-1));//是不含beginIndex那个位置的,是从i位置到beginIndex的长度,这段长度中都是以此时height为高,因为中间的数一定比height高,都被弹出去了
                  }
                  stack.push(i);
              }
              while(!stack.isEmpty()){
                  int heightIndex = stack.pop();
                  int height = heights[heightIndex];
                  int beginIndex = stack.size()==0?-1:stack.peek();
                  area = Math.max(area,height*(heights.length-beginIndex-1));
              }
              return area;
          }
      }
    

85 长方形最大的面积 难

  • 题目描述

    Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.

    Example:

    Input:
    [
    [“1”,”0”,”1”,”0”,”0”],
    [“1”,”0”,”1”,”1”,”1”],
    [“1”,”1”,”1”,”1”,”1”],
    [“1”,”0”,”0”,”1”,”0”]
    ]
    Output: 6

  • 解法

    其实就是求直方图最大面积的延伸。可以把求 1 的面积转换成一行一行的直方图。如果是 1 就和上面累加求高度,如果是 0 则这行这列高度就是0.

  • 代码

      class Solution {
          public int maximalRectangle(char[][] matrix) {
              if(matrix.length==0) return 0;
              int length = matrix[0].length;
              int[] heights = new int[length];
              int max = 0;
              for(int i =0;i<matrix.length;i++){
                  for(int j =0;j<length;j++){
                      heights[j] = matrix[i][j]=='0'?0:heights[j]+1;
                  }
                  max = Math.max(max,max(heights));
              }
              return max;
          }
    
          public int max(int[] heights){
              int max = 0;
              Stack<Integer> stack = new Stack<>();
              for(int i=0;i<heights.length;i++){
                  while(!stack.isEmpty()&&heights[i]<heights[stack.peek()]){
                      int index = stack.pop();
                      int thisHeight = heights[index];
                      int beginIndex = stack.isEmpty()==true?-1:stack.peek();
                      max = Math.max(max,thisHeight*(i-beginIndex-1));
                  }
                  stack.push(i);
              }
              while(!stack.isEmpty()){
                  int index = stack.pop();
                  int thisHeight = heights[index];
                  int beginIndex = stack.isEmpty()==true?-1:stack.peek();
                  max = Math.max(max,thisHeight*(heights.length-beginIndex-1));
              }
              return max;
          }
      }
    

94 二叉树的中序遍历 中

  • 题目描述

    Given a binary tree, return the inorder traversal of its nodes’ values.

    Example:

    不写了,要求不要用递归

  • 解法

    while循环,中序即左中右,于是先一直到最左,把中间节点放到栈里,然后吐出来,把他的右边放栈里。

  • 代码

      class Solution {
          public List<Integer> inorderTraversal(TreeNode root) {
              Stack<TreeNode> stack = new Stack<>();
              List<Integer> lists = new ArrayList<>();
              while(!stack.isEmpty()||root!=null){
                  while(root!=null){
                      stack.add(root);
                      root=root.left;
                  }
                  root = stack.pop();
                  lists.add(root.val);
                  root = root.right;
              }
              return lists;
          }
      }
    

96 二叉搜索树的数量 中

  • 题目描述

    Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

    Example:

    Input: 3
    Output: 5

  • 解法

    题目比较难,动态规划思想比较好理解。需要推导以下公式:对于n>=2的情况,事实上,1,2,..n都可以作为根节点,若i作为根节点,根据BST的性质,左子树不为空时(左子树为空,只能是i=1),左子树的所有节点必须小于根节点,即[1,i-1]必须位于左子树,同时,右子数节点必须值必须大于根节点值,则[i+1,n]必须位于右子树;

    所以 dp[n] = (求和1 - n) dp(i-1)*dp(n-i)

  • 代码

      class Solution {
          public int numTrees(int n) {
              int[] dp = new int[n+1];
              dp[0] = 1;
              dp[1] = 1;
              //dp[n] = 求和1 - n dp(i-1)*dp(n-i)
              for(int i=2;i<=n;i++){
                  for(int j=1;j<=i;j++){
                      dp[i]+=dp[j-1]*dp[i-j];
                  }
              }
              return dp[n];
          }
      }
    

98 验证是否是二叉搜索树 中

  • 题目描述

    Given a binary tree, determine if it is a valid binary search tree (BST).

    Example:

  • 解法

    最简单的方法就是中序遍历一下是不是下个数大于上个数。 或者用递归的方式,传递值也可以

  • 代码

      class Solution {
          public boolean isValidBST(TreeNode root) {
              Stack<TreeNode> stack = new Stack<>();
              boolean first = true;
              int lastValue = Integer.MIN_VALUE;
              while(!stack.isEmpty()||root!=null){
                  while(root!=null){
                      stack.add(root);
                      root = root.left;
                  }
                  root = stack.pop();
                  if(!first&&root.val<=lastValue) return false;
                  first = false;
                  lastValue = root.val;
                  root = root.right;
              }
              return true;
          }
    
          //递归的方式
          public boolean isValidBST(TreeNode root) {
              return helper(root, null, null);
          }
          public boolean helper(TreeNode root, Integer low, Integer up) {
              if(root==null) return true;
              if(low!=null&&root.val<=low) return false;
              if(up!=null&&root.val>=up) return false;
              return helper(root.left,low,root.val) && helper(root.right,root.val,up);
          }
      }
    

102 二叉树的层次遍历需打出层次 中

  • 题目描述

    Given a binary tree, return the level order traversal of its nodes’ values. (ie, from left to right, level by level).

    Example:

  • 解法

    层次遍历,记一下每次的数量,都打出来以后插入一个结果就可以了。

  • 代码

      class Solution {
          public List<List<Integer>> levelOrder(TreeNode root) {
              Queue<TreeNode> queue = new LinkedBlockingQueue<>();
              List<List<Integer>> lists = new ArrayList<>();
              if(root==null) return lists;
              List<Integer> list = new ArrayList<>();
              queue.add(root);
              int size = 1;
              int temp = 0;
              while(!queue.isEmpty()){
                  TreeNode tree = queue.poll();
                  temp++;
                  list.add(tree.val);
                  if(tree.left!=null){
                      queue.add(tree.left);
                  }
                  if(tree.right!=null){
                      queue.add(tree.right);
                  }
                  if(temp==size){
                      lists.add(list);
                      list = new ArrayList<>();
                      temp = 0;
                      size = queue.size();
                  }
              }
              return lists;
          }
      }
    

104 二叉树的最大深度 简单

  • 题目描述

    Given a binary tree, find its maximum depth.

    The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

    Note: A leaf is a node with no children.

    Example:

  • 解法

    两种办法,一种是递归,每次递归加一就好了。第二种是层次遍历,数层数。

  • 代码

      class Solution {
          public int maxDepth2(TreeNode root) {
              if(root==null) return 0;
              return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
          }
          public int maxDepth(TreeNode root) {
              if(root==null) return 0;
              int res = 0;
              Queue<TreeNode> queue = new LinkedBlockingQueue<>();
              queue.add(root);
              while(!queue.isEmpty()){
                  res++;
                  for(int i = queue.size();i>0;--i){ //size会变注意一下
                      TreeNode temp = queue.poll();
                      if(temp.left!=null) queue.add(temp.left);
                      if(temp.right!=null) queue.add(temp.right);
                  }
              }
              return res;
          }
      }
    

104 前序中序复原二叉树 中等

  • 题目描述

    Given preorder and inorder traversal of a tree, construct the binary tree.

    Note: You may assume that duplicates do not exist in the tree.

    Example:

  • 解法

    前序的第一个数字即是头节点,因此可以把中序根据这个数字拆成左右两部分,之后以此递归。

  • 代码

      class Solution {
          //前序第一个是头节点,中序找到前序的第一个头节点就是左树的,中序跳多长,前序也跳多长,下一个就是头节点
          public TreeNode buildTree(int[] preorder, int[] inorder) {
              return helper(preorder,0, inorder, 0, preorder.length);
          }
          public TreeNode helper(int[] preorder, int preBegin, int[] inorder, int inBegin, int length){
              if(length<=0||preBegin>=preorder.length||inBegin>=preorder.length) return null;
              int headVal = preorder[preBegin];
              TreeNode head = new TreeNode(headVal);
              if(length==1) return head;
              int i=inBegin;
              for(;i<=inBegin+length-1;i++){
                  if(inorder[i]==headVal){
                      break;
                  }
              }
              head.left = helper(preorder, preBegin+1, inorder, inBegin, i-inBegin);
              head.right = helper(preorder, preBegin+i-inBegin+1, inorder, i+1,length-(i-inBegin)-1);
              return head;
          }
      }
    

114 二叉树转链表 中等

  • 题目描述

    Given a binary tree, flatten it to a linked list in-place.

    Example:

  • 解法

    递归,左节点设为null,右节点是递归值。注意要记录下之前的右节点。将返回的左节点值遍历到最后一个,在连上之前的右节点的递归。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          public void flatten(TreeNode root) {
              root = helper(root);
          }
          public TreeNode helper(TreeNode root) {
              if(root == null) return null;
              TreeNode head = root;
              TreeNode temp = root.right;
              root.right = helper(root.left);
              root.left = null;
              while(root.right!=null){
                  root = root.right;
              }
              root.right = helper(temp);
              return head;
          }
      }
    

121 股票的最佳买卖时间 简单

  • 题目描述

    Say you have an array for which the ith element is the price of a given stock on day i.

    If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.

    Note that you cannot sell a stock before you buy one.

    Example:

    Input: [7,1,5,3,6,4]
    Output: 5
    Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
    Not 7-1 = 6, as selling price needs to be larger than buying price.

  • 解法

    记录一个最小值,遍历每次减一下就可以了。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          public int maxProfit(int[] prices) {
              if(prices.length == 0) return 0;
              int min = prices[0];
              int maxMinus = prices[0]-min;
              for(int i = 1;i<prices.length;i++){
                  maxMinus = Math.max(prices[i]-min,maxMinus);
                  min = Math.min(min,prices[i]);
              }
              return maxMinus;
          }
      }
    

124 二叉树的最大路径 难

  • 题目描述

    Given a non-empty binary tree, find the maximum path sum.

    For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

    Example:

    leetcode124

  • 解法

    依此计算每个节点左通路,右通路的值。最大值有四种情况:它本身、它本身+左通路、它本身+右通路、它本身+左通路+右通路。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          int max=Integer.MIN_VALUE;
          public int maxPathSum(TreeNode root) {
              helper(root);
              return max;
          }
          public int helper(TreeNode root){
              if(root == null) return 0;
              int left = helper(root.left);
              int right = helper(root.right);
              int ans = Math.max(root.val,Math.max(left+root.val,right+root.val));//返回的是当前节点,但前节点左路,当前节点右路的最大值
              max = Math.max(max,Math.max(ans,left+right+root.val));//取最大,当前节点,当前节点左路,当前节点右路,当前节点+当前节点左路+当前节点右路的最大值
              return ans;
          }
      }
    

128 最大连续数组 难

  • 题目描述

    Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

    Your algorithm should run in O(n) complexity.

    Example:

    Input: [100, 4, 200, 1, 3, 2]
    Output: 4
    Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

  • 解法

    最简单的思路:放到一个set里,遍历数组找相邻得数。但时间复杂度其实大于O(n2)了。

    所以可以改进一下,当没有比这个值小的时候才去找,避免了重复,时间也就是O(n)了。

  • 代码

      class Solution {
          public int longestConsecutive(int[] nums) {
              if(nums.length==0) return 0;
              HashSet<Integer> set = new HashSet<>();
              int max = 1;
              for(int i=0;i<nums.length;i++){
                  set.add(nums[i]);
              }
              for(int i =0;i<nums.length;i++){
                  int count = 1;
                  int val = nums[i];
                  if(!set.contains(new Integer(val-1))){
                      while(set.contains(new Integer(++val))){
                          count++;
                      }
                  }
                  // val = nums[i];
                  // while(set.contains(new Integer(--val))){
                  //     count++;
                  // }
                  max = Math.max(count,max);
              }
              return max;
          }
      }
    

136 唯一数 易

  • 题目描述

    Given a non-empty array of integers, every element appears twice except for one. Find that single one.

    Note:
    Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

    Example:

    Input: Input: [2,2,1]
    Output: 1

  • 解法

    异或:相同是0,不同是1。 其他都有两个异或就是0,所以最后剩下的值就是单个的值。

  • 代码

      class Solution {
          public int singleNumber(int[] nums) {
              if(nums.length == 1) return nums[0];
              int ans = nums[0];
              for(int i=1;i<nums.length;i++){
                  ans ^= nums[i];
              }
              return ans;
          }
      }
    

138 从随机指针拷贝链表 中等

  • 题目描述

    A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

    Return a deep copy of the list.

    Example:

    leetcode138 Input:
    {“$id”:”1”,”next”:{“$id”:”2”,”next”:null,”random”:{“$ref”:”2”},”val”:2},”random”:{“$ref”:”2”},”val”:1}
    Explanation:
    Node 1’s value is 1, both of its next and random pointer points to Node 2.
    Node 2’s value is 2, its next pointer points to null and its random pointer points to itself.

  • 解法

    三次循环,第一次循环复制节点,第二次循环为复制的节点的随机值赋值,第三次循环拆开。

  • 代码

      /*
      // Definition for a Node.
      class Node {
          public int val;
          public Node next;
          public Node random;
    
          public Node() {}
    
          public Node(int _val,Node _next,Node _random) {
              val = _val;
              next = _next;
              random = _random;
          }
      };
      */
      class Solution {
          public Node copyRandomList(Node head) {
              if(head == null) return null;
              Node dup = head;
              //第一次是复制
              while(dup!=null){
                  Node next = dup.next;
                  Node add = new Node(dup.val,dup.next,dup.random);
                  dup.next = add;
                  dup.next.next = next;
                  dup = dup.next.next;
              }
              //第二次是给复制的节点添加随机值
              dup = head;
              while(dup!=null){
                  dup.next.random = dup.random==null? null: dup.random.next;
                  dup = dup.next.next;
              }
              //第三次是给拆开
              dup = head;
              Node res = new Node();
              Node ret = res;
              while(dup!=null){
                  res.next = dup.next;
                  res=res.next;
                  dup.next = dup.next.next;
                  dup = dup.next;
              }
              return ret.next;
          }
      }
    

139 单词分词 中等

  • 题目描述

    Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

    Example:

    Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
    Output: true
    Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”. Note that you are allowed to reuse a dictionary word.

  • 解法

    可以考虑用动态规划解。每个字符每个字符的走。dp[i]代表从头到这个位置是否可分词。dp[i]是dp[j] && set.contains(s.substring(j,i))。

  • 代码

      class Solution {
          public boolean wordBreak(String s, List<String> wordDict) {
              HashSet<String> set = new HashSet<>();
              for(String w:wordDict){
                  set.add(w);
              }
              //公式:dp[i] = dp[j] && set.contains(s.substring(j,i))
              boolean[] dp = new boolean[s.length()+1];
              dp[0] = true;
              for(int i=1;i<=s.length();i++){
                  for(int j=0;j<i;j++){
                      if(set.contains(s.substring(j,i)) && dp[j]==true){
                          dp[i] = true;
                          break;
                      }
                  }
              }
              return dp[s.length()];
          }
      }
    

141 链表是否有圈 简单

  • 题目描述

    Given a linked list, determine if it has a cycle in it.

    To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

    Example:

  • 解法

    双指针,一个快跑一个慢跑。快的一次跑两步,慢的一次跑一步,撞上了就有圈。

  • 代码

      public class Solution {
          public boolean hasCycle(ListNode head) {
              if(head == null) return false;
              ListNode fast = head;
              ListNode slow = head;
              while(true){
                  if(fast==null||fast.next==null){
                      return false;
                  }
                  fast = fast.next.next;
                  slow = slow.next;
                  if(fast==slow){
                      break;
                  }
              }
              return true;
          }
      }
    

142 链表圈开始的位置 中等

  • 题目描述

    Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

    To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

    Note: Do not modify the linked list.

    Example:

  • 解法

    双指针,一个快跑一个慢跑。快的一次跑两步,慢的一次跑一步,撞上了。再让一个指针回到头,两个同时慢走,再遇见就是起始点。

  • 代码

      public class Solution {
          public ListNode detectCycle(ListNode head) {
              if(head == null) return null;
              ListNode fast = head;
              ListNode slow = head;
              while(true){
                  if(fast==null||fast.next==null){
                      return null;
                  }
                  fast = fast.next.next;
                  slow = slow.next;
                  if(fast==slow){
                      break;
                  }
              }
              slow = head;
              while(slow!=fast){
                  slow = slow.next;
                  fast = fast.next;
              }
              return fast;
          }
      }
    

146 LRU内存 中等

  • 题目描述

    Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

    get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
    put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

    The cache is initialized with a positive capacity.

    Follow up:
    Could you do both operations in O(1) time complexity?

    Example:

    LRUCache cache = new LRUCache( 2 /* capacity */ );
    cache.put(1, 1);
    cache.put(2, 2);
    cache.get(1); // returns 1
    cache.put(3, 3); // evicts key 2
    cache.get(2); // returns -1 (not found)
    cache.put(4, 4); // evicts key 1
    cache.get(1); // returns -1 (not found)
    cache.get(3); // returns 3
    cache.get(4); // returns 4

  • 解法

    LRU是Least Recently Used 近期最少使用算法。内存管理的一种页面置换算法,对于在内存中但又不用的数据块(内存块)叫做LRU,操作系统会根据哪些数据属于LRU而将其移出内存而腾出空间来加载另外的数据。因为要O(1)复杂度,肯定用map,建立一个了链表,每个元素都与map绑定。当使用时断开链表,并放在头里。

  • 代码

      class LRUCache {
          static class Node {
              private int key;
              private int value;
              Node prev, next;
              public Node(int key, int value) {
                  this.key = key;
                  this.value = value;
              }
          }
          private int capacity;
          private Map<Integer, Node> map;
          private Node dummyhead, dummytail;
    
          public LRUCache(int capacity) {
              this.capacity = capacity;
              this.map = new HashMap<>();
              this.dummyhead = new Node(-1, -1);
              this.dummytail = new Node(-1, -1);
              this.dummyhead.next = this.dummytail;
              this.dummytail.prev = this.dummyhead;
          }
          public int get(int key) {
              Node node = getNode(key);
              if(null == node) return -1;
              return node.value;
          }
          Node getNode(int key) {
              Node node = map.get(key);
              if(null == node) return null;
              disconnect(node);
              insertHead(node);
              return node;
          }
          void disconnect(Node node) {
              node.next.prev = node.prev;
              node.prev.next = node.next;
          }
          void insertHead(Node node) {
              node.next = dummyhead.next;
              dummyhead.next.prev = node;
              node.prev = dummyhead;
              dummyhead.next = node;
          }
          public void put(int key, int value) {
              Node node = getNode(key);
              if(null != node) {
                  node.value = value;
              }
              else {
                  node = new Node(key, value);
                  insertHead(node);
                  map.put(key, node);
                  if(map.size() > capacity) {
                      Node tail = dummytail.prev;
                      disconnect(tail);
                      map.remove(tail.key);
                  }
              }
          }
      }
    

148 链表的排序 中等

  • 题目描述

    Sort a linked list in O(n log n) time using constant space complexity.

    Example:

    Input: 4->2->1->3
    Output: 1->2->3->4

  • 解法

    链表的归并排序。

  • 代码

      class Solution {
          public ListNode sortList(ListNode head) {
              if(head == null||head.next==null) return head;//就一个元素或者没有元素就直接返回
              ListNode slow = head;
              ListNode fast = head;
              ListNode slowPre = null;
              while(fast!=null && fast.next!=null){
                  slowPre = slow;
                  fast = fast.next.next;
                  slow =slow.next;
              }
              slowPre.next = null;
              ListNode l1 = sortList(head);
              ListNode l2 = sortList(slow);
              return merge(l1,l2);
          }
          public ListNode merge(ListNode head1, ListNode head2){
              ListNode head = new ListNode(-1);
              ListNode pre = head;
              while(head1!=null&&head2!=null){
                  if(head1.val<head2.val){
                      pre.next = head1;
                      head1 = head1.next;
                  }else{
                      pre.next = head2;
                      head2 = head2.next;
                  }
                  pre = pre.next;
              }
              while(head1!=null){
                  pre.next = head1;
                  head1 = head1.next;
                  pre = pre.next;
              }
              while(head2!=null){
                  pre.next = head2;
                  head2 = head2.next;
                  pre = pre.next;
              }
              return head.next;
          }
      }
    

152 子数组的最大乘积 中等

  • 题目描述

    Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

    Example:

    Input: [-2,0,-1]
    Output: 0
    Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

  • 解法

    相比于之前的连续数组的最大和只需要增加记录最小值就可以了。因为乘积两个负数相乘可能是正数反而成为最大。

  • 代码

      class Solution {
          public int maxProduct(int[] nums) {
              int max = nums[0];
              int maxCurrent = nums[0];
              int minCurrent = nums[0];
              for(int i=1;i<nums.length;i++){
                  int tempMax = maxCurrent;
                  int tempMin = minCurrent;
                  maxCurrent = Math.max(tempMax*nums[i],Math.max(nums[i],tempMin*nums[i]));
                  minCurrent = Math.min(tempMax*nums[i],Math.min(nums[i],tempMin*nums[i]));
                  max = Math.max(maxCurrent,max);
              }
              return max;
          }
      }
    

155 最小栈 简单

  • 题目描述

    Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

    push(x) – Push element x onto stack.
    pop() – Removes the element on top of the stack.
    top() – Get the top element.
    getMin() – Retrieve the minimum element in the stack.

    Example:

    MinStack minStack = new MinStack();
    minStack.push(-2);
    minStack.push(0);
    minStack.push(-3);
    minStack.getMin(); –> Returns -3.
    minStack.pop();
    minStack.top(); –> Returns 0.
    minStack.getMin(); –> Returns -2.

  • 解法

    由两个栈来实现,一个每次都存,一个只存当前位置的最小值。栈先进后出的特点。

    如果只能用一个栈实现的话,可以设一个最小值,每次当有新的最小值时,先把老的最小值插入栈,再插入新值。这样当pop的时候,pop的值时最小值时,再pop一下就是新的最小值了。

  • 代码

      class MinStack {
          //两个栈,一个栈存储值,另一个栈存储当前的最小值
          //因为栈的先进后出特性,保证记录的小的可以压在最后
          /** initialize your data structure here. */
          Stack<Integer> minStack = new Stack<>();
          Stack<Integer> stack = new Stack<>();
          public MinStack() {}
    
          public void push(int x) {
              stack.push(x);
              if(minStack.isEmpty()||x<=minStack.peek()){
                  minStack.push(x);
              }
          }
    
          public void pop() {
              if(stack.isEmpty()) return;
              int x=stack.pop();
              if(x==minStack.peek()){
                  minStack.pop();
              }
          }
    
          public int top() {
              if(stack.isEmpty()) return -1;
              return stack.peek();
          }
    
          public int getMin() {
              if(stack.isEmpty()) return -1;
              return minStack.peek();
          }
      }
    
      /**
      * Your MinStack object will be instantiated and called as such:
      * MinStack obj = new MinStack();
      * obj.push(x);
      * obj.pop();
      * int param_3 = obj.top();
      * int param_4 = obj.getMin();
      */
      public class MinStack {
          private int min_val = Integer.MAX_VALUE;
          private Stack<Integer> s = new Stack<>();
    
          /** initialize your data structure here. */
          public MinStack() {}
    
          public void push(int x) {
              if (x <= min_val) {
                  s.push(min_val);
                  min_val = x;
              }
              s.push(x);
          }
    
          public void pop() {
              if (s.pop() == min_val) min_val = s.pop();
          }
    
          public int top() {
              return s.peek();
          }
    
          public int getMin() {
              return min_val;
          }
      }
    

160 两个链表的焦点 简单

  • 题目描述

    Write a program to find the node at which the intersection of two singly linked lists begins.

    For example, the following two linked lists:

    Example:

  • 解法

    算出两个ListNode各自的长度,让长的先走差值步。再一起走,碰上了即是交点。

  • 代码

      /**
      * Definition for singly-linked list.
      * public class ListNode {
      *     int val;
      *     ListNode next;
      *     ListNode(int x) {
      *         val = x;
      *         next = null;
      *     }
      * }
      */
      public class Solution {
          public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
              ListNode a = headA;
              int countA = 0;
              while(a!=null){
                  a=a.next;
                  countA++;
              }
              ListNode b = headB;
              int countB = 0;
              while(b!=null){
                  b=b.next;
                  countB++;
              }
              if(countA>countB){
                  for(int i=0;i<countA-countB;i++){
                      headA = headA.next;
                  }
              }else{
                  for(int i=0;i<countB-countA;i++){
                      headB = headB.next;
                  }
              }
              while(headA!=headB){
                  headA = headA.next;
                  headB = headB.next;
              }
              return headA;
          }
      }
    

169 主要元素 简单

  • 题目描述

    Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

    You may assume that the array is non-empty and the majority element always exist in the array.

    Example:

    Input: [3,2,3]
    Output: 3

  • 解法

    排个序,返回中间数就好了。

  • 代码

      class Solution {
          public int majorityElement(int[] nums) {
              Arrays.sort(nums);
              return nums[nums.length/2];
          }
      }
    

198 强盗偷钱 简单

  • 题目描述

    You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

    Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

    Example:

    Input: [2,7,9,3,1]
    Output: 12
    Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
    Total amount you can rob = 2 + 9 + 1 = 12.

  • 解法

    动态规划,dp[i]表示0-i抢劫的钱,不要考虑后面没抢的,那在后面会考虑到。dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])。关键还是找准递推公式。

  • 代码

      class Solution {
          public int rob(int[] nums) {
              if(nums.length==0) return 0;
              //动态规划,dp[i]表示0-i抢劫的钱,不要考虑后面没抢的,那在后面会考虑到。
              //dp[i] = Math.max(dp[i-1],dp[i-2]+nums[i])
              int[] dp = new int[nums.length];
              dp[0] = nums[0];
              if(nums.length==1) return dp[0];
              dp[1] = Math.max(nums[1],nums[0]);
              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];
          }
      }
    

200 岛的数量 中

  • 题目描述

    Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

    Example:

    Input:
    11000
    11000
    00100
    00011
    Output: 3

  • 解法

    设一个是否访问过的标示,先把所有的0设为访问过,之后遍历二维数组。当遇见没访问过的时候,访问他前后左右的。最后统计能有多少个没访问过。

  • 代码

      class Solution {
          public int numIslands(char[][] grid) {
              if(grid.length==0) return 0;
              boolean[][] isVisited = new boolean[grid.length][grid[0].length];
              for(int i=0;i<grid.length;i++){
                  for(int j=0;j<grid[0].length;j++){
                      if(grid[i][j]=='0'){
                          isVisited[i][j] = true;
                      }
                  }
              }
              int count = 0;
              for(int i=0;i<grid.length;i++){
                  for(int j=0;j<grid[0].length;j++){
                      if(isVisited[i][j]==false){
                          count++;
                          helper(grid,isVisited,i,j);
                      }
                  }
              }
              return count;
          }
          public void helper(char[][] grid,boolean[][] isVisited,int row,int column){
              if(row<0||column<0||row==grid.length||column==grid[0].length){
                  return;
              }
              if(isVisited[row][column]){
                  return;
              }
              isVisited[row][column] = true;
              helper(grid,isVisited,row+1,column);
              helper(grid,isVisited,row-1,column);
              helper(grid,isVisited,row,column+1);
              helper(grid,isVisited,row,column-1);
          }
      }
    

206 反转链表 简单

  • 题目描述

    Reverse a singly linked list.

    Example:

    Input: 1->2->3->4->5->NULL
    Output: 5->4->3->2->1->NULL

  • 解法

    递归来做,每次都遍历一次,非常的慢。用循环效率会高很多,但是需要搞清楚逻辑关系,记录好现在的,现在的下一个(和现在的做反转),下下个(即下一组的现在的),以及每一组的头(各下一组连接上)。

  • 代码

      class Solution {
          public ListNode reverseList(ListNode head) {
              if(head==null) return null;
              ListNode res = new ListNode(-1);
              helper(head,res);
              return res.next;
          }
          public void helper(ListNode head, ListNode res){
              ListNode temp = head;//此时的最后一个
              ListNode last = null;//倒数第二个,把它下一个要置为空
              while(temp.next!=null){
                  last = temp;
                  temp = temp.next;
              }
              if(last == null){
                  res.next = temp;
                  return;
              }
              last.next = null;
              res.next = temp;
              helper(head,res.next);
          }
          public ListNode reverseList2(ListNode head) {
              if(head==null) return null;
              if(head.next==null) return head;
              ListNode now = head; //当前节点
              ListNode nextNow = null; //下一个的作为当前节点,需要把当前下一个的作为他的下一个
              ListNode pre = null; //记录当前节点,给下一个当下一个用
              ListNode next = null; //当前的真实下一个,他需要把当前作下一个,结束时他是pre
              while(now!=null){
                  next = now.next; //查看当前的下一个
                  now.next = pre; //这个节点链上上一组
                  if(next==null){ //如果到头了
                      pre = now;
                      break;
                  }
                  nextNow = next.next;//下一组就是下下个
                  next.next = now; //next的下一个就是现在的,做反转
                  now = nextNow;//换到下一组
                  pre = next; //给下一组链上
              }
              return pre;
          }
      }
    

207 课程安排 中等

  • 题目描述

    There are a total of n courses you have to take, labeled from 0 to n-1.

    Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

    Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

    Example:

    Input: 2, [[1,0],[0,1]]
    Output: false
    Explanation: There are a total of 2 courses to take.
    To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

  • 解法

    感觉这道题其实挺难的,由于没有学过图论,只能结合看的答案从自身的理解解释一下。目标就是解释清到最后所有的课程都可以不被依赖。首先先记录所有有被依赖到的课程,之后找到哪门课没有被任何课程依赖从他入手,如果所有课程都依赖于某一门课,那么一定在中间存在闭环,肯定不行。拿不被任何课程依赖的课程查看他的依赖,将他依赖的课程数量逐一再减下去,当减完后,他也就变成了只依赖别的课的课程。这样一门一门课的依赖去找。如果到最后还有某门课还存在依赖的课程没被减完,贼证明这门课和某一门课存在了闭环,谁都无法消下去了。

  • 代码

      class Solution {
          public boolean canFinish(int numCourses, int[][] prerequisites) {
              Map<Integer,List<Integer>> yilaiguanxi = new HashMap<>();//记录课程的依赖关系
              int[] yilaishuliang = new int[numCourses];//记录每门课程到现在还被依赖的数量
              //记录依赖关系和依赖数量
              for(int i=0;i<prerequisites.length;i++){
                  int yilai = prerequisites[i][0];//依赖的课程
                  int beiyilai = prerequisites[i][1];//被依赖的课程
                  yilaishuliang[beiyilai]++;
                  if(!yilaiguanxi.containsKey(yilai)){
                      List<Integer> list = new ArrayList<>();
                      list.add(beiyilai);
                      yilaiguanxi.put(yilai,list);
                  }else{
                      yilaiguanxi.get(yilai).add(beiyilai);
                  }
              }
              LinkedList<Integer> meibeiyilai = new LinkedList<>();//没被依赖的课程表,拿他去找依赖的课程让依赖的课程都解开最后也变成没被依赖的课程
              for(int i=0;i<numCourses;i++){ //找没被依赖的课程
                  if(yilaishuliang[i] == 0){ //找到的没被依赖的课程
                      meibeiyilai.add(i); //这门课没被任何课依赖
                  }
              }
              while(!meibeiyilai.isEmpty()){ //没被依赖的课都被算清之前,找依赖关系
                  int zhaoyilai = meibeiyilai.removeFirst();//捋这个没被依赖的关系,并且这个找完关系了就给清出去
                  yilaishuliang[zhaoyilai] = -1;//他没被任何依赖后,设为-1
                  if(!yilaiguanxi.containsKey(zhaoyilai)){//他就没依赖任何家伙
                      continue;
                  }
                  List<Integer> list = yilaiguanxi.get(zhaoyilai);//拿到他所有依赖的课程
                  for(int j=0;j<list.size();j++){
                      int beiyilaiIndex = list.get(j);//这个被依赖的课程
                      yilaishuliang[beiyilaiIndex]--;//这个课程被依赖的数量-1
                      if(yilaishuliang[beiyilaiIndex]==0){ //这门课的所有依赖课也都解开了,他也就成了没被任何课依赖的课
                          meibeiyilai.add(beiyilaiIndex);
                      }
                  }
              }
              for(int i=0;i<numCourses;i++){ //最后再找一遍还有没被依赖的课
                  if(yilaishuliang[i] != -1){ //如果某门课不是-1,证明他还存在着被依赖的关系,也就是之前的步骤没有进入他的环,它存在闭环关系
                      return false;
                  }
              }
              return true;
          }
      }
    

208 字典树(前缀树)中等

  • 题目描述

    Implement a trie with insert, search, and startsWith methods.

    Example:

    Trie trie = new Trie();
    trie.insert(“apple”);
    trie.search(“apple”); // returns true
    trie.search(“app”); // returns false
    trie.startsWith(“app”); // returns true
    trie.insert(“app”);
    trie.search(“app”); // returns true

  • 解法

    字典树,每个树的树枝都有26个字母,有这个字母就见这个对象。当一个词在这里完结的时候,给他附上一个结束标志为表示这里有结束的单词。

  • 代码

      class Trie {
    
          TrieNode root = new TrieNode();
          /** Initialize your data structure here. */
          public Trie() {
          }
          /** Inserts a word into the trie. */
          public void insert(String word) {
              root.insert(word,0);
          }
          /** Returns if the word is in the trie. */
          public boolean search(String word) {
              TrieNode trie = root.findChar(word,0);
              if(trie!=null && trie.wordEnd == true) return true;
              return false;
          }
          /** Returns if there is any word in the trie that starts with the given prefix. */
          public boolean startsWith(String prefix) {
              TrieNode trie = root.findChar(prefix,0);
              if(trie!=null) return true;
              return false;
          }
      }
    
      class TrieNode{
          TrieNode[] children = new TrieNode[26];
          boolean wordEnd = false;
          public void insert(String word, int index){
              if(index == word.length()){
                  wordEnd = true;
                  return;
              }
              int pos = word.charAt(index)-'a';
              if(children[pos]==null){
                  children[pos] = new TrieNode();
              }
              children[pos].insert(word, index+1);
          }
          public TrieNode findChar(String word, int index){
              if(index == word.length()){
                  return this;
              }
              int pos = word.charAt(index)-'a';
              if(children[pos]==null) return null;
              return children[pos].findChar(word,index+1);
          }
      }
    
      /**
      * Your Trie object will be instantiated and called as such:
      * Trie obj = new Trie();
      * obj.insert(word);
      * boolean param_2 = obj.search(word);
      * boolean param_3 = obj.startsWith(prefix);
      */
    

215 数组中第k个最大数字 中等

  • 题目描述

    Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

    Example:

    Input: [3,2,3,1,2,4,5,5,6] and k = 4
    Output: 4

  • 解法

    最简单方法就是排序。或者就是用优先队列(最大堆)。

  • 代码

      class Solution {
          public int findKthLargest(int[] nums, int k) {
              Arrays.sort(nums);
              return nums[nums.length-k];
          }
          public int findKthLargest2(int[] nums, int k) {
              PriorityQueue<Integer> queue = new PriorityQueue<>();
              for(int i=0;i<nums.length;i++){
                  queue.add(nums[i]);
                  if(i>=k) queue.poll();
              }
              return queue.poll();
          }
      }
    

221 最大正方形 中等

  • 题目描述

    Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

    Example:

    221

  • 解法

    动态规划,但是递推公式有一点难推。dp[i][j]看作是以i,j为右下角时,可以形成的最大正方形面积的边长。递推时就看左,上以及左上的长度。取这三个长度的最小值即为他们三临近都为1的最大长/宽/斜线,再加1就是他所可以围成的正方形最大边长。即dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;

  • 代码

      class Solution {
          //动态规划,dp[i][j]表示以i,j为右下角时能组成的最大正方形边长,既然能组成正方形,也就是保证左边点,上边点以及斜上边点为右下角能组成正方形的最小值+1(因为只要这三点有一个组成中有问题,这正方形就组不起来)
          public int maximalSquare(char[][] matrix) {
              int[][] dp = new int[matrix.length][matrix[0].length];
              int max = 0;//最大边的长度
              for(int i=0;i<matrix.length;i++){
                  for(int j=0;j<matrix[0].length;j++){
                      if(matrix[i][j]=='1'){
                          if(i==0||j==0){
                              dp[i][j] = 1;
                          }else{
                              dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                          }
                      }
                      max=Math.max(max,dp[i][j]);
                  }
              }
              return max*max;
          }
      }
    

226 对称二叉树 简单

  • 题目描述

    Invert a binary tree.

    Example:

  • 解法

    左右树互换在递归就好了。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          public TreeNode invertTree(TreeNode root) {
              if(root == null) return null;
              TreeNode oldLeft = root.left;
              root.left = invertTree(root.right);
              root.right = invertTree(oldLeft);
              return root;
          }
      }
    

226 判断链表是否是回文 简单

  • 题目描述

    Given a singly linked list, determine if it is a palindrome.

    Follow up:Could you do it in O(n) time and O(1) space?

    Example:

    Input: 1->2->2->1
    Output: true

  • 解法

    得有三个指针,一个指针负责跑到尾,一个指针负责跑到中间点(做后半段起点),一个指针负责帮助head反转前半段顺序(head将作为前半段起点)。其中奇偶的中点是不一样的,奇数的中点需要往后走一个。然后循环判断值是否相等即可。

  • 代码

      class Solution {
          public boolean isPalindrome(ListNode head) {
              if (head == null || head.next == null) return true;
              ListNode prev = null;
              ListNode slow = head;//将作为后中央往后走
              ListNode fast = head;
              while(fast!=null && fast.next != null){
                  fast = fast.next.next;
                  head = slow; // head成为中央往前走
                  slow = slow.next;
                  head.next = prev;
                  prev = head;
              }
              if(fast != null){
                  slow = slow.next;//fast不为空也就是奇数,中央的数要去下一个
              }
              while(slow!=null && head!=null){
                  if(slow.val!=head.val) return false;
                  slow = slow.next;
                  head = head.next;
              }
              return true;
          }
      }
    

236 树的最低公共节点 中等

  • 题目描述 Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

    According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

    Example:

  • 解法

    深度搜索,只有分别深度搜索左右节点,只有左右都有时,他就是最低公共节点,否则还在他的上级。

  • 代码

      class Solution {
          public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
              if(root==null||root ==p||root==q) return root;
              TreeNode left = lowestCommonAncestor(root.left, p, q);//深度搜索左边节点,如果有返回的话,证明左边节点必定有一个
              TreeNode right = lowestCommonAncestor(root.right, p, q);//深度搜索右边节点,如果有返回的话,证明右边节点必定有一个
              if(left!=null && right!=null){//左右都有节点证明他是最低公共节点
                  return root;
              }
              if(left!=null) return left;//如果左节点有值,返回左节点
              else return right;//如果有节点有值返回右节点,如果两节点都没有返回右节点也就是返回null
          }
      }
    

238 数组除了自己外的乘积 中

  • 题目描述 Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

    Example:

    Input: [1,2,3,4]
    Output: [24,12,8,6]

    Note: Please solve it without division and in O(n).

    Follow up:
    Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

  • 解法

    将数组拆为两部分,一个是当前数左边数的乘积,一个是当前数右边数的乘积,这样在对应相乘就是除了这个数的乘积。

  • 代码

      class Solution {
          //分成两部分,一个是到此位置前一个的积,一个是此位置以后的积
          public int[] productExceptSelf(int[] nums) {
              int length = nums.length;
              int[] res = new int[length];
              if(length == 0) return res;
              int[] forward = new int[length];//每个数表示这个位置往前的乘积
              int[] back = new int[length];//每个数表示这个位置往后的乘积
              forward[0] = 1;
              back[length-1] = 1;
              for(int i=1;i<nums.length;i++){
                  forward[i] = forward[i-1]*nums[i-1];
              }
              for(int i=length-2;i>=0;i--){
                  back[i] = back[i+1]*nums[i+1];
              }
              for(int i=0;i<nums.length;i++){
                  res[i] = forward[i]*back[i];
              }
              return res;
          }
      }
    

239 滑动窗口的最大值 难

  • 题目描述 Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.

    Example:

    Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
    Output: [3,3,5,5,6,7]

    Note: Please solve it without division and in O(n).

    Follow up:
    Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

  • 解法

    建一个双向链表(只保存序号),加数的时候比目前最后一个数小就加进去,比他大就从尾循环弹出,所以链表的头永远都是最大的,每次比较时只要在确定头的序号是在窗口内的就行。

  • 代码

      class Solution {
          public int[] maxSlidingWindow(int[] nums, int k) {
              if(nums.length==0){
                  return new int[0];
              } 
              int[] res = new int[nums.length-k+1];
              LinkedList<Integer> list = new LinkedList<>();//建一个双向链表(只保存序号),加数的时候比目前最后一个数小就加进去,比他大就从尾循环弹出,所以链表的头永远都是最大的,每次比较时只要在确定头的序号是在窗口内的就行。
              for(int i=0;i<k;i++){
                  while(!list.isEmpty()&&nums[list.getLast()]<=nums[i]){
                      list.removeLast();
                  }
                  list.add(i);
              }
              res[0] = nums[list.getFirst()];
              for(int i=k;i<nums.length;i++){
                  while(!list.isEmpty()&&nums[list.getLast()]<=nums[i]){
                      list.removeLast();
                  }
                  list.add(i);
                  if(i-list.getFirst()>=k){
                      list.removeFirst();
                  }
                  res[i-k+1] = nums[list.getFirst()];
              }
              return res;
          }
      }
    

240 搜索二维矩阵 中

  • 题目描述

    Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

    • Integers in each row are sorted in ascending from left to right.
    • Integers in each column are sorted in ascending from top to bottom.

      Example:

      Consider the following matrix: [
      [1, 4, 7, 11, 15],
      [2, 5, 8, 12, 19],
      [3, 6, 9, 16, 22],
      [10, 13, 14, 17, 24],
      [18, 21, 23, 26, 30]
      ]
      Given target = 5, return true.
      Given target = 20, return false.

  • 解法

    抓住每个元素左边比他小,下边比他大的特点,从右上角(即头)开始遍历。

  • 代码

      class Solution {
          //抓住每个元素左边比他小,下边比他大的特点,从右上角(即头)开始遍历
          public boolean searchMatrix(int[][] matrix, int target) {
              if(matrix.length==0) return false;
              int columns = matrix[0].length;
              int rows = matrix.length;
              int i = 0;
              int j = columns-1;
              while(i<rows && j>-1){
                  int num = matrix[i][j];
                  if(num == target) return true;
                  else if(num<target) i++;
                  else if(num>target) j--;
              }
              return false;
          }
      }
    

253 会议室2 中

  • 题目描述

    Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

    Example:

    Given [[0, 30],[5, 10],[15, 20]], return 2.

  • 解法

    可以对全部元素按开始时间排序,之后将每个的结束时间放入优先队列,队列里有几个元素,代表正在有几个会议室使用中,并且记录的是结束时间。如果下一个的开始时间小于当前最早的结束时间,那么也就要加一个会议室。否则就是一个会议室已经结束了,把它剔除。

  • 代码

      public class Solution {
          public static void main(String[] args) {
              Interval i1 = new Interval(2,10);
              Interval i2 = new Interval(3,6);
              Interval i3 = new Interval(12,19);
              Interval i4 = new Interval(13,20);
              Interval[] in = {i1,i2,i3,i4};
              Solution s= new Solution();
              s.minMeetingRooms(in);
          }
          public int minMeetingRooms(Interval[] intervals) {
              //先对时间排序,之后创一个优先队列。如果下一个的开始时间比这个的结束时间小,就证明要加一个会议室了。否则的话,就证明这个时间段已经过了,下一个时间的可以用这个会议室,这个的结束时间就更新了,也就是剔除这个时间
              Arrays.sort(intervals, Comparator.comparingInt(i -> i.start));
              PriorityQueue<Integer> queue = new PriorityQueue<>();
              int num = 0;
              for(int i=0;i<intervals.length;i++){
                  queue.add(intervals[i].end);
                  if(intervals[i].start<queue.peek()){
                      num++;
                  }else{
                      queue.poll();
                  }
              }
              return num;//或者是queue.size()
          }
          public static class Interval {
              int start;
              int end;
              Interval() { start = 0; end = 0; }
              Interval(int s, int e) { start = s; end = e; }
          }
      }
    

279 完全平方和 中

  • 题目描述

    Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n. Example:

    Input: n = 13
    Output: 2
    Explanation: 13 = 4 + 9.

  • 解法

    动态规划,如果他能开方,就设为1,否则就是相加后的最小值。 但其实可以改成可能出现的开方的拼凑。

  • 代码

      class Solution {
          public int numSquares2(int n) {
              int[] dp = new int[n+1];
              for(int i=1;i<=n;i++){
                  int min = n;
                  for(int j=1;j*j<=i;j++){
                      min = Math.min(min,1+dp[i-j*j]);
                  }
                  dp[i] = min;
              }
              return dp[n];
          }
          public int numSquares(int n) {
              int[] dp = new int[n+1];
              for(int i=1;i<=n;i++){
                  if(isPerfectSquare(i)){
                      dp[i]=1;
                  }else{
                      int min = Integer.MAX_VALUE;
                      for(int j=1;j<=i/2;j++){
                          min = Math.min(min,dp[j]+dp[i-j]);
                      }
                      dp[i] = min;
                  }
              }
              return dp[n];
          }
          public boolean isPerfectSquare(int num) {
              int i = 1;
              while (num > 0) {
                  num -= i;
                  i += 2;
              }
              return num == 0;
          }
      }
    

283 移动0 简单

  • 题目描述

    Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

    Example:

    Input: [0,1,0,3,12]
    Output: [1,3,12,0,0]

  • 解法

    时间复杂度较低的方法:找到一个 0 跟他后面非 0 的交换。

    时间复杂度低的方法:记录着最前面 0 的位置,当遇到不是 0 的数字的时候,把最前面 0 的位置设为这个数字。有种逆向思维的感觉,把非 0 数往前放。之后在最前面非 0 位置后面全设为 0 就可以了。

  • 代码

      class Solution {
          public void moveZeroes(int[] nums) {
              for(int i=0;i<nums.length;i++){
                  if(nums[i]==0){
                      int j = i+1;
                      for(;j<nums.length;j++){
                          if(nums[j]!=0){
                              nums[i] = nums[j];
                              nums[j] = 0;
                              break;
                          }
                      }
                      if(j == nums.length-1){
                          break;
                      }
                  }
              }
          }
          public void moveZeroes2(int[] nums) {
              int index=0; // 目前最前面0的位置
              for(int i=0;i<nums.length;i++){
                  if(nums[i]!=0){
                      nums[index++] = nums[i];//当前最前面是0的位置也就是这个数,最前面0的位置+1
                  }
              }
              //index后面的也就全都是0了,因为后面的数已经全部放到前面去了
              for(int i=index;i<nums.length;i++){
                  nums[i] = 0;
              }
          }
      }
    

287 寻找重复数字 中等

  • 题目描述

    Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

    Example:

    IInput: [1,3,4,2,2]
    Output: 2

    Note:

    1. You must not modify the array (assume the array is read only).
    2. You must use only constant, O(1) extra space.
    3. Your runtime complexity should be less than O(n2).
    4. There is only one duplicate number in the array, but it could be repeated more than once.
  • 解法

    最简单方式就是 O(n2) 挨个比了。 以下两种方法都需要利用数在n内这一特点 比较牛的做法就是把它转换成链表的重复入口问题。每个数组对应的值就是它下一个到的位置。这样一块一慢会相遇。相遇后在一个从头走,一个从相遇点走,一次走一个,再次相遇就是重复值。 还可以是 2 分,每次找中间数,之后遍历,如果大于中间数的数量超过了中间数字,则就在这一区域内。

  • 代码

      class Solution {
          public int findDuplicate(int[] nums) {
              for(int i=0;i<nums.length;i++){
                  int num = nums[i];
                  for(int j=i+1;j<nums.length;j++){
                      if(nums[j]==num) return num;
                  }
              }
              return -1;
          }
          public int findDuplicate2(int[] nums) {
              int slow = 0;
              int fast = 0;
              do{
                  slow = nums[slow];
                  fast = nums[nums[fast]];
              }while(slow!=fast);
              fast = 0;
              while(fast!=slow){
                  slow = nums[slow];
                  fast = nums[fast];
              }
              return fast;
          }
          public int findDuplicate3(int[] nums) {
              int begin = 1;
              int end = nums.length;
              while(begin < end){
                  int mid = begin+(end - begin)/2;
                  int count = 0;
                  for(int i=0;i<nums.length;i++){
                      if(nums[i]<=mid){
                          count++;
                      }
                  }
                  if(count>mid){
                      end = mid;
                  }else{
                      begin = mid+1;
                  }
              }
              return begin;
          }
      }
    

295 数据流中的中位数 难

  • 题目描述

    Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

    Example:

    [2,3,4], the median is 3
    [2,3], the median is (2 + 3) / 2 = 2.5

    Note:

    1. You must not modify the array (assume the array is read only).
    2. You must use only constant, O(1) extra space.
    3. Your runtime complexity should be less than O(n2).
    4. There is only one duplicate number in the array, but it could be repeated more than once.
  • 解法

    剑指 offer 原题,一个大队列,一个小队列分别保存小一半的数和大一半的数,插入时比较看是大一半还是小一半的最多就交换下顺序。

  • 代码

      class MedianFinder {
          //一个大队列,一个小队列,大队列放大一半的数,小队列放小一半的数
          PriorityQueue<Integer> minValueFirst = new PriorityQueue<>();// 大一半的数
          PriorityQueue<Integer> maxValueFirst = new PriorityQueue<>((o1,o2)->o2-o1); //小一半的数
          int count = 0;
          /** initialize your data structure here. */
          public MedianFinder() {
          }
          public void addNum(int num) {
              count++;
              if(count==1) minValueFirst.add(num);//第一个数,算他大一半,也就是大一半永远比小一半多或相等
              else{
                  if((count&1)==1){//奇数时大一半的要多一个
                      if(num >= maxValueFirst.peek()){//底下的数比新数小,所以新数直接插入大数队列
                          minValueFirst.add(num);
                      }else{//否则小的数的最大的成为大数的最小的
                          minValueFirst.add(maxValueFirst.poll());
                          maxValueFirst.add(num);
                      }
                  }else{//偶数情况下要保持数量相等,插入小数队列中
                      if(num <= minValueFirst.peek()){//比最大数的最小的要小,直接插入
                          maxValueFirst.add(num);
                      }else{
                          maxValueFirst.add(minValueFirst.poll());
                          minValueFirst.add(num);
                      }
                  }
              }
          }
          public double findMedian() {
              if((count&1)==1){//奇数直接返回大队列最小的,偶数返回中位数
                  return minValueFirst.peek();
              }else{
                  return (minValueFirst.peek()+maxValueFirst.peek())/2.0;
              }
          }
      }
    
      /**
      * Your MedianFinder object will be instantiated and called as such:
      * MedianFinder obj = new MedianFinder();
      * obj.addNum(num);
      * double param_2 = obj.findMedian();
      */
    

297 序列化和反序列化二叉树 难

  • 题目描述

    Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

    Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

    Example:

  • 解法

    可以直接前序遍历,树之间用 , 分割(因为树有可能是两位数),当用到空,用 # 分割。这样在反序列化的时候就是按前序遍历反序列化就可以了,先左节点调用递归,再右节点,用一个数组记录到的位置(数组是地址)。

    第二种和广度搜索类似,一层一层按左中右放。拿出来时候,如果也是按广度搜索拿,有值放值,# 放空。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      public class Codec {
    
          // 前序遍历
          public String serialize(TreeNode root) {
              if(root == null) return "";
              StringBuilder s = new StringBuilder();
              Stack<TreeNode> stack = new Stack<>();
              stack.add(root);
              while(!stack.isEmpty() || root!=null){
                  while(root!=null){
                      s.append(root.val+",");// 防止树的值是两位数
                      stack.add(root);
                      root = root.left;
                  }
                  s.append("#,");
                  if(!stack.isEmpty()){
                      root = stack.pop();
                      root = root.right;
                  }
              }
              return s.toString().substring(0,s.length()-1);
          }
    
          // Decodes your encoded data to tree.
          public TreeNode deserialize(String data) {
              if(data.equals("")) return null;
              int[] index = {0};
              String[] trees = data.split(",");
              return helper(trees,index);
          }
          public TreeNode helper(String[] trees, int[] index){
              if(trees[index[0]].equals("#")) return null;
              TreeNode tree = new TreeNode(Integer.valueOf(trees[index[0]]));
              ++index[0];
              tree.left = helper(trees,index);
              ++index[0];
              tree.right = helper(trees,index);
              return tree;
          }
      }
    
      // Your Codec object will be instantiated and called as such:
      // Codec codec = new Codec();
      // codec.deserialize(codec.serialize(root));
    
      /**
       * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      public class Codec {
    
          // 前序遍历
          public String serialize(TreeNode root) {
              if(root == null) return "";
              StringBuilder s = new StringBuilder();
              LinkedList<TreeNode> q = new LinkedList<>();
              q.add(root);
              while(q.size()>0){
                  TreeNode t = q.poll();
                  if(t==null){
                      s.append("#,");
                      continue;
                  }
                  s.append(t.val+",");
                  q.add(t.left);
                  q.add(t.right);
              }
              return s.toString().substring(0,s.length()-1);
          }
    
          // Decodes your encoded data to tree.
          public TreeNode deserialize(String data) {
              if(data.equals("")) return null;
              String[] datas = data.split(",");
              int index = 0;
              TreeNode tree = new TreeNode(Integer.parseInt(datas[index]));
              index++;
              LinkedList<TreeNode> queue = new LinkedList<>();
              queue.add(tree);
              while(queue.size()>0){
                  TreeNode node = queue.poll();
                  if(node==null) continue;
                  if(!datas[index].equals("#")){
                      TreeNode temp = new TreeNode(Integer.parseInt(datas[index]));
                      node.left = temp;
                      queue.add(temp);
                  }else{
                      node.left = null;
                      queue.add(null);
                  }
                  index++;
                  if(!datas[index].equals("#")){
                      TreeNode temp = new TreeNode(Integer.parseInt(datas[index]));
                      node.right = temp;
                      queue.add(temp);
                  }else{
                      node.right = null;
                      queue.add(null);
                  }
                  index++;
              }
              return tree;
          }
      }
    
      // Your Codec object will be instantiated and called as such:
      // Codec codec = new Codec();
      // codec.deserialize(codec.serialize(root));
    

300 最长递增子序列 中

  • 题目描述

    Given an unsorted array of integers, find the length of longest increasing subsequence.

    Example:

    Input: [10,9,2,5,3,7,101,18]
    Output: 4
    Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

  • 解法

    动态规划,dp[i] 表示以 nums[i] 为结尾的数字最大递增子序列,然后从头到 i 再算。当一个数比 i 小,证明这个数的 dp 可以加 1 作为 dp[i]。递推公式即为:dp[i] = Math.max(dp[i],dp[j]+1)

    第二种思路是可以想象,求最大的递增序列中,新来的一个数替换已有序列中最小的比该数大的数,该序列都不会受影响,因为序列能在增长只有当比最右边数大即可以了,所以利用这一原理,用 TreeSet 可以直接解决这一问题。ceiling 即是找最小的比该数大的数,每个数都加进去,替换掉比他大的最小的数,如果没得替换,也就序列长度加一了。

    接着上面这个思路,直接用二分查找也行。因为序列中已经是递增序列了,用二分查找可以直接定位到最小的比该数大的数。

  • 代码

      class Solution {
          public int lengthOfLIS(int[] nums) {
              //动态规划,dp[i] 表示以 i 为结尾的最大长度,每个 dp[i] 在去从 0 开始搜索。遇到比 i 小的数更新,dp[i]=max(dp[j]+1, dp[i]),即 dp[j] 后面还有 dp[i] 也就是 dp[j]+1 了
              int length = nums.length;
              int[] dp = new int[length];
              int res = 0;
              for(int i=0;i<length;i++){
                  dp[i] = 1;
                  for(int j=0;j<i;j++){
                      if(nums[j]<nums[i]) dp[i] = Math.max(dp[i],dp[j]+1);
                  }
                  res = Math.max(res,dp[i]);
              }
              return res;
          }
          public int lengthOfLIS2(int[] nums) {
              //递增序列可以想为,一个新数,替换里面一个最小的比他大的数,也不会影响整体结果,所以可以用天然排序的 treeset 来做。ceiling 方法即是返回一个最小的比他大的数
              TreeSet<Integer> set = new TreeSet<>();
              for(int num:nums){
                  Integer ceil = set.ceiling(num);
                  if(ceil!=null) set.remove(ceil);
                  set.add(num);
              }
              return set.size();
          }
    
          public int lengthOfLIS3(int[] nums) {
              //递增序列可以想为,一个新数,替换里面一个最小的比他大的数,也不会影响整体结果,所以可以用天然排序的 treeset 来做。ceiling 方法即是返回一个最小的比他大的数
              int[] res = new int[nums.length+1];
              int lengthNow = 0;
              for(int num:nums){
                  int index = binarySearch(res,lengthNow,num);
                  lengthNow = Math.max(lengthNow,index);
                  res[index] = num;
              }
              return lengthNow;
          }
          public int binarySearch(int[] sorts, int end, int num){
              int start = 1;
              while(start <= end){
                  int mid = start+(end - start)/2;
                  if(sorts[mid]>=num){
                      end = mid-1;
                  }else{
                      start = mid+1;
                  }
              }
              return start;
          }
      }
    

301 最简单的匹配方法 难

  • 题目描述

    Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

    Example:

    Input: “(a)())()”
    Output: [“(a)()()”, “(a())()”]

  • 解法

    这题可以用 DFS 和 BFS 两种方法,BFS 比较简单直观一点。就是创一个 set 和 queue,从队列中取值后截取一个再扔进队列。当一个队列中的值已经合法了后,后面的就不用看了,因为肯定是最少匹配了。

  • 代码

      class Solution {
          public List<String> removeInvalidParentheses(String s) {
              //深度优先和广度优先两种,广度优先好理解一些,从头遍历这个字符串,一直判断是否可以匹配,如果匹配了,证明已经找到了最少的办法,因为必须把前面搞定后面才有继续的意义所以已经是最少了。每次删掉一个字符串看看是不是匹配的。
              HashSet<String> set = new HashSet<>();//记录有无重复,重复的无需再判断了
              List<String> res = new LinkedList<>();
              LinkedList<String> q = new LinkedList<>();
              boolean found = false;
              q.add(s);
              set.add(s);
              while(!q.isEmpty()){
                  String ss = q.removeFirst();
                  if(isValid(ss)){
                      res.add(ss);
                      found = true;
                  }
                  if (found) continue;
                  for(int i =0;i<ss.length();i++){
                      if(ss.charAt(i)!='('&&ss.charAt(i)!=')'){
                          continue;
                      }
                      String temp = ss.substring(0,i)+ss.substring(i+1);
                      if(!set.contains(temp)){
                          q.add(temp);
                          set.add(temp);
                      }
                  }
              }
              return res;
          }
          public boolean isValid(String s){
              int count = 0;
              for(int i=0;i<s.length();i++){
                  char c = s.charAt(i);
                  if(c == '('){
                      count++;
                  }else if(c==')'&&count--==0) return false;
              }
              return count==0;
          }
      }
    

309 有冷却时间的最佳买卖股票 中

  • 题目描述

    Say you have an array for which the ith element is the price of a given stock on day i.

    Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

    You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
    After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

    Example:

    Input: [1,2,3,0,2]
    Output: 3
    Explanation: transactions = [buy, sell, cooldown, buy, sell]

  • 解法

    用三个状态记录。第一步必须买,买完后要么等着,要么卖,卖完后必须闲置了。闲置的上一步是闲置或者卖掉。所以 buy[i] = max(buy[i-1],rest[i-1]-prices[i])。卖出后不可能再卖出,卖出后也直接进入闲置状态。sell[i]=buy[i-1]+prices[i],买入后不可能直接闲置,闲置一定是卖出去了或者上一步也是闲置。所以 rest[i] = max(sell[i-1],rest[i-1])。

  • 代码

      class Solution {
          public int maxProfit(int[] prices) {
              if(prices.length==0||prices.length==1) return 0;
              //总共分为三个状态,分别是买入,卖出,和卖出后的休息一天
              int[] buy = new int[prices.length];//可能是前一天后的等待中,或者是闲置后的今天买入。不可能是上一天的卖出。buy[i] = max(buy[i-1],rest[i-1]-prices[i])
              int[] sell = new int[prices.length];//卖出后不可能再卖出,卖出后也直接进入闲置状态。所以 sell[i]=buy[i-1]+prices[i]
              int[] rest = new int[prices.length];//买入后不可能直接闲置,闲置一定是卖出去了或者上一步也是闲置。所以 rest[i] = max(sell[i-1],rest[i-1])
              buy[0] = -prices[0];
              sell[0] = 0;
              rest[0] = 0;
              for(int i=1;i<prices.length;i++){
                  buy[i] = Math.max(buy[i-1],rest[i-1]-prices[i]);
                  sell[i] = buy[i-1]+prices[i];
                  rest[i] = Math.max(rest[i-1],sell[i-1]);
              }
              return Math.max(sell[prices.length-1],rest[prices.length-1]);//因为最后状态只能是闲置或者刚刚买。
          }
      }
    

312 打气球游戏 难

  • 题目描述

    Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

    Find the maximum coins you can collect by bursting the balloons wisely.

    Example:

    Input: [3,1,5,8]
    Output: 167
    Explanation: nums = [3,1,5,8] –> [3,5,8] –> [3,8] –> [8] –> [] coins = 315 + 358 + 138 + 181 = 167

  • 解法

    318

    从 i 到 j 的最大值可以看为剔除中间一个数后,两边的最大值的和加上剔除数乘上两边的数。这样就可以推导出动态规划的公式:dp[i][k-1] + nums[k]nums[i-1]nums[j+1] + dp[k+1][j] , i<=k<=j。

    但是动态规划时需要保证从小到大都能覆盖上,也就是控制 i 和 j 的差由小变大。这样 [i][j] 的范围就是从小变大。所以循环最外层应该是 [i][j] 的差从 1 到最大。

    动态规划从小往大算,先找到小是如何定义的。在本题中也就是 i j 的差是从小开始,所以 i j 的差要从小变大,即放到了最外层循环。

  • 代码

      class Solution {
          public int maxCoins(int[] nums) {
              //遍历每一长串 i 到 j,每次选中一个 k 当不打,打剩下的。这样这个问题就变成了 dp[i][k-1] + nums[k]*nums[i-1]*nums[j+1] + dp[k+1][j] , i<=k<=j
              int length = nums.length;
              int[] nums2 = new int[length+2]; //头尾附上 1
              for(int i=0;i<length;i++){
                  nums2[i+1] = nums[i];
              }
              nums2[0] = 1;
              nums2[length+1] = 1;
              int[][] dp = new int[length+2][length+2]; //头尾附上 1
              for(int delta = 1;delta<=length;delta++){// 差值越来越大,逐渐拉大 i j 的距离。这样是由小变大走
                  for(int i=1;i<=length-delta+1;i++){
                      int j = i+delta-1;
                      for(int k=i;k<=j;k++){
                          dp[i][j] = Math.max(dp[i][j],dp[i][k-1] + nums2[k]*nums2[i-1]*nums2[j+1] + dp[k+1][j]);
                      }
                  }
              }
              return dp[1][length];
          }
      }
    

322 硬币找零 中

  • 题目描述

    You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

    Example:

    Input: coins = [1, 2, 5], amount = 11
    Output: 3
    Explanation: 11 = 5 + 5 + 1

  • 解法

    本来想用贪婪 + 回溯,先从大的硬币找起,渐渐变小,但没想到超时了。

    改用动态规划,dp[i] = Math.min(dp[i],dp[i-coins])。

  • 代码

      class Solution {
    
          public int coinChange(int[] coins, int amount) {
              int[] dp = new int[amount+1];
              for(int i = 1;i<=amount;i++){
                  dp[i] = Integer.MAX_VALUE-1;
                  for(int coin:coins){
                      if(i-coin>=0) dp[i] = Math.min(dp[i],dp[i-coin]+1);
                  }
              }
              return dp[amount]==Integer.MAX_VALUE-1?-1:dp[amount];
          }
            
          int res = Integer.MAX_VALUE;
          public int coinChange2(int[] coins, int amount) {
              Arrays.sort(coins);
              int ans = helper(coins, amount, coins.length-1, 0);
              if(ans == Integer.MAX_VALUE) return -1;
              return ans;
          }
          public int helper(int[] coins, int amount, int index, int count){
              if(amount<0){
                  return Integer.MAX_VALUE;
              }
              if(amount==0){
                  return count;
              }
              for(int i = index;i>=0;i--){
                  int ans = helper(coins, amount-coins[i], i, count+1);
                  if(ans!=-1){
                      res = Math.min(res,ans);
                  }
              }
              return res;
          }
      }
    

337 入室盗贼 3 中

  • 题目描述

    The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

    Determine the maximum amount of money the thief can rob tonight without alerting the police.

    Example:

    337

  • 解法

    最简单的就是递归搜索,比较跟加孙子节点的和和子节点的和。但速度肯定很慢了。

    当然可以用一个 map 存储中间计算过的结果。

  • 代码

      class Solution {
          public int rob(TreeNode root) {
              if(root==null){
                  return 0;
              }
              int val = root.val;
              int left=0,right=0;
              if(root.left!=null){
                  left = rob(root.left.left)+rob(root.left.right);
              }
              if(root.right!=null){
                  right = rob(root.right.left)+rob(root.right.right);
              }
              return Math.max(val+left+right,rob(root.left)+rob(root.right));
          }
          Map<TreeNode,Integer> map = new HashMap<>();
          public int rob2(TreeNode root) {
              if(root==null){
                  return 0;
              }
              if(map.containsKey(root)) return map.get(root);
              int val = root.val;
              int left=0,right=0;
              if(root.left!=null){
                  left = rob(root.left.left)+rob(root.left.right);
              }
              if(root.right!=null){
                  right = rob(root.right.left)+rob(root.right.right);
              }
              int ans = Math.max(val+left+right,rob(root.left)+rob(root.right));
              map.put(root,ans);
              return ans;
          }
            
      }
    

338 计算 bit 数 中

  • 题目描述

    Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

    Example:

    Input: 5
    Output: [0,1,1,2,1,2]

  • 解法

    动态规划,dp[i] 是 i/2 的值(偶数),奇数时 +1。

  • 代码

      class Solution {
          public int[] countBits(int num) {
              int[] dp = new int[num+1];//递推公式为 dp[i]=dp[i/2]+i&1
              for(int i=1;i<=num;i++){
                  dp[i]=dp[i/2]+(i&1);//(& 运算优先级在 + - 后)
              }
              return dp;
          }
      }
    

347. 最常用的 K 个元素 中

  • 题目描述

    Given a non-empty array of integers, return the k most frequent elements.

    Example:

    Input: nums = [1,1,1,2,2,3], k = 2
    Output: [1,2]

  • 解法

    用 Map 先记录次数,然后遍历 Map 的 key,放到优先队列中(这个优先队列的创建可以直接引入 Map),之后取前 k 个就可以了。

  • 代码

      class Solution {
          public List<Integer> topKFrequent(int[] nums, int k) {
              Map<Integer,Integer> map = new HashMap<>();
              for(int i=0;i<nums.length;i++){
                  Integer temp = map.get(nums[i]);
                  if(temp==null){
                      map.put(nums[i],1);
                  }else{
                      map.put(nums[i],temp+1);
                  }
              }
              PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)->map.get(b)-map.get(a));
              for(Integer key:map.keySet()){
                  queue.add(key);
              }
              List<Integer> list = new LinkedList<>();
              for(int i=0;i<k;i++){
                  list.add(queue.poll());
              }
              return list;
          }
      }
    

394. 字符串解码 中

  • 题目描述

    Given an encoded string, return its decoded string.

    The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

    You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

    Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won’t be input like 3a or 2[4].

    Example:

    s = “3[a]2[bc]”, return “aaabcbc”.
    s = “3[a2[c]]”, return “accaccacc”.
    s = “2[abc]3[cd]ef”, return “abcabccdcdcdef”.

  • 解法

    核心是用了两个栈。一个栈用来存储中括号前的数字,一个栈存储中括号前的字符串。遇到 [ 将数字和字符串放入栈中。遇到 ] 推出数字和字符串。在字符串上累加数字个的字符串。

  • 代码

      class Solution {
          public String decodeString(String s) {
              char[] cs = s.toCharArray();
              int curNum = 0;//计算括号前的数字大小
              StringBuilder res = new StringBuilder();
              Stack<Integer> number = new Stack<>();
              Stack<StringBuilder> string = new Stack<>();
              int i =0;
              while(i<s.length()){
                  char c = s.charAt(i);
                  if(Character.isDigit(c)){//计算到中括号前的数是多少
                      while(Character.isDigit(s.charAt(i))){
                          curNum = 10*curNum+s.charAt(i++)-'0';
                      }
                  }else if(c=='['){//遇到左括号了,要把左括号之前的字符串存到栈里面,到了右括号拿出来拼接
                      number.push(curNum);
                      string.push(res);
                      res = new StringBuilder();
                      curNum = 0;
                      i++;
                  }else if(c==']'){//遇到右括号,拿出来之前的拼上当前的 str 的倍数
                      String temp = res.toString();
                      res = string.pop();
                      curNum = number.pop();
                      for(int j = 0;j<curNum;j++){
                          res.append(temp);
                      }
                      i++;
                      curNum = 0;
                  }else{
                      res.append(c);
                      i++;
                  }
              }
              return res.toString();
          }
      }
    

406. 根据高度重建队列 中

  • 题目描述

    Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

    Example:

    Input: [[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
    Output: [[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]

  • 解法

    题意是对数组排序,使得每个位置的数组的第二个数满足在他前面比他身高(第一个数)高或相等的个数等于他的第二个数。

    可以先对数组排序,使得个子高的在前,如果身高相等,让第二个数小的在前。这样比如一开始 [7,0] [7,1] [7,2] 就会排好,然后比如说后面有一个 [6,1],说明只有一个大于或等于它,又因为比6大的已经全部取出。所以把它放在位置1,这样就变成[7,0] [6,1] [7,1] [7,2]。然后比如又有一个[5,0],就放在位置0,以此类推。

  • 代码

      class Solution {
          public int[][] reconstructQueue(int[][] people) {
              Arrays.sort(people,(o1,o2)->{
                  if(o1[0]!=o2[0]){
                      return o2[0]-o1[0];
                  }
                  return o1[1]-o2[1];
              });
              LinkedList<int[]> list = new LinkedList<>();
              for(int i=0;i<people.length;i++){
                  list.add(people[i][1],people[i]); //add(index,value)
              }
              return list.toArray(new int[0][]);
          }
      }
    

416. 相等和的两个分区 中

  • 题目描述

    Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

    Example:

    Input: [1, 5, 11, 5]
    Output: true
    Explanation: The array can be partitioned as [1, 5, 5] and [11].

  • 解法

    无论哪种做法,首先要知道如果可以分成两个相等的数组,整个数组的和必须是偶数。切分成的每个数组的和是总和的一半。

    第一种是 dfs 回溯法,一个一个加下去就好了。但是为了时间,可以判断一步是否有重复的,如果有重复值就没有必要重复计算了。

    第二种方法是动态规划。每一次循环相当于截止到目前的数能组合到的数字。

  • 代码

      class Solution {
          public boolean canPartition(int[] nums) {
              //能分成两份证明是偶数且两分的和均为总和的一半,这样问题变成了找能不能相加达到某值。
              int sum = 0;
              for(int num:nums){
                  sum+=num;
              }
              if((sum &1)==1) return false;
              Arrays.sort(nums);
              return sum(nums,0,sum/2);
          }
          public boolean sum(int[] nums, int index, int target){
              if(target == 0) return true;
              if(target < 0) return false;
              boolean flag = false;
              for(int i=index;i<nums.length;i++){
                  flag = sum(nums,i+1,target-nums[i]);
                  if(flag) return true;
                  while(i<nums.length-1 && nums[i]==nums[i+1]) i++;//当有重复的时候,可以跳过了,因为在之前的步骤里算过了
              }
              return flag;
          }
          public boolean canPartition2(int[] nums) {
          //能分成两份证明是偶数且两分的和均为总和的一半,这样问题变成了找能不能相加达到某值。
              int sum = 0;
              for(int num:nums){
                  sum+=num;
              }
              if((sum &1)==1) return false;
              sum = sum >> 1;
              boolean[] dp = new boolean[sum+1]; //表示能不能组成当前 i
              dp[0] = true;
              for(int i = 0;i<nums.length;i++){ //每个数遍历,相当于看前 i 个数可以组合出的大小
                  for(int j =sum;j>=nums[i];j--){ //能组合的最大是 sum,之后挨个减,看看能不能组合出其他数
                      dp[j] |= dp[j-nums[i]];
                      if(dp[sum]) return true;
                  }
              }
              return dp[sum];
          }
      }
    

437. 找到数的和 中

  • 题目描述

    You are given a binary tree in which each node contains an integer value.

    Find the number of paths that sum to a given value.

    The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

    The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

    Example:

    example

  • 解法

    dfs 深度搜索,比较简单的可以中序遍历树,然后对每一个节点做一次搜索。

    当然其实也可以不需要栈,直接递归遍历解决。

  • 代码

      /**
      * Definition for a binary tree node.
      * public class TreeNode {
      *     int val;
      *     TreeNode left;
      *     TreeNode right;
      *     TreeNode(int x) { val = x; }
      * }
      */
      class Solution {
          public int pathSum(TreeNode root, int sum) {
              int[] a = new int[]{0};
              Stack<TreeNode> stack = new Stack<>();
              TreeNode node = root;
              while(node!=null||stack.size()>0){
                  while(node!=null){
                      dfs(node,a,sum);
                      stack.push(node);
                      node = node.left;
                  }
                  if(stack.size()>0){
                      node = stack.pop();
                      node = node.right;
                  }
              }
              return a[0];
          }
          public void dfs(TreeNode node, int[] a, int target){
              if(node==null){
                  return;
              }
              if(target-node.val == 0){
                  a[0]++;
              }
              dfs(node.left,a,target-node.val);
              dfs(node.right,a,target-node.val);
          }
          public int pathSum2(TreeNode root, int sum) {
              if(root == null)
                  return 0;
              return dfs(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);
          }
          public int dfs2(TreeNode node, int target){
              int a = 0;
              if(node==null){
                  return 0;
              }
              if(target-node.val == 0){
                  a++;
              }
              a += dfs(node.left,target-node.val);
              a += dfs(node.right,target-node.val);
              return a;
          }
      }
    

438. 找出字符串中所有的同字母依序词 中

  • 题目描述

    Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s.

    Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

    The order of output does not matter.

    Example:

    Input: s: “cbaebabacd” p: “abc”
    Output:
    [0, 6]
    Explanation:
    The substring with start index = 0 is “cba”, which is an anagram of “abc”.
    The substring with start index = 6 is “bac”, which is an anagram of “abc”.

  • 解法

    最简单的方法是硬解,循环每一位数,用数组存储各个字符的个数,最后只要满足数组中全 0 就是符合条件。

    巧妙的方法是利用两个数组和 Arrays.equals(arr1, arr2) 方法。首先把要比较的序列存储到一个数组中,之后遍历长字符串,当遍历的长度大于寻找的字符串长度时,开始比较两个数组是否相等。这样相当于一直有一个离最近的滑动窗口,只要窗口相等时也就相等了。

  • 代码

      class Solution {
          public List<Integer> findAnagrams(String s, String p) {
              char[] ss = s.toCharArray();
              char[] ps = p.toCharArray();
              int[] pnum = new int[26];
              boolean possible = true;
              for(char temp:ps){
                  pnum[temp-'a']++;
              }
              List<Integer> list = new ArrayList<>();
              for(int i=0;i<ss.length;i++){
                  if(ss.length-i<ps.length) break;
                  for(int j=0;j<ps.length;j++){
                      if(pnum[ss[i+j]-'a']==0){
                          possible = false;
                          break;
                      }
                      pnum[ss[i+j]-'a']--;
                  }
                  if(possible){
                      for(int num:pnum){
                          if(num>0){
                              possible = false;
                              break;
                          }
                      }
                  }
                  if(possible) list.add(i);
                  possible = true;
                  pnum = new int[26];
                  for(char temp:ps){
                      pnum[temp-'a']++;
                  }
              }
              return list;
          }
          public List<Integer> findAnagrams2(String s, String p) {
              char[] ss = s.toCharArray();
              char[] ps = p.toCharArray();
              List<Integer> list = new LinkedList<>();
              if(ss.length<ps.length) return list;
              int[] snum = new int[26];
              int[] pnum = new int[26];//都跟他比,他是基准值
              for(char ptemp:ps){
                  pnum[ptemp-'a']++;
              }
              for(int i=0;i<ss.length;i++){
                  snum[ss[i]-'a']++;
                  if(i>=ps.length) snum[ss[i-ps.length]-'a']--;
                  if(i>=ps.length-1 && Arrays.equals(snum,pnum)){
                      list.add(i-ps.length+1);
                  }
              }
              return list;
          }
      }
    

448. 找到所有数组中消失的数字 简单

  • 题目描述

    给定一个范围在  1 ≤ a[i] ≤ n ( n = 数组大小 ) 的 整型数组,数组中的元素一些出现了两次,另一些只出现一次。

    找到所有在 [1, n] 范围之间没有出现在数组中的数字。

    您能在不使用额外空间且时间复杂度为O(n)的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。

    Example:

    输入:
    [4,3,2,7,8,2,3,1]
    输出:
    [5,6]

  • 解法

    这题其实之前有类似的,如果不能借助辅助空间,其实数组本身就是辅助空间。因为数组大小都在 1-n 中,所以把数组的值与处于他数组下标如果不等就进行交换,一直换直到换到等。这样读一个数的时候可以直接一直换好几个,目的就是让每次换的数都到他指定位置除非重复。

  • 代码

      class Solution {
          public List<Integer> findDisappearedNumbers(int[] nums) {
              List<Integer> list = new LinkedList<>();
              for(int i=0;i<nums.length;i++){
                  while(nums[nums[i]-1]!=nums[i]){
                      swap(nums,i,nums[i]-1);
                  }
              }
              for(int i=0;i<nums.length;i++){
                  if(nums[i]!=i+1){
                      list.add(i+1);
                  }
              }
              return list;
          }
          public void swap(int[] nums,int a,int b){
              int temp = nums[a];
              nums[a] = nums[b];
              nums[b] = temp;
          }
      }
    

461. 汉明距离 简单

  • 题目描述

    两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

    给出两个整数 x 和 y,计算它们之间的汉明距离。

    Example:

    输入: x = 1, y = 4 输出: 2
    解释:
    1 (0 0 0 1)
    4 (0 1 0 0)

  • 解法

    汉明距离也就是找二进制后的不一样,自然想到了异或,异或后 0 就是不一样的。

  • 代码2

      class Solution {
          public int hammingDistance(int x, int y) {
              //汉明距离也就是找二进制后的不一样,自然想到了异或,异或后 0 就是不一样的
              String s = Integer.toBinaryString(x^y);
              int res = 0;
              for(int i=0;i<s.length();i++){
                  if(s.charAt(i)=='1') res++;
              }
              return res;
              //return Integer.bitCount(x ^ y); //其实有这种数 1 的方法
          }
      }
    

494. 目标和 中等

  • 题目描述

    给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

    返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

    Example:

    输入: nums: [1, 1, 1, 1, 1], S: 3
    输出: 5

  • 解法

    汉明距离也就是找二进制后的不一样,自然想到了异或,异或后 0 就是不一样的。

  • 代码

      class Solution {
          public int findTargetSumWays(int[] nums, int S) {
              // nums:[1,2,3,4,5] sum:3
              // 一种可能解为:1+3+5-2-4 -> 可以分解为 sum(正) 135 和 sum(负) 24
              // sum(正)-sum(负) = target
              // 两边都加上 sum(正)
              // 2sum(正) = target+sum(负)+sum(正)
              // sum(正) = (target+sum(负)+sum(正))/2
              // sum(正) = (target+sum)/2
              // 所以问题转变为这堆数里组成一个数的可能性,就是典型的动态规划问题
              int sum = 0;
              for(int num:nums){
                  sum+=num;
              }
              int valDouble = sum+S;
              if(S*2>valDouble || (valDouble &1)==1){
                  return 0;
              }
              S = valDouble>>1;
              // 这个动态规划需要一步一步走,二维的好想一些
              // 表示到第 i 个数,有多少种方式组成 j
              // 这样后面的数就等于前面的数加上这个数
              int[][] dp = new int[nums.length+1][S+1];
              //为第一列设初始值
              for(int j=1;j<=S;j++){
                  dp[0][j] = 0;
              }
              //因为有一步 j>=nums[i-1] 判断,所有要有为得出 0 的可能性设为 1
              for(int i=0;i<=nums.length;i++){
                  dp[i][0] = 1;
              }
              int min = nums[0];
              for(int k=1;k<nums.length;k++){
                  if(min>nums[k]) min = nums[k];
              }
              for(int i=1;i<=nums.length;i++){
                  // 从最小的正数开始有可能
                  for(int j=min;j<=S;j++){
                      if(j>=nums[i-1]) //防止数组越界
                      dp[i][j] = dp[i-1][j]+dp[i-1][j-nums[i-1]];//上一位的 j 加上这一位的 j-这一位的值
                      else
                      dp[i][j] = dp[i-1][j];
                  }
              }
              return dp[nums.length][S];
          }
          //下面这个方法是一位数组方法
          public int findTargetSumWays(int[] nums, int S) {
              int sum = 0;
              for(int num:nums){
                  sum+=num;
              }
              int valDouble = sum+S;
              if(S*2>valDouble || (valDouble &1)==1){
                  return 0;
              }
              S = valDouble>>1;
              int[] dp = new int[S+1];
              dp[0] = 1;
              int res = 0;
              // 在第 i 个数有多少种可能组成 dp[j] 的值
              for (int i = 0; i < nums.length; i++) {
                  // 因为组成和的时候不能包括 nums[i] 数字本身,所以要让 j 从大到小,以防止 j 可以由包含比自己小的数组成。
                  for (int j = S; j >= nums[i]; j--) {
                      dp[j] += dp[j - nums[i]];
                  }
              }
              return dp[S];
          }
      }
    

538. 把二叉搜索树转换为累加树 简单

  • 题目描述

    给定一个二叉搜索树(Binary Search Tree),把它转换成为累加树(Greater Tree),使得每个节点的值是原来的节点值加上所有大于它的节点值之和。

    Example:

    538

  • 解法

    因为二叉搜索树右边节点比左边大,所有题意就变成了节点加上他的所有右节点了。这样就是中序遍历的反着了。

  • 代码

      class Solution {
          public TreeNode convertBST(TreeNode root) {
              Stack<TreeNode> stack = new Stack<>();
              TreeNode node = root;
              int val = 0;
              while(stack.size()>0||node!=null){
                  while(node!=null){
                      stack.add(node);
                      node=node.right;
                  }
                  if(stack.size()>0){
                      node = stack.pop();
                      val+=node.val;
                      node.val = val;
                      node =node.left;
                  }
              }
              return root;
          }
    
          int sum = 0;
          //递归方式,与中序遍历相反
          public TreeNode convertBST(TreeNode root) {
              if(root==null) return null;
              convertBST(root.right);
              sum += root.val;
              root.val = sum;
              convertBST(root.left);
              return root;
          }
      }
    

543. 二叉树的直径 简单

  • 题目描述

    给定一棵二叉树,你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。

    Example:

    543

  • 解法

    就是找每一个节点的左右深度最大的和就是二叉树的最大路径。

  • 代码2

      class Solution {
          int max = 0;
          public int diameterOfBinaryTree(TreeNode root) {
              helper(root);
              return max;
          }
          public int helper(TreeNode root) {
              if(root == null){
                  return 0;
              }
              int left = helper(root.left);
              int right = helper(root.right);
              max = Math.max(left+right,max);
              return 1+Math.max(left,right);
          }
      }
    

560. 和为 K 的子数组 中等

  • 题目描述

    给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

    Example:

    输入:nums = [1,1,1], k = 2
    输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

  • 解法

    前缀和。比如说 3-5 的值就可以用 1-5 的前缀和减去 1-2 的前缀和。这样只用一个 sum,用 sum 减去目标值查看有没有前缀和,再每次用 map 记录当前的和就可以了。

  • 代码2

      class Solution {
          public int subarraySum(int[] nums, int k) {
              Map<Integer, Integer> map = new HashMap<>();
              // 用前缀和的差求有没有连续的数到达这个数,比如说 1-5 减去 1-2 的值就是 3-5 的值。
              int sum = 0;
              int res = 0;
              map.put(0,1); // 控制当 sum 和 k 相等时可以增加一个
              for(int num:nums){
                  sum+=num;
                  int x = sum - k;//求出需要找到的前缀和
                  Integer xNum = map.get(x);
                  if(xNum!=null){
                      res += xNum;
                  }
                  Integer sumNum = map.get(sum);
                  map.put(sum,sumNum==null?1:sumNum+1);
              }
              return res;
          }
      }
    

581. 最短无序连续子数组 简单

  • 题目描述

    给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

    你找到的子数组应是最短的,请输出它的长度。

    Example:

    输入: [2, 6, 4, 8, 10, 9, 15]
    输出: 5

  • 解法

    第一种方案是直接复制一个数组然后对该数组排序,找到第一个和最后一个跟原数组不一样的位相减。

    第二种方案是设定两个指针,一个从头走,一个从尾走。从头走记录逐渐变大的值,当遇到不能变大的值的时候,证明这个点是一定会被换掉的,一直找到会被换掉的最右头。 同理,从尾往回走的,应记录逐渐变小的值,当遇到不能变小,也就证明这一端是一定会被改变的,可以找到一定要被改变的最左端。

  • 代码

      class Solution {
          public int findUnsortedSubarray(int[] nums) {
              int[] copys = nums.clone();
              Arrays.sort(copys);
              int low = 0;
              for(;low<nums.length;low++){
                  if(copys[low]!=nums[low]){
                      break;
                  }
              }
              if(low == nums.length-1) return 0;
              int high = nums.length-1;
              for(;high>=low;high--){
                  if(copys[high]!=nums[high]){
                      break;
                  }
              }
              return high-low+1;
          }
          public int findUnsortedSubarray2(int[] nums) {
              int left = -1;
              int right = -2;
              int getBig = nums[0]; //从最左端往最右端,应该会逐渐变大,当不变大时,也就证明此时的位置一定会换回最大值的左边,也就需要重新设置最右端
              int getSmall = nums[nums.length-1]; //从最右端往最左端,应该会逐渐变小,当不变小时,也就证明此时的位置一定会换回最大值的右边,也就需要重新设置最左端
              for(int i=0;i<nums.length;i++){
                  getBig = Math.max(getBig,nums[i]);
                  getSmall = Math.min(getSmall,nums[nums.length-1-i]); //两端走
                  if(getBig>nums[i]){
                      right = i;
                  }
                  if(getSmall<nums[nums.length-1-i]){
                      left = nums.length-1-i;
                  }
              }
              return right - left+1;
          }
      }
    

617. 合并二叉树 简单

  • 题目描述

    给定两个二叉树,想象当你将它们中的一个覆盖到另一个上时,两个二叉树的一些节点便会重叠。

    你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠,那么将他们的值相加作为节点合并后的新值,否则不为 NULL 的节点将直接作为新二叉树的节点。

    Example:

    leetcode 617

  • 解法

    用 t1 做返回值递归,不断为 t1 设定左右节点。当任何一个节点为空时,返回另一个节点。

  • 代码

      class Solution {
          public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
              if(t1==null&&t2==null) return null;
              if(t1==null){
                  return t2;
              }
              if(t2==null){
                  return t1;
              }
              t1.val += t2.val;
              t1.left = mergeTrees(t1.left,t2.left);
              t1.right = mergeTrees(t1.right,t2.right);
              return t1;
          }
      }
    

621. 任务调度器 中等

  • 题目描述

    给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务,或者在待命状态。

    然而,两个相同种类的任务之间必须有长度为 n 的冷却时间,因此至少有连续 n 个单位时间内 CPU 在执行不同的任务,或者在待命状态。

    你需要计算完成所有任务所需要的最短时间。

    Example:

    输入: tasks = [“A”,”A”,”A”,”B”,”B”,”B”], n = 2
    输出: 8
    执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.

  • 解法

    这题可以找规律做。分两种情况: 首先是 AAAABBBBCCCDE n=3 -> ABXX ABXX ABXX AB 共 (最长位数的字符-1)*(n+1)+最长重复个数 像这里最后一个 AB 就是重复个数所以+2。 但如果是 AAAABBBBCCCDE n=2 -> ABXABXABXABX 是 12 位,不够总位数,所以剩下的数字还得往后面补。

  • 代码

      class Solution {
          public int leastInterval(char[] tasks, int n) {
              // 有两种情况,一种是最长就是 tasks 的长度,即全打乱排列,像 AAAABBBBCCCDE n=2
              // ABXABXABXABX 是 12 位,不够所有的位数
              // 第二种是 AAAABBBBCCCDE n=3 ABXXABXXABXXAB 共 (最长位数的字符-1)*(n+1)+最长重复个数 像这里最后一个 AB 就是重复个数所以+2
              int[] chars = new int[26];
              for(char c:tasks){
                  chars[c-'A']++;
              }
              Arrays.sort(chars);
              int repeat = 0;
              for(int i =25;i>=0;i--){
                  if(chars[i]==chars[25]) repeat++;
              }
              return Math.max(tasks.length,(chars[25]-1)*(n+1)+repeat);
          }
      }
    

647. 回文子串 中等

  • 题目描述

    给定一个字符串,你的任务是计算这个字符串中有多少个回文子串。

    具有不同开始位置或结束位置的子串,即使是由相同的字符组成,也会被计为是不同的子串。

    Example:

    输入: “abc”
    输出: 3
    解释: 三个回文子串: “a”, “b”, “c”.

  • 解法

    这道题主要是检查回文的判断方法。

    第一种是暴力一维动态规划解法,一个新的字符串的回文数量是他之前结果的回文数量加上每一位到新的最后一位的回文数量。

    比较好一点的做法是用一个二维数组动态规划。dp[i][j] 表示 i 到 j 的位置是否是回文。是回文的条件是 i 和 j 的字符相同且 dp[i+1][j-1] 是回文(如果不相邻,相邻的话直接判断 i 和 j 的字符是否相同)。

    最好的方法是以字符串每个字符为中心往外扩展查看是否还是回文。需要注意中心有可能是奇数或者偶数,当奇数的时候,中心是一个字符,当偶数的时候,中心是两个字符。

  • 代码

      class Solution {
          public int countSubstrings(String s) {
              int[] dp = new int[s.length()];//每个新的 dp 是之前的 dp 加上新增的回文数量。新增的回文数量即是从字符串头开始到新增字符的回文数量。
              dp[0] = 1;
              for(int i=1;i<s.length();i++){
                  int temp=0;
                  for(int j=0;j<=i;j++){//判断从第 j 位到第 i 位是否是回文
                      if(isHuiwen(s.substring(j,i+1))) temp++;
                  }
                  dp[i] = dp[i-1]+temp;
              }
              return dp[s.length()-1];
          }
          public boolean isHuiwen(String s){
              char[] cs = s.toCharArray();
              int mid = (cs.length-1)/2;
              int i=0;
              while(i<=mid){
                  if(cs[i]==cs[cs.length-1-i]){
                      i++;
                      continue;
                  }
                  return false;
              }
              return true;
          }
          public int countSubstrings2(String s) {
              //回文的通用做法,动态规划
              boolean[][] dp = new boolean[s.length()][s.length()]; //dp[i][j] 是否是回文
              int res = 0;
              char[] cs = s.toCharArray();
              for(int i=0;i<s.length();i++){
                  for(int j=0;j<=i;j++){
                      if(cs[i]==cs[j] && (i-j<=1 || dp[j+1][i-1])){
                          dp[j][i]=true;
                          res++;
                      }
                  }
              }
              return res;
          }
          public int countSubstrings3(String s) {
              char[] cs = s.toCharArray();
              int count = 0;
              //回文的第二种做法,选定字符串的每个字符都作为中心,查看是否有可能是以他为中心的回文,这时要注意中心有可能是奇数即一个,也有可能是两个即偶数。
              for(int i=0;i<cs.length;i++){
                  count+=center(i,i,cs);
                  count+=center(i,i+1,cs);
              }
              return count;
          }
          public int center(int left, int right, char[] cs){
              int count = 0;
              while(left>=0 && right<cs.length&&cs[left--]==cs[right++]){ //以这一个(两个)字符为中心往外扩展
                  count++;
              }
              return count;
          }
      }
    

739. 每日温度 中等

  • 题目描述

    根据每日 气温 列表,请重新生成一个列表,对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高,请在该位置用 0 来代替。

    例如,给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73],你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。

    提示:气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度,都是在 [30, 100] 范围内的整数。

  • 解法

    最开始想用的方法是两个栈来解决,一个栈存温度,一个栈存温度对应的 index。这样当一个新的温度比当前栈顶的温度大的时候,就依次剔除栈内的温度并跟 index 对比获取天数。最后记着清空一次栈赋值 0 就可以了。

    但其实一个栈足够了,毕竟有了 index 也就有了对应的温度了。

  • 代码

      class Solution {
          public int[] dailyTemperatures(int[] T) {
              // 创建一个栈,比上一个数小就扔到栈中,遇到大的就弹出来
              // 但由于要记录天数和温度,还需要一个栈记录天数,两个栈要保证一一对应
              Stack<Integer> wendu = new Stack<Integer>();
              Stack<Integer> index = new Stack<Integer>();
              int[] res = new int[T.length];
              for(int i =0;i<T.length;i++){
                  while(!wendu.isEmpty()&&wendu.peek()<T[i]){
                      wendu.pop();
                      int thisIndex = index.pop();
                      res[thisIndex] = i-thisIndex;
                  }
                  wendu.push(T[i]);
                  index.push(i);
              }
              while(!index.isEmpty()){
                  res[index.pop()] = 0;
              }
              return res;
          }
          public int[] dailyTemperatures2(int[] T) {
              // 完全可以简化为一个栈,毕竟有了索引其实就有了温度
              Stack<Integer> index = new Stack<Integer>();
              int[] res = new int[T.length];
              for(int i =0;i<T.length;i++){
                  while(!index.isEmpty()&&T[index.peek()]<T[i]){
                      int thisIndex = index.pop();
                      res[thisIndex] = i-thisIndex;
                  }
                  index.push(i);
              }
              while(!index.isEmpty()){
                  res[index.pop()] = 0;
              }
              return res;
          }
      }
    

Search

    Table of Contents