8.25刷题

发表于 | 分类于 | 0 comments

276. Paint Fence

题目描述

有一排栅栏，现在有k的颜色。要求只能最多有两个连续的栅栏有相同得颜色，求总共可能有多少种上颜料的方式。

算法

在这题的DP中，主要存在了两种状态：

  1. 下一个与上一个同样颜色
  2. 下一个与上一不同颜色

但是这样想我们发现题目并不要解决，因为我们还要考虑上一个的前一个的颜色，如果为相同，那么必须为不同的颜色。因此我们的状态转移矩阵使用最后的两个颜色的相同或不同作为状态转移矩阵，same和differ

对于新来的栅栏，如果我们希望是same状态，那么只有一种情况，即上两个是differ而且与最后一个相同颜色，那么总的数量只能是differ。如果希望是differ状态，那么情况时(same + differ) * (k-1)

这样，即可写出程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numWays(int n, int k) {
        if (n == 0)
            return 0;
        if (n == 1)
            return k;
        int samelastwo = k;
        int diflastwo = k * (k - 1);
        for (int i = 2; i < n; i++) {
            int temp = diflastwo;
            diflastwo = (samelastwo + diflastwo) * (k - 1);
            samelastwo = temp;
        }
        return diflastwo + samelastwo;
    }
}

相关问题

256. Paint House

用三种颜色喷涂房子，并找出最小的cost

关键思路：找出所有可能存在的状态，然后找出到达这个状态的表达。之后找出初始状态

265. Paint House II

更多的颜色

关键思路：与上一题类似

198. House Robber

找出两种状态，然后依次按照状态变量进行推进

213. House Robber II

主要是以最后一个能不能强最为状态的缩减，将问题递归到前一个问题。即强[0, i-2]或者强[1, i-1]两个状态上来

303. Range Sum Query - Immutable

题目描述

给定整数数组nums，计算下标i与j之间的元素和（i ≤ j），包含边界。

测试样例见题目描述。

算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumArray {
    int[] store; 
    public NumArray(int[] nums) {
        store = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i > 0)
                store[i] = store[i - 1] + nums[i];
            else
                store[i] = nums[i];
        }
    }
    
    public int sumRange(int i, int j) {
        return i == 0 ? store[j] : store[j] - store[i - 1];
    }
}

304. Range Sum Query 2D - Immutable

题目描述

现在变为了2D矩阵，求sum

算法

为了查询的更快，可以使用小方块面积相加减的方法进行计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class NumMatrix {
    int[][] sum;
    public NumMatrix(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0)
            return;
        sum = new int[matrix.length + 1][matrix[0].length + 1];
        
        for (int i = 1; i <= matrix.length; i++) {
            for (int j = 1; j <= matrix[0].length; j++) {
                sum[i][j] = matrix[i - 1][j - 1] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
            }
        }
        
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1];
    }
}