Posted Updated LeetCode / Easy2 minutes read (About 243 words)

682. Baseball Game

问题
You are keeping score for a baseball game with strange rules. The game consists of several rounds, where the scores of past rounds may affect future rounds’ scores.

At the beginning of the game, you start with an empty record. You are given a list of strings ops, where ops[i] is the ith operation you must apply to the record and is one of the following:

  1. An integer x - Record a new score of x.
  2. “+” - Record a new score that is the sum of the previous two scores. It is guaranteed there will always be two previous scores.
  3. “D” - Record a new score that is double the previous score. It is guaranteed there will always be a previous score.
  4. “C” - Invalidate the previous score, removing it from the record. It is guaranteed there will always be a previous score.

Return the sum of all the scores on the record.

遍历选项，根据内容决定对ArrayList的操作。
然后遍历将ArrayList加和，返回。

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
class Solution {
    public int calPoints(String[] ops) {
        int ans = 0;
        List<Integer> records = new ArrayList();
        
        for (String op : ops){
            switch(op){
                case "+":
                    records.add(records.get(records.size()-1)+records.get(records.size()-2));
                    break;
                case "D":
                    records.add(records.get(records.size()-1)*2);
                    break;
                case "C":
                    records.remove(records.size()-1);
                    break;
                default:
                    records.add(Integer.parseInt(op));
            }
        }
        
        for (int record : records){
            ans += record;
        }                 
        return ans;
    }
}
Posted Updated LeetCode / Medium2 minutes read (About 351 words)

994. Rotting Oranges

问题
You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange, or
  • 2 representing a rotten orange.
    Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

由于腐烂的橘子每次都只能影响周围的橘子，因此采用BFS。
将所有腐烂的橘子加入队列。
如果没有新鲜的橘子，则返回0。
每次出队列，如果周围有新鲜的橘子存在，则将新鲜的橘子替换为腐烂并加入队列。
每个level结束后，time+1。

最后遍历一遍，如果还有新鲜的橘子，返回-1。

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<Integer> q = new LinkedList();
        int row = grid.length;
        int col = grid[0].length;
        int fresh = 0;
        for (int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if ( grid[i][j] == 2){
                    q.add(i * col + j);
                }
                else if (grid[i][j] == 1){
                    fresh++;
                }
            }
        }
        if(fresh == 0){return 0;}
        
        int count = q.size()-1;
        int temp = 0;
        int time = -1;
        while(!q.isEmpty()){
            int i = q.peek() / col;
            int j = q.poll() % col;
            
            if(i-1>=0 && grid[i-1][j] == 1){
                grid[i-1][j] = 2;
                q.add((i-1)*col+j);
                temp++;
            }
            if(j-1>=0 && grid[i][j-1] == 1){
                grid[i][j-1] = 2;
                q.add(i*col+(j-1));
                temp++;
            }
            if(i+1<row && grid[i+1][j] == 1){
                grid[i+1][j] = 2;
                q.add((i+1)*col+j);
                temp++;
            }
            if(j+1<col && grid[i][j+1] == 1){
                grid[i][j+1] = 2;
                q.add(i*col+(j+1));
                temp++;
            }
            
            if(count == 0){
                count = temp;
                temp = 0;
                time++;
            }
            count--;
        }
        
        for (int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if ( grid[i][j] == 1){
                    return -1;
                }
            }
        }
        return time;
        
    }
}
Posted Updated LeetCode / Easy / 复习2 minutes read (About 319 words)

542. 01 Matrix

问题
Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.
The distance between two adjacent cells is 1.

由于是搜索最近的距离，因此可以采用BFS搜索。
首先创建一个距离矩阵，将所有原矩阵为0的位置填上距离0，将其他位置填上无穷大。
使用BFS搜索，将所有0的坐标放入队列。
取出队列头元素，将其周围的距离矩阵的元素与自身距离矩阵的元素+1比较，将较小的值设置在周围的距离矩阵上。
同时，将改变数值的坐标再次放入队列。

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
37
38
39
40
41
42
43
44
45
class Solution{
    public int[][] updateMatrix(int[][] mat) {

        Queue<Integer> q = new LinkedList();
        int row = mat.length;
        int col = mat[0].length;
        int[][] ans = new int[row][col];
                                   
        for ( int i = 0; i < row; i++ ){
            for (int j = 0; j < col; j++){
                if (mat[i][j] == 0){
                    ans[i][j] = 0;
                    q.add(i*col + j);
                }
                else{
                    ans[i][j] = Integer.MAX_VALUE;
                }
            }
        }

            
        while(!q.isEmpty()){
            int i = q.peek() / col;
            int j = q.poll() % col;
            
            if(i-1 >= 0 && ans[i][j]+1 < ans[i-1][j]){
                ans[i-1][j] = ans[i][j]+1;
                q.add((i-1)*col + j);
            }
            if(i+1 < row && ans[i][j]+1 < ans[i+1][j]){
                ans[i+1][j] = ans[i][j]+1;
                q.add((i+1)*col + j);
            }
            if(j-1 >= 0 && ans[i][j]+1 < ans[i][j-1]){
                ans[i][j-1] = ans[i][j]+1;
                q.add(i*col + (j-1));
            }
            if(j+1 < col && ans[i][j]+1 < ans[i][j+1]){
                ans[i][j+1] = ans[i][j]+1;
                q.add(i*col + (j+1));
            }
        }
        return ans;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 361 words)

116. Populating Next Right Pointers in Each Node

问题
You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1
2
3
4
5
6
 struct Node {
 int val;
 Node *left;
 Node *right;
 Node *next;
>}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

递归，当root为null时返回。
如果root有右节点，则左节点next指向右节点。
如果root有右节点同时next已经指向了一个节点，则将其右节点next指向该节点的左子节点。
递归左右子节点，并返回root。

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
37
38
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if (root==null){return root;}
        if (root.right!=null){
            root.left.next = root.right;
            if (root.next!=null){
                root.right.next = root.next.left;
            }
        }
        connect(root.left);
        connect(root.right);
        return root;
    }
}

BFS搜索每一个节点，将节点指向队列中next下一个节点。
当计数器达到2的指数时，将节点指向null。

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
37
38
39
40
41
42
class Solution {
    public Node connect(Node root) {
        if (root == null){
            return root;
        }
        
        int count = 1;
        Queue<Node> q = new LinkedList();
        q.offer(root);
        while (!q.isEmpty()){
            count++;
            Node curr = q.poll();
            if ( isPow(count) ){
                curr.next = null;
            }
            else{
                curr.next = q.peek();
            }
            if(curr.left!=null){
                q.add(curr.left);
            }
            if(curr.right!=null){
                q.add(curr.right);
            }

        }
        return root;
    }
    
    private boolean isPow(int val){
        if(val == 0 || val == 1){
            return false;
        }
        while ( val % 2 == 0 ){
            val = val / 2;
        }
        if (val == 1){
            return true;
        }
        return false;
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 170 words)

20. Valid Parentheses

问题
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.

用栈储存遍历中的字符。
如果是“（”，“{”或“[”，则入栈。
如果是其他字符，且不与栈顶的字符成对，则返回false。
其他情况需要pop掉栈顶。

  • toCharArray(): 将字符串转换为字符数组，便于遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        
        for (char c : s.toCharArray()){
            if ( c == '(' || c == '{' || c == '[' ){
                stack.push(c);
            }
            else if ( stack.size() == 0 || 
                     c == ')' && stack.peek() != '(' || 
                     c == '}' && stack.peek() != '{' || 
                     c == ']' && stack.peek() != '[') {
                return false;
            }
            else{
                stack.pop();
            }
        }
        return stack.isEmpty();
    }
}
Follow

Recents

Archives

Links

×