Small knowledge, big challenge! This paper is participating in theEssentials for programmers”Creative activities

📢 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 force button algorithm continued to punch card 33 days 🎈!
🚀 Algorithm 🚀

🌲 : Yang Hui triangle

Given a non-negative integer numRows, generate the former numRows 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: numRows =5Output: [[1], [1.1], [1.2.1], [1.3.3.1], [1.4.6.4.1]]
Copy the code

Example 2:

Enter: numRows =1Output: [[1]]
Copy the code

Tip:

  • 1 <= numRows <= 30

🌻C# method: dynamic programming

Thinking analytical

Using dynamic programming

Based on the graphic example given in the title, we need to define a Jagged array with the same length as numRows.

By observing the legend, it is not difficult to see that for two dimensional access variables like I and j, when j=0 or j= I, the target value is 1. Otherwise, the target value is dp[I][j] = dp[i-1][J-1] + DP [i-1][j].

Code:

public class Solution {
    public IList<IList<int>> Generate(int numRows) {
        int[][] dp =new int[numRows][];
        for(int i = 0; i<numRows; i++) { dp[i] =new int[i+1];
            for(int j = 0; j<=i; j++) {if(j==0 || j ==i)
                {
                    dp[i][j] = 1;
                }
                else
                {
                    dp[i][j] = dp[i- 1][j- 1] + dp[i- 1][j];
                }
            }
        }

        IList<IList<int>> p = new List<IList<int> > ();for(int i = 1; i<= numRows; i++) {var list = dp[i- 1].ToList();
            p.Add(list);
        }
        
        returnp; }}Copy the code

The execution result

By execution time:212Ms, in all CBeat 31.47% of users in # commitMemory consumption:25.9MB, in all CBeat 52.99% of users in # commit
Copy the code

🌻Java method 1: mathematics

Thinking analytical

Code:

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++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(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        returnret; }}Copy the code

The execution result

By execution time:0Ms, beat out all Java commits100.00% user memory consumption:36.3MB, beat out all Java commits38.54% of the userCopy the code

Complexity analysis

Time complexity: O(n^2) where n is the length of the array. Each number is accessed only once. Space complexity: O(n), where n is the length of the array. The spatial complexity does not consider the return value, so the spatial complexity depends primarily on the depth of the recursive stack, which is O(logn).Copy the code

💬 summary

  • Today is the thirty-third 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!