This article is participating in “Java Theme Month – Java Swipe Card”, see the activity link for details

Topic describes

118. Given a non-negative integer numRows, generate the former numRows rows of the Yanghui triangle.

119. Given a non-negative index K where k ≤ 33, return row K of the Yanghui triangle.

Thought analysis

First of all, we will make a special treatment of Yang Hui triangle, as shown in the figure below:

After the processing shown in the figure, the elements of each row are treated as elements of an array, and the following conclusions can be drawn:

  1. The entries at 0 and k-1 on row k are always 1;
  2. The elements at position I (0< I

Based on the above conclusions, we can get the following code for 118.

Question 119 shows the data on line K +1, so only a simple adjustment is needed:

  1. K starts at 0
  2. You just return row k plus 1

From the above, the following is the first code of 119.

This scheme can be optimized. Every time a row of data is calculated, an array is needed to save it, so that the next row can be calculated based on the data in this row. We can consider performing in-situ operation in the same array, thus reducing the space complexity to O(1). Here if calculated from the front to rear, will lead to the result error for value is replaced, for example, according to the line 4 when calculating the value of the fifth line 2 position, because the value of the position 1 4 has been calculated and replace the fourth row 1 position 3, so will cause calculation errors, so consider here since after the forward calculation.

The optimized code is as follows: 119 second copy of the code.

The code shown

/ / 118
public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> ret = new ArrayList<>();
    // Special value handling
    if (numRows == 0)
        return ret;
    Integer[] nums = null;
    for (int k = 1; k <= numRows; k++) {
        // Record the contents of line k-1
        Integer[] lastNums = nums;
        // Initialize an array of k rows
        nums = new Integer[k];
        for (int j = 0; j < k; j++) {
            if (j == 0 || j == k - 1) {
                nums[j] = 1;
            } else {
                nums[j] = lastNums[j - 1] + lastNums[j];
            }
        }
        ret.add(new ArrayList<>(Arrays.asList(nums)));
    }
    return ret;
}
Copy the code
/ / 119
public List<Integer> getRow(int rowIndex) {
    Integer[] nums = null;
    for (int k = 0; k <= rowIndex; k++) {
        // Record the contents of line k-1
        Integer[] lastNums = nums;
        // Initialize an array of k rows
        nums = new Integer[k + 1];
        for (int j = 0; j < k + 1; j++) {
            if (j == 0 || j == k) {
                nums[j] = 1;
            } else {
                nums[j] = lastNums[j - 1] + lastNums[j]; }}}return Arrays.asList(nums);
}

/ / optimization
public List<Integer> getRow1(int rowIndex) {
    Integer[] nums = new Integer[rowIndex + 1];
    for (int k = 0; k <= rowIndex; k++) {
        for (int j = k; j >= 0; j--) {
            if (j == 0 || j == k) {
                nums[j] = 1;
            } else {
                nums[j] = nums[j - 1] + nums[j]; }}}return Arrays.asList(nums);
}
Copy the code

conclusion

Change your thinking, clarify your thinking, keep learning, and keep optimizing ^_^