《算法系列》之模拟

简介

  模拟题大多给人的感觉是，脑子会了，手就是调不出来，会对代码的掌握能力要求很高。但这里有一个陷阱，对于大多数题目来讲，模拟方式做题并不是一个很好的选择，你想动态规化的题你能模拟吗？动规的题模拟的话，部分题计算机算到宇宙重启都算不完，可能模拟是思维难度上最简单的方式，但是并不一定是当前题最好的选择，如果有别的解法，不用选择最笨的模拟方式。但也有题直接一来就是模拟方式，没有更好的解法，有的还是大厂常考题（如：螺旋矩阵），为什么呢？因为很考代码掌握能力。

理论基础

  模拟的理论基础其实更多的应该是抽象的能力。leetcode上的题，都有一个特点，偏算法实现，基本算法模型能在题面上第一时间看出来。但有一天你面试的时候，发现在平时几十个字的算法题，变成了几百个字的小作文。面试要求就是，要你抽象出算法模型，然后用合适的算法去解决它，这时抽象能力差了，题都读不明白，更别说解题了。模拟题里的抽象算leetcode里考察比较多的了，比如螺旋矩阵，生命矩阵啥的。模拟题并没有什么章法，多练即是章法。能第一时间知道这是模拟类的题最好了，就不是扣破脑袋想骚代码了，因为通常你都想不出来，而白白浪费宝贵的时间！

解题心得

• 模拟题一般是思维难度上简单，代码实现上较难。
• 一道算法题，能用其它解法就不要用模拟法，因为时间复杂度比较高。
• 模拟题很考察代码掌握能力。
• 要想模拟题做的好，抽象能力少不了。
• 多做模拟题有个好处，即我们能第一时间知道这题是不是模拟题，而不用去想巧解，否则会在不通的路浪费了时间。

算法题目

43. 字符串相乘

题目解析：用数组模仿乘法，详细解析如下。

num1的第i位(高位从0开始)和num2的第j位相乘的结果在乘积中的位置是[i+j, i+j+1]
例: 123 * 45,  123的第1位 2 和45的第0位 4 乘积 08 存放在结果的第[1, 2]位中

 index:    0 1 2 3 4  
 
           1 2 3
       *     4 5
       ---------
             1 5
           1 0
         0 5
       ---------
         0 6 1 5
           1 2
         0 8
       0 4
       ---------
       0 5 5 3 5
这样我们就可以单独都对每一位进行相乘计算把结果存入相应的index中   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

代码如下：

/**
 * 模拟
 *
 **/
class Solution {
    public String multiply(String num1, String num2) {
        int n1 = num1.length() - 1;
        int n2 = num2.length() - 1;
        if(n1 < 0 || n2 < 0) return "";
        int[] mul = new int[n1 + n2 + 2];
        
        for(int i = n1; i >= 0; --i) {
            for(int j = n2; j >= 0; --j) {
                int bitmul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');      
                bitmul += mul[i + j + 1]; // 先加低位判断是否有新的进位
                
                mul[i + j] += bitmul / 10;
                mul[i + j + 1] = bitmul % 10;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        int i = 0;
        // 去掉前导0
        while(i < mul.length-1 && mul[i] == 0) 
            i++;
        for(; i < mul.length; ++i)
            sb.append(mul[i]);
        return sb.toString();
    }
}
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

54. 螺旋矩阵

题目解析：这是一道经典模拟题，没有特别的解法，考察的就是代码掌握能力，理解题意后，然后模拟整个遍历的过程即可。
代码如下：

/**
 * 模拟
 */
class Solution {
    public List spiralOrder(int[][] matrix) {

        List res = new ArrayList<>();
        if (matrix.length == 0) {
            return res;
        }

        int start_x = 0;
        int start_y = 0;
        int direction = 0;
        int top_border = -1; // 上边界
        int right_border = matrix[0].length; // 右边界
        int bottom_border = matrix.length; // 下边界
        int left_border = -1; // 左边界

        // direction 向右：0，向下：2，向左3，向上：4
        while (true) {

            // 遍历完后返回
            if (res.size() == matrix.length * matrix[0].length) {
                return res;
            }
            // 注意，二维数组的行列，和坐标x,y轴，对应关系为 行 = y，列 = x
            res.add(matrix[start_y][start_x]);
            switch (direction) {
                // 向右
                case 0:
                    if (start_x + 1 == right_border) {
                        // 到底则改变方向，向下，向下移一行，上边界也向下移一行
                        direction = 1;
                        start_y += 1;
                        top_border += 1;
                    } else {
                        // 如果没到右边界，则持续往右
                        start_x += 1;
                    }
                    break;
                // 向下
                case 1:
                    if (start_y + 1 == bottom_border) {
                        // 到底则改变方向，向左，向左移一列，右边界也向左移一列
                        direction = 2;
                        start_x -= 1;
                        right_border -= 1;
                    } else {
                        // 如果没到下边界，则持续往下
                        start_y += 1;
                    }
                    break;
                // 向左
                case 2:
                    if (start_x - 1 == left_border) {
                        // 到底则改变方向，向上，向上移一行，下边界也向上移一行
                        direction = 3;
                        start_y -= 1;
                        bottom_border -= 1;
                    } else {
                        // 如果没到左边界，则持续往左
                        start_x -= 1;
                    }
                    break;
                // 向上
                case 3:
                    if (start_y - 1 == top_border) {
                        // 到底则改变方向，向右，向右移一列，左边界也向右移一列
                        direction = 0;
                        start_x += 1;
                        left_border += 1;

                    } else {
                        // 如果没到上边界，则持续往上
                        start_y -= 1;
                    }
                    break;
            }
        }
    }
}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

59. 螺旋矩阵 II

题目解析：和上题一样，面试常考题，考察的就是代码掌握能力，旋转整个数组。
代码如下：

/**
 * 模拟
 */
class Solution {
    public int[][] generateMatrix(int n) {

        int[][] res = new int[n][n];

        // 为零直接返回
        if (n == 0) {
            return res;
        }

        int start_row = 0; // 行位置
        int start_column = 0; // 列位置
        int direction = 0; // 方向，向右：0，向下：1，向左2，向上：3
        int top_border = -1; // 上边界
        int bottom_border = n; // 下边界
        int left_border = -1; // 左边界
        int right_border = n; // 右边界

        for (int i = 1; i <= n * n; i++) {

            res[start_row][start_column] = i;
            switch (direction) {
                // 向右
                case 0:
                    // 判断是否到右边界
                    if (start_column + 1 == right_border) {
                        // 到底则改变方向，向下
                        direction = 1;
                        // 位置向下移一行，上边界也向下移一行
                        start_row += 1;
                        top_border += 1;
                    } else {
                        // 如果没到右边界，则持续往右
                        start_column += 1;
                    }
                    break;
                // 向下
                case 1:
                    // 判断是否到下边界
                    if (start_row + 1 == bottom_border) {
                        // 到底则改变方向，向左
                        direction = 2;
                        // 位置向左移一列，右边界也向左移一列
                        start_column -= 1;
                        right_border -= 1;
                    } else {
                        // 如果没到下边界，则持续往下
                        start_row += 1;
                    }
                    break;
                // 向左
                case 2:
                    // 判断是否到左边界
                    if (start_column - 1 == left_border) {
                        // 到底则改变方向，向上
                        direction = 3;
                        // 位置向上移一行，下边界也向上移一行
                        start_row -= 1;
                        bottom_border -= 1;
                    } else {
                        // 如果没到左边界，则持续往左
                        start_column -= 1;
                    }
                    break;
                // 向上
                case 3:
                    // 判断是否到上边界
                    if (start_row - 1 == top_border) {
                        // 到底则改变方向，向右
                        direction = 0;
                        // 位置向右移一列，左边界也向右移一列
                        start_column += 1;
                        left_border += 1;

                    } else {
                        // 如果没到上边界，则持续往上
                        start_row -= 1;
                    }
                    break;
            }
        }
        return res;
    }
}
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87

68. 文本左右对齐

题目解析：困难型的模拟题，根据题干描述的贪心算法，对于每一行，我们首先确定最多可以放置多少单词，这样可以得到该行的空格个数，从而确定该行单词之间的空格个数。
代码如下：

/**
 * 模拟
 */
class Solution {
    public List fullJustify(String[] words, int maxWidth) {
        List ans = new ArrayList();
        int right = 0, n = words.length;
        while (true) {
            int left = right; // 当前行的第一个单词在 words 的位置
            int sumLen = 0; // 统计这一行单词长度之和
            // 循环确定当前行可以放多少单词，注意单词之间应至少有一个空格
            while (right < n && sumLen + words[right].length() + right - left <= maxWidth) {
                sumLen += words[right++].length();
            }

            // 当前行是最后一行：单词左对齐，且单词之间应只有一个空格，在行末填充剩余空格
            if (right == n) {
                StringBuffer sb = join(words, left, n, " ");
                sb.append(blank(maxWidth - sb.length()));
                ans.add(sb.toString());
                return ans;
            }

            int numWords = right - left;
            int numSpaces = maxWidth - sumLen;

            // 当前行只有一个单词：该单词左对齐，在行末填充剩余空格
            if (numWords == 1) {
                StringBuffer sb = new StringBuffer(words[left]);
                sb.append(blank(numSpaces));
                ans.add(sb.toString());
                continue;
            }

            // 当前行不只一个单词
            int avgSpaces = numSpaces / (numWords - 1);
            int extraSpaces = numSpaces % (numWords - 1);
            StringBuffer sb = new StringBuffer();
            sb.append(join(words, left, left + extraSpaces + 1, blank(avgSpaces + 1))); // 拼接额外加一个空格的单词
            sb.append(blank(avgSpaces));
            sb.append(join(words, left + extraSpaces + 1, right, blank(avgSpaces))); // 拼接其余单词
            ans.add(sb.toString());
        }
    }

    // blank 返回长度为 n 的由空格组成的字符串
    public String blank(int n) {
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; ++i) {
            sb.append(' ');
        }
        return sb.toString();
    }

    // join 返回用 sep 拼接 [left, right) 范围内的 words 组成的字符串
    public StringBuffer join(String[] words, int left, int right, String sep) {
        StringBuffer sb = new StringBuffer(words[left]);
        for (int i = left + 1; i < right; ++i) {
            sb.append(sep);
            sb.append(words[i]);
        }
        return sb;
    }
}
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

289. 生命游戏

题目解析：如果需要原地算法，则用数组记更多信息，除0，1外，int类型可以记更多信息，-1代表这个细胞过去是活的现在死了，2代表这个细胞过去是死的现在活了。
代码如下：

/**
 * 模拟 
 * 
 */
class Solution {
    public void gameOfLife(int[][] board) {
        int[] neighbors = {0, 1, -1};

        int rows = board.length;
        int cols = board[0].length;

        // 遍历面板每一个格子里的细胞
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {

                // 对于每一个细胞统计其八个相邻位置里的活细胞数量
                int liveNeighbors = 0;

                for (int i = 0; i < 3; i++) {
                    for (int j = 0; j < 3; j++) {

                        if (!(neighbors[i] == 0 && neighbors[j] == 0)) {
                            // 相邻位置的坐标
                            int r = (row + neighbors[i]);
                            int c = (col + neighbors[j]);

                            // 查看相邻的细胞是否是活细胞
                            if ((r < rows && r >= 0) && (c < cols && c >= 0) && (Math.abs(board[r][c]) == 1)) {
                                liveNeighbors += 1;
                            }
                        }
                    }
                }

                // 规则 1 或规则 3 
                if ((board[row][col] == 1) && (liveNeighbors < 2 || liveNeighbors > 3)) {
                    // -1 代表这个细胞过去是活的现在死了
                    board[row][col] = -1;
                }
                // 规则 4
                if (board[row][col] == 0 && liveNeighbors == 3) {
                    // 2 代表这个细胞过去是死的现在活了
                    board[row][col] = 2;
                }
            }
        }

        // 遍历 board 得到一次更新后的状态
        for (int row = 0; row < rows; row++) {
            for (int col = 0; col < cols; col++) {
                if (board[row][col] > 0) {
                    board[row][col] = 1;
                } else {
                    board[row][col] = 0;
                }
            }
        }
    }
}
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

回到首页

刷 leetcode 500+ 题的一些感受

下一篇

《算法系列》之位运算