2022 年 5月

2022.5.1

409. 最长回文串

class Solution {
    public int longestPalindrome(String s) {
        Map<Character, Integer> map = new HashMap<>();
        int ans = 0;
        for(int i = 0; i < s.length(); i++) map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        boolean flag = false;
        for(Character key : map.keySet()){
            while(map.get(key) >= 2){
                ans += 2;
                map.put(key, map.get(key) - 2);
            }
            if(map.get(key) == 1) flag = true;
        }
        return flag ? ans + 1 : ans;
    }
}

2022.5.2

面试题 17.24. 最大子矩阵

class Solution {
    public int[] getMaxMatrix(int[][] matrix) {
        // 保存最大子矩阵的左上角和右下角
        int[] ans = new int[4];//保存最大子矩阵的左上角和右下角的行列坐标
        int n = matrix.length, m = matrix[0].length;
        // 二维转一维，累加
        int[] b = new int[m];
        int sum = 0, maxSum = Integer.MIN_VALUE;
        // 记录左上角
        int beginr1 = 0, beginc1 = 0;

        // 定上行
        for(int i = 0; i < n; i++){
            // 每次换上行都要重新算b
            for(int t = 0; t < m; t++) b[t] = 0;
            // 定下行 [i, j]
            for(int j = i; j < n; j++){
                // 每次新加一行，sum也要重新统计
                sum = 0;
                // 遍历第j行
                for(int k = 0; k < m; k++){
                    // 将二维变成一维
                    b[k] += matrix[j][k];   
                    if(sum > 0) sum += b[k];
                    // 小于零重新开始
                    else{
                        sum = b[k];
                        // 重新记录左上角
                        beginr1 = i;
                        beginc1 = k;
                    }
                    if(sum > maxSum){
                        maxSum = sum;
                        ans[0] = beginr1;//更新答案
                        ans[1] = beginc1;
                        ans[2] = j;
                        ans[3] = k;
                    }
                }
            }
        }
        return ans;
    }
}

2022.5.3

102. 二叉树的层序遍历

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null) return ans;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> path = new ArrayList<>();
            while(len-- > 0){
                TreeNode node = queue.poll();
                path.add(node.val);
                if(node.left!=null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
            ans.add(path);
        }
        return ans;
    }
}

2022.5.4

516. 最长回文子序列

class Solution {
    public int longestPalindromeSubseq(String s) {
        // dp[i][j] 区间[i,j] 最长的回文子序列长度
        // if(s[i] == s[j] ) dp[i][j] = dp[i+1][j-1] + 2
        // else dp[i][j] = max(dp[i+1][j], dp[i][j-1])
        int n = s.length();
        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++) dp[i][i] = 1;
        for(int i = n - 1; i >= 0; i--){
            for(int j = i + 1; j < n; j++){
                if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2;
                else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][n-1];
    }
}

2022.5.5

剑指 Offer 26. 树的子结构

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        return isSame(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    private boolean isSame(TreeNode node1, TreeNode node2){
        if(node2 == null) return true;
        if(node1 == null || node1.val != node2.val) return false;
        return isSame(node1.left, node2.left) && isSame(node1.right, node2.right);
    }
}

2022.5.6

70. 爬楼梯

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++) dp[i] = dp[i-1] + dp[i-2];
        return dp[n];
    }
}