leetcode之模拟刷题总结1_leetcode 模拟是什么

leetcode之模拟刷题总结1

1-字符串相乘
题目链接：题目链接戳这里！！！

第一思路：用BigInteger来处理大数，但是题目要求不允许使用BigInteger，哈哈

用BigIntger的AC代码如下：

import java.math.BigInteger ;
class Solution {
    public String multiply(String num1, String num2) {
        BigInteger s1 = new BigInteger(num1) ;
        BigInteger s2 = new BigInteger(num2) ;
        return s2.multiply(s1).toString() ;
    }
}
1
2
3
4
5
6
7
8

这题考的是模拟，我们呢看一下,就是模拟每一位数依次相乘，然后错位相加的过程，可以看一下下面的图，就是1234与567相乘的计算过程。

AC代码如下：

class Solution {
    public String multiply(String num1, String num2) {
        if(num1.equals("0") || num2.equals("0")){
            return "0" ;
        }
        int n1 = num1.length() ;
        int n2 = num2.length() ;
        String res = "0" ;
        StringBuilder str = new StringBuilder() ;
        List<String> list = new ArrayList<>() ;
        for(int i=n1-1; i>=0; i--){
            String s = "" ;
            int ans = 0 ;
            for(int j=n2-1; j>=0; j--){
                int temp = (num1.charAt(i)-'0')*(num2.charAt(j)-'0') ;
                if(ans > 0){
                    temp += ans ;
                    ans = 0 ;
                }
                if(temp>=10 && j!=0){
                    ans = temp / 10 ;
                    s += temp % 10 ;
                }else{
                    if(temp<10){
                    s += temp ;
                    }else{
                        s += temp%10 ;
                        s += temp/10 ;
                    }
                }
            }
            str = new StringBuilder(s) ;
            s = str.reverse().toString() ;
            for(int k=n1-1; k>i; k--){
                s+= "0" ;
            }
            res = add(res, s) ;
        }
        return res;
    }
    public String add(String num1, String num2){
       int i=num1.length()-1, j = num2.length()-1, add=0 ;
       StringBuilder ss = new StringBuilder() ;
       while(i>=0 || j>=0 || add!=0){
           int x = i>=0 ? (num1.charAt(i)-'0') : 0 ;
           int y = j>=0 ? (num2.charAt(j)-'0') : 0 ;
           int result = x + y + add ;
           add = result / 10 ;
           ss.append(result%10) ;
           i -- ;
           j -- ;
       }
       return ss.reverse().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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

2-字符串相乘
题目链接：题目链接戳这里！！！

第一思路：这题直接用BigIntger,分分钟解决，不过题目说了不要用，那就是要模拟这个相加的过程。

import java.math.BigInteger ;
class Solution {
    public String addStrings(String num1, String num2) {
        BigInteger s1 = new BigInteger(num1) ;
        BigInteger s2 = new BigInteger(num2) ;
        return s1.add(s2).toString() ;
    }
}
1
2
3
4
5
6
7
8

模拟过程就是每一位相加，大于10的进位。

class Solution {
    public String addStrings(String num1, String num2) {
        int i=num1.length()-1, j=num2.length()-1, add = 0 ;
        StringBuilder s = new StringBuilder() ;
        while(i>=0 || j>=0 || add!=0){
            int x = i>=0 ? (num1.charAt(i)-'0') : 0 ;
            int y = j>=0 ? (num2.charAt(j)-'0') : 0 ;
            int result = x + y + add ;
            add = result / 10 ;
            s.append(result%10) ;
            i -- ;
            j -- ;
        }
        return s.reverse().toString() ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3-各位相加
题目链接：题目链接戳这里！！！

循环暴力法：

class Solution {
    public int addDigits(int num) {
        int sum = 10 ;
        while(sum>9){
            sum = 0 ;
        while(num!=0){
            sum += num%10 ;
            num /= 10 ;
        }
        num = sum ;
    }
        return sum ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

递归法：

class Solution {
    public int addDigits(int num) {
        if(num<10){
            return num ;
        }
        int sum = 0 ;
        while(num != 0){
            sum += num% 10 ;
            num = num/10 ;
        }
        return addDigits(sum) ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

模拟：一句代码搞定，O(1)时间复杂度

class Solution {
    public int addDigits(int num) {
        return (num-1)%9+1 ;
    }
}
1
2
3
4
5

4-螺线矩阵
题目链接：题目链接戳这里！！！

思路：定义上下左右四个方向的边界，模拟移动过程，并更新边界，直到全部走完所有的矩形块。

题目不难，但是细节慢慢。

AC代码如下：

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        int top = 0, bottom = matrix.length-1, left =0, right = matrix[0].length-1;
        List<Integer> list = new ArrayList<>() ;
        while(true){
            for(int i=left; i<=right; i++){
                list.add(matrix[top][i]) ;
            }
            top++ ;
            if(top>bottom){
                break ;
            }
            for(int i=top; i<=bottom; i++){
                list.add(matrix[i][right]) ;
            }
            right -- ;
            if(left>right){
                break ;
            }
            for(int i=right; i>=left; i--){
                list.add(matrix[bottom][i]) ;
            }
            bottom -- ;
            if(bottom<top){
                break ;
            }
            for(int i=bottom; i>=top; i--){
                list.add(matrix[i][left]) ;
            }
            left ++ ;
            if(left>right){
                break ;
            }

        }
        return list ;
    }
}
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

5-螺线矩阵II
题目链接：题目链接戳这里！！！

思路：这题和上题思路一样，都是定义四个边界，模拟螺旋矩阵的生成的过程。

AC代码如下：

class Solution {
    public int[][] generateMatrix(int n) {
        int top=0, bottom=n-1, left=0, right=n-1;
        int [][] res = new int [n][n] ;
        int idx = 1 ;
        while(idx <= n*n){
            for(int i=left; i<=right; i++){
                res[top][i] = idx++ ;
            }
            top ++ ;
            for(int i=top; i<=bottom; i++){
                res[i][right] = idx++ ;
            }
            right -- ;
            for(int i=right; i>=left; i--){
                res[bottom][i] = idx++ ;
            }
            bottom -- ;
            for(int i=bottom; i>=top; i--){
                res[i][left] = idx++ ;
            }
            left ++ ;
        }
        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

6-生命游戏
题目链接：题目链接戳这里！！！

思路：这题也是标准的模拟，先将数组board全部复制给数组ans,我们对每个点模拟出8个方向，通过判断8个方向的值，修改ans数组，最后再将ans数组的值全部复制给board即可。

AC代码如下：

class Solution {
    public void gameOfLife(int[][] board) {
        int [] x = {-1,-1,-1,0,0,1,1,1} ;
        int [] y = {-1,0,1,-1,1,-1,0,1} ;
        int [][] ans = new int [board.length][board[0].length] ;
        for(int i=0; i<ans.length; i++){
        for(int j=0; j<ans[0].length; j++){
            ans[i][j] = board[i][j] ;
        }
    }
        int cnt ;
        for(int i=0; i<board.length; i++){
            for(int j=0; j<board[0].length; j++){
                 cnt = 0 ;
                for(int k=0; k<8; k++){
                    int nx = i + x[k] ;
                    int ny = j + y[k] ;
            if(nx>=0 && nx<board.length && ny>=0 && ny<board[0].length && board[nx][ny]==1){
                cnt ++  ;
                }
            }
            if(cnt<2){
                ans[i][j] = 0 ;
            }else if(cnt>3){
                ans[i][j] = 0 ;
            }else if(cnt==3){
                ans[i][j] = 1 ;
            }
        }
    }
    for(int i=0; i<ans.length; i++){
        for(int j=0; j<ans[0].length; j++){
            board[i][j] = ans[i][j] ;
        }
    }
    
}
}
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

7-二进制求和
题目链接：题目链接戳这里！！！

思路：这题也是模拟，模拟二进制相加的过程即可，和模拟整数相加的过程很像，二进制每一位相加得到的结果为0或者1不需要进位，要是结果为2或者3则需要进位。

AC代码如下：

class Solution {
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder() ;
        int i = a.length()-1, j=b.length()-1, add=0 ;
       
        while(i>=0 || j>=0 || add!=0){
            int x = i>=0 ? (a.charAt(i)-'0') : 0 ;
            int y = j>=0 ? (b.charAt(j)-'0') : 0 ;
            int result = x + y + add ;
            if(result==0 || result==1){
                res.append(result) ;
                add = 0 ;
            }else if(result==2){
                res.append(0) ;
                add = 1 ;
            }else if(result==3){
                res.append(1) ;
                add = 1;
            }
            i -- ;
            j -- ;
        }
        return res.reverse().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

8-提莫攻击
题目链接：题目链接戳这里！！！

思路：模拟一下攻击过程就行了，时间间隔外攻击则累加时间间隔，时间间隔内攻击，则累加两次攻击的时间差。

AC代码如下：

class Solution {
    public int findPoisonedDuration(int[] timeSeries, int duration) {
        int res = 0 ;
        for(int i=0; i+1<timeSeries.length; i++){
            if(timeSeries[i]+duration<=timeSeries[i+1]){
                res += duration ;
            }else{
                res += timeSeries[i+1] - timeSeries[i] ;
            }
        }
        return res+duration ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

9-对角线遍历
题目链接：题目链接戳这里！！！

思路：模拟对角线遍历的过程，这个过程需要很细心，观察规律，首先根据当前横纵坐标之和确定层次，然后根据层次确定方向，当向上遍历时候，需要考虑三点，当向下遍历时候，也需要考虑三处，两处转弯，一处不转弯。

AC代码如下：

class Solution {
    public int[] findDiagonalOrder(int[][] mat) {
        int [] res = new int [mat.length*mat[0].length] ;
        int row = 0, col = 0 ;
        for(int i=0; i<res.length; i++){
            res[i] = mat[row][col] ;
            //row+col代表层次,偶数代表向上走,奇数代表向下走
            if(((row+col)&1)==0){ //向上走
                if(col==mat[0].length-1){
                    row ++ ;
                }else if(row==0){
                    col ++ ;
                }else{
                    row -- ;
                    col ++ ;
                }
            }else{ //向下走
                if(row==mat.length-1){
                    col ++ ;
                }else if(col==0){
                    row++ ;
                }else{
                    row ++ ;
                    col -- ;
                }
            }
        }
        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

10-复数乘法
题目链接：题目链接戳这里！！！

思路：模拟复数乘法过程
(a+bi)*(c+di)=(ac-bd)+(ad+bc)i

AC代码如下：

class Solution {
    public String complexNumberMultiply(String num1, String num2) {
        int idx1 = 0, idx2 = 0 ;
        for(int i=0; i<num1.length(); i++){
            if(num1.charAt(i)=='+'){
                idx1 = i ;
            }
        }
        for(int j=0; j<num2.length(); j++){
            if(num2.charAt(j) == '+'){
                idx2 = j ;
            }
        }
        String a = num1.substring(0,idx1) ;
        String b = num1.substring(idx1+1,num1.length()-1) ;
        String c = num2.substring(0,idx2) ;
        String d = num2.substring(idx2+1,num2.length()-1) ;
    int shi = Integer.parseInt(a)*Integer.parseInt(c)-Integer.parseInt(b)*Integer.parseInt(d) ;
    int xu = Integer.parseInt(a)*Integer.parseInt(d)+Integer.parseInt(b)*Integer.parseInt(c) ;
    return shi+"+"+xu+"i";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

不积硅步，无以至千里，不积小流，无以成江河，加油吧，年轻人！！！