LC Python 刷题笔记 有志者事竟成

加油！共勉！

# 206. Reverse Linked List

Complexity analysis

Time complexity : Assume that n is the list's length, the time complexity is O(n).

Space complexity : O(1).

1. def reverseList(self, head: ListNode) -> ListNode:
   
2.         
   
3.         prev_node = None #设之前节点为空
   
4.         curr_node = head #设当前节点等于链表头
   
5. 
   
6.         while curr_node : #当前节点如果为空则退出循环
   
7.             next_node = curr_node.next #下一个节点从当前节点下一位开始：2->3->4->5
   
8.             curr_node.next = prev_node #转换指针方向，转换前的输出：1->2->3->4->5，转换后当前节点的输出：1
   
9.             prev_node = curr_node #之前节点等于当前节点等于：1
   
10.             curr_node = next_node #当前节点等于下一个节点：2->3->4->5
    
11.             #由于指针反向，5次循环后退出，prev_node的值：5->4->3->2->1
    
12.    
    
13.         return prev_node #退出循环输出之前节点：5->4->3->2->1

复制代码

加油,欣赏你,不要怂就是干!!

算法第三计：Iteration 迭代：it is the repeat process.

算法第四计：Recursion 递归：it calls itself with smaller input values which obtains the result for the current input by applying simple operations to the returned value for the smaller input.


# 92 Reverse Linked List II

Iterative Link Reversa - Complexity Analysis

Time Complexity：Considering the list consists of N nodes, I process each of the nodes at most once, so it is O(N).

Space Complexity：Since I simply adjust some pointers in the original linked list and only use O(1) additional memory for achieving the final result.

基础概念：数字字符串反转
初等难度：全链表反转，数字字符串一部分反转
中等难度：链表的一部分反转，二叉树反转
高级难度：二叉树上某个树枝上的叶子反转

这是一道中等难度链表中一部分需要反转的题目，需要使用递归或者迭代去做。

1. '''
   
2. Reverse a linked list from position m to n. Do it in one-pass.
   
3. 
   
4. Note: 1 ≤ m ≤ n ≤ length of list.
   
5. 
   
6. Example:
   
7. 
   
8. Input: 1->2->3->4->5->NULL, m = 2, n = 4
   
9. Output: 1->4->3->2->5->NULL
   
10. '''
    
11. 
    
12. def reverseBetween(self, head, m, n):
    
13.     if not head: return None
    
14.     current, prev = head, None
    
15.         
    
16.     while m > 1:
    
17.         prev = current
    
18.         current = current.next
    
19.         m, n = m - 1, n - 1
    
20.     end, start = current, prev
    
21.         
    
22.     while n:
    
23.         first = current.next
    
24.         current.next = prev
    
25.         prev = current
    
26.         current = first
    
27.         n -= 1
    
28.             
    
29.     if start: start.next = prev
    
30.     else: head = prev
    
31.     end.next = current
    
32.     return head

复制代码

passionlk 发表于 2020-7-31 22:36
加油,欣赏你,不要怂就是干!!

对，不BB，干就完了

递归：是重复调用函数自身实现循环。

迭代：是函数内某段代码实现循环。

普通循环：循环代码中参与运算的变量同时是保存结果的变量，当前保存的结果作为下一次循环计算的初始值。

下面这几道题，我都是用Recursion递归构建子函数去做的，和LC的标准方法不一样。

# 38. Count and Say

1. def countAndSay(self, n):
   
2.         if n == 1: return '1'
   
3.         if n == 2: return '11'
   
4.         s = '11'
   
5.         for i in range(2,n):
   
6.             s = helper(s)
   
7.         return s
   
8.    
   
9. def helper(s):
   
10.     a = s[0]
    
11.     for i in range(1,len(s)):
    
12.         if s[i] != s[i-1]:
    
13.             a = a + ',' + str(s[i])
    
14.         else:
    
15.             a = a + str(s[i])
    
16.     b = a.split(',')
    
17.     s = ''
    
18.     for j in range(len(b)):
    
19.         s = s + str(b[j].count(b[j][0])) + b[j][0]
    
20.     return s

复制代码

[/i][/i][/i]

118. Pascal's Triangle 和 38. Count and Say，这类题都是一样的，凡是下一步操作需要基于上一步结果的问题，都可以考虑用子函数。


# 118 Pascal's Triangle

1. '''
   
2. Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.
   
3. 
   
4. Example:
   
5. 
   
6. Input: 5
   
7. Output:
   
8. [
   
9.      [1],
   
10.     [1,1],
    
11.    [1,2,1],
    
12.   [1,3,3,1],
    
13. [1,4,6,4,1]
    
14. ]
    
15. '''
    
16. 
    
17. def generate(self, numRows: int) -> List[List[int]]:
    
18.     if numRows == 0: return []
    
19.     if numRows == 1: return [[1]]
    
20.     if numRows == 2: return [[1],[1,1]]
    
21.     n = [1,1]
    
22.     s = [[1],[1,1]]
    
23.     for j in range(2,numRows):
    
24.         n = helper(n)
    
25.         s.append(n)
    
26.     return s
    
27.    
    
28. def helper(n):
    
29.     m = [0] * (len(n) + 1)
    
30.     m[0] = n[0]
    
31.     m[-1] = n[-1]
    
32.     for i in range(1,len(m)-1):
    
33.         m[i] = n[i-1] + n[i]
    
34.     return m

复制代码

# 119 Pascal's Triangle II

1. '''
   
2. Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal's triangle.
   
3. 
   
4. Note that the row index starts from 0.
   
5. 
   
6. 
   
7. In Pascal's triangle, each number is the sum of the two numbers directly above it.
   
8. 
   
9. Example:
   
10. 
    
11. Input: 3
    
12. Output: [1,3,3,1]
    
13. '''
    
14. 
    
15. def getRow(self, rowIndex: int) -> List[int]:
    
16.     if rowIndex == 0: return [1]
    
17.     if rowIndex == 1: return [1,1]
    
18.     n = [1,1]
    
19.     for j in range(1,rowIndex):
    
20.         n = helper(n)
    
21.     return n
    
22.    
    
23. def helper(n):
    
24.     m = [0] * (len(n) + 1)
    
25.     m[0] = n[0]
    
26.     m[-1] = n[-1]
    
27.     for i in range(1,len(m)-1):
    
28.         m[i] = n[i-1] + n[i]
    
29.     return m

复制代码

哈哈 楼主加油！

二叉树的基础操作和概念

Binary Tree

Binary Search Tree: A Binary Search Tree or "ordered binary tree" is a type of binary tree where the nodes are arranged in order. For each node, all elements in its left sub-tree are less to the node, and all the elements in its right sub-tree are greater than the node.

最基础的操作：二叉树遍历

# 270 Closest Binary Search Tree Value

把二叉树上所有的值遍历一次，找出和目标值最接近的数值。

1. '''
   
2. Given a non-empty binary search tree and a target value, find the value in the BST that is closest to the target.
   
3. 
   
4. Note:
   
5. 
   
6. Given target value is a floating point.
   
7. You are guaranteed to have only one unique value in the BST that is closest to the target.
   
8. Example:
   
9. 
   
10. Input: root = [4,2,5,1,3], target = 3.714286
    
11. 
    
12.     4
    
13.    / \
    
14.   2   5
    
15. / \
    
16. 1   3
    
17. 
    
18. Output: 4
    
19. '''
    
20. 
    
21. def closestValue(self, root: TreeNode, target: float) -> int:
    
22.     if not root : return []
    
23.     result = []  
    
24.     current = []
    
25.     current.append(root)
    
26.     while current :
    
27.         next_level = []
    
28.         for n in current :
    
29.             m1 = abs(target - n.val)
    
30.             result.append([m1,n.val])
    
31.             if n.left :
    
32.                 next_level.append(n.left)
    
33.             if n.right :
    
34.                 next_level.append(n.right)
    
35.             current = next_level
    
36.         result.sort()
    
37.     return result[0][1]

复制代码