35. Search Insert Position
tags. Array
向有序列表里找到需要插入值的index，且You may assume no duplicates in the array.
Example 1:
1
2
|
Input: [1,3,5,6], 5
Output: 2
|
我的Solution：
1
2
3
4
5
6
|
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
for i in range(len(nums)):
if nums[i]>=target:
return i
return len(nums)
|
Runtime: 64 ms, faster than 22.39% of Python3 online submissions for Search Insert Position.
Memory Usage: 14.3 MB, less than 5.97% of Python3 online submissions for Search Insert Position.
这道题很简单，我给出的复杂度是O(N)，实际上还可以提升。
Solution来源: https://leetcode.com/problems/search-insert-position/discuss/15306/6-line-Python-solution-similar-to-34.Search-for-a-Range-44ms
使用binary search的方法使复杂度降至O(log(N))
1
2
3
4
5
6
7
|
def searchInsert(self, nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if target > nums[mid]: left = mid + 1
else: right = mid - 1
return left
|
Runtime: 56 ms, faster than 86.79% of Python3 online submissions for Search Insert Position.
Memory Usage: 14.2 MB, less than 5.97% of Python3 online submissions for Search Insert Position.
268. Missing Number
tag. math
列表长度为n，找到列表中从0到n里面少的那个数字。要求时间复杂度是O(N), 空间复杂度是O(1).
Example 1:
1
2
|
Input: [3,0,1]
Output: 2
|
我的解法：
1
2
3
4
|
class Solution:
def missingNumber(self, nums: List[int]) -> int:
total_sum = sum(range(len(nums)+1))
return total_sum - sum(nums)
|
Solution来源: https://leetcode.com/problems/missing-number/solution/
1
2
3
4
5
|
class Solution:
def missingNumber(self, nums):
expected_sum = len(nums)*(len(nums)+1)//2 #这里用高斯公式首项加末项乘以相数除以二的方法，相比sum函数，复杂度降低到O(1)
actual_sum = sum(nums) # 但是这里的复杂度还是O(N)
return expected_sum - actual_sum
|
方法二. Bit Manipulation
利用XOR抑或运算^
| Index |
0 |
1 |
2 |
3 |
| Value |
0 |
1 |
3 |
4 |
missing=4∧(0∧0)∧(1∧1)∧(2∧3)∧(3∧4)
=(4∧4)∧(0∧0)∧(1∧1)∧(3∧3)∧2
=0∧0∧0∧0∧2=2
1
2
3
4
5
6
|
class Solution:
def missingNumber(self, nums):
missing = len(nums)
for i, num in enumerate(nums):
missing ^= i ^ num
return missing
|
python中抑或的运算
原文链接：https://blog.csdn.net/xtj332/article/details/6639009
按位异或 ^
方法: 对位相加,特别要注意的是不进位.
举例：
2^5
解法:10^101=111,二进制111得到十进制的结果是7.
1^1
解法:1+1=0.(本来二进制1+1=10,但不能进位,所以结果是0)
-3^4
解法: -3的补码是11111101,4的补码是100 (也即00000100),11111101^00000100=11111101,补码11111101,转为原码是1000111,即十进制的-7.
XOR小结 ：两个相同的整数XOR的结果恒为0，0与任意整数N抑或的结果恒为N。
344. Reverse String
tag. String
反转字符数组，要求要inplace。
我的解法:
1
2
3
4
5
6
7
|
class Solution:
def reverseString(self, s: List[str]) -> None:
"""
Do not return anything, modify s in-place instead.
"""
for i in range(len(s)//2):
s[i],s[-i-1] = s[-i-1],s[i]
|
p.s. 一个仅适用于python的解法：return s[::-1]
19. Remove Nth Node From End of List
tag. linkedlist
Given a linked list, remove the n-th node from the end of list and return its head. 即去掉倒数第N个节点(Given n will always be valid.)
Example:
1
2
|
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
|
我的Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
#if head.next is None:
# return None
a,b = head,head
for _ in range(n):
b = b.next
if b is None: #去掉第一个节点
head = head.next
return head
while b.next is not None:
a = a.next
b = b.next
a.next = a.next.next
return head
|
101. Symmetric Tree
tag. tree
判断一个树是否对称。
1
2
3
4
5
|
1
/ \
2 2
/ \ / \
3 4 4 3
|
Solution来源: https://leetcode.com/problems/symmetric-tree/discuss/33050/Recursively-and-iteratively-solution-in-Python
Iterative解法
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def isSymmetric(self, root):
if not root: return True
stack = [(root.left, root.right)]
while stack:
cur = stack.pop()
l, r = cur[0], cur[1]
if not l and not r: continue
if not l and r or not r and l or l.val != r.val: return False
stack.append((l.right, r.left))
stack.append((l.left, r.right))
return True
|