算法笔记-模拟法

图怪兽_1c0d7e7f12c31bb6d16bd88fddb324ab_47277.png

必备知识

有些问题的描述和解决方法已经很清楚，只需要按照描述去一步一步的执行即可，这种方法就是计算机解决问题的一种最普遍最直接的方法—-模拟法。
模拟法并不是程序，只是我们依赖计算机的运算速度解决问题的一种方法或模式，针对具体问题要设计具体的程序。
模拟法适用于问题求解清晰、运算规模较小的问题。如果问题求解的时空代价很大，就要考虑是否有其它更好的解决方案。

相关题目

推多米诺（mid)

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 String pushDominoes(String dominoes) {
        char[] s = dominoes.toCharArray();
        int n = s.length, i = 0;
        char left = 'L';
        while (i < n) {
            int j = i;
            while (j < n && s[j] == '.') { // 找到一段连续的没有被推动的骨牌
                j++;
            }
            char right = j < n ? s[j] : 'R';
            if (left == right) { // 方向相同，那么这些竖立骨牌也会倒向同一方向
                while (i < j) {
                    s[i++] = right;
                }
            } else if (left == 'R' && right == 'L') { // 方向相对，那么就从两侧向中间倒
                int k = j - 1;
                while (i < k) {
                    s[i++] = 'R';
                    s[k--] = 'L';
                }
            }
            left = right;
            i = j + 1;
        }
        return new String(s);
    }
}

球会落何处（mid）

我们依次判断每个球的最终位置。对于每个球，从上至下判断球位置的移动方向。在对应的位置，如果挡板向右偏，则球会往右移动；如果挡板往左偏，则球会往左移动。若移动过程中碰到侧边或者 V 型，则球会停止移动，卡在箱子里。如果可以完成本层的移动，则继续判断下一层的移动方向，直到落出箱子或者卡住。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] findBall(int[][] grid) {
        int n = grid[0].length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int j = 0; j < n; j++) {
            int col = j;  // 球的初始列
            for (int[] row : grid) {
                int dir = row[col];
                col += dir;  // 移动球
                if (col < 0 || col == n || row[col] != dir) {  // 到达侧边或 V 形
                    col = -1;
                    break;
                }
            }
            if (col >= 0) {  // 成功到达底部
                ans[j] = col;
            }
        }
        return ans;
    }
}

复数乘法（mid)

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
class Solution {
    //模拟:先移除i进行运算,再添加
    //(1+1i)*(1+1i)=1+1i+1i-1=0+2i
    //(1+1)*(1+1)=1+1i+1i-1=0+2i
    //(1+-i)*(1+-i)=1-i-i-1=0+-2i
    public String complexNumberMultiply(String num1, String num2) {
        //解析
        String[] n1 = num1.split("\\+");
        String[] n2 = num2.split("\\+");
        int n1Real = Integer.valueOf(n1[0]);
        int n2Real = Integer.valueOf(n2[0]);
        String n1rs = n1[1].replace("i", "");
        if(n1rs=="-"||n1rs=="")n1rs+="1";
        int n1Imaginary = Integer.valueOf(n1rs);
        String n2rs = n2[1].replace("i", "");
        if(n2rs=="-"||n2rs=="")n2rs+="1";
        int n2Imaginary = Integer.valueOf(n2rs);
        //运算
        int real = n1Real*n2Real+n1Imaginary*n2Imaginary*-1;
        int imaginary = n1Imaginary*n2Real+n2Imaginary*n1Real;
        return real+"+"+imaginary+"i";
    }
    public String complexNumberMultiply(String num1, String num2) {
        String[] complex1 = num1.split("\\+|i");
        String[] complex2 = num2.split("\\+|i");
        int real1 = Integer.parseInt(complex1[0]);
        int imag1 = Integer.parseInt(complex1[1]);
        int real2 = Integer.parseInt(complex2[0]);
        int imag2 = Integer.parseInt(complex2[1]);
        return String.format("%d+%di", real1 * real2 - imag1 * imag2, real1 * imag2 + imag1 * real2);
    }
}

寻找最近的回文数

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 String nearestPalindromic(String n) {
        long selfNumber = Long.parseLong(n), ans = -1;
        List<Long> candidates = getCandidates(n);
        for (long candidate : candidates) {
            if (candidate != selfNumber) {
                if (ans == -1 ||
                    Math.abs(candidate - selfNumber) < Math.abs(ans - selfNumber) ||
                    Math.abs(candidate - selfNumber) == Math.abs(ans - selfNumber) && candidate < ans) {
                    ans = candidate;
                }
            }
        }
        return Long.toString(ans);
    }

    public List<Long> getCandidates(String n) {
        int len = n.length();
        List<Long> candidates = new ArrayList<Long>() {{
            add((long) Math.pow(10, len - 1) - 1);
            add((long) Math.pow(10, len) + 1);
        }};
        long selfPrefix = Long.parseLong(n.substring(0, (len + 1) / 2));
        for (long i = selfPrefix - 1; i <= selfPrefix + 1; i++) {
            StringBuffer sb = new StringBuffer();
            String prefix = String.valueOf(i);
            sb.append(prefix);
            StringBuffer suffix = new StringBuffer(prefix).reverse();
            sb.append(suffix.substring(len & 1));
            String candidate = sb.toString();
            candidates.add(Long.parseLong(candidate));
        }
        return candidates;
    }
}

1424. 对角线遍历 II（mid)

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
class Solution {
    //模拟：根据条件:同一斜线x+y相等
    public int[] findDiagonalOrder(List<List<Integer>> nums) {
        int n = nums.size();
        int total = 0;
        Map<Integer,ArrayList<Integer>> map = new HashMap<>();
        for(int i=0;i<n;i++){
            int length = nums.get(i).size();
            total+=length;
            for(int j=0;j<length;j++){
                int key = i+j;
                ArrayList<Integer> list = map.getOrDefault(key,new ArrayList<>());
                list.add(nums.get(i).get(j));
                map.put(key,list);
            }
        }
        //逆序输出map里的list
        int[] ret = new int[total];
        int index = 0;
        for(int i=0;i<map.size();i++){
            ArrayList<Integer> list = map.get(i);
            for(int j=list.size()-1;j>=0;j--)ret[index++]=list.get(j);
        }
        return ret;
    }
    //模拟(超时)
    public int[] findDiagonalOrder0(List<List<Integer>> nums) {
        int n = nums.size();
        List<Integer> list = new ArrayList<>();
        int m = 0;
        for(int i=0;i<n;i++){
            int length = nums.get(i).size();
            if(length>m)m=length;
            int x = i,y = 0;
            while(x>=0&&y<m){
                if(nums.get(x).size()>y){
                    list.add(nums.get(x).get(y));
                }
                x--;
                y++;
            }
        }
        for(int i=1;i<m;i++){
            int x = n - 1,y = i;
            while(x>=0&&y<m){
                if(nums.get(x).size()>y){
                    list.add(nums.get(x).get(y));
                }
                x--;
                y++;
            }
        }
        int[] ret = new int[list.size()];
        for(int i=0;i<list.size();i++)ret[i]=list.get(i);
        return ret;
    }
}

57. 插入区间（mid）

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
class Solution {
    //模拟:
    //1.插入的区间在首尾
    // 1.1 首部分区间 [l0,r0] l0>newR
    // 1.2 尾部区间，新区间大于旧区间所有区间。
    //2.插入的区间在中间
    // 2.1 没有重叠区间 [l0,r0] r0<newl [l1,r1], newr<l1
    // 2.2 有区间重叠，判断是否可以合并,l1,r1,如果newl<=r1则可以合并,合并后[min(l1,newl),max(r1,newr)]
    //   2.2.1 新区间覆盖旧区间
    //   2.2.2 旧区间覆盖新区间
    //   2.2.3 新区间和旧区间正好接上
    //   2.2.4 新区间和旧区间有交集
//    [[1,2],[3,5],[6,7],[8,10],[12,16]]
//            [4,8]
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length;
        List<int[]> ret = new ArrayList<>();
        if(n<=0)return new int[][]{{newInterval[0],newInterval[1]}};
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        boolean hasAdd = false;
        if(newEnd<intervals[0][0]){//1.1情况：插入到首区间
            ret.add(new int[]{newStart,newEnd});
            hasAdd = true;
        }
        for(int[] interval:intervals){//2.情况:需要判断是否有重合的区间
            int start = interval[0];
            int end = interval[1];//System.out.println(start+"|"+end+"|"+hasAdd+"|"+newEnd+"|"+newStart);
            if (hasAdd){//已经添加过了
                ret.add(interval);
                continue;
            }
            if (end<newStart){//没有交集
                ret.add(interval);
            } else if(newEnd<start){//与新区间没有交集了
                if(!hasAdd){
                    ret.add(new int[]{newStart,newEnd});
                    hasAdd = true;
                }
                ret.add(interval);
            }else if(end>=newStart||(newStart<interval[0]&&newEnd>interval[1])){//有交集
                newStart = Math.min(start,newStart);
                newEnd = Math.max(end,newEnd);
            }
        }
        if(!hasAdd)ret.add(new int[]{newStart,newEnd});//1.2情况：插到末尾区间
        return ret.toArray(new int[ret.size()][]);
    }
}

相关资料

基础算法 > 刷题记录
算法笔记-模拟法
https://mikeygithub.github.io/2021/01/18/yuque/算法笔记-模拟法/
作者
Mikey
发布于
2021年1月18日
许可协议