Leetcode daily practice (Yanghui triangle)

Look at the problem directly ：

Given a nonnegative index k, among k ≤ 33, Go back to the third part of Yanghui triangle k That's ok .
In Yanghui triangle , Each number is the sum of the numbers at the top left and right of it .
Example :
Input : 3
Output : [1,3,3,1]

The question is to give a nonnegative index k, Ask for the third in Yang Hui's triangle k That's ok , I believe you are no stranger to the Yanghui triangle , Don't understand the students go to Baidu to make up lessons .

For this question , Because given the index k Value range of , So we can find out 33 The Yang Hui triangle of the row is stored in a two-dimensional array , And then according to k Returns the data of the corresponding line ; So how to write the specific code ？ Let's analyze first ：

It's easy to find the rules , First of all 1 Yes 1 A numerical , The first 2 Yes 2 A numerical , The first 3 Yes 3 A numerical , And so on , The first i Yes, there is i A numerical ; secondly , For each line , Its first and last element values are 1, From this we can get the following code ：

	@Test
    public void test() {
    
        //  because k Small is equal to 33, At most it needs to be calculated 33 That's ok 
        int[][] nums = new int[32][];
        //  For the first i That's ok , All of them have i Column 
        for (int i = 0; i < nums.length; ++i) {
    
            nums[i] = new int[i + 1];
        }
        for (int i = 0; i < nums.length; ++i) {
    
            for (int j = 0; j < nums[i].length; ++j) {
    
                if (j == 0 || j == i) {
    
                    //  The first and last elements of each line are 1
                    nums[i][j] = 1;
                }
            }
        }
        for (int[] num : nums) {
    
            for (int n : num) {
    
                System.out.print(n + "\t");
            }
            System.out.println();
        }
    }

Running results ：

1	
1	1	
1	0	1	
1	0	0	1	
1	0	0	0	1	
1	0	0	0	0	1	
1	0	0	0	0	0	1	
1	0	0	0	0	0	0	1	
......

The key now is these 0 How to calculate the value of the element in position ？ Carefully observe the structure of Yang Hui triangle , It's not hard to find this rule ：

These values are obtained by adding the value of the element in the previous row to the value of the element in the previous row , such as ： The fifth row 6, It is determined by the value of the corresponding element in the previous line 3 and 3 The value of the previous element of 3 Add up to get , So continue to transform the code ：

	@Test
    public void test() {
    
        //  because k Small is equal to 33, At most it needs to be calculated 33 That's ok 
        int[][] nums = new int[32][];
        //  For the first i That's ok , All of them have i Column 
        for (int i = 0; i < nums.length; ++i) {
    
            nums[i] = new int[i + 1];
        }
        for (int i = 0; i < nums.length; ++i) {
    
            for (int j = 0; j < nums[i].length; ++j) {
    
                if (j == 0 || j == i) {
    
                    //  The first and last elements of each line are 1
                    nums[i][j] = 1;
                }else {
    
                    //  For other locations , Its value is equal to the value of the element corresponding to the previous line plus the value of the element corresponding to the previous line 
                    nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1];
                }
            }
        }
        for (int[] num : nums) {
    
            for (int n : num) {
    
                System.out.print(n + "\t");
            }
            System.out.println();
        }
    }

Running results ：

1	
1	1	
1	2	1	
1	3	3	1	
1	4	6	4	1	
1	5	10	10	5	1	
1	6	15	20	15	6	1	
1	7	21	35	35	21	7	1
......	

Now we have the Yanghui triangle , Just according to the given k Value to get the array value of the corresponding row , Last code ：

	@Test
    public void test() {
    
        Scanner sc = new Scanner(System.in);
        System.out.println(" Please enter k value :");
        int k = sc.nextInt();
        //  because k Small is equal to 33, At most it needs to be calculated 33 That's ok 
        int[][] nums = new int[k][];
        //  For the first i That's ok , All of them have i Column 
        for (int i = 0; i < nums.length; ++i) {
    
            nums[i] = new int[i + 1];
        }
        for (int i = 0; i < nums.length; ++i) {
    
            for (int j = 0; j < nums[i].length; ++j) {
    
                if (j == 0 || j == i) {
    
                    //  The first and last elements of each line are 1
                    nums[i][j] = 1;
                } else {
    
                    //  For other locations , Its value is equal to the value of the element corresponding to the previous line plus the value of the element corresponding to the previous line 
                    nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1];
                }
            }
        }
        //  obtain k Row data 
        int[] num = nums[k - 1];
        List<Integer> list = new ArrayList<>();
        for (int i : num) {
    
            list.add(i);
        }
        System.out.println(list);
        sc.close();
    }

Running results ：

 Please enter k value :
6
[1, 5, 10, 10, 5, 1]

because LeetCode There are input and output constraints in , So you still need to change the code ：

import java.util.Scanner;

class Solution {
    
    public List<Integer> getRow(int rowIndex) {
    
        int[][] nums = new int[rowIndex + 1][];
        //  For the first i That's ok , All of them have i Column 
        for (int i = 0; i < nums.length; ++i) {
    
            nums[i] = new int[i + 1];
        }
        for (int i = 0; i < nums.length; ++i) {
    
            for (int j = 0; j < nums[i].length; ++j) {
    
                if (j == 0 || j == i) {
    
                    //  The first and last elements of each line are 1
                    nums[i][j] = 1;
                } else {
    
                    //  For other locations , Its value is equal to the value of the element corresponding to the previous line plus the value of the element corresponding to the previous line 
                    nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1];
                }
            }
        }
        //  obtain k Row data 
        int[] num = nums[rowIndex];
        List<Integer> list = new ArrayList<>();
        for (int i : num) {
    
            list.add(i);
        }
        return list;
    }
}

It should be noted that , The third line of the title example turns out to be [1,3,3,1]：

Explain that it is from the first 0 Line starts to count , Pay attention to this detail , Finally, of course, the code passed the test ：

That's the end of the question , But the title still gives an advanced requirement ：

Advanced ： You can optimize your algorithm to O(k) The complexity of space ？

For the program just now , We can calculate the spatial complexity , For one k Array of rows , Its spatial complexity is (1 + k) * k / 2, It can be seen that the consumption of space is relatively large , So is there a way to reduce the space complexity to O(k), That is to say, only one device with a capacity of k Array to achieve this requirement ？

Imagine , For Yang Hui triangle data of a certain line , Its value should be the top element value plus the top left element value , therefore , We can store the data of each row in a one-dimensional array first , And then use it to find every line that follows , For example, seeking the second place 3 The element value of the row , So first you need to get the first line , There is only one element value in the first line 1：

For the second line , Its element value is 2 individual 1：

But clearly , We can't do this , Because it's going to cause every row that follows to fail to compute properly , A value should be placed at the beginning of each row except the first one 0 As occupancy

At this point, we just need to push the element value from right to left every time , For the last element of the second line , Its value is equal to the sum of the upper and upper left values , That's the index 0 And index 1 Add the values of the elements in position , obtain 1 Reassign to index 1：

Then calculate the number of 3 That's ok , The first 3 Yes 3 Element values , Add a value before calculating 0：

Right to left , The last element value is equal to the index 1 And index 2 Add the values of the elements in position , The result is 1：

The value of the penultimate element equals the index 0 And index 1 Add the values of the elements in position , The result is 2：

And then continue to add 0：

Continue to calculate in the same way , The last element value is equal to the index 3 And index 2 position （ In fact, the current position plus the left position ） The element value of , The result is 1：

Continue to solve ：

Go on to the left ：

It's a bit of a detour , But it's easy to understand , As for why to add 0 operation , We can get the answer from the structure of Yanghui triangle ：

For each row of element values , You need to know the element distribution of the previous line , First of all 0 Lines and the first element of each line don't need to be considered , The value must be 1, So we start at the end of each line , The calculation stops until the first element value , The values of the elements in these positions are equal to the values of the elements above and above left , such as ：

The first 1 OK, No 2 Elements 1 It should be from the top 0 And the top left 1 Add up to get , But because there's only one array now , So add 0 Is a must ,0 It acts as the upper element value of the last element , From this we get the law , For each element value , It is equal to the sum of the element value of the current position plus the element value of the previous position in the one-dimensional array .

Finally, we can get the code ：

class Solution {
    
    public static List<Integer> getRow(int rowIndex) {
    
        List<Integer> nums= new ArrayList<Integer>();
        nums.add(1);
        for (int i = 1; i <= rowIndex; ++i) {
    
            nums.add(0);
            for (int j = i; j > 0; --j) {
    
                nums.set(j, nums.get(j) + nums.get(j - 1));
            }
        }
        return nums;
    }
}

This reduces the space complexity to O(k).