Posted Updated LeetCode / Easy / 复习a few seconds read (About 86 words)

118. Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal’s triangle.

动态规划，直接按照杨辉三角形的定义计算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> generate(int numRows) {
        ArrayList<List<Integer>> ans = new ArrayList<List<Integer>>(numRows);

        for (int i = 0; i < numRows ; i++){
            List<Integer> arr = new ArrayList<Integer>(i+1);
  
            for (int j = 0; j <= i; j++){
                if ( j == 0 || j == i ){
                    arr.add(1);
                }
                else{
                    arr.add(ans.get(i-1).get(j-1)+ans.get(i-1).get(j));
                }
            }
            ans.add(arr);
        }
        return ans;
    }
}

Posted Updated LeetCode / Easya minute read (About 207 words)

566. Reshape the Matrix

问题概述
In MATLAB, there is a handy function called reshape which can reshape an m x n matrix into a new one with a different size r x c keeping its original data.

You are given an m x n matrix mat and two integers r and c representing the number of rows and the number of columns of the wanted reshaped matrix.

The reshaped matrix should be filled with all the elements of the original matrix in the same row-traversing order as they were.

If the reshape operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.

根据数组的数学公式得出其位置，一次遍历将原数组中的数字填入。
O(r*c)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[][] matrixReshape(int[][] mat, int r, int c) {
        
        int[][] ans = new int[r][c];

        int oldR = mat.length;
        int oldC = mat[0].length;
        
        
        if ( oldR * oldC != r * c ){
            return mat;
        }
        for (int i = 0; i < r*c ; i++ ){
            int m = i/oldC;
            int n = i%oldC;
            
            int p = i/c;
            int q = i%c;        
            ans[p][q] = mat[m][n];
        }
        return ans;
    }
}
Posted Updated LeetCode / Medium / 复习a minute read (About 146 words)

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

环型替换，先求出数列长度和轮转次数的最大公约数m。
然后依次替换数列中的每个值。

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
//Rotate Array

class Solution {
    public void rotate(int[] nums, int k) {
        if (k != 0){
            int m = gcd(nums.length,k);
        
            for (int n = 0; n < m; n++ ) {
                int i = n + k;
                i %= nums.length;

                int temp = nums[n];
                while( true ){
                    int tempI = nums[i];
                    nums[i] = temp;
                    temp = tempI;
                
                    i += k;
                    i %= nums.length;
                
                    if (i == n){
                        nums[n] = temp;
                        break;
                    }
                }
            }
        }
    }
    
    private int gcd(int a, int b){
        int max = a;
        int min = b;
        if (max == min){
            return min;
        }
        
        if ( a < b ){
            max = b;
            min = a;
        }
        
        return gcd(max - min, min);
    }
}

Follow

Recents

Archives

Links

×