LeetCode


动态规划

  1. 给一个数组,寻找最大的子数组和,可以删除某个子数组中的一个元素或者不删
class Solution {
    public int maximumSum(int[] arr) {
        int[][] dp = new int[arr.length][2];
        dp[0][0] = arr[0];
        dp[0][1] = 0;
        int res = dp[0][0];
        for (int i = 1; i < arr.length; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], 0) + arr[i];
            dp[i][1] = Math.max(dp[i - 1][1] + arr[i], dp[i - 1][0]);
            res = Math.max(Math.max(dp[i][0], dp[i][1]), res);
        }
        return res;
    }
}

标准动态规划题,定义一个二维数组做dp数组,第一列记录不删除元素情况的最大前缀和,第二列记录删除元素的最大前缀和。判断删除元素的最大前缀和就是判断 前面删除过元素(dp[i-1] [1])+当前元素 和 前面未删除元素dp[i-1] [0] 的大小

深度遍历

题记:递归是真难

MEDIUM

  1. 这道题题目表达的真的和shit一样

    总结一下就是如果根节点到叶子节点的路径和大于limit那么这一条线上的点都不用删除,如果一个节点不存在任何一条这样的路径上就删除

class Solution {
    public TreeNode sufficientSubset(TreeNode root, int limit) {
        //递归最终还是要回到根节点,所以直接返回root也行
        return dfs(root, 0, limit);
    }
    public TreeNode dfs(TreeNode cur, int sum, int limit) {
        //先判断是不是空节点
        if (cur == null) return null;
        sum = sum + cur.val;
        //这部分用来判断叶子节点是不是要删除
        if (cur.left == null && cur.right == null) {
            if (sum < limit) return null;
            return cur;
        }
        //一定要cur等于,不然相当于没改
        cur.left = dfs(cur.left, sum , limit);
        cur.right = dfs(cur.right, sum, limit);
        //dfs之后还要判断一下是不是要删除
        if (cur.left == null && cur.right == null) return null;
        return cur;
    }
}

BFS

MEDIUM

  1. 题目意思是给了一个二维数组,可以走上下左右,左上左下右上右下,只能走0,最后到右下角的最短路径,没路返回-1.
class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int n = grid.length;
        
        //如果起始位置是1,直接返回-1
        if (grid[0][0] == 1) return -1;
        
        //dist数组是记录从起始点到当前点的最短路径,初始化为最大值
        int[][] dist = new int[n][n];
        Arrays.stream(dist).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
        
        //队列记录可以到达的点
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{0, 0});
        dist[0][0] = 1;
        
        while (!queue.isEmpty()) {
            int[] temp = queue.poll();
            
            //到达目标位置则返回结果
            if (temp[0] == n - 1 && temp[1] == n - 1) return dist[n - 1][n - 1];
            
            //双循环是遍历当前点的八个方向
            for (int i = -1; i <= 1; i++) {
                for (int j = -1; j <= 1; j++) {
                    
                    //二维数组不能越界
                    if (temp[0] + i < 0 || temp[1] + j < 0 
                        				|| temp[0] + i >= n || temp[1] + j >= n) 
                        continue;
                    
                    //判断当前方向是不是0,dist是判断最短距离
                    if (grid[temp[0] + i][temp[1] + j] == 1 
                        || dist[temp[0] + i][temp[1] + j] <= dist[temp[0]][temp[1]] + 1)
                        continue;
                    
                    //前两个if都通过就可以改这个方向的情况,并且把点放到队列
                    dist[temp[0] + i][temp[1] + j] = dist[temp[0]][temp[1]] + 1;
                    queue.offer(new int[]{temp[0] + i, temp[1] + j});
                }
            }
        }
        return -1;
    }
}

记录一下二维数组初始化方法:

//setAll方法
Arrays.setAll(matrix, i -> {
    int[] row = new int[matrix[i].length];
    Arrays.fill(row, Integer.MAX_VALUE);
    return row;
});
//stream流
Arrays.stream(matrix).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));

二分查找

HARD

  1. 给一个矩阵,每行取一个元素,求所有情况中,和为第k小的情况
//思路:两行两行合并,每次返回这两行合并后的前k个情况

class Solution {
    public int kthSmallest(int[][] mat, int k) {
        int[] temp = mat[0];
        //每次将前两行的结果与下一行在执行merge
        for (int i = 1; i < mat.length; i++) {
            temp = merge(temp, mat[i], k);
        }
        return temp[k-1];
    }
    
    public int[] merge(int[] a, int[] b, int k) {
        //使用小根堆取出最小的k种情况
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b.length; j++) {
                priorityQueue.add(a[i] + b[j]);
            }
        }
        int[] res = new int[Math.min(priorityQueue.size(), k)];
        for (int i = 0; i < k && !priorityQueue.isEmpty(); i++) {
            res[i] = priorityQueue.poll();
        }
        return res;
    }
}
    

MYSQL

题记:记录一些方法

550.

SELECT round(sum(b.event_date is not null)/count(*),2) fraction	
			//不能用count,不管是不是null都会被统计
FROM
  (SELECT player_id, MIN(event_date) AS min_date //选最小的一行
   FROM activity
   GROUP BY player_id) AS a
LEFT JOIN activity AS b
ON a.player_id = b.player_id and datediff(b.event_date, a.min_date)=1;	//日期相差一天,前一个日期减后一个

1193.

if(condition,condition(true),condition(false))

DATE_FORMAT(date, '%Y-%m-%d')	//日期截断选其中的对应位置参数就行

评论
  目录