• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号
登陆 注册
描述文字

qiyuangong/leetcode: Python & JAVA Solutions for Leetcode

原作者: [db:作者] 来自: 网络 收藏 邀请

开源软件名称：

qiyuangong/leetcode

开源软件地址：

https://github.com/qiyuangong/leetcode

开源编程语言：

Python 77.0%

开源软件介绍：

Python & JAVA Solutions for Leetcode (inspired by haoel's leetcode)

Remember solutions are only solutions to given problems. If you want full study checklist for code & whiteboard interview, please turn to jwasham's coding-interview-university.

Also, there are open source implementations for basic data structs and algorithms, such as Algorithms in Python and Algorithms in Java.

I'm currently working on Analytics-Zoo - an unified Data Analytics and AI platform. Check it out, if you are interested in big data and deep learning.

Problems & Solutions

Python and Java full list. ♥ means you need a subscription.

# Title Solution Basic idea (One line)
1 Two Sum Python Java 1. Hash O(n) and O(n) space.
2. Sort and search with two points O(n) and O(1) space.
2 Add Two Numbers Python Java Take care of the carry from lower digit.
3 Longest Substring Without Repeating Characters Python Java 1. Check every possible substring O(n^2)
2. Remember the character index and current check pos, if character index >= current pos, then there is duplicate
4 Median of Two Sorted Arrays Python Java 1. Merge two sorted lists and compute median, O(m + n) and O(m + n)
2. An extension of median of two sorted arrays of equal size problem
5 Longest Palindromic Substring Python Java Background knowledge
1. DP if s[i]==s[j] and P[i+1, j-1] then P[i,j]
2. A palindrome can be expanded from its center
3. Manacher algorithm
7 Reverse Integer Python Java Overflow when the result is greater than 2147483647 or less than -2147483648.
8 String to Integer (atoi) Python Java Overflow, Space, and negative number
9 Palindrome Number Python Java Get the len and check left and right with 10^len, 10
11 Container With Most Water Python Java 1. Brute Force, O(n^2) and O(1)
2. Two points, O(n) and O(1)
12 Integer to Roman Python Java Background knowledge Just like 10-digit number, divide and minus
13 Roman to Integer Python Add all curr, if curr > prev, then need to subtract 2 * prev
15 3Sum Python 1. Sort and O(n^2) search with three points
2. Multiple Two Sum (Problem 1)
16 3Sum Closest Python Sort and Multiple Two Sum check abs
18 4Sum Python The same as 3Sum, but we can merge pairs with the same sum
19 Remove Nth Node From End of List Python Java 1. Go through list and get length, then remove length-n, O(n) and O(n)
2. Two pointers, first pointer goes to n position, then move both pointers until reach tail, O(n) and O(n)
20 Valid Parentheses Python 1. Stack
2. Replace all parentheses with '', if empty then True
21 Merge Two Sorted Lists Python Add a dummy head, then merge two sorted list in O(m+n)
23 Merge k Sorted Lists Python 1. Priority queue O(nk log k)
2. Binary merge O(nk log k)
24 Swap Nodes in Pairs Python Add a dummy and store the prev
28 Implement strStr() Python 1. O(nm) comparison
2. KMP
35 Search Insert Position Python Binary Search
46 Permutations Python 1. Python itertools.permutations
2. DFS with swapping, O(n^2) and O(n^2)
3. iteratively generate n-permutations with (n-1)-permutations, O(n^3) and O(n^2)
47 Permutations II Python 1. DFS with swapping, check duplicate, O(n^2) and O(n^2)
2. iteratively generate n-permutations with (n-1)-permutations, O(n^3) and O(n^2)
53 Maximum Subarray Python 1. Recursion, O(nlgn), O(lgn)
2. Bottom-up DP, O(n) and O(n)
3. Bottom-up DP, f(x) = max(f(x-1)+A[x], A[x]), f(x) = max(f(x-1)+A[x], A[x]),O(n) and O(1)
54 Spiral Matrix Python O(nm) 1. Turn in the corner and loop
2. (0, 1) -> (1, 0) -> (0, -1) -> (-1, 0)
62 Unique Paths Python 1. Bottom-up DP, dp[i][j] = dmap[i-1][j] + dmap[i][j-1], O(mn) and O(mn)
2. Combination (m+n-2, m-1)
63 Unique Paths II Python Bottom-up DP, dp[i][j] = dmap[i-1][j] + dmap[i][j-1] (if block, then 0), O(mn) and O(mn)
65 Valid Number Python 1. strip leading and tailing space, then check float using exception, check e using split
2. check is number split by . or e, note that number after e may be negative
66 Plus One Python Check if current digit == 9.
70 Climbing Stairs Python Bottom-up DP, dp[i] = dp[i - 2] + dp[i- 1]
1. O(n) and O(n)
2. Only two variables are needed, O(n) and O(1)
72 Edit Distance Python Background
1. DP O(n^2) space
2. DP O(n) space
78 Subsets Python 1. DFS Recursion, O(2^n) and O(2^n)
2. Recursion on a binary number, O(2^n) and O(2^n)
3. Sort and iteratively generate n subset with n-1 subset, O(n^2) and O(2^n)
90 Subsets II Python 1. DFS Recursion with duplicate check, O(2^n) and O(2^n)
2. Recursion on a binary number, O(2^n) and O(2^n)
3. Sort and iteratively generate n subset with n-1 subset, note that if nums[index] == nums[index - 1] then generate from last end to curr end, O(n^2) and O(2^n)
94 Binary Tree Inorder Traversal Python 1. Recursion, O(n) and O(1)
2. Stack and check isinstance(curr, TreeNode), O(n) and O(n)
3. Stack and check left and right, O(n) and O(n)
98 Validate Binary Search Tree Python 1. Stack O(n) and O(n)
2. Recursion O(n) and O(n)
104 Maximum Depth of Binary Tree Python Recursion max(left, right) + 1
108 Convert Sorted Array to Binary Search Tree Python Recursion O(n) and O(nlgn)
109 Convert Sorted List to Binary Search Tree Python 1. Two points fast (next next) and slow (next) O(nlgn) and O(n)
2. Bottom-up recursion O(n) and O(lgn)
110 Balanced Binary Tree Python Recursion 1. Top-down O(n^2) and O(n), Bottom-up recursion with sentinel -1 O(n) and O(n)
111 Minimum Depth of Binary Tree Python 1. Recursion, note that when size of left (ld) or right (rd) is 0, then min = 1 + ld + rd
2. BFS check by level (right most), which is much faster than recursion
124 Binary Tree Maximum Path Sum Python Recursion O(n) and O(n), max (left + node, right + node, left + node + right)
125 Valid Palindrome Python Exclude non-alphanumeric characters and compare O(n)
128 Longest Consecutive Sequence Python Set or hash, pop adjacency, O(n) and O(n)
133 Clone Graph Python Hash and DFS or BFS
136 Single Number Python 1. Hash or set, O(n) and O(n)
2. xor O(n) and O(1)
137 Single Number II Python 1. ctypes 32 % 3 and &, O(n) and O(1)
2. ones, twos, threes as bitmask (e.g. ones represents ith bit had appeared once), O(n) and O(1)
138 Copy List with Random Pointer Python 1. Hash O(n) and O(n)
2. Modify original structure: Original->Copy->Original, then node.next.random = node.random.next, O(n) and O(1)
141 Linked List Cycle Python 1. Hash or set
2. Two points (fast and slow)
3. Add a max and check if reach the max
142 Linked List Cycle II Python Two points, a+b=nr
143 Reorder List Python 1. List as index to rebuild relation, O(n) and O(n)
2. Two points, O(n) and O(1)
144 Binary Tree Preorder Traversal Python 1. Recursion, O(n) and O(n)
2. Stack, O(n) and O(n)
145 Binary Tree Postorder Traversal Python 1. Recursion, O(n) and O(n)
2. Stack and queue (insert 0), O(n) and O(n)
3. Stack and isinstance(curr, TreeNode), O(n) and O(n)
146 LRU Cache Python 1. Queue and dict
2. OrderedDict
150 Evaluate Reverse Polish Notation Python Stack
151 Reverse Words in a String Python 1. Python split by space
2. Reverse all and reverse words
152 Maximum Product Subarray Python DP, f(k) = max(f(k-1) * A[k], A[k], g(k-1) * A[k]), g(k) = min(g(k-1) * A[k], A[k], f(k-1) * A[k]), O(n) and O(1)
153 Find Minimum in Rotated Sorted Array Python Binary search with conditions, A[l] > A[r]
154 Find Minimum in Rotated Sorted Array II Python Binary search with conditions, A[l] > A[r], A[l]=A[mid]=A[r]
155 Min Stack Python Java Add another stack for min stack, maintance this stack when the main stack pop or push: 1. Only push min, such that len(minStack)<=len(Stack) 2. Push min again when current top is min, such that len(minStack)=len(Stack)
156 Binary Tree Upside Down ♥ Python p.left = parent.right, parent.right = p.right, p.right = parent, parent = p.left, p = left
157 Read N Characters Given Read4 ♥ Python Handle the edge case (the end)
158 Read N Characters Given Read4 II - Call multiple times ♥ Python Store the pos and offset that is read by last read4
159 Longest Substring with At Most Two Distinct Characters ♥ Python Maintain a sliding window that always satisfies such condition
161 One Edit Distance ♥ Python 1. Check the different position and conditions
2. Edit distance
163 Missing Ranges ♥ Python Add -1 to lower for special case, then check if curr - prev >= 2
166 Fraction to Recurring Decimal Python % and Hash to find duplicate
167 Two Sum II - Input array is sorted Python Two points O(n) and O(1)
170 Two Sum III - Data structure design ♥ Python 1. Hash, O(1) for add, O(n) for find, O(n) space
2. sorted list, O(logn) for add, O(n) for find, O(n) space
3. Sort before find, O(1) for add, O(nlogn) for find, O(n) space
179 Largest Number Python Java Define a comparator with str(x) + str(y) > str(y) + str(x), O(nlgn) and O(n)
186 Reverse Words in a String II ♥ Python Reverse all and reverse each words
198 House Robber Python f(k) = max(f(k – 2) + num[k], f(k – 1)), O(n) and O(1)
200 Number of Islands Python 1. Quick union find, O(nlogn) and O(n^2)
2. BFS with marks, O(n^2) and O(1)
204 Count Primes Python Java CPP Sieve of Eratosthenes, O(nloglogn) and O(n)
206 Reverse Linked List Python Java CPP 1. Stack, O(n) and O(n)
2. Traverse on prev and curr, then curr.next = prev, O(n) and O(1)
3. Recursion, O(n) and O(1)
213 House Robber II Python f(k) = max(f(k – 2) + num[k], max(dp[0ls-2],dp[1ls-1], O(n) and O(1)
215 Kth Largest Element in an Array Python Java 1. Sort, O(n) and O(n)
2. Heap, O(nlgk) and O(n)
3. Quick selection, O(klgn) and O(n)
216 Combination Sum III Python Generate all combinations of length k and keep those that sum to n
217 Contains Duplicate Python 1. Set and compare length
2. Sort and check i,i +1
219 Contains Duplicate II Python 1. Brute force
2. Maintenance a set that contains previous k numbers, and check if curr in set
220 Contains Duplicate III Python 1. Sort and binary Search
2. Bucket sort
221 Maximal Square Python 1. Brute force
2. dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1, O(mn) and O(mn)
3. dp[j] = min([j], dp[j-1], prev) + 1, O(mn) and O(n)
223 Rectangle Area Python Java Rectangle A + B - common area, O(1) and O(1)
228 Summary Ranges Python Detect start and jump, O(n) and O(1)
236 Lowest Common Ancestor of a Binary Tree Python Java 1. Recursive check left, val and right, LCA is the split paths in tree, O(n) and O(n)
2. Store parents during traversing tree, reverse check their lowest common parent, O(n) and O(n)
238 Product of Array Except Self Python Java The ans is [0,i -1] * [i+1, len- 1]. We can twice for left and right (reverse), O(n) and O(n)
243 Shortest Word Distance Python Update index1 and index2, and check distance, O(n) and O(1)
246 Strobogrammatic Number ♥ Python Hash table and reverse string, O(n) and O(n)
249 Group Shifted Strings ♥ Python Hash and generate hash code for each string, O(n) and O(n)
252 Meeting Rooms Python 1. Sort and compare intervals[i].end with intervals[i+1], O(nlogn) and O(1)
2. Sort and check intervals when count >= 2, O(nlogn) and O(n)
253 Meeting Rooms II ♥ Python Java 1. Priority queue and sort, O(nlogn) and O(n)
2. Go through timeline. If it's a start then meeting + 1, else meeting - 1. The ans is the max(meeting) in timeline. O(nlogn) and O(n)
259 3Sum Smaller Python 1. Reduce to two sum smaller, then binary search, O(n^2lgn) and O(1)
2. Reduce to two sum smaller, then two points, O(n^2) and O(1)
266 Palindrome Permutation ♥ Python Compute frequency, check number of odd occurrences <= 1 then palindrome, O(n) and O(n)
267 Palindrome Permutation II ♥ Python Check palindrome then generate half with Permutations II, O(n^2) and O(n^2)
268 Missing Number Python Java 1. Find missing by n * (n - 1)/2 - sum(nums)
2. XOR with index
3. Sort and binary search
270 Closest Binary Search Tree Value ♥ Python 1. Recursively brute force, O(n) and O(n)
2. Recursively compare root result with current kid's result (left or right), O(logn) and O(logn)
3. Iteratively compare root result with current kid's result (left or right), O(logn) and O(logn)
273 Integer to English Words Python Java Careful about corner cases, such 1-20 and 21-Hundred, O(lgn) and O(1)
274 H-Index Python Background
1. Sort and check number of papers greater than h, O(nlogn) and O(1)
2. Counting sort, O(n) and O(n)
276 Paint Fence ♥ Python ways[i>2] = (ways[i-1] + ways[i-2]) * (k - 1), O(n) and O(1)
280 Wiggle Sort ♥ Python 1. Sort and insert (n - 1) / 2 from tail to correct position, O(nlogn) and O(1)
2. Sort and swap(i, i + 1) from 1 to n - 1, O(nlogn)
3. Iteratively check order and reverse order, if not satisfied, then swap i with i + 1, O(n)
286 Walls and Gates Python BFS with queue, O(mn) and O(mn)
288 Unique Word Abbreviation ♥ Python hash
293 Flip Game ♥ Python Python string slicing
294 Flip Game II ♥ Python 1. Backtracking to ensure that next step is False, O(n!!) and O(n!!)
2. Backtracking with memo, O(n!!) and O(n!)
3. DP based on Sprague-Grundy Function
296 Best Meeting Point ♥ Python Think hard about Manhattan Distance in 1D case. Sort and find mean, O(mnlogmn) and O(1)
298 Binary Tree Longest Consecutive Sequence ♥ Python Bottom-up or top-down recursion, O(n) and O(n)
305 Number of Islands II Python Quick union find with weights, O(nlogn) and O(n)
322 Coin Change Python Bottom-up or top-down DP, dp[n] = min(dp[n], dp[n - v_i]), where v_i is the coin, O(amount * n) and O(amount)
336 Palindrome Pairs Python Java 1. Create a reverse word to index map, then for each word, check prefix and posfix, O(nk^2) and O(n)
2. Tire tree, O(nk^2) and O(n)
337 House Robber III Python 1. Recursion with hash map, O(n) and O(n)
2. Recursion on two steps, O(n) and O(1)
339 Nested List Weight Sum ♥ Python Depth-first recursion
340 Longest Substring with At Most K Distinct Characters ♥ Python Maintain a sliding window with at most k distinct characters and a count for this window. Note that the start position need a loop to update.
346 Moving Average from Data Stream ♥ Python fix-sized queue or dequeue, O(1) and O(n)
347 Top K Frequent Elements Python Java 1. Sort by frequency, O(nlogn) and O(n).
2. we can build a min heaq (based on frequency), then pop min until there are k element, O(klgn) and O(n)
351 Android Unlock Patterns ♥ Python Backtracking, O(n!) and O(n)
359 Logger Rate Limiter ♥ Python 1. hash which stores the latest timestamp, O(1) and O(n)
2. Using Priority queue to remove older logs, O(n) and O(n)
366 Find Leaves of Binary Tree ♥ Python 1. Set or hash to check leaft, O(n^2) and O(n)
2. Recursively check level and return them, O(n) and O(n)
367 Valid Perfect Square Python Java Integer square root
1. 1+3+…+(2n-1) = n^2
2. Binary search
3. Newton's method
368 Largest Divisible Subset Python Sort and generate x subset with previous results, O(n^2) and O(n^2)
369 Plus One Linked List ♥ Python 1. Stack or list that store the list, O(n) and O(n)
2. Two points, the first to the tail, the second to the latest place that is not 9, O(n) and O(1)
370 Range Addition ♥ Python Interval problem with cumulative sums, O(n + k) and O(n)
383 Ransom Note Python Java Get letter frequency (table or hash map) of magazine, then check randomNote frequency
384 Shuffle an Array Python Fisher–Yates shuffle, O(n) and O(n)
387 First Unique Character in a String Python Java Get frequency of each letter, return first letter with frequency 1, O(n) and O(1)
388 Longest Absolute File Path Python Store last length and rindex, O(n) and O(n)
389 Find the Difference Python Java 1. Imaging letter a as 0, then the sum(t)-sum(s) is the result
2. Based on solution 1, bit manipulate
400 Nth Digit Python Java islands * 4 - overlaps * 2
401 Binary Watch Python Java Note that 12 * 60 is much less than 2^n or n^2.
404 Sum of Left Leaves Python Java 1. Recursively DFS with root.left.left and root.left.right check
2. The same DFS based on stack
405 Convert a Number to Hexadecimal Python Java Two's complement 1. Bit manipulate, each time handle 4 digits
2. Python (hex) and Java API (toHexString & Integer.toHexString)
408 Valid Word Abbreviation ♥ Python Go over abbr and word, O(n) and O(1)
409 Longest Palindrome Python Java Length of Palindrome is always 2n or 2n + 1. So, get all possible 2*n, and choose a single one as 1 if it exists.
412 Fizz Buzz Python Java Cpp 1. From 1 to n, condition check
2. Condition check and string connect
414 Third Maximum Number Python Java 1. Keep max 1-3 then compare, O(n) and O(1)
2. PriorityQueue, O(n) and O(1)
415 Add Strings Python Java Two points, careful abour carry, O(n) and O(n)
416 Partition Equal Subset Sum Python DP, Check if sum of some elements can be half of total sum, O(total_sum / 2 * n) and O(total_sum / 2)
421 Maximum XOR of Two Numbers in an Array Python Check 0~32 prefix, check if there is x y in prefixes, where x ^ y = answer ^ 1, O(32n) and O(n)
422 Valid Word Square ♥ Python Compare row with column, O(n^2)
434 Number of Segments in a String Python Java 1. trim &split
2. Find segment in place
437 Path Sum III Python Java 1. Recursively travese the whole tree, O(n^2)
2. Cache sum in Hash based on solution 1. Note that if sum(A->B)=target, then sum(root->a)-sum(root-b)=target.
438 Find All Anagrams in a String Python Java Build a char count list with 26-256 length. Note that this list can be update when going through the string. O(n) and O(1)
443 String Compression Python Java Maintain curr, read, write and anchor (start of this char).
448 Find All Numbers Disappeared in an Array Python Java Value (1, n) and index (0, n-1). Mark every value postion as negative. Then, the remain index with positive values are result. O(n)
453 Number of Segments in a String Python Java Each move is equal to minus one element in array, so the answer is the sum of all elements after minus min.
458 Poor Pigs Python Java 2 pigs for 5 * 5 metric
461 Hamming Distance Python Java Hamming Distance is related to XOR for numbers. So, XOR then count 1. O(n)
463 Island Perimeter Python Java math, find the area, actual number, then find the digit
475 Heaters Python Java 1. Binary search hourse in heater array, O(nlogn) and O(1)
2. Two points, O(nlogn) and O(1)
479 Largest Palindrome Product

鲜花
握手
雷人
路过
鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
More+
上一篇：
idaSmilence/javaDesign发布时间：2022-06-22
下一篇：
square/retrofit: A type-safe HTTP client for Android and the JVM发布时间：2022-06-22
热门推荐
More+
热门话题
More+
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服（服务时间 9:00～18:00）

在线QQ客服
地址：深圳市南山区西丽大学城创智工业园
电邮：jeky_zhao#qq.com
移动电话：139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap