cornerCao

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 = [8,2,4,7], limit = 4

[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


输入：nums = [10,1,2,4,7,2], limit = 5


输入：nums = [4,2,2,2,4,4,2,2], limit = 0



### 算法

#### 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



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


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


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