头像

cornerCao


访客:57199

离线:8天前



cornerCao
4个月前
class Solution(object):
    def numberOf1Between1AndN_Solution(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 0
        str_n = str(n)
        dp = [0 for _ in range(len(str_n) + 1)] # dp[i]表示0到i位数的1的个数
        dp[0] = 0 
        for i in range(1, len(str_n) + 1):
            dp[i] = 10 * dp[i-1] + 10 ** (i - 1)

        res = 0
        for i in range(len(str_n)):
            val = int(str_n[i])
            p = len(str_n) - i - 1
            res += dp[p] * val
            if val > 1:
                res += 10 ** p
            elif val == 1:
                if i + 1 < len(str_n):
                    res += int(str_n[i+1:]) + 1
                else:
                    res += 1
        return res



cornerCao
5个月前

题目描述

给你一个整数数组 nums,和一个表示限制的整数 limit,请你返回最长连续子数组的长度,该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit。

如果不存在满足条件的子数组,则返回 0。

样例

输入:nums = [8,2,4,7], limit = 4
输出:2 
解释:所有子数组如下:
[8] 最大绝对差 |8-8| = 0 <= 4
[8,2] 最大绝对差 |8-2| = 6 > 4
[8,2,4] 最大绝对差 |8-2| = 6 > 4
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4
[2] 最大绝对差 |2-2| = 0 <= 4
[2,4] 最大绝对差 |2-4| = 2 <= 4
[2,4,7] 最大绝对差 |2-7| = 5 > 4
[4] 最大绝对差 |4-4| = 0 <= 4
[4,7] 最大绝对差 |4-7| = 3 <= 4
[7] 最大绝对差 |7-7| = 0 <= 4
因此,满足题意的最长子数组的长度为 2。
输入:nums = [10,1,2,4,7,2], limit = 5
输出:4 
解释:满足题意的最长子数组是 [2,4,7,2],其最大绝对差 |2-7| = 5 <= 5。
输入:nums = [4,2,2,2,4,4,2,2], limit = 0
输出:3

算法

(滑动窗口 + 单调队列) $O(n)$

首先,看到连续子数组/子区间的问题,很容易就想到用滑动窗口来做,即维护l, r指针,指针内部形成满足题目要求的区间。

这题重点在于如何维护区间的最大值最小值。回忆经典的滑动窗口最大值问题,我们可以用两个单调队列分别维护这段区间的最大值和最小值,于是问题便迎刃而解。

每次移动r指针,同时维护单调队列。判断区间是否满足要求(即最大值 - 最小值 <= limit),不满足则移动l指针并维护两个单调队列直到满足要求。

时间复杂度

只需要遍历一遍数组,l, r指针均为单方向移动,复杂度为O(N).

Python 代码

from collections import deque
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        up = deque() # 单调上升队列,头为区间最小值
        down = deque() # 单调下降队列,头为区间最大值
        l = 0
        res = 0
        for r in range(len(nums)):
            while len(up) > 0 and nums[up[-1]] >= nums[r]: # 维护上升队列
                up.pop()
            # 注意队列里放的必须是下标而不是值,这样才能在移动左指针的时候更新队列
            up.append(r) 
            while len(down) > 0 and nums[down[-1]] <= nums[r]: # 维护下降队列
                down.pop()
            down.append(r)
            # 当发现条件不满足(即最大值-最小值>limit)时移动左指针
            while l < r and nums[down[0]] - nums[up[0]] > limit: 
                if l == down[0]:
                    down.popleft()
                if l == up[0]:
                    up.popleft()
                l += 1
            res = max(res, r - l + 1) # 更新结果
        return res



活动打卡代码 AcWing 62. 丑数

cornerCao
5个月前
import heapq
class Solution(object):
    def getUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        nums = [1]
        i, j, k = 0, 0, 0
        while len(nums) < n:
            min_n = min(nums[i] * 2, min(nums[j] * 3, nums[k] * 5))
            if min_n == nums[i] * 2:
                i += 1
            if min_n == nums[j] * 3:
                j += 1
            if min_n == nums[k] * 5:
                k += 1
            nums.append(min_n)
        return nums[n - 1]



cornerCao
5个月前
n = int(input())
nums = list(map(int, input().split()))
max_n = (1 << 13)
dp = [[0 for _ in range(max_n)] for _ in range(2)]
dp[1][0] = 1
mod = 10 ** 9 + 7
for i in range(0, len(nums)):
    for j in range(max_n):
   #     print(i, i %2, j^nums[i])
        dp[i%2][j] = (dp[(i-1)%2][j] + dp[(i-1)%2][j^nums[i]]) % mod

def is_prime(n):
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

res = 0
for j in range(2, max_n):
    if is_prime(j):
        res = (res + dp[(len(nums)-1)%2][j]) % mod
print(res)



cornerCao
5个月前
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        last_max = nums[0]
        res = last_max
        for i in range(1, len(nums)):
            if last_max >= 0:
                last_max += nums[i]
            else:
                last_max = nums[i]
            res = max(res, last_max)
        return res


活动打卡代码 AcWing 53. 最小的k个数

cornerCao
5个月前
import heapq
class Solution(object):
    def getLeastNumbers_Solution(self, nums, k):
        """
        :type input: list[int]
        :type k: int
        :rtype: list[int]
        """
        heap = []
        for n in nums:
            if len(heap) < k:
                heapq.heappush(heap, -n)
            else:
                top = -heapq.heappop(heap)
                if top > n:
                    heapq.heappush(heap, -n)
                else:
                    heapq.heappush(heap, -top)
        res = []
        while len(heap) > 0:
            res.append(-heapq.heappop(heap))
        return res[::-1]



cornerCao
5个月前
class Solution(object):
    def moreThanHalfNum_Solution(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cnt = 0; num = -1
        for n in nums:
            if cnt == 0:
                num = n
                cnt = 1
            elif num == n:
                cnt += 1
            else:
                cnt -= 1
        cnt = 0
        for n in nums:
            if n == num:
                cnt += 1
        return num if cnt > len(nums) // 2 else -1


活动打卡代码 AcWing 50. 序列化二叉树

cornerCao
5个月前
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:

    def serialize(self, root):
        """Encodes a tree to a single string.

        :type root: TreeNode
        :rtype: str
        """
        if root is None:
            return ''
        return '{},{},{}'.format(root.val, self.serialize(root.left), self.serialize(root.right))

    def help(self, vals, idx):
        if idx >= len(vals) or vals[idx] == '':
            return None, idx 
        root = TreeNode(int(vals[idx]))
        root.left, left_end = self.help(vals, idx + 1)
        root.right, right_end = self.help(vals, left_end + 1)
        return root, right_end

    def deserialize(self, data):
        """Decodes your encoded data to tree.

        :type data: str
        :rtype: TreeNode
        """
        root, end = self.help(data.split(','), 0)
        return root




cornerCao
5个月前
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def help(self, root):
        if root is None:
            return None, None
        left_h, left_t = self.help(root.left)
        right_h, right_t = self.help(root.right)
        head = root; tail = root
        root.left = left_t; root.right = right_h
        if left_t is not None:
            left_t.right = root
            head = left_h
        if right_h is not None:
            right_h.left = root
            tail = right_t
        return head, tail

    def convert(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        head, tail = self.help(root)
        return head




cornerCao
5个月前
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):

    def findPath(self, root, sum):
        """
        :type root: TreeNode
        :type sum: int
        :rtype: List[List[int]]
        """
        if root is None:
            return []
        paths = []
        path = []; path_sum = 0
        stk = [(root, 0)]
        while len(stk) > 0:
            node, prev_sum = stk.pop()
            while path_sum != prev_sum:
                path_sum -= path.pop()
            path.append(node.val)
            path_sum += node.val
            if node.left is None and node.right is None and path_sum == sum:
                paths.append(path[::])
            if node.right is not None:
                stk.append((node.right, path_sum))
            if node.left is not None:
                stk.append((node.left, path_sum))
        return paths