“This article has participated in the call for good writing activities, click to view: the back end, the big front end double track submission, 20,000 yuan prize pool waiting for you to challenge!”
Get straight to the point:
Given a nonnegative index k, where k ≤ 33, return the KTH row of the Yang Hui triangle. In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right. Example: input: 3 output: [1,3,3,1]
Given a nonnegative index k, ask to get the k row in the Yang Hui triangle, Yang Hui triangle believe everyone is familiar with it, don’t understand the students to baidu to make up the course.
For this problem, because the value range of index K is given, we can first solve the 33 rows of Yang Hui triangle and store them in a two-dimensional array, and then return the corresponding row of data according to the specific value of K. So how do you write the code? Let’s analyze it first:
It’s easy to see how this works. First, row 1 has 1 value, row 2 has 2 values, row 3 has 3 values, and so on, row I has I values. Second, for each line, the first and last elements are 1, resulting in the following code:
@Test
public void test(a) {
// Since k is equal to 33, at most 33 rows need to be computed
int[][] nums = new int[32] [];// For row I, there is column I
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 row are 1
nums[i][j] = 1; }}}for (int[] num : nums) {
for (int n : num) {
System.out.print(n + "\t"); } System.out.println(); }}Copy the codeRunning 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.Copy the codeNow the key is how do we evaluate the values of these elements at zero? A careful observation of the structure of Yang Hui Triangle also reveals this rule:
These values are obtained by adding the value of the previous element in the corresponding row to the value of the previous element in the row. For example, 6 in the fifth row is obtained by adding the value of the previous element in the corresponding row 3 to the value of the previous element in the row 3.
@Test
public void test(a) {
// Since k is equal to 33, at most 33 rows need to be computed
int[][] nums = new int[32] [];// For row I, there is column I
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 row are 1
nums[i][j] = 1;
}else {
For other positions, the value is equal to the value of the element on the previous row plus the value of the element on the previous row
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(); }}Copy the codeRunning 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.Copy the codeNow that we have got Yang Hui’s triangle, we just need to get the corresponding array value according to the given k value. The last code is:
@Test
public void test(a) {
Scanner sc = new Scanner(System.in);
System.out.println("Please enter k value :");
int k = sc.nextInt();
// Since k is equal to 33, at most 33 rows need to be computed
int[][] nums = new int[k][];
// For row I, there is column I
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 row are 1
nums[i][j] = 1;
} else {
For other positions, the value is equal to the value of the element on the previous row plus the value of the element on the previous row
nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1]; }}}// Get k rows of data
int[] num = nums[k - 1];
List<Integer> list = new ArrayList<>();
for (int i : num) {
list.add(i);
}
System.out.println(list);
sc.close();
}
Copy the codeRunning results:
Please enter k value:6
[1.5.10.10.5.1]
Copy the codeBecause of the input/output constraints in LeetCode, we still need to modify the code:
import java.util.Scanner;
class Solution {
public List<Integer> getRow(int rowIndex) {
int[][] nums = new int[rowIndex + 1] [];// For row I, there is column I
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 row are 1
nums[i][j] = 1;
} else {
For other positions, the value is equal to the value of the element on the previous row plus the value of the element on the previous row
nums[i][j] = nums[i - 1][j] + nums[i - 1][j - 1]; }}}// Get k rows of data
int[] num = nums[rowIndex];
List<Integer> list = new ArrayList<>();
for (int i : num) {
list.add(i);
}
returnlist; }}Copy the codeNote that the third line of the problem example results in [1,3,3,1] :
It is calculated from line 0. Notice this detail, and of course the code passes the test:
This is the end of the problem, but the problem still gives a further requirement:
Advancements: Can you optimize your algorithm to O(k) space complexity?
For program just now, we can calculate the space complexity, for an array of k lines, its space complexity is (1 + k) / 2 * k, visible for space consumption is relatively large, so, is there a way to keep space complexity to O (k), which is only use a capacity for k array to achieve this requirement?
Imagine, for a row of Yang hui triangle data, its value should be above the element value add elements of the upper left, so we can to each line of data, first there is a one dimensional array, through it out again the next each line, such as 3 lines of element value, so the first thing you need to draw the first row, the first line of the element value is only a 1:
For the second line, its element value is two ones:
Obviously, we can’t do this, as this would cause each of the following lines to be incorrectly evaluated, and should place a value of 0 as a placeholder before calculating the start of each line except the first:
For the last element in the second row, its value is equal to the sum of the upper and upper left values, i.e. the sum of the elements at index 0 and 1, resulting in 1 and reassigned to index 1:
Then count line 3, which has three element values, adding a value 0 before counting:
From right to left, the last element is equal to the sum of the elements at index 1 and index 2, resulting in 1:
The penultimate element value is equal to the sum of the element values at index 0 and index 1, resulting in 2:
Then add another 0:
Continuing in the same way, the last element is equal to the value of the element at index 3 and index 2 (i.e. the current position plus the left position), yielding 1:
Continue solving:
Continue to the left:
Although this process is a bit convoluted, it is actually quite easy to understand. For why we need to add 0, we can get the answer from the construction of Yang Hui’s triangle:
Element values for each row, all need to know the element of the previous line distribution, the first 0 rows and each row of the first element to consider, the value is 1, so we from each line of the last, has been calculated to the first element value to stop, the position of the element value is above and left of all elements, such as:
First lines of the second element 1 should be made by above the 0 and 1 addition of left, but because now there is only one array, so add 0 is a must, above is the last element of the 0 as element values, the resulting rule, for each element value, it is equal to the current location in the one-dimensional array element value and the previous position of the element value combined.
The resulting 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)); }}returnnums; }}Copy the codeThis successfully reduces the space complexity to O(k).