Leetcode deduction topic summary (topic No.: 53, 3, 141, interview question 022, the entry node of the link in the sword finger offer chain, 20, 19, Niuke NC1, 103, 1143, Niuke 127)

​​​​​

1. LT53： The largest sum of successive subarrays

 

1. LT3： Longest substring without repeating characters

Recommend test cases ：

① s = "pwwkewp"

（ Be careful ： Scan second p When ,HashMap It already exists in p, however , This already exists p At this moment, I am not involved in the longest substring , It's just a legacy of history p）

②"aab"

（ Be careful ： Because the last element b Also included in the longest substring ）

1. LT141： Circular list

 

 

Ideas ：

1. If there are rings ： The speed pointer must be while Meet in

2.while Medium fast pointer null It must be because there is no ring , however , Without ring ,while Medium and fast pointer is not necessarily null

1. LT Interview questions 10.01： Merge sorted arrays

 

 

1. LT The finger of the sword offer022： The entry node of a link in a list

  Ideas ：

Step1： Speed pointer while（true） meet .

Step2： Slow pointer to head, Slow pointer one step, fast pointer one step , The encounter node is the entry node of the ring .

1. LT20： Valid parenthesis

key word ： Stack

Think carefully ：

① The stack may not be empty at the end （ There are left parentheses that are not matched ）

② Use i Traverse the whole parentheses that need to be matched .

③while There is only one mismatch in the loop , Just directly return false;

④while Every time you match a set of parentheses in the loop continue, At the same time continue Don't forget before i Traverse to ++;

1. LT19： Delete the last of the linked list n Nodes

key word ： Go ahead n Step

  Ideas ： Both the fast pointer and the slow pointer point to dummy node , Go ahead n Step （ Slow hands don't move ）. Fast pointer and slow pointer together, you step by step （ Until the fast pointer goes to the last node of the linked list ）, Now , The slow pointer points to the node in front of the deleted node , The fast pointer points to the end of the linked list , At this time, you only need to put the... Of the node pointed to by the slow pointer next Make changes ：slow.next = slow.next.next;

1. NC1： Add big numbers

key word ：StringBuilder

Be careful ：

①StringBuilder ②int change String use int + ""  ③char change int use char - '0'

④ character string s And string t Different length , therefore , When it's not long enough , By default, one of the addends is 0;

⑤ There may be a carry when the vertical addition is added to the end 1, So the code line49 Still check carry

1. LT103： Zigzag sequence traversal of binary tree

key word ： queue Queue Interface and implementation classes LinkedList, Traverse direction marks flag

Be careful ：

① Sequence traversal , There is a limit on the number of players who leave the team each time n = queue.size();

②//for The limit of the cycle is n, It can't be queue.size(), because for Add queue operation in , Elements in the queue increase , therefore queue.size() It is changing. .

1. LT： Longest common subsequence （ Sequences can be discontinuous ）

key word ： Dynamic programming int[][] dp = new int[m + 1][n + 1];

Ideas ： Draw dp matrix , Match from the upper left corner to the lower right corner .

situation ①：【i】==【j】 equal , So the maximum is 1 add （ No, 【i】&& No, 【j】 The maximum value in the case of ）

Corresponding ： dp[i + 1][j + 1] = 1 + dp[i][j];

situation ②： It's not equal , That explains. , No, 【i】 Or not 【j】 It's all right .

Corresponding ：dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);

// When they are not equal , Yes a no a One kind , Corresponding situation ：dp[i][j + 1], Yes b no b One kind , Corresponding situation ：dp[i + 1][j]

1. NC127: The longest public substring （ The string must be continuous without interruption ）

key word ： Dynamic programming int[][] dp = new int[m + 1][n + 1];

Ideas ：

dp【i】【j】 On behalf of i and j The longest common substring at the end , So when 【】！=【】 When , The longest common substring that ends with them is no , Length is 0, therefore if([i] != [j]) When , There will be dp[i + 1][j + 1] = 0;

When if([i] != [j]) When , There will be dp[i + 1][j + 1] = 1 + dp[i][j];