leetcode-6-3-2021

Posted on In

This is a record of my craking process for Leetcode.

1. Number of Ways to Paint N × 3 Grid(#1411)#

1.1 Soulution#

Considering the base case (1 * 3) There are several possible choices. 121 212 213 232 312 313 (1 2 3 represents RGB 3 different colors). Then we can consider the next following posible choice in (2 * 3)

Let 121 represents head and tail have the same color and the middle pos varies

Let 123 represent every pos has different color

Then we can derive the following fomular
$$b_{121} = a_{121} * 3 + a_{123} * 2$$
$$b_{123} = a_{121} * 2 + a_{123} * 2$$

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numOfWays(int n) {
        long a121 = 6, a123 = 6, b121, b123, mod = (long)1e9 + 7;
        for (int i = 1; i < n; ++i) {
            b121 = a121 * 3 + a123 * 2;
            b123 = a121 * 2 + a123 * 2;
            a121 = b121 % mod;
            a123 = b123 % mod;
        }
        return (int)((a121 + a123) % mod);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
impl Solution {
    pub fn num_of_ways(n: i32) -> i32 {
        let (mut r, mut s) = (6_i64, 6_i64) ; 
        let x = 10_i64.pow(9) + 7; 
        for i in 1..n {
            let _r = r * 3 + s * 2; 
            let _s = r * 2 + s * 2; 
            r = _r % x; 
            s = _s % x; 
        }
        ((r + s) % x) as i32 
    }
}

2. Robot Bounded In Circle (#1041)#

2.1 Soulution#

The trick in this problem is to consider the impossible cases (The robot does not come back to original nor the bot face the initial position after iteration)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isRobotBounded(String instructions) {
        int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0;
        int idx = 0;
        for (char i : instructions.toCharArray()) {
            if (i == 'L')
                idx = (idx + 3) % 4;
            else if (i == 'R')
                idx = (idx + 1) % 4;
            else {
                x += directions[idx][0];
                y += directions[idx][1];
            }    
        }
        return (x == 0 && y == 0) || (idx != 0);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
impl Solution {
    pub fn is_robot_bounded(instructions: String) -> bool {
        let mut d = (0, 1);
        let mut p = (0, 0);
        for c in instructions.chars() {
            match c {
                'G' => p = (p.0 + d.0, p.1 + d.1),
                'L' => d = (-d.1, d.0),
                'R' => d = (d.1, -d.0),
                _ => {}
            }
        }
        p == (0, 0) || d != (0, 1)
    }
}