Common Python Tricks in Leetcode
General
Patterns
- Arrays & Hashing
- Sliding Window & 2 pointers
- Subset level by level (BFS)
- Modified Binary Search (O(log(n))) / O(log(m * n))
- Top K elements (Heap)
- Linked List
Sliding Window and Two Pointers
1 | class Solution: |
Tree
- Recursive Solutions are often used.
Modified Binary Search
- Usually be aware of
pivot = low + 1
to check do you really need to move the pivot + 1 or - 1.
Usage
Try to use range all the time, less confusion
1 | prices = [1,2,3,4] |
Playing with strings
Sort and Reverse string
- You cannot sort a string or reverse a string using default functions (e.g.
reversed()
,.sort()
). - You can use
s[::-1]
to reverse the string.
Checking a char is not special character, we can use this .isalnum()
(built-in function). Otherwise you can leverage ascii code ord()
and char()
.
1 | def isPalindrome(self, s: str) -> bool: |
Sets
Sets cannot contain duplicate. Therefore we can simply check the length of list.
- Useful to check duplicates
List
enumerate
allows you to get the index and the item easily.
1 | for i, n in enumerate(nums): |
Dropping list in-place can do
1 | your_list = [1, 2, 3, 4, 5, 6, 7, 8, 9] |
Linked List
- Most questions are swapping questions.
Stack
List can be acted as a stack, using .pop()
to throw away the last value
Dict
your_dict.get(item, 0)
the 0 marks the default value if item is not found.
loop through dict is also easy
1 | def topKFrequent(self, nums: List[int], k: int) -> List[int]: |
defaultdict
defaultdict
streamline handling of missing keys by avoiding repetitive checks or KeyError handling.
1 | d = defaultdict(list) |
Moreover it can handle tuples, unlike dict()
1 | def groupAnagrams(self, strs: List[str]) -> List[List[str]]: |
English
- Anagram: means two strings contain same number of characters. Can be solved by comparing two dicts, or even single defaultdict (using the difference properties)
- Palindrome: means the inverted string would be the same. Can be solved by
s[::-1]
All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
Comment