目录

每日Leetcode02

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