LettCode每日一题/Java

title: LeetCode每日一题
copyright: true
toc: true
tags:

Java
算法
categories:
编程
abbrlink: 10097df6
date: 2020-05-25 19:56:04

LettCode每日一题/Java

题目链接，代码，讲解思路，附带Java知识点

五月

2020/05/25

2020/05/25题目描述

class LRUCache {
 int capacity;
 private Map<Integer, Integer> map = new LinkedHashMap<Integer, Integer>();
 public LRUCache(int capacity) {
     this.capacity = capacity;
 }
 public int get(int key) {
     Integer tmp  = -1;
     if (map.containsKey(key)) {
         tmp = map.get(key);
         map.remove(key);
         map.put(key, tmp);
     }
     return tmp;
 }
 public void put(int key, int value) {
     if(map.containsKey(key)) {
         map.remove(key);
     }
     else if ( capacity == 0 ) {
         Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
         iterator.next();
         iterator.remove();
     }
     else {
         capacity--;
     }
     map.put(key, value);
 }
}

思路讲解

链接

六月 0602-0607

20200/06/02

2020/03/02题目：https://leetcode-cn.com/problems/reverse-linked-list/
1. 代码 ```java /**
- Definition for singly-linked list.
- public class ListNode {
- int val;
- ListNode next;
- ListNode(int x) { val = x; }
- } */ class Solution { public ListNode reverseList(ListNode head) { ListNode resetHead = null; ListNode currentNode = head; ListNode tempNode = null; while( currentNode!= null ) {
```
   tempNode = currentNode.next;
   currentNode.next = resetHead; //指向反向
   resetHead = currentNode;  //“头部”移动
   currentNode = tempNode;
```
  } return resetHead; } } ```

思路
要求将 1->2->3->4->5->NULL实现反转5->4->3->2->1->NULL，想法是可以通过简单的将链表指向反转，即使用两个指针，一个指向当前所在节点A,另一个指向前一个节点B，原本A->B，可以变成B->A，接着移动节点。
时间复杂度O(1),空间复杂度O(n)

2020/06/02题目：https://leetcode-cn.com/problems/qiu-12n-lcof/

代码：

class Solution {
public int sumNums(int n) {
  int sum = n;
  boolean flag = n > 0 && (sum += sumNums(n-1)) > 0;
  return sum;
}
}

思路：不可使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句实现数加，则通过&&操作来完成判断操作(不一定成立)和求和操作(添加必成立条件)。
Java在使用逻辑操作符的时候，存在一种短路现象，即一旦可以确定整个表达式的值，就不会再接着计算剩余的部分，如testA()&&testB(),当testA()返回值为true时，会接着计算testB()的值；当testA()返回false时，整个算式的值已经确定，testB()不执行，应用这样的机制来实现题目中隐含的条件判断。所以&&称为短路与，||称为长路与

2020/06/03

题目：https://leetcode-cn.com/problems/new-21-game/动态规划题

代码：

class Solution {
public double new21Game(int N, int K, int W) {
  double[] dp = new double[K+W];
  double sum = 0;
  if (K + W <= N) return 1.0;
  for ( int i = K ; i <= N ; i++ ) {
      dp[i] = 1 ;
  }
  for (int i = K ; i< K + W ; i++) {
      sum += dp[i];
  }
  for ( int i = K-1 ; i >= 0 ; i--) {
      dp[i] = sum / W;
      sum = sum - dp[i+W] + dp[i];
  }
  return dp[0];
}
}

思路
1. 定义数组元素的含义，假设一维数组dp[i]为Alice开始持有的数字i并获胜的概率
2. 数组元素间的关系和初始值
  1. 当 i>N时，dp[i]=0;
  2. 当K<=i<=N时，dp[i]=1;
  3. 当0<=i<K时，dp[i]=(dp[i+1]+dp[i+2]+…+dp[i+W])/W;
3. 然后一步步倒退，可以计算出当dp[0]，即Alice开始持有的数字为0获胜的概率，即题解
4. 为什么除以W参考链接
时间复杂度空间复杂度O(N+M),但还可以再降

2020/06/04

题目：https://leetcode-cn.com/problems/rotting-oranges/
该题为求无向图的最短路径，采用广度优先算法

代码

class Solution {
public int orangesRotting(int[][] grid) {
  //p1,p2为对应的x,y方向操作，目的是为了减少后面上下移动的代码重复度
  int[] p1 = {1,-1,0,0};
  int[] p2 = {0,0,1,-1};
  Deque<int[]> queue = new ArrayDeque<int[]>();

  int count = 0;//计算新鲜橘子的数量
  for ( int i = 0; i < grid.length ;i++) {
      for (int j = 0; j < grid[0].length ; j++) {
          if ( grid[i][j] == 2) {
              queue.offer(new int[] {i,j});
          }
          else if(grid[i][j] == 1) {
              count++;
          }
      }
  }

  int time = 0;
  while (!queue.isEmpty() && count >0) { //添加count>0的原因是当第一次所有橘子都腐烂时，队列中还存在元素，但这一步并不需要计算在最短的时间内
      time++;
      int size = queue.size();
      for ( int i = 0 ; i < size;i++) { //每一轮都将队列中的元素全部利用，即所有腐烂的橘子都会作用
          int[] temp = queue.poll();
          for(int j = 0; j < p1.length ;j++) {
              int x = temp[0] + p1[j];
              int y = temp[1] + p2[j];
              if( x>=0 && x < grid.length && y>=0 && y<grid[0].length&&grid[x][y]==1) {
                  grid[x][y] = 2;
                  queue.offer(new int[] {x,y});
                  count--;
              }
          }
      }
  }
  if (count!=0) time = -1;
  return time;
}
}

思路
1. 通过该题的描述，可以发现其本质是无向图的最短路径问题，故采用BFS。
2. 初始时，首先进行遍历，将所有腐烂的橘子都加入到队列中，并统计新鲜橘子的数量；
3. 在该题中，在每轮中，需要将腐烂的橘子的上下左右中存在的新鲜橘子加入的队列中，这里通过两个数组p1,p2来简化上下左右加入过程中的代码；
4. 在问题的具体实现方面，需要注意的是，当第一次出现所有的橘子都被腐烂的情况时，队列中会加入新腐烂的橘子，队列不为空，所以使用!queue.isEmpty() && count >0来使得出现该情况时就会直接结束对队列的操作。
时间复杂度？空间复杂度？

题目：https://leetcode-cn.com/problems/product-of-array-except-self/

代码

class Solution {
public int[] productExceptSelf(int[] nums) {
  int length = nums.length;
  int[] Right = new int[length];
  int[] output = new int[length];

  output[0] = 1;
  Right[length-1] = 1;
  for (int i = 1 ; i < length; i++) {
      output[i] = output[i-1] * nums[i-1];
  }
  for ( int i = length - 2; i>= 0 ; i--) {
      Right[i] = Right[i+1] * nums[i+1];
      output[i] *= Right[i];
  }

  return output;
}
}

思路
1. 在该题中，output[index]的值为下标index中的全部前缀元素与后缀元素的乘积，可以找到index与其前缀(后缀)元素积的关系，即output[i] = output[i-1] * nums[i-1];这里使用output先计算不同index的前缀元素积，后缀使用Right数组存放不同index对应的后缀元素积，有Right[i] = Right[i+1] * nums[i+1];
2. 当index=0时，前缀元素积存在初值1，当index=length-1时，后缀元素积有初值1
时间复杂度O(n),空间复杂度O(n)

2020/06/05

题目：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/

代码：

class Solution {
public int[] spiralOrder(int[][] matrix) {
  int m = matrix.length ;
  if(m == 0) return new int[0];
  int n = matrix[0].length;
  int[] res = new int[m*n];
  int index = 0;
  int left = 0 ,right = n-1 ,up = 0 , down = m-1;
  while(true) {
      for (int i = left ;i <= right;i++) {
          res[index++] = matrix[up][i];
      }
      up++;
      if(up>down) break;
      for ( int i = up ; i <= down ;i++) {
          res[index++] = matrix[i][right];
      }
      right--;
      if(left>right) break;
      for ( int i = right ;i >=left;i--) {
          res[index++] = matrix[down][i];
      }
      down--;
      if(up>down) break;
      for (int i = down ; i >= up;i--) {
          res[index++] = matrix[i][left];
      }
      left++;
      if(left>right) break;
  }
  return res;
}
}

思路1
1. 主要实现的思路如下图所示，按照螺旋读取设置的读取顺序是右、下、左、上，而且在每一次读完一个方向时，矩阵的规模都会缩小，通过更改矩阵边界值up,down,left,right来实现
2. 按照1中所描述的思路，我们可以使用while循环来实现螺旋读取，但是由于存在像上图一般的5的情况，当按照右读的顺序读取完就应该结束循环，由于不同矩阵的情况不同，在我们对某一个方向上的读取完成后都要进行一个判定，当某两条边界交错时（up>down或者left>right）就完成了读写，结束循环。
3. 时间复杂度O(m*n)空间复杂度O(1)

思路2：出处

可以模拟打印矩阵的路径。初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，则顺时针旋转，进入下一个方向。
判断路径是否进入之前访问过的位置需要使用一个与输入矩阵大小相同的辅助矩阵 visited，其中的每个元素表示该位置是否被访问过。当一个元素被访问时，将 visited中的对应位置的元素设为已访问。
如何判断路径是否结束？由于矩阵中的每个元素都被访问一次，因此路径的长度即为矩阵中的元素数量，当路径的长度达到矩阵中的元素数量时即为完整路径，将该路径返回。

代码：

class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
   return new int[0];
}
int rows = matrix.length, columns = matrix[0].length;
boolean[][] visited = new boolean[rows][columns];
int total = rows * columns;
int[] order = new int[total];
int row = 0, column = 0;
int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int directionIndex = 0;
for (int i = 0; i < total; i++) {
   order[i] = matrix[row][column];
   visited[row][column] = true;
   int nextRow = row + directions[directionIndex][0], nextColumn = column + directions[directionIndex][1];
   if (nextRow < 0 || nextRow >= rows || nextColumn < 0 || nextColumn >= columns || visited[nextRow][nextColumn]) { //通过是否可能越界来判断是否需要转向
       directionIndex = (directionIndex + 1) % 4; //妙，方向轮转
   }
   row += directions[directionIndex][0];
   column += directions[directionIndex][1];
}
return order;
}
}

3.

时间复杂度O(mn),空间复杂度O(mn)——因为多使用了visit数组

题目：https://leetcode-cn.com/problems/distribute-candies-to-people/

代码：

class Solution {
public int[] distributeCandies(int candies, int num_people) {
  int[] ans = new int[num_people];
  int count = 1,index = -1;
  while(candies>0){
      index++;
      index = index % num_people;
      if(candies >= count){
          ans[index] += count;
          candies -= count;
          count++;

      }
      else{
          ans[index] += candies;
          candies=0;
      }

  }
  return ans;
}
}

思路：
使用count记录需要每次需要分发的糖果，使用index = index % num_people来实现分发对象的轮转。
时间复杂度O(max(sqrt(G),N))，空间复杂度O(1)

2020/06/06

题目：https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/

代码：

class Solution {
public int[][] findContinuousSequence(int target) {
  int temp , start = 0;
  int limit = (int)Math.sqrt(2*target);
  List<int[]> list = new ArrayList<int[]>();
  for (int i = limit ;i >= 2;i--) {
      temp = target - i*(i-1)/2;
      if ( temp % i == 0) {
          start = temp/i;
          int[] n = new int[i];
          for ( int j = 0 ; j < i;j++) {
              n[j] = start+j;
          }
          list.add(n);
      }
  }
  int[][] res = new int[list.size()][];
  for(int i = 0;i<res.length;i++) {
      res[i] = list.get(i);
  }
  return res;
}
}

思路1：
1. 由题意值，target可以由下述数学公式表达 $LeetCode每日一题 - 图2$ %7D%7B2%7D%20%E2%80%94%E2%80%94%EF%BC%881%EF%BC%89%0A#card=math&code=target%20%3D%20na_1%2B%5Cfrac%7Bn%28n-1%29%7D%7B2%7D%20%E2%80%94%E2%80%94%EF%BC%881%EF%BC%89%0A)

在该公式中，我们可以将n作为窗口的大小，a1作为该窗口的初始值 $LeetCode每日一题 - 图3$ %7D%7B2%7D%7D%7Bn%7D%20%E2%80%94%E2%80%94%EF%BC%882%EF%BC%89%0A#card=math&code=a_1%20%3D%20%5Cfrac%7Btarget-%5Cfrac%7Bn%28n-1%29%7D%7B2%7D%7D%7Bn%7D%20%E2%80%94%E2%80%94%EF%BC%882%EF%BC%89%0A)

在这个过程中，当a1=1时，我们可以计算出，最大的窗口应为2*target的平方(取整)。

2.

在题目中要求序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。所以我们这里从“最大窗口数”开始进行遍历，找其中满足条件的n和a1的组合。

3.

最后将List输出为二维数组。

思路2——暴力滑窗法

class Solution {
public int[][] findContinuousSequence(int target) {
  List<int[]> list = new ArrayList<>();

  //🧠里要有一个区间的概念，这里的区间是(1, 2, 3, ..., target - 1)
  //套滑动窗口模板，l是窗口左边界，r是窗口右边界，窗口中的值一定是连续值。
  //当窗口中数字和小于target时，r右移; 大于target时，l右移; 等于target时就获得了一个解
  for (int l = 1, r = 1, sum = 0; r < target; r++) {
      sum += r;
      while (sum > target) {
          sum -= l++;
      }
      if (sum == target) {
          int[] temp = new int[r - l + 1];
          for (int i = 0; i < temp.length; i++) {
              temp[i] = l + i;
          }
          list.add(temp);
      }
  }

  int[][] res = new int[list.size()][];
  for (int i = 0; i < res.length; i++) {
      res[i] = list.get(i);
  }
  return res;
}
}

题目：https://leetcode-cn.com/problems/longest-consecutive-sequence/

代码：

class Solution {
public int longestConsecutive(int[] nums) {
int max = 0 ;
Set<Integer> numSet = new HashSet<Integer>();
for( int x : nums){
   numSet.add(x);
}
for(int num : numSet){
   if(!numSet.contains(num-1)){
       int currentNum = num;
       int currentMax = 1;
       while(numSet.contains(currentNum+1)){
           currentMax++;
           currentNum++;
       }
       max = Math.max(max,currentMax);
   }
}
return max;
}
}

2.

思路：

     1. 遍历数组中的元素x，通过查看其相邻元素是否存在于数组之中来判断是否连续,连续序列应该是仅从这个序列最小的数开始查找判断的（这样可有效降低运行时间），这个通过判断x-1在数组中来实现仅从最小值开始，之后就判断x+1是否在数组中，并记录长度。
     2. 由于题目给定的数组中元素可能存在重复的情况，而且要求时间复杂度为O(n)，而且在这个过程中频繁应用“包含于”这样的语义，故将数组转换为HashSet，在HashSet中，使用contains(包含于)的时间复杂度为O(1),也可以满足题目要求。
     3. 时间复杂度O(n),空间复杂度O(n)

2020/06/07

题目：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/

代码：

class MaxQueue {
public Deque<Integer> main_que;
public Deque<Integer> sup_que;
public MaxQueue() {
  main_que = new ArrayDeque<>();
  sup_que = new ArrayDeque<>();
}

public int max_value() {
  if(main_que.isEmpty())   return -1;
  return sup_que.peek();
}

public void push_back(int value) {
  main_que.offer(value);
  while(!sup_que.isEmpty()&&value > sup_que.peekLast()){
      sup_que.pollLast();
  }
  sup_que.offer(value);
}

public int pop_front() {
  if(main_que.isEmpty()) return -1;
  int res = main_que.poll();
  if(res == sup_que.peek()){
      sup_que.poll();
  } 
  return res;
}
}

思路：
1. push_back:向队列中传入元素；pop_front：删除队列头部元素
2. 由于还要保存最大值，如果我们仅使用一个额外的int变量进行保存，那么当目前的最大值弹出，我们就无法及时知道弹出之后队列的最大值，所以这里需要使用一个辅助队列来存储当前队列的最大值以及可能出现的次大值，通过!sup_que.isEmpty()&&value > sup_que.peekLast()使得在该辅助队列的队尾存储的值总是当前添加的值，这样不论主队列中的弹出顺序如何，辅助队列中总是存储着与之对应的最大值。
3. 实现push_back的同时，要比较要压入的值如当前的最大值进行比较，实现最大值的更新；实现pop_front的时候，如果弹出的值是最大值，需要删除辅助队列中的相应值。
4. 题目：https://leetcode-cn.com/problems/word-ladder-ii/
代码： ```java public class Solution { private static final int INF = 1<<20;

public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
    Map<String,Integer> wordId = new HashMap<>();//单词到ID
    ArrayList<String> idWord= new ArrayList<>();//id到单词

    int id = 0;
    //将单词都加入至wordID中，每个单词有一个ID
    for(String s : wordList){
        wordId.put(s,id++);
        idWord.add(s);
    }
    //wordList中无enword
    if(!wordId.containsKey(endWord)) return new ArrayList<>();
    //把begin加入
    if(!wordId.containsKey(beginWord)){
        wordId.put(beginWord,id);
        idWord.add(beginWord);
    }
    //边
    int size = idWord.size();
    ArrayList<Integer>[] edges = new ArrayList[size]; //edges存放的是对每个点的连接信息，所以其大小应为点的总数，存放的类型是List<Integer>
    for(int i = 0 ;i<size; i++ ){
        edges[i] = new ArrayList<>();
    }
    for(int i = 0 ; i < size ; i++){
        for (int j = i+1 ; j < size ; j++){
            if(differentNum(idWord.get(i),idWord.get(j))){
                edges[i].add(j);
                edges[j].add(i);
            }
        }
    }

    int dest = wordId.get(endWord);//获取目标字符串对应的id
    List<List<String>> res = new ArrayList<>();
    int[] cost = new int[id+1]; //存放到每个点的代价,cost[i]为起点到i的距离
    for(int i = 0 ;i <id+1; i++){
        cost[i] = INF;
    }

    //将起点加入队列
    Queue<ArrayList<Integer>> que = new LinkedList<>();
    ArrayList<Integer> tmpBegin = new ArrayList<>();
    tmpBegin.add(wordId.get(beginWord));
    que.add(tmpBegin);
    cost[wordId.get(beginWord)] = 0;

    //搜索
    /*
    * hit:0;hot:1;dot:2;dog:3;lot:4;log:5;cog:6.
    * 第一轮[0],第二轮[0,1],第三轮[[0,1,2],[0,1,4]],第四轮[[0,1,4],[0,1,2,3]]
    * 第五轮[[0,1,2,3],[0,1,4,5]],第六轮[[0,1,4,5],[0,1,2,3,6]],
    * 第七轮[[0,1,2,3,6],[0,1,4,5,6]]
    * */
    while(!que.isEmpty()){
        ArrayList<Integer> current = que.poll();
        int last = current.get(current.size()-1);
        if(last == dest){
            ArrayList<String> tmp = new ArrayList<>();
            for (int index : current){
                tmp.add(idWord.get(index));
            }
            res.add(tmp);
        }
        else{
            for(int i = 0; i < edges[last].size() ;i++){
                int to = edges[last].get(i);
                if(cost[last] + 1 <= cost[to]){  //这一条件是生成最短路径的关键,如在该情况下cost[4]=2,那么在[0,1,2]序列的时候就没有必要继续添加4了，因为此时起始点到4的距离更近
                    cost[to]=cost[last]+1;
                    ArrayList<Integer> tmp = new ArrayList<>(current);//将current的内容拷贝至tmp
                    tmp.add(to);
                    que.add(tmp);
                }
            }
        }
    }

    return res;
}
public  static  boolean differentNum(String s1 , String s2){
    int res = 0;
    for ( int i = 0; i< s1.length() && res < 2 ;i++ ){
        if (s1.charAt(i)!=s2.charAt(i)){
            res++;
        }
    }
    return  res==1;
}

}



   2. 
思路：

      1. 题中要求最短转换序列，则首先想到图的最短路径求法BFS，所以我们将该题所给数组抽象为图。将每个单词抽象为一个点，如果两个单词仅相差一个单词，我们则认为这两个点是连通的，边的权重都为1。
      2. 在具体转换为图的过程，为了操作简单，我们为每个单词建立一个序号，并建立单词、序号之间的双向映射(wordID和idWord),并建立这些单词之间的连通关系，即记录边的信息edges。
      3. 使用BFS对图进行遍历，并返回最后的解。
      4. [参考链接1](https://leetcode-cn.com/problems/word-ladder-ii/solution/dan-ci-jie-long-ii-by-leetcode-solution/)

<a name="fa4d1ac6"></a>
## 六月 0608-0614

<a name="dbf3220d"></a>
### 2020/06/08

1. 
题目：[https://leetcode-cn.com/problems/satisfiability-of-equality-equations/](https://leetcode-cn.com/problems/satisfiability-of-equality-equations/)  并查集

   1. 
代码——并查集Union-Find:
```java
//加权quick-union算法，通过sz数组将小树合并到大树上
//还可继续使用路径压缩的方法来优化
public class UnionFind {
    public  int[] id ;
    public  int[] sz;
    int count ;

    public UnionFind(int count) {
        this.count = count;
        id = new int[count];
        sz = new int[count];
        for(int i = 0; i < count; i++){
            id[i] = i;
            sz[i] = 1;
        }
    }

    public int count(){
        return  count;
    }
    public int find( int p ){
        while (p!=id[p]) p = id[p];  //未进行路径压缩的方法
        return p ;
    }
    public  boolean connection(int p , int q){
        if(find(p) == find(q)) return true;
        return false;
    }
    public void union(int p , int q){
        int pId = find(p);
        int qId = find(q);
        if(pId == qId ) return;
        if(sz[pId] < sz[qId]){
            id[pId] = qId;
            sz[qId] += sz[pId];
        }
        else {
            id[qId] = pId;
            sz[pId] += sz[qId];
        }
        count --; //每合并一次，并查集的总数少一次
    }
}

代码——具体实现部分：

public static  boolean equationsPossible(String[] equations) {
        UnionFind uf = new UnionFind(26);//equations中可能含有任意的小写字母
        for(String s : equations){
            if(s.charAt(1) == '='){
                char p = s.charAt(0);
                char q = s.charAt(3);
                uf.union(p-'a',q-'a');
            }
        }

        for( String s : equations){
            if(s.charAt(1) == '!'){
                char p = s.charAt(0);
                char q = s.charAt(3);
                if(uf.connection(p-'a',q-'a')) return  false;
            }
        }
        return true;
    }

思路：
将 equations 中的算式根据 == 和 != 分成两部分，先处理 == 算式，使得他们通过相等关系各自结合形成集合，!= 算式，不等号即两者不连通，若不等式两端的字母处在同一个集合，则有矛盾，返回false。

题目：https://leetcode-cn.com/problems/coin-change/

代码：

class Solution {
public int coinChange(int[] coins, int amount) {
  if(amount < 0 ) return -1;
  if(amount == 0 ) return 0;
  int[] dp = new int[amount+1];
  Arrays.fill(dp,amount+1);//dp[i]恒小于amount+1

  dp[0] = 0;
  for(int i = 0; i <dp.length;i++){
      for(int x : coins){
          if(i-x < 0) continue;
          dp[i] = Math.min(dp[i],1+dp[i-x]);
      }
  }
  if(dp[amount] == amount+1)
      return -1;
  return dp[amount];
}
}

思路：
1. dp[i]为凑成总金额i过程中所需要的最少的硬币数，当amout = 0时，dp[0] = 0。 $LeetCode每日一题 - 图4$

这样就可以使用动态规划的思想来进行问题的求解。

2.

BFS:等价于在图上求最短路径，起点为amout，终点为0。使用visited数组记录某个节点是否被访问，防止重复访问，之后采用BFS求解即可。

2020/06/09

题目：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof/

代码：

class Solution {
public int translateNum(int num) {
  List<Integer> n = new ArrayList<>();
  while(num>=10){
      n.add(num%10);
      num = num/10;
  }
  n.add(num);
  int sz = n.size();
  if(sz==1) return 1;
  int[] dp = new int[sz];
  dp[0] = 1;
  if(sz >= 2){
      int temp = n.get(sz-1)*10 + n.get(sz-2);
      if(temp >= 10 && temp<=25) dp[1] = 2;
      else dp[1] = 1;
      for(int i = sz - 3 , j = 2; i >= 0; i-- ,j++){
          int tmp = n.get(i+1)*10 + n.get(i);
          if( tmp >= 10 && tmp <= 25) dp[j] = dp[j-1]+ dp[j-2];
          else dp[j] = dp[j-1];
      }
  }
  return dp[sz-1];
}
}

思路：
1. 使用动态规划的思想，dp[i]为i位数最多的翻译方法，当第i位与i-1位组成的数字在[0,25]之间，dp[i] = dp[i-1]+dp[i-2];否则dp[i] = dp[i-1]; $LeetCode每日一题 - 图5$

2.

在具体实现方面，为了方便将num中的数字进行添加和组合，将num转换为数字列表，方便实现存取。

3.

在初值方面，dp[0]= 1，dp[1]=1或2。

4.

时间复杂度O(n),空间复杂度O(N)

题目：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

代码：

class Solution {
public int maxProfit(int[] prices) {
  int sz = prices.length;
  if(sz <= 1){
      return 0;
  }
  //第i天的最大利润=第i天卖出价格-i天内买入的最低价格
  int max = 0 , min = prices[0];
  for(int i = 1; i < sz; i++){
      max = Math.max(max, prices[i] - min);
      min = Math.min(min , prices[i]);
  }
  return max;
}
}

思路：
使用dp思想，第i天获得的最大利润dp[i]=第i天的卖出价格price[i]-i天内最低的买入价格min，题目的解是最大的利润，所以我们直接可以使用max进行目前最大利润的存储，不需要记录所有的dp[i]。

2020/06/10

题目：回文数https://leetcode-cn.com/problems/palindrome-number/

代码：

//   使用了字符串的解法
public static boolean isPalindrome(int x) {
  if(x<0) return false;
  List<Integer> num = new ArrayList<>();
  while(x>=10){
      num.add(x%10);
      x /= 10;
  }
  num.add(x);
  int sz = num.size();
  for(int i = 0 ,j = sz-1;i<sz;i++,j--){
      if(num.get(i)!=num.get(j)) return false;
  }
  return true;
}
//    不使用字符串的解法
public static  boolean isPalindrome1(int x){
  int res = 0, temp = x;
  if(x < 0)   return false;
  while (temp>=10){
      res = res*10 + temp%10;
      temp /= 10;
  }
  res = res*10+temp;
  return x==res;
}

思路：
1. 使用字符串，即将num中的各个数字分离开，通过比较前序读和后序读的数字是否一致来判断是否为回文。
2. 不使用字符串，正常的num从左到右，位次由高到低，如果其是回文，则从右往左读，位次由高变低，得到的数字应与num相等。
3. 题目：二叉树的直径https://leetcode-cn.com/problems/diameter-of-binary-tree/ no

代码

public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public int ans = 0;
//    public int rdeep = 0;
public int deepTree(TreeNode root){
  if(root == null) return 0;
  int left = deepTree(root.left);
  int right = deepTree(root.right);
  ans = Math.max(ans,left+right);
  return  Math.max(left,right)+1;
}
public int diameterOfBinaryTree(TreeNode root) {
  deepTree(root);
  return ans-1;
}

思路：
1. 一颗二叉树的直径长度是任意两个节点路径长度中的最大值，这条路径不一定经过根节点。
2. root的高度=max(左子树的高度，右子树的高度)+1；root的直径=左子树的高度+右子树的高度。但是直径路径不一定经过根节点，所以需要去搜索一遍root所有的子树对应的直径，去取最大值。
3. 题目:https://leetcode-cn.com/problems/partition-array-into-three-parts-with-equal-sum/

代码：

/*该题还可以使用双指针遍历，
* 使用双指针left，right, 从数组两头开始一起找，节约时间
* 当 left + 1 < right 的约束下，可以找到数组两头的和都是 sum/3,那么中间剩下的元素和就一定也是sum/3;left + 1 < right的约束就是要中间有剩下的元素
*/
public static boolean canThreePartsEqualSum(int[] A) {
  int av = 0 ,sz = A.length,count = 3 , sum = 0;
  for(int x : A){
      av += x;
  }
  if(av%3!=0) return false;
  av /= 3;

  for(int i = 0; i<sz;i++) {
      sum += A[i];
      if(sum==av){
          if(--count == 0) return true; //当count=0时，无论是否遍历至最后一个数字，都已经存在3个分组了，此时后面剩余的数字的均值都为0，可任意合并，故可直接退出
          sum=0;
      }
  }
  return false;
}

思路
计算出每个分块需要的和的大小，之后遍历，找到满足三个分块即可，此时数组中若还有剩余，剩余部分和为0，可合并至第三个分块，故可不管。

2020/06/11

题目:每日温度https://leetcode-cn.com/problems/daily-temperatures/

代码：

class Solution {
public int[] dailyTemperatures(int[] T) {
 int sz = T.length , count = 0;
  int[] ans = new int[sz];
  Stack<Integer> sk = new Stack<>();

  for(int i = 0;i<sz ; i++){
     while (!sk.empty()&& T[i] > T[sk.peek()]){
         int index = sk.pop();
         ans[index] = i - index;
     }
     sk.add(i);
  }
  return ans;
}
}

思路：
1. 该题要找的时某个数字的下一较大值，使用递减栈。将列表中的元素值存入栈中，当下一刻要存的值after大于栈顶的值top时，如果存入after将会破坏递减特性，故将栈中小于after的元素全部弹出，这些元素的下一较大值即为after。
2. 该题是求元素间的距离，为了方便，在入栈的时候，我们仅存入索引，通过索引进行进栈出栈的动作。

题目：下一个更大元素https://leetcode-cn.com/problems/next-greater-element-i/

代码：

class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
  Stack<Integer> sk = new Stack<>();
  Map<Integer,Integer> map = new HashMap<>();
  int sz = nums1.length;
  int[] ans = new int[sz];
  for(int i = 0 ;i < nums2.length;i++){
      while (!sk.empty() && sk.peek() < nums2[i]) {
          map.put(sk.pop(),nums2[i]);
      }
      sk.add(nums2[i]); //该题直接存放元素即可，没必要存储索引
  }
  while (!sk.empty()) map.put(sk.pop(),-1);
  for(int i = 0; i<sz;i++){
      ans[i] = map.get(nums1[i]);
  }
  return ans;
}
}

思路：
该题与题目一解题思路一致，但该题求得是nums1中元素在nums2中得下一更大值，对nums2进行题目一同一得操作，然后需要将栈顶元素与下一更大值建立映射，之后从映射关系选取nums1中得元素完成求解

题目：下一个更大元素(2)https://leetcode-cn.com/problems/next-greater-element-ii/

代码：

class Solution {
public int[] nextGreaterElements(int[] nums) {
  int sz = nums.length;
  int[] ans = new int[sz];
  Stack<Integer> sk = new Stack<>();
  Arrays.fill(ans,-1);
  for(int i = 0 ; i < 2*sz ;i++){
      while (!sk.empty() && nums[sk.peek()] < nums[i%sz])
          ans[sk.pop()%sz] = nums[i%sz];
      sk.push(i%sz);
  }
  return ans;
}
}

思路
该题主要在于循环数组的处理，我们只需要考虑索引indx在[0,2*nums.length)的情况即可,对于数组下标的处理使用模除即可满足数组元素的循环。

题目：接雨水https://leetcode-cn.com/problems/trapping-rain-water/

代码：

class Solution {
public int trap(int[] height  ) {
  //第一个0要处理
  int sum = 0;
  int sz = height.length;
  Stack<Integer> sk = new Stack<>();
  for(int i = 0 ; i < sz;i++){
      while (!sk.empty() && height[sk.peek()] < height[i] ){
          int h = height[sk.peek()];
          sk.pop();
          if(sk.empty()) break;
          int distance = i - sk.peek() - 1;
          int min = Math.min(height[sk.peek()],height[i]);
          sum = sum + distance*(min - h);
      }
      sk.push(i);
  }
  return sum; 
}
}

思路：
1. 利用前面几题的下一最大值的思想，当栈顶元素小于当前元素，说明在这两个元素之间可能存在水槽
2. 在计算水槽的大小时，存在[2,1,0,1,3]这种复杂的情况，我们可以按不同的高度(层)差*距离差，计算不同的水槽大小，比如[2,1,0,1]时，高度差为1，距离差为1。在计算h=[2,1,0,1,3]时(0已经弹出),h[3]时对应的高度差为0，距离差为1。在计算h[1]时，高度差为1，距离差为3，得到总的水槽大小为4
3. 距离差=当前元素下标-弹出栈顶元素top的下标；
  高度差=min(当前元素值，当前栈顶值)-top;取min是因为存在[3,1,0,1,2,5]这种类似的情景

2020/06/12

题目：两数之和https://leetcode-cn.com/problems/two-sum/

代码

class Solution {
public int[] twoSum(int[] nums, int target) {
  int[] res = new int[2];
  Map<Integer,Integer> set = new HashMap<>();
  for(int i = 0 ; i < nums.length ; i++){
      int another = target - nums[i] ;
      if (set.containsKey(another)) return new int[] {set.get(another),i};
      set.put(nums[i],i);
  }
  return res;
}
}

思路
在解决该题中，需要保持数组中元素和索引的对应关系，两层循环可以做到，但是时间复杂度不理想，可以借助哈希表来降低时间复杂度。在每一轮添加nums[i]时，检查哈希表中是否存在target-nums[i]并找出相应的索引即可。因为本题假设每种输入只对应一个答案，所以对target=9,nums=[5,4,4]这种情况不需要特别考虑。

题目：三数之和https://leetcode-cn.com/problems/3sum/

代码

class Solution {
public List<List<Integer>> threeSum(int[] nums) {
  List<List<Integer>> res = new LinkedList<>();
  int lg = nums.length;
  if ( lg < 3 ) return res;
  Arrays.sort(nums);
  for ( int index = 0 ; index < lg ; index++){
      int right = lg - 1;
      int target = 0 - nums[index];
      if ( index > 0 && nums[index] == nums[index-1]) continue;

      for ( int left = index + 1 ; left < lg ; left++){
          if ( left > index+1 && nums[left] == nums[left-1]) continue;
          while ( right > left && nums[right] + nums[left] > target) right--;
          if (left == right) continue;
          if(nums[right] + nums[left] == target){
              List<Integer> temp = new LinkedList<>();
              temp.add(nums[index]);
              temp.add(nums[left]);
              temp.add(nums[right]);
              res.add(temp);
          }
      }
  }
  return res;
}
}

思路
1. 如果将一个数固定A，那么该问题和两数之和就有一些类似，即B+C= target-num[i],这里可以使用双指针来简化操作。
2. 2.将数组排序，并使用双指针。对于去重问题，最大的难点是其可能存在多个相同的数字，使得A+B+C=target，如[1,0,-1,1],target=0，对于该问题，我们可以通过在遍历中加入控制条件来实现，对A(最外层遍历)和对于left指针来说，只从离下一不同元素最近的元素开始，仅从它们中的最后以为开始。由于数组是有序的，所以可以容易使得的List内元素也是有序的。

2020/06/13

题目：https://leetcode-cn.com/problems/climbing-stairs/

代码：

class Solution {
public int climbStairs(int n) {
  if(n == 1) return 1;
  if(n == 2) return 2;
  int past = 2 , ppast = 1 ,res = 0;
  for(int i = 3; i <= n; i++){
      res = past+ppast;
      ppast = past;
      past = res;
  }
  return res;
}
}

思路：
使用DP思想，dp[i]为爬i阶台阶的方法，dp[1]=1,dp[2] =2,dp[i]=dp[i-1]+dp[i-2]。由于在这个过程中，我们每次仅仅使用的只有dp[]的部分内容，所以可以直接使用两个变量来保存，即ppast和past。

题目：最长上升序列https://leetcode-cn.com/problems/longest-increasing-subsequence/

代码：

class Solution {
public int lengthOfLIS(int[] nums) {
 Stack<Integer> sk = new Stack<>();
  int sz = nums.length ,  res = 1;
  if(sz == 0) return 0;
  int max = Integer.MIN_VALUE;
  for (int i = 0 ; i < sz ; i++){
      while (!sk.isEmpty() && nums[i] <= sk.peek()){
          res = Math.max(sk.size(),res);
          max = Math.max(sk.pop(),max);
      }
      if (max > Integer.MIN_VALUE && nums[i] > max) res++;
      sk.push(nums[i]);
  }
  return Math.max(res,sk.size());
}
}

思路
1. 题目要求上升序列，可以采用单调栈的思想；
2. 但是题目存在[1,3,6,7,9,4,10,5,6]这种情况，仅仅使用单调栈，在遍历至4时，会将6,7,9全部弹栈，之后将10压栈时，计算的序列长度为1,3,4,10，正确的应为1,3,6,7,9,10。所以我们在这里使用一个max记录前一升序序列中的最大值，若当前的nums[i]>max，则通过res+1和max(res,sk.size())的方式延申前一较长升序序列。

2020/06/14

题目：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/submissions/
1. 代码： ```java //二分查找 class Solution { public int findBestValue(int[] arr, int target) { Arrays.sort(arr); int sz = arr.length , res = 0; if (arr[sz-1] < target/sz) return arr[sz-1]; //sum(arr)<target,直接返回最大值 int[] prefix = new int[sz+1]; for (int i = 1 ; i <= sz ; i++)//计算前缀，方便求解
```
  prefix[i] = prefix[i-1] + arr[i-1];
```
  int left = 0 , right = arr[sz-1] ; //原本这里的lfet和right都是下标，但是本题要寻找的解并不一定在数组arr中，这里使用值更贴合题意。 while (left <= right){
```
  int mid = (left+right)/2;
  int index = Arrays.binarySearch(arr,mid);
  if ( index < 0) index = -index - 1 ;
  //binarySearch的返回值：1、如果找到关键字，则返回值为关键字在数组中的位置索引;2、如果没有找到关键字，返回值为负的插入点值，所谓插入点值就是第一个比关键字大的元素在数组中的位置索引，即 (-(insertion point) - 1) 。
  int sum = prefix[index] + (sz-index)*mid;

  if ( sum <= target){
      left = mid + 1;
      res = mid; //保存了使得sum小于targe的最大值
  }
  else {
      right = mid - 1;
  }
```
  } //随着mid的增加,对应的abs(sum-target)应该大->小->大，所以题解只可能是res和res+1,故需要比较 int samllerSum = 0 ,biggerSum = 0; for (int x : arr){
```
  samllerSum += Math.min(x,res);
  biggerSum += Math.min(x,res+1);
```
  } if ( Math.abs(samllerSum-target) > Math.abs(biggerSum-target))
```
  return res+1;
```
  return res; } }

//暴力查找 public static int problem1300(int[] arr , int target){ // 随着value的增加，数组和与target的差值应该是大->小->大 int sz = arr.length; int mean = target/sz; int pre = Integer.MAX_VALUE; //记录前一轮的差值 int max = 0; for (int i : arr) max = Math.max(i,max); if (max < mean) return max; //总数和小于target for (int i = mean ; ; i++){ int sum = 0; for ( int v : arr) sum+=Math.min(i,v); int temp = Math.abs(sum-target); if ( temp >= pre) return i-1; //比较差值，看前一点是否是最小值。 pre = temp; } }



   2. 
思路1-二分查找：

      1. 将数组排序，通过二分查找的方式不断缩短搜索空间，这里题解可能不为数组arr中的值，每次查找的范围不应该仅是数组中的离散元素(即仅通过索引查找)，应该是一个完整的区间(包括数组中的元素)，所以在具体二分查找的时候的搜索空间应在具体元素值的基础上进行变动。
      2. 在一般情况下，随着value值得增大，数组和与target的差值会大->小->大，所以我们只要记住使得sum<=target的最大value值即可，题解必在value和value+1(sum>target)之间。
   3. 
思路2——暴力查找

      1. 一般情况下查找的下界应该为target/arr.length(),value值逐渐增大，且随着value值增大，数组和与target的差值会大->小->大；
      2. 所以比较每一轮sum和target的差值cut，并记录差值较小时的value值，一旦当前轮次的cut大于等于上一轮的cut值，我们就可以认为上一轮可能时符合题解的value，添加等于是为了在多个符合题解的方案中取最小的value

<a name="7b003fce"></a>
## 六月0615-0622

<a name="4eab84ec"></a>
### 2020/06/15

1. 
题目：最长公共前缀https://leetcode-cn.com/problems/longest-common-prefix/

   1. 
代码：
```java
class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        int index = strs[0].length();
        for (String x : strs) index = Math.min(x.length(),index); //找到字符串的最小长度
        if (index == 0) return "";
        for (int i = 1 ; i < strs.length ; i++){
            for (int j = 0 ; j < index ; j++){
                if (strs[i].charAt(j) != strs[0].charAt(j)){
                    index = j;
                    break;
                }
            }
            if (index == 0) return "";
        }
        return strs[0].substring(0,index);
    }
}

思路——横向比较
1. 依次遍历字符串数组中的每个字符串，对于每个遍历到的字符串，更新最长公共前缀，当遍历完所有的字符串以后，即可得到字符串数组中的最长公共前缀。
2. 在具体实现方面，我们先找到该数组中的最短字符串的长度index，并以index作为每个字符串比较的索引下界，因为在该数组的最长公共前缀的长度应<=index，只需比较[0,index]即可。
3. 题目：岛屿的最大面积https://leetcode-cn.com/problems/max-area-of-island/

DFS代码：

public static int problem695(int[][] grid){
  int res = 0 ;
  for (int i = 0 ; i < grid.length ; i++){
      for (int j = 0 ; j < grid[0].length ; j++){
          if ( grid[i][j] ==1 ){
              res = Math.max(res,dfs_695(i,j,grid));
          }
      }
  }
  return res;
}
public static int dfs_695(int x , int y , int[][] grid){
  if( x < 0 || x >= grid.length || y < 0 || y>= grid[0].length || grid[x][y]==0 )
      return 0;
  grid[x][y] = 0 ;//沉岛
  int num = 1;
  num+= dfs_695(x+1 , y ,grid);
  num+=dfs_695(x-1,y,grid);
  num+=dfs_695(x,y-1,grid );
  num+=dfs_695(x,y+1,grid);
  return num;
}

DFS思路：
1. 题解即网格中每个连通形状的面积，然后取最大值。
2. 如果在一个土地上，以 4 个方向探索与之相连的每一个土地（以及与这些土地相连的土地），那么探索过的土地总数将是该连通形状的面积。为了确保每个土地访问不超过一次，我们每次经过一块土地时，将这块土地的值置为 0。这样我们就不会多次访问同一土地。
3. 使用DFS会先向着某个土地的一个方向进行搜索，之后再换方向。

BFS代码：

public static int problem695(int[][] grid){
  int[] opx = {1,-1,0,0};
  int[] opy = {0,0,1,-1};
  int max = 0 ;
//        boolean[][] visit = new boolean[grid.length][grid[0].length]; 可以不使用visit数组来标记,可以通过使用一个岛之后就将其置0实现(沉岛)
  int[][] visit = new int[grid.length][grid[0].length];
  Deque<int[]> que = new ArrayDeque<>();
  for (int i = 0 ; i < grid.length ; i++){
      for (int j = 0 ; j < grid[0].length ; j++){
          int conut = 0;
          if(grid[i][j]==1){
              que.offer(new int[] {i,j});
              grid[i][j] = 0;
              conut++;
          }
          while (!que.isEmpty()){
              int size = que.size();
              for (int k = 0 ; k < size;k++){
                  int[] temp = que.poll();
                  for (int l = 0 ; l < opx.length ; l++){
                      int x = temp[0] + opx[l];
                      int y = temp[1] + opy[l];
                      if (x>=0 && x<grid.length && y>=0 && y < grid[0].length  && grid[x][y] == 1) {
                          que.offer(new int[] {x,y});
                          grid[x][y] = 0;
                          conut++;
                      }
                  }
              }
          }
          max = Math.max(conut,max);
      }
  }
  return  max ;
}

思路——BFS
1. 该题需要搜索相连的土地，BFS也可以完成。
2. 在某片土地上，先将其周围存在的土地加入队列，成为下一轮次需要遍历的元素，依次遍历完所有相邻的土地。

2020/06/16

题目：二叉树序列化与反序列化https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

代码：

public class Codec {

// Encodes a tree to a single string.
public String serialize(TreeNode root) {
  StringBuilder res = new StringBuilder();
  Queue<TreeNode> treelist = new LinkedList<>();
  treelist.add(root);
  while (!treelist.isEmpty()){
      TreeNode temp = treelist.poll();
      if (temp ==null){
          res.append("null,");
      }
      else {
          treelist.offer(temp.left);
          treelist.offer(temp.right);
          res.append(temp.val+",");
      }
  }
  res.setLength(res.length()-1);
  return res.toString();
}

// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
  String[] nodes = data.split(",");
  TreeNode root = getNode(nodes[0]);
  if (root == null) return null;
  Queue<TreeNode> parents = new LinkedList<>();
  TreeNode parent = root;
  boolean isLeft = true;
  for (int i = 1 ; i < nodes.length ; i++){
      TreeNode temp = getNode(nodes[i]);
      if (isLeft)
          parent.left = temp;
      else
          parent.right = temp;
      if (temp!=null)
          parents.offer(temp);
      isLeft = !isLeft;
      if (isLeft)//当重新变为左孩子时，即一个父节点的孩子节点已经寻找完，该下一个节点进行孩子节点的寻找了
          parent = parents.poll();

  }
  return root;
}
private  TreeNode getNode(String s){
  if (s.equals("null")) return null;
  return new TreeNode(Integer.valueOf(s));
}
}

思路：
1. 序列化：序列化即二叉树的编码过程，可以使用BFS来进行二叉树的遍历。
2. 反序列化：即解码过程，根据序列化使用BFS的特点，第i层的父节点的所有孩子节点都在第i+1层，所以先遍历第i层的父节点，找到i+1层对应的孩子节点，依次类推。按题中要求，每个父节点总会存两个孩子节点，且顺序为左右，可使用一个指示变量isLeft来标志当前节点是左孩子还是右孩子。
3. 题目：字符串压缩https://leetcode-cn.com/problems/compress-string-lcci/

代码

class Solution {
public String compressString(String S) {
  int length = S.length();
  if(length==0) return S;
  int left = 0, right = 0 , count = 0 ;
  StringBuilder ans = new StringBuilder();
  for (; right < length ; right++  ){
      if ( S.charAt(left) == S.charAt(right)){
          count ++;
      }
      else{
          ans.append(S.charAt(left)).append(count);
          left = right;
          count = 1;
      }
  }
  if (right == length){
      ans.append(S.charAt(right-1)).append(count);
  }

  if (length <= ans.length()) return S;
  return  ans.toString();
}
}

思路：
使用左右指针来完成相同字符串的压缩，左指针指向的是对应字符，右指针与左指针只差即为字符出现个数。

2020/06/17

题目：最佳观光组合https://leetcode-cn.com/problems/best-sightseeing-pair/

代码

class Solution {
public int maxScoreSightseeingPair(int[] A) {
  int sz = A.length;
  int max = A[0]+0 , res = 0;
  for(int j = 1 ; j < sz ; j++){
      res = Math.max(max+A[j]-j,res); // 先求res后更新max，确保max是区间[0,j)的值
      max = Math.max(A[j]+j,max);
  }
  return res;
}
}

思路：
该题是找A[i]+A[j]+i-j的最大值，两层循环查找的时间复杂度过高。i<j，我们可以固定j的位置，变动i的位置,这样A[i]+A[j]+i-j中A[j]-j的值是一个确定的值，我们只需要使得A[i]+i去[0,j)之间的最大值即可。

题目：单词拼写https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters/submissions/

代码——使用map

public static int countCharacters(String[] words, String chars) {
  int res = 0;
  Map<Character,Integer> charmap = new HashMap<Character,Integer>();
  for (int i = 0; i < chars.length() ; i++){
      if (charmap.containsKey(chars.charAt(i))) {
          charmap.put(chars.charAt(i),charmap.get(chars.charAt(i))+1);
          continue;
      }
      charmap.put(chars.charAt(i),1);
  }
  for (int i = 0 ; i <words.length;i++){
      if (chars.length()<words[i].length()) continue;
      Map<Character,Integer> wordmap = new HashMap<>();
      boolean flag = true;

      for (int j = 0 ; j < words[i].length() ; j++){
          if (wordmap.containsKey(words[i].charAt(j))) {
              wordmap.put(words[i].charAt(j),wordmap.get(words[i].charAt(j))+1);
              continue;
          }
          wordmap.put(words[i].charAt(j),1);
      }
      for (Character key : wordmap.keySet()){
          if (!charmap.containsKey(key) || charmap.get(key) < wordmap.get(key) ) flag = false;
      }
      if (flag) res += words[i].length();
  }
  return res;
}

代码-数组

public static int problem1160_arrar(String[] words, String chars){
  int res = 0;
  int[] charnum = new int[26];
  for (char ch : chars.toCharArray())
      charnum[ch-'a']++;
  int[] wordnum = new int[26];

  for (String word : words){
      boolean flag = true;
      Arrays.fill(wordnum,0);
      for (char ch : word.toCharArray()){
          wordnum[ch-'a']++;
          if (wordnum[ch-'a'] > charnum[ch-'a']) flag = false;
      }
      if (flag) res+= word.length();
  }
  return res;
}

思路
1. 对于一个单词word，只要其中每个字母的数量都不大于chars中对应字母的数量，chars就可以拼写出单词word。
2. 使用HashMap对出现的字母和数量进行统计对比，但是时间复杂度高；可以直接使用数组来存对应字母的数量并进行对比即可。

2020/06/18

题目：从先序遍历还原二叉树https://leetcode-cn.com/problems/recover-a-tree-from-preorder-traversal/

代码：

class Solution {
public TreeNode recoverFromPreorder(String S) {
  int sz = S.length();
  int pos = 0 ;
 Stack<TreeNode> tree = new Stack<>();
  while (pos < sz){
      int deepth = 0 , value = 0;
      while (S.charAt(pos)=='-'){
          deepth++;
          pos++;
      }
      while (pos < sz&&Character.isDigit(S.charAt(pos))){
          value = value*10+(S.charAt(pos)-'0');
          pos++;
      }
      TreeNode node = new TreeNode(value);
      if (deepth == tree.size()){ //
          if (!tree.isEmpty()){  
              tree.peek().left = node;
          }
      }
      else {
          while (deepth!=tree.size()){
              tree.pop();
          }
          tree.peek().right = node;
      }
      tree.push(node);
  }
  while (tree.size()>1) tree.pop();
  return tree.peek();
}
}

思路

树的先序遍历的顺序是根-左结点-右节点。在字符串中‘-’的数量表示了节点的深度，当节点x的深度小于y的深度(x.index>y.index),我们可以通过回溯找到x的父节点z，并链接成为z的右孩子。因此可以先保存各个节点与深度的映射关系，之后以用单调栈来逐渐还原树。但是这样的解法存在一个问题，Map无法处理存在节点值重复这一情况。

根据先序遍历的顺序特征，从根节点先向左子树进行遍历，深度增加，当达到叶子结点时，开始遍历右子树，深度发生变化。右子树的父节点就是深度为h-1的节点(右子树的深度为h)，在这个过程中，存在FILO，故使用栈来还原。栈的大小即为深度+1，所以通过比较结点深度和栈的大小进行入栈弹栈来还原树。

public static TreeNode problem1028(String s){
//该方法使用单调栈来实现树的还原，但是由于中间使用了Map这样的数据结构，所以导致其不能还原存在重复元素的树
int sz = s.length();
int cnt = 0 , num = 0;
if (sz==0) return null;
List<Integer> temp = new ArrayList<>();
Map<Integer,Integer> hash = new HashMap<>();
for (int i = 0 ; i < sz ; ){
   if (s.charAt(i)!='-'){
       num = num*10 + (s.charAt(i) - '0');
       i++;
       if (i<sz && s.charAt(i)=='-'){
           temp.add(num);
           hash.put(num,cnt);
           cnt = 0;
           num = 0;
       }
   }
   else {
       cnt ++;
       i++;
   }
}
temp.add(num);
hash.put(num,cnt);

//将根节点放进去
Stack<TreeNode> sk = new Stack<>();
TreeNode root = new TreeNode(temp.get(0));
sk.push(root);
for (int i = 1 ; i < temp.size() ;i++){
   while (!sk.isEmpty() && hash.get(sk.peek().val) >= hash.get(temp.get(i)) ){
       sk.pop();
   }
   TreeNode node = new TreeNode(temp.get(i));
   if (sk.peek().left==null){
       sk.peek().left = node;
   }
   else {
       sk.peek().right = node;
   }
   sk.push(node);
   System.out.println(sk.peek().val);
}
while (!sk.isEmpty()) sk.pop();

return root;
}

题目：矩形重叠https://leetcode-cn.com/problems/rectangle-overlap/

代码：

class Solution {
public boolean isRectangleOverlap(int[] rec1, int[] rec2) {
  return !(rec1[0]>=rec2[2] || rec1[2]<=rec2[0] || rec1[1]>=rec2[3] || rec1[3] <=rec2[1]);
}
}

思路：
只需要考虑不重叠的情况即可，即矩形A的最右边在矩形B的左边，最左边在B的右边，上下同理。

最长回文串

代码

class Solution {
public int longestPalindrome(String s) {
  int[] cnt = new int[58]; //用58是因为A-z之间在ASCII上有58个数，中间有6个字符
  int res = 0;
  for(char ch : s.toCharArray()){
      cnt[ch-'A']++;
  }
 for(int x : cnt){
  res+= x-(x%2);
 }
 //如果最终长度大于s的长度，则说明存在奇数字符，+1
  return res<s.length()?res+1:res;
}
}

思路：
数量为偶数的字母必定可以组成回文串，数量为奇数可以取比其小的偶数数量计数，如果存在奇数数量的字符，可以将其放在中央，但只能计算一次。

2020/06/19

题目：验证回文串https://leetcode-cn.com/problems/valid-palindrome/

代码：

class Solution {
public boolean isPalindrome(String s) {
  int sz = s.length();
  int left = 0 , right = sz-1;
  while(left < right){
      while(left<right && !Character.isLetterOrDigit(s.charAt(left))){
          left++;
      }
      while ( left < right && !Character.isLetterOrDigit(s.charAt(right))){
          right--;
      }
      if( left < right){
    if(Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right)))
              return false;
          right--;
          left++;
      }
  }
  return true;
}
}

思路：
左右指针同时检索，当指针指向内容是数字或者字母时进行比较，在比较的过程中需要将字母转换成小写字母。

题目：无重复字符的最长子串https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

代码

class Solution {
public int lengthOfLongestSubstring(String s) {
  int max = 0;
  int lg = s.length();
  Deque<Character> dq = new ArrayDeque<>();
  for (int i = 0 ; i < s.length() ; i++){
      while (!dq.isEmpty() && dq.contains(s.charAt(i))){
          max = Math.max(max,dq.size());
          dq.poll();
      }
      dq.add(s.charAt(i));
  }
  if (!dq.isEmpty()) max = Math.max(dq.size(),max);
  return  max;
}
}

思路：
该题在寻找无重复字符的最长子串的过程中，较为重要的是，当碰到重复字符时，我们应该去除哪些字符，如在“dvdf”中，最长子串为”vdf”。考虑到一旦存在重复字符，该字符及字符前的字符都需要不可再算作新一轮的子串中，这种FIFO的特性，可以利用队列很好的解决这个问题。

2020/06/20

题目：正则表达式匹配https://leetcode-cn.com/problems/regular-expression-matching/

代码

public static boolean problem10(String s, String p){
//        当p是.任意匹配字符，单个字母仅比较字母即可，字母+星号需要特殊处理
  int s_sz = s.length() , p_sz = p.length();
  boolean[][] dp = new boolean[s_sz+1][p_sz+1]; //dp指的是前i个和前j个是否可以匹配
  dp[0][0]  = true;
  for (int i = 0 ; i<=s_sz;i++){
      for (int j = 1; j<=p_sz;j++){
          if (p.charAt(j-1) == '*'){
              if (j-1==0) return false;
              dp[i][j] = dp[i][j-2];
              if (match(s,p,i,j-1)){//匹配0次还是1次
                  dp[i][j] = dp[i-1][j];
              }
          }
          else {
              if (match(s,p,i,j)){
                  dp[i][j] = dp[i-1][j-1];
              }
          }
      }
  }

  return dp[s_sz][p_sz];
}
public static boolean match(String s, String p , int i , int j){
  if (i==0) return false;
  if (p.charAt(j-1) == '.') return true;
  return s.charAt(i-1) == p.charAt(j-1);
}

思路
1. 使用dp[i][j]来表示s的前i个字符与p的前j个字符是否匹配的状况；
2. 对于普通字符,只需要判断s[i-1]==p[j-1],就存在dp[i][j] = dp[i-1][j-1]。对于‘.’，直接有dp[i][j]=dp[i-1][j-1]。对于字符+‘’，在每一轮次的匹配过程中，有匹配0次(末尾不相同)和1次的选择，当表示匹配0次的时候，应该有dp[i][j]=dp[i][j-2]；当为匹配1次的选择时，有dp[i][j]=dp[i-1][j]。这样就可以得到整个dp，从而得到答案。

2020/06/21

题目：二叉树中的最大路径和https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

代码：

class Solution {
public int ans = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
  deepTree(root);
  return ans;
}
public int deepTree(TreeNode root){
  if(root == null) return 0;
  int left = Math.max(0,deepTree(root.left));
  int right = Math.max(0,deepTree(root.right));
  ans = Math.max(ans,left+right+root.val);
  return Math.max(right,left) + root.val;
}
}

题解与思路：
1. 题解：
  本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。
  二叉树的特点是：一个节点，被一个父节点连接，连接左右两个子节点；路径的特点：途径上的一个节点只能选择来去两个方向。即一条路径不可能出现分叉。
2. 对于某个节点来说，如果最大路径包括该节点，则存在两种情况，即该节点的单个最长路径最长子树+向上回溯父节点，表现为max(left,right)+root.val；或者该节点左右子树都在路径中,表现为left+right+root.val。并不断更新最大值。对于负数的处理，如果子树路径长度为负则将其置0，表示未将其计算在最大路径之中。
3. 使用最大贡献值来理解题意

题目：使数组唯一的最小增量https://leetcode-cn.com/problems/minimum-increment-to-make-array-unique/

代码

class Solution {
public int minIncrementForUnique(int[] A) {
// 先排序
  Arrays.sort(A);
  int move = 0;
  for (int i = 1; i < A.length; i++) {
      if (A[i] <= A[i - 1]) {
          int last = A[i];
          A[i] = A[i - 1] + 1;
          move += A[i] - last;
      }
  }
  return move;
}
}

思路
将数组排序，遍历数组，如果当前元素小于等于前一元素，则将其变为前一元素大小+1，并累计次操作所需要的move数。

六月06/22-06/29

2020/06/22

题目：模式匹配https://leetcode-cn.com/problems/pattern-matching-lcci/
1. 代码： ```java class Solution { public boolean patternMatching(String pattern, String value) {

// cala+cblb=value.length(); // 特殊情况 if (value.length()==0){//pattern中只可有一个字母 if (pattern.length()!=0){ for (int i = 1 ; i < pattern.length() ;i++){ if ( pattern.charAt(i)!=pattern.charAt(i-1)) return false; } }//双空 return true; } if (pattern.length()==0) return false; if (pattern.length()==1) return true; int c1 = 0 , c2 = 0; //c1记录pattern.charAt(0)的数量,c2记录另一个 char a = pattern.charAt(0); for (int i = 0 ; i < pattern.length() ; i++){ if (pattern.charAt(i)==a) c1++; else c2++; }

    int lv = value.length() , lp = pattern.length();
    if ( c2 == 0 ){ //当pattern中仅有一个字母的时候，需要判断value中的字符按pattern中分开形成的字符串是否相同
        if (lv%c1!=0) return false;
        int l1 = lv/c1;
        String s = value.substring(0,l1);
        for (int i = s.length() ; i < lv ; i+=l1){
            if (!value.substring(i,i+l1).equals(s)){
                return false;
            }
        }
        return true;
    }

// 当pattern中有两个字母时，通过l1la+l2lb=value.length()这个等式，固定l1，找到符合条件的l2即可 for (int l1 = 0 ; l1 c1 <= lv ; l1++){ int rest = lv - l1c1; if ( rest%c2 != 0) continue;; int l2 = rest/c2 , curposition = 0; boolean ismatch = true; String temp1 = “” , temp2 = “”; for (char ch : pattern.toCharArray()){ //从pattern出发匹配value中的值 if (ch == a) { String curstring1 = value.substring(curposition,curposition+=l1); if (temp1.length()==0) temp1=curstring1; //‘a’或者’b’代表的模式 else if (!curstring1.equals(temp1)){ ismatch = false; break; } } else { String curstring2 = value.substring(curposition,curposition+=l2); if (temp2.length()==0) temp2 = curstring2;//‘a’或者’b’代表的模式 else if (!curstring2.equals(temp2)){ ismatch = false; break; } } } if (ismatch && !temp1.equals(temp2)) return true; } return false; } }



   2. 
思路：
<br />pattern中两种字母代表两种模式，题解与value满足的条件如下：ca*la+cb*lb=value.length();ca为字母a代表的模式，la为value中ca的数量，通过固定ca的大小la，就可以得到cb的大小lb，这样就可以根据长度在value中截取到不同模式代表的字符串，通过遍历比较即可判断是否存在这样的la,lb（参考pattern的顺序在value中截取遍历）。


<a name="8f99b266"></a>
### 2020/06/23

1. 
题目：二进制求和https://leetcode-cn.com/problems/add-binary/

   1. 
代码：
```java
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder();
        int la = a.length() , lb = b.length();
        int i = la-1 , j = lb-1 , add = 0;
        for (; i>=0&&j>=0 ; i--,j--){
            int sum = a.charAt(i)-'0' + b.charAt(j)-'0'+add;
            res.append(sum%2);
            if (sum>=2) add = 1;
            else add = 0;
        }
        while (i>=0){
            int sum = a.charAt(i)-'0' + add;
            res.append(sum%2);
            if (sum>=2) add = 1;
            else add = 0;
            i--;
        }
        while (j>=0){
            int sum = b.charAt(j)-'0' + add;
            res.append(sum%2);
            if (sum>=2) add = 1;
            else add = 0;
            j--;
        }
        if (add ==1 ) res.append(add);
        if (res.length()>1 && res.charAt(res.length()-1) == '0') res.setLength(res.length()-1);
        return res.reverse().toString();
    }
}

思路：
将二进制字符串转换为十进制数进行运算在出现较长的二进制字符串时会出现数字溢出，故模拟二进制的加法直接对二进制字符串进行操作。使用add来记录进位信息，遍历字符串，对应位相加+add，得到题解。

题目：链表的中间结点https://leetcode-cn.com/problems/middle-of-the-linked-list/

代码：

class Solution {
public ListNode middleNode(ListNode head) {
  ListNode s = head , f = head;
  while(f!=null && f.next!=null){ //f!=null为偶数个的截止条件，f.next!=null为奇数个的截止条件
      f = f.next.next;
      s = s.next;
  }
  return s;
}
}

思路：
1. 可以统计整个链表的长度length，中间结点的索引为length/2（索引从0开始，故不需要其他处理）。
2. 使用快慢指针，快指针每次走两步，慢指针走一步，当快指针走到末尾时，慢指针刚好指向中间结点。
3. 题目：环形链表https://leetcode-cn.com/problems/linked-list-cycle/

代码

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

思路
使用快慢指针，如果链表中存在环，那么快指针会与慢指针相遇，如果链表中不存在环，那么快指针会指向空。

2020/06/24

题目：最接近的三数之和https://leetcode-cn.com/problems/3sum-closest/

代码：

class Solution {
public int threeSumClosest(int[] nums, int target) {
  int ans = 0 , sum = 0, presub = Integer.MAX_VALUE;
  Arrays.sort(nums);
  int sz = nums.length;
  for (int i = 0 ; i < sz ; i++){
      int right = sz-1;
      int left = i + 1;
      if (i > 0 && nums[i] == nums[i-1]) continue; //避免枚举重复元素
      while (left < right){
          sum = nums[right]+nums[left]+nums[i];
          int sub = Math.abs(target-sum);
          if (sub == 0)  return sum;
          if (sub < presub){
              ans = sum;
              presub = sub;
          }
          if (sum > target ) {
              int rtemp = right-1;
              while (left < rtemp && nums[right] == nums[rtemp]){ //避免枚举重复元素
                  rtemp--;
              }
              right =  rtemp;
          }
          else {
              int ltemp = left+1;
              while (ltemp < right && nums[left] == nums[ltemp]) //避免枚举重复元素
                  ltemp++;
              left = ltemp;
          }
      }
  }
  return ans;
}
}

思路
与三数之和解题思路几乎一致，使用排序+双指针即可得到题解。

2020/06/25

题目：单词拆分https://leetcode-cn.com/problems/word-break/

代码：

public static boolean problrm139(String s , List<String> wordDict){
  Set<String> wordDictSet = new HashSet<>(wordDict);
  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 (dp[j] && wordDictSet.contains(s.substring(j,i))){ //拆分进行动态规划
              dp[i] = true;
              break;
          }
      }
  }
  return dp[s.length()];
}

思路
我们定义 dp[i] 表示字符串 s 前 i 个字符组成的字符串 s[0..i-1]是否能被空格拆分成若干个字典中出现的单词。从前往后计算考虑转移方程，每次转移的时候我们需要枚举包含位置 i-1 的最后一个单词，看它是否出现在字典中以及除去这部分的字符串是否合法即可。公式化来说，我们需要枚举 s[0..i-1]中的分割点 j，看 s[0..j-1]组成的字符串 s1 (默认j=0时s1为空串)和s[j…i-1]组成的字符串s2是否都合法，如果两个字符串都合法，则s1和s2拼接形成的字符串也同样合法。由于计算到dp[i]时我们已经计算出了dp[0…i-1]的值，因此字符串s1是否合法可以直接由dp[j]得知，剩下的只要s2是否合法即可，因此我们可以转移方程： $LeetCode每日一题 - 图6$ %0A#card=math&code=dp%5Bi%5D%20%3D%20dp%5Bj%5D%5C%26%5C%26check%28s%5Bj%E2%80%A6i-1%5D%29%0A)

其中国check(s[j…i-1])表示子串s[j……i-1]是否出现在字典中。且dp[0] = true。