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

年过30，饿不死，吃不饱，对于无背景无天赋的普通大陆华裔男性一代移民来说，如果想年薪30万+美金，读MBA可能性不大还费钱，抱领导粗腿可能性也不大，领导自己都没挣30万呢。

唯一的希望就是刷题进大厂，其他的真的看不到什么可行性。

你们泡妞，我刷题
你们电游，我刷题
你们钓鱼，我刷题
你们游行，我刷题
你们看片，我刷题

1800年代，华工在黑暗的矿坑里淘金
1900年代，华工在黑暗的厨房里刷碗
2000年代，华工在黑暗的小屋里做题

不怨天，不怨地，只怪我爸不努力，从我做起，扭转家庭的惯性下滑，徐徐图之，愚公移山。

从12万年薪到30万年薪，中间只隔着1000+道LC算法题。干TM的。

天真         

backtouzhaogong 发表于 2020-7-31 00:10
刷题有点动力挺好的，pregame pump talk细节不用深究，能激发斗志就行。
楼主能透露一下此番刷题的频率和 ...

没有频率，也没有顺序，就是平推，从#1 Two Sum开始，一直到最后的#1533        
Find the Index of the Large Integer。一边WFH，一边等待着机会。目前的工作已经干了6年多，闭着眼睛都知道怎么干。商科背景没学过CS，毕业就干SQL，现在是从SQL转算法coding。我记得一次面试的时候，面试官中国老哥问我会编程吗？我说会SQL，他说SQL不算编程，只是复杂一点的EXCEL。哈哈哈。莫欺少年穷，等着。

欣赏你“不要怂就是干”的态度，爱你

刷题有点动力挺好的，pregame pump talk细节不用深究，能激发斗志就行。
楼主能透露一下此番刷题的频率和顺序吗？

算法第一计：Brute Force 暴力搜索 - 字典法

简单直接，直接For Loop循环，构筑临时的dic{}存储过程中的变量。

Time complexity 时间复杂度 : Because, for each element, I try to find its complement by looping through the rest of array which takes O(n) time. Therefore, the time complexity is O(n^2).

Space complexity 空间复杂度：O(1)

# 1 Two Sum

直接上循环，把每次的值装入临时创建的字典，直到找到答案，最后返回。

1. '''
   
2. Given an array of integers, return indices of the two numbers such that they add up to a specific target.
   
3. 
   
4. You may assume that each input would have exactly one solution, and you may not use the same element twice.
   
5. 
   
6. Example:
   
7. 
   
8. Given nums = [2, 7, 11, 15], target = 9,
   
9. 
   
10. Because nums[0] + nums[1] = 2 + 7 = 9,
    
11. return [0, 1].
    
12. '''
    
13. 
    
14. nums = [2, 7, 11, 15]
    
15. target = 9
    
16. 
    
17. def twoSum(nums, target):
    
18.     dic = {}
    
19.     for i, num in enumerate(nums):
    
20.         n = target - num
    
21.         if n not in dic:
    
22.             dic[num] = i
    
23.         else:
    
24.             return [dic[n], i]
    
25. 
    
26. print(twoSum(nums,target))

复制代码

加油加油💪

李浩泉 发表于 2020-07-30 09:19:03
没有频率，也没有顺序，就是平推，从#1 Two Sum开始，一直到最后的#1533        
Find the Index of the Large Integer。一边WFH，一边等待着机会

我最近一直在刷SQL😂😂

算法第二计：Two Pointers 双指针 （包括：左右指针法，快慢指针法 - 弗洛伊德的乌龟（slow 指针）和兔子（fast 指针））

左右指针法：

# 167 Two Sum II - Input array is sorted
# 1099 Two Sum Less Than K

Complexity analysis

Time complexity : Each of the n elements is visited at most once, thus the time complexity is O(n).

Space complexity : I only use two indexes, the space complexity is O(1).

I can apply brute force directly to get O(n^2) time and O(1) space. But I do not make use of the property where the input array is sorted. 如果可以sorting的话，就可以考虑使用左右双指针来节约时间。这类题如果不用双指针，直接上两个嵌套的loop循环，面试一定会被challange。当使用左右指针法的时候，记得用while loop，不用再用for loop了。

1. '''
   
2. Given an array A of integers and integer K, return the maximum S such that there exists i < j with A[i] + A[j] = S and S < K. If no i, j exist satisfying this equation, return -1.
   
3. 
   
4. 
   
5. 
   
6. Example 1:
   
7. 
   
8. Input: A = [34,23,1,24,75,33,54,8], K = 60
   
9. Output: 58
   
10. Explanation:
    
11. We can use 34 and 24 to sum 58 which is less than 60.
    
12. '''
    
13. 
    
14. A = [34,23,1,24,75,33,54,8]
    
15. K = 60
    
16. 
    
17. def twoSumLessThanK(A, K):
    
18.     n = -1
    
19.     A.sort()
    
20.     left, right = 0, len(A) -1
    
21.     while left < right:
    
22.         if A[left] + A[right] < K:
    
23.             n = max(n, A[left] + A[right])
    
24.             left += 1
    
25.         else:
    
26.             right -= 1
    
27.     return n
    
28. 
    
29. print(twoSumLessThanK(A, K))

复制代码

[/i]

左右指针法：

# 167 Two Sum II - Input array is sorted

1. '''
   
2. Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
   
3. 
   
4. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.
   
5. 
   
6. Note:
   
7. 
   
8. Your returned answers (both index1 and index2) are not zero-based.
   
9. You may assume that each input would have exactly one solution and you may not use the same element twice.
   
10. Example:
    
11. 
    
12. Input: numbers = [2,7,11,15], target = 9
    
13. Output: [1,2]
    
14. Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
    
15. '''
    
16. 
    
17. numbers = [2,7,11,15]
    
18. target = 9
    
19. 
    
20. def twoSum(numbers,target):
    
21.     left = 0
    
22.     right = len(numbers) - 1
    
23.     while left < right:
    
24.         if numbers[left] + numbers[right] == target:
    
25.             return [left+1,right+1]
    
26.         elif numbers[left] + numbers[right] < target:
    
27.             left += 1
    
28.         elif numbers[left] + numbers[right] > target:
    
29.             right -= 1
    
30.                
    
31. print(twoSum(numbers,target))

复制代码

lz有群吗 ds转码+1

快慢指针法：

# 141. Linked List Cycle

这道题是有典故的，称为：弗洛伊德的乌龟（slow 指针）和兔子（fast 指针），和薛定谔的猫差不多一样有名。1960年代提出来的，距今差不多已经60年了。罗伯特·W·弗洛伊德，美国计算机科学家，1978年图灵奖得主，14岁高中毕业，芝加哥大学少年班，17岁大学毕业，26岁卡耐基梅隆大学计算机副教授，32岁斯坦福正教授，唯一的只有本科学历的教授！

Complexity analysis

Time complexity : Let me denote n as the total number of nodes in the linked list. To analyze its time complexity, I consider the following two cases separately.

• List has no cycle: The fast pointer reaches the end first and the run time depends on the list's length, which is O(n).
• List has a cycle: I break down the movement of the slow pointer into two steps, the non-cyclic part and the cyclic part, the worst case time complexity is O(N+K), which is O(n).
  

Space complexity : O(1). I only use two nodes (slow and fast) so the space complexity is O(1).

1. '''
   
2. 
   
3. Given a linked list, determine if it has a cycle in it.
   
4. 
   
5. To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
   
6. 
   
7. 
   
8. 
   
9. Example 1:
   
10. 
    
11. Input: head = [3,2,0,-4], pos = 1
    
12. Output: true
    
13. Explanation: There is a cycle in the linked list, where tail connects to the second node.
    
14. 
    
15. Input: head = [1], pos = -1
    
16. Output: false
    
17. Explanation: There is no cycle in the linked list.
    
18. 
    
19. '''
    
20. 
    
21. # Definition for singly-linked list.
    
22. # class ListNode:
    
23. #     def __init__(self, x):
    
24. #         self.val = x
    
25. #         self.next = None
    
26. 
    
27. class Solution:
    
28.     def hasCycle(self, head: ListNode) -> bool:
    
29.         slow = head
    
30.         fast = head
    
31.         while fast and fast.next :
    
32.             fast = fast.next.next
    
33.             slow = slow.next
    
34.             if slow == fast:
    
35.                 return True
    
36.         return False

复制代码

当然如果不用双指针，这道题也有其解法，比如：

1. # Definition for singly-linked list.
   
2. # class ListNode(object):
   
3. #     def __init__(self, x):
   
4. #         self.val = x
   
5. #         self.next = None
   
6. 
   
7. class Solution(object):
   
8.     def hasCycle(self, head):
   
9.         """
   
10.         :type head: ListNode
    
11.         :rtype: bool
    
12.         """
    
13.         while head:
    
14.             if head.val == 'I LOVE MEIZI':
    
15.                 return True
    
16.             else:
    
17.                 head.val = 'I LOVE MEIZI'
    
18.             head = head.next
    
19.         return False

复制代码