Posted Updated LeetCode / Mediuma minute read (About 189 words)

413. Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

  • For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
    Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

动态规划，遍历一次记录所有数字的差。
然后遍历并计算连续相同的数字数量temp。
当不相同时，则计算temp长度可以选择的组合数，将其添加到count。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {

        if(nums.length == 1) return 0;
        int[] difference = new int[nums.length-1];
        for(int i = 0; i < nums.length-1; i++){
            difference[i] = nums[i+1] - nums[i];
        }
        
        int count = 0;
        int temp = 1;
        int prev = difference[0];
        for(int j = 1; j < nums.length-1; j++){
            if(difference[j] == prev){
                temp++;
            }
            else{
                count += combinations(temp);
                temp = 1;
            }
            prev = difference[j];
        }
        count += combinations(temp);
        return count;
    }
    
    private int combinations(int n){
        return (n * (n-1)) / 2;
    }
}
Posted Updated LeetCode / Mediuma minute read (About 208 words)

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

动态规划，每一个位置的线路都等于其左侧和上侧的两条线路的加和。
将初始的两个边值设置为1，然后计算直至终点位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int count;
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++){
            dp[0][j] = 1;
        }
        
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
Posted Updated LeetCode / Medium3 minutes read (About 385 words)

785. Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

  • There are no self-edges (graph[u] does not contain u).
  • There are no parallel edges (graph[u] does not contain duplicate values).
  • If v is in graph[u], then u is in graph[v] (the graph is undirected).
  • The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.
    A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

原题等于问：每个节点与其相连接的节点是否可以颜色不同？
通过BFS搜索，将每一层通过开关flag分组。
创建一个visited数组，记录分组和遍历情况。
当节点被放入错误的分组时，返回false。

注意因为图里的各个节点可能不连接，因此需要遍历对所有节点进行BFS搜索，通过visited的情况进行剪枝。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<int[]> q = new LinkedList<>();
        int[] visited = new int[graph.length];
        
        for(int i = 0; i < graph.length; i++){
            boolean flag = false;
            if(graph[i].length == 0 || visited[i] != 0) continue;
            q.add(graph[i]);
            visited[i] = 1;
            int size = 1;
        
            while(!q.isEmpty()){
                for(int j = 0; j < size; j++){
                    int[] node = q.poll();
                    for(int next : node){
                        if(visited[next] == 0){
                            q.add(graph[next]);
                        }
                        if(flag){
                            if(visited[next] == 2) return false;
                            visited[next] = 1;
                        }
                        else{
                            if(visited[next] == 1) return false;
                            visited[next] = 2;
                        }
                    }
                }
                flag = !flag;
                size = q.size();
            }
        }
        return true;
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 409 words)

1631. Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

A*算法，启发式搜索。BFS搜索结合Priority Queue。
采用一个数组储存当前访问点的位置，以及其effort。
采用优先队列，优先搜索effort最小的方向。
每次循环倾倒出队列中所有的元素。
计算上一个节点和当前节点的差值作为nextEffort，并和上一个节点的effort作比较，较大的作为当前节点的effort，
将effort作为权重，优先搜索一个层级内effort较小的路径。
将所有操作加入队列，并排除越界的位置。
当当前节点为最后一个节点时，返回其effort。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    int min;
    public int minimumEffortPath(int[][] heights) {
        int[][] operations = {{1,0},{-1,0},{0,1},{0,-1}};
        int m = heights.length, n = heights[0].length;
        
        Queue<int[]> q = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int[] point = {0, 0, 0};
        int size = 1;
        int[][] visited = new int[m][n];
        
        q.add(point);
        while(!q.isEmpty()){
            
            for(int k = 0; k < size; k++){
                int[] curr = q.poll();
                int i = curr[0], j = curr[1], currEffort = curr[2];
                if(visited[i][j] == 1) continue;
                visited[i][j] = 1;
                if(i == m-1 && j == n-1) return currEffort;
                for(int[] operation : operations){
                    int nextX = i + operation[0];
                    int nextY = j + operation[1];
                    if(nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) continue;
                    int nextEffort = Math.max(currEffort, Math.abs(heights[i][j] - heights[nextX][nextY]));
                    int[] next = {nextX, nextY, nextEffort};
                    
                    q.add(next);
                }
            }
            size = q.size();
        }
        return -1;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 209 words)

45. Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

设置一个当前可以访问的最大范围limit，在遍历中对其进行更新。
和当前可访问位置中的最远距离end，每次访问到达end时，计算步数。

遍历数组，比较limit和当前i能访问的最远距离i+nums[i]，保留较大值。
当i达到end时，更新end为之前记录的可访问最远距离limit。步数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int jump(int[] nums) {
        int count = 0;
        int limit = 0;
        int end = 0;
        
        for(int i = 0; i < nums.length-1; i++){
            limit = Math.max(limit, i + nums[i]);
            if(i == end){
                end = limit;
                count++;
            }
        }
        
        return count;
    }
}
Follow

Recents

Archives

Links

×