Leetcode Notes
Merge Sorted Array
https://leetcode.com/problems/merge-sorted-array/
var merge = function(nums1, m, nums2, n) {
let nums = nums1.slice(0, m)
let i = 0
let j = 0
let k = 0
while (i < m || j < n) {
if (nums[i] < nums2[j] && i < m) {
nums1[k] = nums[i]
k++
i++
} else if (nums[i] > nums2[j] && j < n) {
nums1[k] = nums2[j]
k++
j++
} else if (i < m) {
nums1[k] = nums[i]
k++
i++
} else if (j < n) {
nums1[k] = nums2[j]
k++
j++
} else {
break
}
}
};
**405 ms 50.7 MB**
Median of Two Sorted Arrays
https://leetcode.com/problems/median-of-two-sorted-arrays/
var findMedianSortedArrays = function(nums1, nums2) {
let i = 0
let j = 0
let m = nums1.length
let n = nums2.length
let res = []
while (i < m || j < n) {
if (nums1[i] < nums2[j] && i < m) {
res.push(nums1[i])
i++
} else if (nums1[i] > nums2[j] && j < n) {
res.push(nums2[j])
j++
} else if (i < m) {
res.push(nums1[i])
i++
} else if (j < n) {
res.push(nums2[j])
j++
} else {
break
}
}
if (res.length % 2 == 0) {
let mid = res.length / 2
return (res[mid - 1] + res[mid]) / 2
} else {
return res[(res.length - 1) / 2]
}
};
**189 ms 46.8 MB**
Add Two Numbers II
https://leetcode.com/submissions/detail/845160511/
var addTwoNumbers = function(l1, l2) {
let s1 = []
let t1 = l1
while (t1) {
s1.push(t1.val)
t1 = t1.next
}
let s2 = []
let t2 = l2
while (t2) {
s2.push(t2.val)
t2 = t2.next
}
let j = null
let i = 0
while (s1.length > 0 || s2.length > 0) {
let sum = (s1.pop() || 0) + (s2.pop() || 0) + i
i = sum >= 10 ? 1 : 0
j = new ListNode(sum % 10, j)
}
if (i > 0) {
j = new ListNode(i, j)
}
return j
};
**185 ms 47.7 MB**
Warm Up
Reverse Words in a String III
var reverseWords = function(s) {
return s.split(' ').map((i) => i.split('').reverse().join('')).join(' ')
};
Reverse Linked List
var reverseList = function(head) {
let i = head
let j = null
while (i) {
j = new ListNode(i.val, j)
i = i.next
}
return j
};
Two Sum
var twoSum = function(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return [i, j]
}
}
}
};
Bitwise operators
371. Sum of Two Integers
https://leetcode.com/problems/sum-of-two-integers/description/
class Solution:
def getSum(self, a, b):
maximum = 0xffffffff
rev = False
if a >> 31 != 0 and b >> 31 != 0:
rev = True
while a & b != 0:
i = a
a = (a & b) << 1 & maximum
b = (i ^ b) & maximum
if rev:
return ~(a ^ b ^ maximum)
else:
return a ^ b
28 ms 12.8 MB
37. Single Number II
https://leetcode.com/problems/single-number-ii/description/
The Operators:
x « y
Returns x with the bits shifted to the left by y places (and new bits on the right-hand-side are zeros). This is the same as multiplying x by 2**y.
x » y
Returns x with the bits shifted to the right by y places. This is the same as //‘ing x by 2**y.
x & y
Does a “bitwise and”. Each bit of the output is 1 if the corresponding bit of x AND of y is 1, otherwise it’s 0.
x | y
Does a “bitwise or”. Each bit of the output is 0 if the corresponding bit of x AND of y is 0, otherwise it’s 1.
~ x
Returns the complement of x - the number you get by switching each 1 for a 0 and each 0 for a 1. This is the same as -x - 1.
x ^ y
Does a “bitwise exclusive or”. Each bit of the output is the same as the corresponding bit in x if that bit in y is 0, and it’s the complement of the bit in x if that bit in y is 1.
Just remember about that infinite series of 1 bits in a negative number, and these should all make sense.
Bitwise operators
191. Number of 1 Bits
https://leetcode.com/problems/number-of-1-bits/description/
class Solution:
def hammingWeight(self, n: int) -> int:
count, mask = 0, 0b1
for _ in range(32):
if n & mask != 0:
count += 1
mask <<= 1
return count
if __name__ == '__main__':
assert Solution().hammingWeight(0b00000000000000000000000000001011) == 3
32 ms 12.8 MB
136. Single Number
https://leetcode.com/problems/single-number/description/
class Solution:
def singleNumber(self, nums):
x = 0
for item in nums:
x = x ^ item
return x
if __name__ == '__main__':
assert Solution().singleNumber([4, 1, 2, 1, 2]) == 4
88 ms 15 MB
Alternative solutions:
class Solution:
def singleNumber(self, nums: List[int]) -> int:
import functools
return functools.reduce(lambda x, y: x ^ y, nums)
461. Hamming Distance
https://leetcode.com/problems/hamming-distance/
class Solution:
def hammingDistance(self, x, y):
raw, count, mask = x ^ y, 0, 1
for _ in range(32):
if raw & mask:
count += 1
mask <<= 1
return count
if __name__ == '__main__':
assert Solution().hammingDistance(1, 4) == 2
24 ms 12.8 MB
https://leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/646/
Strings
Implement strStr()
忘记用 Python 的 [x:y] 来一段段匹配了：
if haystack == needle or not needle:
return 0
for i, j in enumerate(haystack):
if i > len(haystack) - len(needle) + 1:
break
if needle and haystack[i] == needle[0]:
if i + len(needle) <= len(haystack):
notMatch = False
for l, m in enumerate(needle):
if haystack[i + l] != needle[l]:
notMatch = True
break
if not notMatch:
return i
return -1
Runtime: 44 ms, faster than 55.70% of Python3 online submissions for Implement strStr().
Memory Usage: 13.4 MB, less than 5.13% of Python3 online submissions for Implement strStr().
1. Two Sum
https://leetcode.com/problems/two-sum/
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
Runtime: 5424 ms, faster than 12.11% of Python3 online submissions for Two Sum.
Memory Usage: 13.6 MB, less than 42.31% of Python3 online submissions for Two Sum.
2. Add Two Numbers
https://leetcode.com/problems/add-two-numbers/
class Solution:
def addTwoNumbers(self, l1, l2):
head = None
last = None
while l1 is not None or l2 is not None:
i = (0 if l1 is None else l1.val) + (0 if l2 is None else l2.val)
if l1 is not None:
l1 = l1.next
if l2 is not None:
l2 = l2.next
if last is None:
head = ListNode(i)
last = head
else:
if last.next is None:
last.next = ListNode(i)
else:
last.next.val += i
last = last.next
if last.val >= 10:
last.val -= 10
last.next = ListNode(1)
return head
Runtime: 112 ms, faster than 61.12% of Python3 online submissions for Add Two Numbers.
Memory Usage: 13.4 MB, less than 5.21% of Python3 online submissions for Add Two Numbers.
3. Longest Substring Without Repeating Characters
https://leetcode.com/problems/longest-substring-without-repeating-characters/
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
count_max = 0
for i in range(len(s)):
k = []
count = 0
for j in range(i, len(s)):
if s[j] in k:
break
else:
k.append(s[j])
count += 1
if count > count_max:
count_max = count
return count_max
Runtime: 1796 ms, faster than 5.02% of Python3 online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 13.4 MB, less than 5.05% of Python3 online submissions for Longest Substring Without Repeating Characters.
https://leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/646/
Strings
First Unique Character in a String
暂不做优化，啥时候要炫技吓人再说：
count = {}
for i, j in enumerate(s):
if j in count:
count[j] += 1
else:
count[j] = 1
for i, j in enumerate(s):
if count[j] == 1:
return i
return -1
做完之后看到有别人用 set，find 和 rfind 来提高效率，以后可以参考。
Valid Anagram
我这个答案不说效率，应该是最精简的了：
return sorted(s) == sorted(t)
而且效率也不算很低：
Your runtime beats 31.55 % of python3 submissions.
顺便提交到了评论区，看看别人的看法：
Valid Palindrome
排除了字母和数字之外的数据之后，就好办了：
j = ''
for i in s:
if i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789':
j += i.lower()
k = j[::-1]
for i in range(0, len(j)):
if j[i] != k[i]:
return False
return True
做完之后看到有人用 ‘’.isalpha() 和 ‘’.isdigit() 两个函数，写起来可以更加精简。
String to Integer (atoi)
一点 Debug code in playground 之后，第一眼就看到了：
def myAtoi(self, str):
"""
:type str: str
:rtype: int
估计 leetcode 的题目 Python 基础代码是自动生成的，才会出现变量名和 Python 关键字冲突的情况。
这题的 cases 也太变态了吧 …
1024 / 1079 test cases passed. Input: “-5-” Output: 0 Expected: -5
我整个人都 -5- 了！
果然有人抱怨了：
1077 / 1079 test cases passed. Input: “-13+8” Output: 0 Expected: -13
简直了，这玩意是数字？！说好的 atoi 呢？问题是之前有个 case 是这样的呀？？
Input: “1-1” Expected: 0
这都 1000 多个 case 了，所以是大家开始互相伤害了吗？
过了，就这样吧：
s = s.strip().rstrip('+').rstrip('-')
found = False
found_num = False
found_sym = False
sections = 0
in_section = False
allowed = '0123456789-+'
symbol = ['-', '+']
symbols = 0
res = ''
last = None
for i in s:
if i not in allowed:
break
if i in allowed:
found = True
res += i
if i.isdigit():
if not in_section:
in_section = True
sections += 1
found_num = True
if in_section and not i.isdigit():
in_section = False
sections += 1
if i in symbol:
if last in symbol:
return 0
found_sym = True
symbols += 1
last = i
print(res, found, sections, symbols)
if sections - symbols == 1:
res = res.split('+')[0] # useless code
elif not res or not found or not found_num or sections > 2:
return 0
res = int(res.rstrip('-+'))
if res > (1 << 31) - 1:
res = (1 << 31) - 1
elif res < -1 << 31:
res = -1 << 31
return res
https://leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/646/
Array
Rotate Array
刚开始没仔细看题，就写了个 nums[-k:] + nums[:k]，后来发现题目中要求 do it in-place，并且要兼容各种 cases，最终写成
nums[:] = (nums[:-k][::-1] + nums[-k:][::-1])[::-1]
25 / 34 test cases passed.
卡在了 nums = [1,2]; k = 3，于是加上
k = k % len(nums)
终于 accepted 了
Strings
Reverse String
用 Python 写简单
s[::-1]
Reverse Integer
x = str(x)
y = -int(x.replace('-', '')[::-1]) if '-' in x else int(x[::-1])
return y if -1 << 31 <= y and y <= (1 << 31) - 1 else 0
这里用 2**31 或者 (1 « 31) - 1 都行
Best practise:
def reverse(self, x):
s = cmp(x, 0)
r = int(`s*x`[::-1])
return s*r * (r < 2**31)