
![image.png](/static/img/d0b1c14a3b9c8a1a9cb9743c78a836f0.image.webp)

```java
public class Solution {
    public String multiply(String num1, String num2) {
         if (num1.equals("0") || num2.equals("0")) {
             return "0";
           }

         int[] result = new int[num1.length() + num2.length()];

         for (int i = num1.length() - 1; i >= 0; i--) {
              for (int j = num2.length() - 1; j >= 0; j--) {
                   int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                   int p1 = i + j, p2 = i + j + 1;
                   int sum = mul + result[p2];

                   result[p2] = sum % 10;
                   result[p1] += sum / 10;
               }
           }

         StringBuilder sb = new StringBuilder();
          for (int i = 0; i < result.length; i++) {
               if (i == 0 && result[i] == 0) {
                   continue;
               }
               sb.append(result[i]);
           }

          return sb.toString();
       }
}


```



![image.png](/static/img/7817fb7a3e548bdb3680ad73ec9b5980.image.webp)

```java
public class Solution {
    public String[] findRestaurant(String[] list1, String[] list2) {
         Map<String, Integer> indexMap = new HashMap<>();
         for (int i = 0; i < list1.length; i++) {
              indexMap.put(list1[i], i);
          }

         int minIndexSum = Integer.MAX_VALUE;
         List<String> commonRestaurants = new ArrayList<>();

         for (int i = 0; i < list2.length; i++) {
              if (indexMap.containsKey(list2[i])) { // 共同爱好
                  int indexSum = i + indexMap.get(list2[i]); // 计算索引和
                  if (indexSum < minIndexSum) { //是否是最小索引和
                      minIndexSum = indexSum;
                       commonRestaurants.clear();
                       commonRestaurants.add(list2[i]);
                   } else if (indexSum == minIndexSum) {
                       commonRestaurants.add(list2[i]);
                   }
               }
           }
        return commonRestaurants.toArray(new String[0]);
         //return commonRestaurants.toArray(new String[0]);
       }
}


```



![image.png](/static/img/d70e27c05e307837cd9eff227e3cd85f.image.webp)

```java
public class Solution {
    public int coinChange(int[] coins, int amount) {
          // 初始化一个比amount大的数，表示无法凑成的金额
          int max = amount + 1;
          // 初始化dp数组，所有值设为最大值
          int[] dp = new int[amount + 1];
          Arrays.fill(dp, max);
          // 金额为0时，不需要任何硬币
          dp[0] = 0;

          // 遍历所有金额
          for (int i = 1; i <= amount; i++) {
               // 遍历所有硬币
               for (int coin : coins) {
                    // 如果当前金额大于等于硬币面值
                    if (i >= coin) {
                         // 更新dp[i]为dp[i]和dp[i - coin] + 1的最小值
                         dp[i] = Math.min(dp[i], dp[i - coin] + 1);
                    }
               }
          }

          // 如果dp[amount]没有被更新过，说明无法凑成该金额
          return dp[amount] == max ? -1 : dp[amount];
      }
}






```




今日刷题

远程服务器重装系统，ssh报错

![image.png](/static/img/92394867f0d14ec5d1573695f1edff0f.image.webp)

证书无效，需要清除缓存重新连接
```
ssh-keygen -R ip
```

ssh标识证书失效


![image.png](/static/img/73de0bb4a574cddf50cf9507f11220e2.image.webp)

思路都在注释里，就是bfs层序遍历

```java
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> averages = new ArrayList<>(); //答案数组 
        if (root == null) {  //特判
            return averages; 
        }

        Queue<TreeNode> queue = new LinkedList<>(); //bfs队列
        queue.offer(root); //根结点入队

        while (!queue.isEmpty()) {
              int levelSize = queue.size();
              double sum = 0;
              for (int i = 0; i < levelSize; i++) {  //入队并计算
                  TreeNode node = queue.poll();
                  sum += node.val;
                  if (node.left != null) {
                      queue.offer(node.left);
                  }
                  if (node.right != null) {
                      queue.offer(node.right);
                  }
              }
              averages.add(sum / levelSize);
          }

        return averages;

    }
}
```

![image.png](/static/img/d3473bc81fc37facd3b1aa2349f259e0.image.webp)
```java
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
                 int lenA = 0, lenB = 0;
         ListNode tempA = headA, tempB = headB;

         // 计算两个链表的长度
         while (tempA != null) {
              lenA++;
               tempA = tempA.next;
           }
         while (tempB != null) {
              lenB++;
               tempB = tempB.next;
           }

         // 对齐链表
         tempA = headA;
         tempB = headB;
         if (lenA > lenB) {
              for (int i = 0; i < lenA - lenB; i++) {
                   tempA = tempA.next;
               }
           } else {
               for (int i = 0; i < lenB - lenA; i++) {
                   tempB = tempB.next;
               }
           }

         // 遍历链表，找到相交节点
         while (tempA != null && tempB != null) {
               if (tempA == tempB) {
                   return tempA;
               }
               tempA = tempA.next;
               tempB = tempB.next;
           }

         return null;
       

    }
}
```

![image.png](/static/img/ca4827df78ed637d3db12e838d5bba48.image.webp)

```java
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root.left,root.right);
    }

    private boolean isMirror(TreeNode t1, TreeNode t2) {
        if (t1 == null && t2 == null) return true;
        if (t1 == null || t2 == null) return false;
        return (t1.val == t2.val)
        && isMirror(t1.right, t2.left)
        && isMirror(t1.left, t2.right);
    }

}
```



![image.png](/static/img/86155841ca9c3dee8f4616e9065a3803.image.webp)

```java
public class Solution {
    public int garbageCollection(String[] garbage, int[] travel) {
         int[] lastPos = new int[]{-1,-1,-1}; // 记录每种垃圾最后出现的位置
         int[] time = new int[4]; // 记录每种垃圾收拾所需的时间
         int count = 0;
         // 遍历垃圾数组，记录每种垃圾最后出现的位置
         for (int i = 0; i < garbage.length; i++) {
              for (int j = 0; j < garbage[i].length(); j++) {
                  char c = garbage[i].charAt(j);
                  if (c == 'M') {
                      lastPos[0] = i;
                      count++;
                      //time[0] += travel[i];
                  } else if (c == 'P') {
                      lastPos[1] = i;
                      count++;
                      //time[1] += travel[i];
                  } else if (c == 'G') {
                      lastPos[2] = i;
                      count++;
                      //time[2] += travel[i];
                  }
              }
          }

          //System.out.println(lastPos[2]); -1,2,3

         // 计算收拾每种垃圾所需的时间
         for (int i = 0; i < 3; i++) {
              if (lastPos[i] > 0) {
                for(int j = 0; j < lastPos[i];j++) {
                    time[i]=time[i]+ travel[j];
                }
                System.out.println(time[2]);
                //time[i] += lastPos[i] * travel[lastPos[i] - 1];
              }
          }

          // 返回收拾所有垃圾所需的时间
          return time[0] + time[1] + time[2] + count;
      }

   
}

```


![image.png](/static/img/0cc71f152e21312bda305d1e57577b06.image.webp)
```java
public class Solution {
    private int minDiff = Integer.MAX_VALUE;
    private Integer prevVal = null;

    public int getMinimumDifference(TreeNode root) {
         inorder(root);
         return minDiff;
     }

    private void inorder(TreeNode node) {
         if (node == null) {
              return;
          }
          inorder(node.left); // 左子树
          if (prevVal != null) {
              minDiff = Math.min(minDiff, node.val - prevVal);
          }
          prevVal = node.val; // 更新前一个节点的值
          inorder(node.right); // 右子树
     }
}



```


![image.png](/static/img/8a535bbb030b543174ba41e819456c47.image.webp)

```java
public class Solution {
    public boolean isValidBST(TreeNode root) {
         return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
      }

    private boolean isValidBST(TreeNode node, long lower, long upper) {
         if (node == null) {
              return true;
           }
           // 当前节点的值必须在lower和upper之间
         if (node.val <= lower || node.val >= upper) {
              return false;
           }
           // 递归验证左子树和右子树
         return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
      }
}

```


算法题常遇到一些字符串操作，记住这些API就能更快码出来，以下是一些常用的字符串处理函数：

### 分割字符串

- `split(String regex)`: 使用正则表达式作为分隔符来分割字符串。
- `split(String regex, int limit)`: 与`split(String regex)`类似，但限制了分割后的数组大小。

### 匹配字符串

- `matches(String regex)`: 判断字符串是否匹配给定的正则表达式。
- `contains(CharSequence s)`: 判断字符串是否包含指定的子字符串。

### 组合字符串

- `concat(String str)`: 将指定字符串连接到当前字符串的末尾。
- `join(CharSequence delimiter, CharSequence... elements)`: 使用指定的分隔符连接一系列元素。

### 替换字符串

- `replace(CharSequence target, CharSequence replacement)`: 将字符串中所有出现的指定字符序列替换为另一个字符序列。
- `replaceAll(String regex, String replacement)`: 使用正则表达式替换所有匹配的子字符串。

### 转换大小写

- `toLowerCase()`: 将字符串中的所有字符都转换为小写。
- `toUpperCase()`: 将字符串中的所有字符都转换为大写。

### 去除空白

- `trim()`: 去除字符串两端的空白字符。
- `strip()`: Java 11新增的方法，去除字符串两端的空白字符。

### 比较字符串

- `equals(Object anotherObject)`: 比较当前字符串与另一个对象是否相等。
- `equalsIgnoreCase(String anotherString)`: 与`equals(Object anotherObject)`类似，但忽略大小写。

### 搜索子字符串

- `indexOf(String str)`: 返回指定子字符串在此字符串中第一次出现处的索引。
- `lastIndexOf(String str)`: 返回指定子字符串在此字符串中最后一次出现处的索引。

### 提取子字符串

- `substring(int beginIndex)`: 返回一个新的字符串，它是此字符串的一个子字符串。
- `substring(int beginIndex, int endIndex)`: 返回一个新的字符串，它是此字符串的一个子字符串。

### 字符串与字节数组转换

- `getBytes()`: 将字符串转换为字节数组。
- `new String(byte[] bytes, int offset, int length)`: 使用指定的字节数组构造一个新的字符串。

### 其他常用方法

- `length()`: 返回字符串的长度。
- `isEmpty()`: 判断字符串是否为空。
- `charAt(int index)`: 返回指定索引处的字符。
- `contains(CharSequence s)`: 判断字符串是否包含指定的子字符串。



以下是代码示例：
```java
public class StringExample {
    public static void main(String[] args) {
        String str = "Hello, World!";

        // 分割字符串
        String[] parts = str.split(", ");
        System.out.println("分割字符串: " + String.join(" ", parts));

        // 匹配字符串
        boolean matches = str.matches(".*World.*");
        System.out.println("匹配字符串: " + matches);

        // 组合字符串
        String combined = str.concat(" How are you?");
        System.out.println("组合字符串: " + combined);

        // 替换字符串
        String replaced = str.replace("World", "Java");
        System.out.println("替换字符串: " + replaced);

        // 转换大小写
        String lower = str.toLowerCase();
        String upper = str.toUpperCase();
        System.out.println("转换大小写: " + lower + " | " + upper);

        // 去除空白
        String trimmed = str.trim();
        System.out.println("去除空白: " + trimmed);

        // 比较字符串
        boolean equals = str.equals("Hello, World!");
        boolean equalsIgnoreCase = str.equalsIgnoreCase("hello, world!");
        System.out.println("比较字符串: " + equals + " | " + equalsIgnoreCase);

        // 搜索子字符串
        int index = str.indexOf("World");
        System.out.println("搜索子字符串: " + index);

        // 提取子字符串
        String subStr = str.substring(7, 12);
        System.out.println("提取子字符串: " + subStr);

        // 字符串与字节数组转换
        byte[] bytes = str.getBytes();
        String fromBytes = new String(bytes);
        System.out.println("字符串与字节数组转换: " + fromBytes);
    }
}
```

