This is the first day of my participation in the Gwen Challenge in November. Check out the details: the last Gwen Challenge in 2021

📢 preface

🚀 Algorithm 🚀
  • 🌲 punch in an algorithm every day, which is not only a learning process, but also a sharing process 😜
  • 🌲 tip: the programming languages used in this column are C# and Java
  • 🌲 to maintain a state of learning every day, let us work together to become a god of algorithms 🧐!
  • 🌲 today is the 34th day 🎈!
🚀 Algorithm 🚀

🌲 Yanghui Triangle 2

Given a non-negative index rowIndex, return the rowIndex 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 1:

Enter: rowIndex =3Output:1.3.3.1]
Copy the code

Example 2:

Enter: rowIndex =0Output:1]
Copy the code

Example 3:

Enter: rowIndex =1Output:1.1]
Copy the code

Tip:

  • 0 <= rowIndex <= 33

🌻C# method: recursion

Thinking analytical

Use recursion, step by step

Code:

public class Solution {
    public IList<int> GetRow(int k) {
    if (k==0) return new List<int> {1};
    var t = GetRow(k - 1);
    var res = new int[k + 1];
    res[0] = 1;
    for (int i = 0; i < t.Count- 1; i++) res[i + 1] = t[i] + t[i + 1];
    res[^1] = 1;
    returnres; }}Copy the code

The execution result

By execution time:192Ms, in all C# beat 66.94% of users in submissionMemory consumption:25.8MB, in all CBeat 14.88% of users in # submissions
Copy the code

🌻Java Method 1: Recursion

Thinking analytical

Code:

class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> C = new ArrayList<List<Integer>>();
        for (int i = 0; i <= rowIndex; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(C.get(i - 1).get(j - 1) + C.get(i - 1).get(j));
                }
            }
            C.add(row);
        }
        returnC.get(rowIndex); }}Copy the code

The execution result

By execution time:2Ms, beat out all Java commits31.54% user memory consumption:36.1MB, beat out all Java commits54.46% of the userCopy the code

Complexity analysis

Time complexity: O(rowIndex^2) Space complexity: O(1 )
Copy the code

💬 summary

  • Today is the thirty-fourth day of clocking!
  • The article USES theC# andJavaTwo programming languages to solve the problem
  • Some methods are also written by the god of reference force buckle, and they are also shared while learning, thanks again to the algorithm masters
  • That’s the end of today’s algorithm sharing, see you tomorrow!