This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 119. Yang Hui Triangle II on LeetCode.

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]Copy the code

Advanced:

  • Can you optimize your algorithm to O(k) space complexity?

Naive DP solution

A naive approach is to simulate the given information.

Code:

class Solution {
    public List<Integer> getRow(int idx) {
        int[][] f = new int[idx + 1][idx + 1];
        f[0] [0] = 1;
        for (int i = 1; i < idx + 1; i++) {
            for (int j = 0; j < i + 1; j++) {
                f[i][j] = f[i - 1][j];
                if (j - 1> =0) f[i][j] += f[i - 1][j - 1];
                if (f[i][j] == 0) f[i][j] = 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < idx + 1; i++) ans.add(f[idx][i]);
        returnans; }}Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n2)O(n^2)O(n2)

Scroll to the array

The scrollarray optimization is very mechanical, simply changing the scrolldimension from I to I % 2 or I & 1.

I & 1 is more stable than I % 2 on machines with different architectures

class Solution {
    public List<Integer> getRow(int idx) {
        int[][] f = new int[2][idx + 1];
        f[0] [0] = 1;
        for (int i = 1; i < idx + 1; i++) {
            for (int j = 0; j < i + 1; j++) {
                f[i & 1][j] = f[(i - 1) & 1][j];
                if (j - 1> =0) f[i & 1][j] += f[(i - 1) & 1][j - 1];
                if (f[i & 1][j] == 0) f[i & 1][j] = 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < idx + 1; i++) ans.add(f[idx & 1][i]);
        returnans; }}Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n)O(n)O(n)

Dimension elimination DP solution

Only the update of row I depends only on row i-1, so the dimension of the row can be eliminated directly:

class Solution {
    public List<Integer> getRow(int idx) {
        int[] f = new int[idx + 1];
        f[0] = 1;
        for (int i = 1; i < idx + 1; i++) {
            for (int j = i; j >= 0; j--) {
                if (j - 1> =0) f[j] += f[j - 1];
                if (f[j] == 0) f[j] = 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = 0; i < idx + 1; i++) ans.add(f[i]);
        returnans; }}Copy the code
  • O(n2)O(n^2)O(n2)
  • Space complexity: O(n)O(n)O(n)

other

The same technique I introduced to you in 978. Longest turbulent subarrays is recommended for review.

The last

This is No.119 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01, and there are 1916 topics on LeetCode by the start date.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.