“This is the fourth day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

  • Related articles

    LeetCode brush questions summary: LeetCode brush questions

    1. Title Description

    Yang Hui Triangle II

    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.

    • In front of the Yang Hui triangle one, today even brush to two, two words do not say, dish him!
    • Big fish brush – Yang Hui triangle one

    Second, train of thought analysis

    • Look at the examples in the title, let’s clarify the idea ~

    • Example 1:

      RowIndex = 3 output: [1,3,3,1]Copy the code

    • Example 2:

      RowIndex = 0 output: [1]Copy the code

    • Example 3:

    • Input: rowIndex = 1 Output: [1,1]Copy the code

    • 0 <= rowIndex <= 33

    • Advanced:

      • You can optimize your algorithm to*O*(*rowIndex*)Space complexity?

    • At first glance, it looks like there’s no difference. Don’t worry. Let’s get this straight

      • One is given a non-negative integernumRows.Before the formation of “Yang Hui triangle”numRowsLine.
      • The other is given a non-negative indexrowIndex, back to the first of the “Yang Fai Triangle”rowIndexLine.
      • So my first reaction is, given the first one, why don’t you get n plus 1 and be done with it?
      • Evaluate the substitution value on a list and participate in the next calculation to get the final row.

    AC code

    • Cyclic recording:

      Class Solution {public List<Integer> getRow(int rowIndex) {// Define List set List<Integer> List = new ArrayList<>(1); list.add(1); for (int i = 1; i < rowIndex + 1; I++) {// define a temporary storage collection List<Integer> newList = new ArrayList<>(); newList.add(1); for (int j = 0; j < list.size() - 1; J++) {/ / calculate accumulative amount newList. Add (list. Get (j) + list. Get (j + 1)); } newList.add(1); list = newList; } return list; }}Copy the code
      • Doesn’t seem to be a problem, does it?

    • I’m such a fool. Advanced is not for me. Old rules, learning the play of the great gods, research thoroughly is not my own thing? Wow ha ha ha

    • Official linear recursive solution:

      class Solution { public List<Integer> getRow(int rowIndex) { List<Integer> row = new ArrayList<Integer>(); row.add(1); for (int i = 1; i <= rowIndex; ++i) { row.add((int) ((long) row.get(i - 1) * (rowIndex - i + 1) / i)); } return row; }}Copy the code

      • Official explanation:

    • Given the index value, you can directly know the row number.

    • Then you can just loop through and get the current content.

    • Such as:

      • RowIndex = 3;

      • The far left and the far right have to be 1. So the starting value must be 1.

      • The first time through the loop you get

        • row.get(i - 1)= row.get(1-1)= 1
        • (rowIndex - i + 1) / i= 3 minus 1 plus 1 over 1= 3

      • The natural result of the second cycle is 3, 1.

      • So the combination is naturally the result we want!

The road ahead is long, I see no end, I will search high and low

If you think I bloggers write well! Writing is not easy, please like, follow, comment and give encouragement to the blogger ~ Hahah