Leetcode-剑指Offer

左旋转字符串

1
2
def reverseLeftWords(s,n):
    return s[n:] + s[:n]

求1+2+…+n

1
2
3
4
5
6
res = 0
def sumNums(n):
    global res
    n > 1 and sumNums(n-1) # n=1 终止递归的需求，可通过短路效应实现
    res += n 
    return res

数组中重复的数字

1
2
3
4
5
6
7
def findRepeatNumber(nums):
    fre_dict={} # 使用字典
    for i in nums:
        fre_dict[i] = fre_dict.get(i,0)+1
        if fre_dict[i]>1:
            return i
    # 另一种思路 ，排序 找nums[i] == nums[i-1]

数组中数字出现的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def singleNumbers(nums): 
    tmp_res = 0     
    a,b = 0,0 
    for i in nums:
        tmp_res = tmp_res ^ i  # 假设需要的结果为为a和b 那么tmp_res = a^b  note: a^a = 0 
    # 将数组分成两部分 一部分只包含a  另一部分只包含b
    pivot = 1
    while tmp_res&pivot ==0:
        pivot = pivot<<1
    
    for i in nums:
        if i &pivot:
            a = a^i
        else:
            b = b^i
    return [a,b]

数组中数字出现的次数 II

1
2
3
4
5
6
7
8
9
10
11
12
13
def singleNumber(nums):
  # 1.数学 (sum(set(nums))*3-sum(nums))//2  2.字典思路 3. 位运算
  # a^a = 0  a^0 = a 位运算
    res = 0
    for i in range(32): # 1 <= nums[i] < 2^31限制
        idx = 1 << i  # 0001   0010   0010
        count = 0 
        for num in nums:
            if num & idx !=0:
                count+=1
        if count%3 ==1: # 表明唯一的那个数在这一位上为1
            res = res|idx
    return res

二叉树的深度

1
2
3
4
def maxDepth(root):
    if not root:return 0 # 递归出口
    return 1 + max(self.maxDepth(root.left),self.maxDepth(root.right))
# 非递归方法： BFS 获得层数即二叉树的深度

链表中倒数第k个节点

1
2
3
4
5
6
7
8
9
10
11
12
def getKthFromEnd(head, k):
    # 思路1: 遍历统计链表长度，倒是第k个节点便是顺数n-k个节点
    # 快慢指针思路
    slow,fast = head,head
    index = 0
    for _ in range(k): # 快指针先走k步
        if not fast: return None
        fast = fast.next
    while fast:
        slow = slow.next
        fast = fast.next
    return slow

二叉树的镜像

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def mirrorTree(root):
    if not root: return None # 递归出口
    root.left, root.right = self.mirrorTree(root.right),self.mirrorTree(root.left)
    return root
# 非递归方法： BFS 对每一层进行迭代 
from collections import deque 
def mirrorTree(root):
    if not root: return None 
    queue = deque()
    queue.append(root)
    while queue: # 对每一层的每一个节点进行遍历
        node = queue.popleft()
        tmp_left, tmp_right =node.left, node.right
        if tmp_left:
            queue.append(tmp_left)
            node.right = tmp_left
        else:
            node.right = None
        if tmp_right:
            queue.append(tmp_right)
            node.left = tmp_right  
        else:
            node.left = None              
    return root

打印从1到最大的n位数

1
2
def printNumbers(n):
    return [ i for i in range(1,10**n) ]

替换空格

1
2
def replaceSpace(self, s):
    return s.replace(' ','%20')

从尾到头打印链表

1
2
3
4
5
6
7
def reversePrint(head):
    res = []
    while head:
        res.append(head.val)
        head = head.next
    return res[::-1]    
# 递归解法 return reversePrint(head.next) + [head.val] if head else []

反转链表

1
2
3
4
5
6
7
8
9
def reverseList(head):
    if not head: return None
    cur,pre = head,None
    while cur:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp 
    return pre

二叉搜索树的第k大节点

1
2
3
4
5
6
7
8
9
10
11
12
13
def kthLargest(root, k):
    # 中序遍历 获得有序数组后返回第k个大的数字。 中序遍历： 左子树 + root + 右子树
    def traverse(root):
        if not root: return 
        res = []
        if root.left:
            res+=(traverse(root.left)) # 注意不能使用append  否则会形成一个嵌套列表 
        res.append(root.val)
        if root.right:
            res+=(traverse(root.right))
        return res
    res = traverse(root)
    return res[-k]

合并两个排序的链表####

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def mergeTwoLists(l1,l2):
    # 思路1: 新建一个链表，依次插入合适的节点
    cur = dummy = ListNode(0) 
    while l1 and l2:
        if l1.val < l2.val:
            cur.next, l1 = l1, l1.next
        else:
            cur.next, l2 = l2, l2.next
        cur = cur.next
    cur.next = l1 if l1 else l2
    return dummy.next

    # 思路2: 使用递归进行
    if not l1:return l2
    if not l2:return l1
    if l1.val <= l2.val:
        l1.next = self.mergeTwoLists(l1.next,l2)
        return l1
    else:
        l2.next = self.mergeTwoLists(l1,l2.next)
        return l2

二进制中1的个数

1
2
3
4
5
6
7
8
9
10
11
12
13
def hammingWeight(n):
    # 位运算 n&(n−1)  二进制数字n最右边的 1 变成 0 ，其余不变。
    res = 0
    while n:
        res += 1
        n &= n - 1
    return res
    # n&1 =1 => n 二进制 最右一位 为 1 ；n&1 = 0 => n 二进制 最右一位 为 0
    res = 0
    while n:
        res += n&1
        n = n>>1
    return res

用两个栈实现队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class CQueue:
    def __init__(self):
       self.A,self.B = [],[]
       # A 负责入队  B负责出队

    def appendTail(self, value):
        self.A.append(value)
    
    def deleteHead(self):
        if self.B: return self.B.pop()
        if not self.A: return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()

复杂链表的复制 ##待定

1
2
def copyRandomList(head):

二叉树的最近公共祖先##待定

和为s的连续正数序列

1
2
3
4
5
6
7
8
9
10
11
12
13
def findContinuousSequence(target):
    # 滑动窗口解决
    nums = list(range(1,(target//2+2))) # 候选的最大值不会超高target/2 +1
    res = []
    start_window,total = 0,nums[0]
    for end_window in range(1,len(nums)):
        total += nums[end_window]
        while total>=target:
            if total == target:  # 窗口和 = target =>当前窗口加入结果 窗口起点右移
                res.append(nums[start_window:end_window+1])
            total -= nums[start_window]
            start_window+=1
    return res

重建二叉树

1
2
3
4
5
6
7
8
9
10
11
def buildTree(preorder, inorder):
    if not preorder:
        return None 
    root = preorder[0]
    pos = inorder.index(root)

    binary_tree = TreeNode(root)
    binary_tree.left = self.buildTree(preorder[1:pos+1],inorder[:pos])
    binary_tree.right = self.buildTree(preorder[pos+1:],inorder[pos+1:])
    return binary_tree

从上到下打印二叉树 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def levelOrder(root):
    from collections import deque
    if not root:return []
    queue = deque()
    queue.append(root)
    res = []
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
            res.append(node.val)
    return res

从上到下打印二叉树 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def levelOrder(root):
    # BFS 层序遍历 使用队列实现
    from collections import deque
    if not root: return []
    queue = deque()
    queue.append(root)
    res = []
    while queue:
        level_size = len(queue)
        cur_level = []
        for _ in range(level_size):
            node = queue.popleft()
            cur_level.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(cur_level)
    return res

礼物的最大价值

1
2
3
4
5
6
7
8
9
def maxValue(grid): 
    # 二维dp  grid[i][j] = max(grid[i][j - 1], grid[i - 1][j]) +  grid[i][j]
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if i == 0 and j == 0: continue
            if i == 0: grid[i][j] += grid[i][j - 1]
            elif j == 0: grid[i][j] += grid[i - 1][j]
            else: grid[i][j] += max(grid[i][j - 1], grid[i - 1][j])
    return grid[-1][-1]

数组中出现次数超过一半的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def majorityElement(nums):
    return sorted(nums)[len(nums)//2]  #  排序后取中间的数

    #Boyer-Moore 投票法 O(n)
    res = nums[0]
    cal = 1
    for i in nums[1:]:
        if cal ==0: 
            res = i
        if i == res:
            cal+=1
        else:
            cal-=1
    return res

和为s的两个数字

1
2
3
4
5
6
7
8
9
10
11
def twoSum(nums,target):  
    left, right = 0,len(nums)-1 # 使用双指针 空间复杂度O(1)
    while left<right:
        sums = nums[left]+nums[right]
        if sums<target:
            left+=1
        elif sums>target:
            right-=1
        else:
            return [nums[left],nums[right]]
    return []

丑数

1
2
3
4
5
6
7
8
9
10
def nthUglyNumber(n):
    # 带条件的动态规划
    dp, a, b, c = [1] * n, 0, 0, 0
    for i in range(1, n):
        n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
        dp[i] = min(n2, n3, n5)
        if dp[i] == n2: a += 1
        if dp[i] == n3: b += 1
        if dp[i] == n5: c += 1
    return dp[-1]

调整数组顺序使奇数位于偶数前面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def exchange(self, nums: List[int]) -> List[int]:
    left,right = 0,len(nums)-1
    while left<right:
    # 保证nums[left]奇数,nums[right]为偶数
        if nums[left]%2==1:  
            left+=1
        else:
            if nums[right]%2 ==1:
                nums[left],nums[right]=nums[right],nums[left]
                left+=1
                right-=1
            else:
                right-=1
    return nums

股票的最大利润

1
2
3
4
5
6
7
8
9
10
11
def maxProfit(prices):
    # opt[i] = max(opt[i-1],prices[i]-min(prices[:i])) 动态规划转移方程
    if not prices: return 0
    min_price = prices[0] # 存储当天前最低的股票
    opt = [0]*len(prices)
    for i in range(1,len(prices)):
        if prices[i]<min_price:
            min_price = prices[i]
        opt[i] = max(opt[i-1],prices[i]-min_price)
    
    return opt[-1]

圆圈中最后剩下的数字

1

把字符串转换成整数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def strToInt(self, str: str) -> int:
    sign,res = 1,0
    str = str.strip()
    
    # 情况1: 字符串只有空格
    if not str: return 0 
    # 首先判断第一个字符
    if str[0] == '-' : sign = -1
    elif str[0] == '+': sign = 1
    elif '0'<=str[0]<='9':res = res*10 + int(str[0])
    else: return res 

    for i in str[1:]:
        if '0'<=i<='9':
            res = res*10 + ord(i) - ord('0')
        else:
            break
    if sign> 0:
        return res if res < 2**31-1 else 2**31-1
    else:
        return res*sign if res*sign > -2**31 else  -2**31

数值的整数次方

1
2
3
4
5
6
7
8
def myPow(self, x: float, n: int) -> float:
    ### 分治思想
    if n == 0: return 1 # base 
    if n<0 : x,n = 1/x,-n  
    if n %2 == 0:
        return self.myPow(x,n//2)**2
    else:
        return x * self.myPow(x,n//2)**2

数字序列中某一位的数字

0～n-1中缺失的数字

1
2
3
4
5
6
7
8
def missingNumber(self, nums: List[int]) -> int:
    for i in range(len(nums)):
        if nums[i] != i:
            return i
    return len(nums) # 类似 [0]这样的情况，缺失的为1

    # 思路2: 排序数组中的搜索问题，首先想到"二分"解决。
    xxx
Algorithm
Leetcode Python

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！