- 1-100:
- 1. Two Sum
- 2. Add Two Numbers
- 3. Longest Substring Without Repeating Characters
- 4. Median of Two Sorted Arrays
- 5. Longest Palindromic Substring
- 6. ZigZag Conversion
- 7. Reverse Integer
- 8. String to Integer (atoi)
- 9. Palindrome Number
- 10. Regular Expression Matching
- 11. Container With Most Water
- 12. Integer to Roman
- 13. Roman to Integer
- 14. Longest Common Prefix
- 15. 3Sum
- 16. 3Sum Closest
- 17. Letter Combinations of a Phone Number
- 18. 4Sum
- 19. Remove Nth Node From End of List
- 20. Valid Parentheses
- 21. Merge Two Sorted Lists
- 22. Generate Parentheses
- 23. Merge k Sorted Lists
- 24. Swap Nodes in Pairs
- 25. Reverse Nodes in k-Group
- 26. Remove Duplicates from Sorted Array
- 27. Remove Element
- 28. Implement strStr()
- 30. Substring with Concatenation of All Words
- 31. Next Permutation
- 32. Longest Valid Parentheses
- 33. Search in Rotated Sorted Array
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 35. 搜索插入位置
- 36. 有效的数独
- 37. 解数独
- 38. 外观数列
- 39. 组合总和
- 40. 组合总和 II
- 75. 颜色分类
- 94. 二叉树的中序遍历
- 95. 不同的二叉搜索树 II
- 100+:
- 101. 对称二叉树
- 110. 平衡二叉树
- 114. 二叉树展开为链表
- 133. Clone Graph
- 169. Majority Element
- 207. Course Schedule
- 210. Course Schedule II
- 300. Longest Increasing Subsequence
- 409. Longest Palindrome
- 695. Max Area of Island
- 794. Valid Tic-Tac-Toe State
- 1071. Greatest Common Divisor of Strings
- 1160. Find Words That Can Be Formed by Characters
- others
- Q: 找两个相加的数
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].- A:
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums_cp = copy.deepcopy(nums)
nums.sort()
i = 0
j = len(nums) - 1
for k in range(len(nums)):
if nums[i] + nums[j] == target:
index_i = nums_cp.index(nums[i])
index_j = nums_cp.index(nums[j])
if index_i == index_j:
index_j = len(nums_cp) - 1 - nums_cp[::-1].index(nums[j])
return [index_i, index_j]
elif nums[i] + nums[j] > target:
j -= 1
else:
i += 1- Q: 加两个链表数据
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.- A:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
result = l1.val + l2.val
l1.val = result % 10
if not l1.next and not l2.next:
if result >= 10:
l1.next = ListNode(1)
elif not l1.next and l2.next:
if result >= 10:
l1.next = self.addTwoNumbers(ListNode(1), l2.next)
else:
l2.next.val += result // 10
l1.next = l2.next
elif l1.next and not l2.next:
if result >= 10:
l1.next = self.addTwoNumbers(l1.next, ListNode(1))
else:
l1.next.val += result // 10
else:
l1.next.val += result // 10
l1.next = self.addTwoNumbers(l1.next, l2.next)
return l1- Q: 寻找最长不重复子串
Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.- A:
- 解法一: 144 ms | 13.5 MB
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if s == "":
return 0
begin = 0
now = 1
longest_substring = 1
while(now < len(s)):
for i in range(begin, now):
if s[now] == s[i]:
begin = i + 1
break
elif i == now - 1 and now - begin + 1 > longest_substring:
longest_substring = now - begin + 1
now += 1
return longest_substring- 解法二: 108 ms | 13.4 MB
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
hash_map = {}
i, result = 0, 0
for j in range(len(s)):
if s[j] in hash_map:
i = max(hash_map[s[j]], i)
result = max(result, j - i + 1)
hash_map[s[j]] = j + 1
return result- Q: 两个有序数组的中位数
- A:
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1 # n > m
m = len(nums1)
n = len(nums2)
i_min = 0
i_max = m
while i_min <= i_max:
i = (i_min + i_max) // 2
j = (m + n + 1) // 2 - i
if i > 0 and nums1[i - 1] > nums2[j]:
i_max = i - 1
elif i < m and nums2[j - 1] > nums1[i]:
i_min = i + 1
else:
# i=0, j=0, i=m, j=n
if (m + n) % 2 == 1:
if i == 0:
return nums2[j - 1]
elif j == 0:
return nums1[i - 1]
else:
return max(nums1[i - 1], nums2[j - 1])
else:
k1 = 0 if i == 0 else nums1[i - 1]
k2 = 0 if j == 0 else nums2[j - 1]
k3 = nums2[j] if i == m else nums1[i]
k4 = nums1[i] if j == n else nums2[j]
return (max(k1, k2) + min(k3, k4)) / 2- Q: 回文串
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.- A:
class Solution:
def longestPalindrome(self, s: str) -> str:
if s == "":
return ""
for i in range(len(s), 1, -1):
for j in range(0, len(s) - i + 1):
mid = (2 * j + i - 1) // 2
if i % 2 == 1:
if s[j: mid] == s[mid+1: j+i][::-1]:
return s[j: j+i]
else:
if s[j: mid+1] == s[mid+1: j+i][::-1]:
return s[j: j+i]
return s[0]- Q: Z字型字符串
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P I N
A L S I G
Y A H R
P I- A:
from collections import OrderedDict
class Solution:
def convert(self, s: str, numRows: int) -> str:
if numRows == 1 or len(s) <= numRows:
return s
hash_map = OrderedDict({i:[] for i in range(numRows)})
index = 0
plus_num = 1
for sub_char in s:
hash_map[index].append(sub_char)
if index == numRows - 1:
plus_num = -1
elif index == 0:
plus_num = 1
index += plus_num
ans = ""
for i in range(numRows):
ans += "".join(hash_map[i])
return ans- Q: 数字翻转
- A:
class Solution:
def reverse(self, x: int) -> int:
ans = abs(x)
result = 0
while ans != 0:
nums = ans % 10
result = result * 10 + nums
ans = ans // 10
if x < 0:
if (result := -result) < -2 ** 31:
return 0
else:
if result > 2 ** 31 - 1:
return 0
return result- Q:
atoi function - A:
class Solution:
def myAtoi(self, str: str) -> int:
return max(min(int(*re.findall('^[\+\-]?\d+', str.lstrip())), 2**31 - 1), -2**31)- Q: 判断是不是回文串
- A:
class Solution:
def isPalindrome(self, x: int) -> bool:
x = list(str(x))
return x == x[::-1]- Q:
.和*的正则匹配
Input:
s = "aa"
p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Input:
s = "ab"
p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".- A:
class Solution:
def isMatch(self, s: str, p: str) -> bool:
hash_map = {}
def dp(i, j):
if (i, j) not in hash_map:
# 如果匹配, 结尾一定是j = len(p), i = len(s)
if j == len(p):
ans = i == len(s)
else:
# 当前字符是否匹配
single_match = i < len(s) and p[j] in (s[i], ".")
# *处只需要判断符合0次或者1次 + 前进一位继续判断
if j + 1 < len(p) and p[j + 1] == "*":
ans = single_match and dp(i + 1, j) or dp(i, j + 2)
else:
ans = single_match and dp(i + 1, j + 1)
hash_map[i, j] = ans
return hash_map[i, j]
return dp(0, 0)- Q: 求[A, B]之间的最大容量, 容量 = min(list[B], list[A]) * (B - A)
Input: [1,8,6,2,5,4,8,3,7]
Output: 49- A:
class Solution:
def maxArea(self, height: List[int]) -> int:
length = len(height)
front = 0
end = length - 1
ans = [0, length - 1, (length - 1) * min(height[0], height[length - 1])]
while(front < end):
if (end - front) * min(height[end], height[front]) > ans[2]:
ans = [front, end, (end - front) * min(height[end], height[front])]
if height[front] > height[end]:
end -= 1
else:
front += 1
return ans[2]- Q: int转罗马数字
- A:
- 解法一:
class Solution: def intToRoman(self, num: int) -> str: ans = "" M_num = num // 1000 ans += M_num * "M" num %= 1000 D_num = num // 500 num %= 500 C_num = num // 100 num %= 100 if D_num == 1: ans += "CM" if C_num == 4 else "D" + C_num * "C" else: ans += "CD" if C_num == 4 else C_num * "C" L_num = num // 50 num %= 50 X_num = num // 10 num %= 10 if L_num == 1: ans += "XC" if X_num == 4 else "L" + X_num * "X" else: ans += "XL" if X_num == 4 else X_num * "X" V_num = num // 5 num %= 5 I_num = num if V_num == 1: ans += "IX" if I_num == 4 else "V" + I_num * "I" else: ans += "IV" if I_num == 4 else I_num * "I" return ans
- 解法二: 贪心
class Solution: def intToRoman(self, num: int) -> str: ans = "" nums = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1] roman = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"] index = 0 while index < 13: while num - nums[index] >= 0: ans += roman[index] num -= nums[index] index += 1 return ans
- Q: 罗马数字转int
- A:
class Solution:
def romanToInt(self, s: str) -> int:
hash_map = {
"M": 1000,
"D": 500,
"C": 100,
"L": 50,
"X": 10,
"V": 5,
"I": 1
}
ans = 0
for i in range(len(s)):
if i < len(s) - 1 and hash_map[s[i]] < hash_map[s[i + 1]]:
ans -= hash_map[s[i]]
else:
ans += hash_map[s[i]]
return ans- Q:
- A:
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if strs == []:
return ""
ans = ""
length = min([len(i) for i in strs])
for i in range(length):
s = strs[0][i]
for j in range(len(strs)):
if strs[j][i] != s:
return ans
ans += s
return ans- Q: 三数之和
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]。- A: 就是从头开始固定第一个数, 寻找另外两个数 = -第一个数, 和2sum解法相同, 在遍历中有重复数字就直接跳过
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
length = len(nums)
if length < 3:
return []
nums.sort()
for i in range(length):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
begin = i + 1
end = length -1
while begin < end:
sum_num = nums[begin] + nums[end] + nums[i]
if sum_num == 0:
ans.append([nums[i], nums[begin], nums[end]])
begin += 1
end -= 1
while begin < end and nums[begin] == nums[begin - 1]:
begin += 1
while end > begin and nums[end] == nums[end + 1]:
end -= 1
elif sum_num > 0:
end -= 1
else:
begin += 1
return ans- Q: 找和最接近target的三个数
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).- A:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
length = len(nums)
if length < 3:
return []
nums.sort()
ans = nums[0] + nums[1] + nums[2]
for i in range(0, length - 2):
if (temp:=nums[i] + nums[i + 1] + nums[i + 2]) > target:
if abs(temp - target) > abs(ans - target):
return ans
else:
return temp
begin = i + 1
end = length - 1
while begin < end:
sum_num = nums[i] + nums[begin] + nums[end]
if sum_num == target:
return target
if abs(sum_num - target) < abs(ans - target):
ans = sum_num
if sum_num > target:
end -= 1
else:
begin += 1
return ans- Q: 九宫格拼音输入法
Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].- A:
def letterCombinations(self, digits: str) -> List[str]:
if digits == "":
return []
hash_map = {
"2": [["a", "b", "c"], 3],
"3": [["d", "e", "f"], 3],
"4": [["g", "h", "i"], 3],
"5": [["j", "k", "l"], 3],
"6": [["m", "n", "o"], 3],
"7": [["p", "q", "r", "s"], 4],
"8": [["t", "u", "v"], 3],
"9": [["w", "x", "y", "z"], 4],
}
ans = hash_map[digits[0]][0]
for i in range(1, len(digits)):
letters = hash_map[digits[i]][0]
num = hash_map[digits[i]][1]
ans *= num
ans = [ans[j] + letters[j // (len(ans) // num)] for j in range(len(ans))]
return ans- Q:
- A:
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
length = len(nums)
if length < 4:
return []
nums.sort()
ans = []
for i in range(0, length - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
if nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target:
return ans
tri_target = target - nums[i]
for j in range(i + 1, length - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
begin = j + 1
end = length - 1
while begin < end:
temp_sum = nums[j] + nums[begin] + nums[end]
if temp_sum == tri_target:
ans.append([nums[i], nums[j], nums[begin], nums[end]])
begin += 1
end -= 1
while begin < end and nums[begin] == nums[begin - 1]:
begin += 1
while begin < end and nums[end] == nums[end + 1]:
end -= 1
elif temp_sum > tri_target:
end -= 1
else:
begin += 1
return ans- Q: 删除链表中的一个节点
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.- A:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
temp_list = []
num = 0
l = ListNode(num)
l.next = head
while l.next:
num += 1
temp_list.append(l.next)
l = l.next
if num == n:
return head.next
temp_list[num - n - 1].next = temp_list[num - n].next
return head- Q: 判断
()[]{}组合的有效性, 栈的应用
Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.
- A:
class Solution:
def isValid(self, s: str) -> bool:
if s == "":
return True
stack = []
hash_map = {
"(": ")",
"[": "]",
"{": "}",
}
for i in range(len(s)):
if len(stack) > (len(s) - i):
return False
if s[i] in hash_map:
stack.append(hash_map[s[i]])
elif stack == [] or s[i] != stack.pop():
return False
if stack != []:
return False
return True- Q: 按序合并两个链表
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4- A:
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
if l1.val > l2.val:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
else:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1- Q: 找出括号数为n的最大有效组合
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]- A:
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
if n == 0:
return [""]
ans = []
def search(s, front, rear):
if rear == 0 and front == 0:
ans.append(s)
if rear > front:
search(s + ")", front, rear - 1)
if front > 0:
search(s + "(", front - 1, rear)
search("(", n - 1, n)
return ans- Q: 合并k个有序链表, 双链表分治合并
- A:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
ans = []
for i in range(len(lists)):
temp_list = lists[i]
while temp_list:
ans.append(temp_list.val)
temp_list = temp_list.next
if len(ans) == 0:
return []
ans.sort()
head = ListNode(1)
temp_list = ListNode(ans[0])
head.next = temp_list
for i in range(1, len(ans)):
temp_list.next = ListNode(ans[i])
temp_list = temp_list.next
return head.next- Q: 链表中数据相互交换
- A:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
"""
:type head: ListNode
:rtype: ListNode
"""
# Dummy node acts as the prevNode for the head node
# of the list and hence stores pointer to the head node.
dummy = ListNode(-1)
dummy.next = head
prev_node = dummy
while head and head.next:
# Nodes to be swapped
first_node = head;
second_node = head.next;
# Swapping
prev_node.next = second_node
first_node.next = second_node.next
second_node.next = first_node
# Reinitializing the head and prev_node for next swap
prev_node = first_node
head = first_node.next
# Return the new head node.
return dummy.next- Q: 反转n个节点
Example:
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5- A:
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
if not head.next:
return head
def k_reverse(head: ListNode):
temp = ListNode(-1)
temp.next = head
for i in range(k):
if head:
head = head.next
else:
return temp.next
head = temp.next
end = head
for i in range(k - 1):
temp = end.next
end.next = temp.next
temp.next = head
head = temp
end.next = k_reverse(end.next)
return head
return k_reverse(head)- Q: 去重
- A:
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
i = 1
length = len(nums)
if length < 2:
return length
while i < length:
if nums[i] == nums[i - 1]:
del nums[i]
length -= 1
else:
i += 1
return len(nums)- Q: 删除某个元素
- A:
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
i, j = 0, 0
length = len(nums)
for i in range(length):
if nums[i] == val:
if j == 0:
j = i
while j < length and nums[j] == val:
j += 1
if j == length:
return i
else:
nums[i], nums[j] = nums[j], nums[i]
return length- Q: 查找第一个匹配的子串
Input: haystack = "hello", needle = "ll"
Output: 2- A:
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
length = len(haystack)
length2 = len(needle)
if length2 == 0:
return 0
for i in range(length):
if i + length2 > length:
return -1
elif haystack[i] == needle[0] and haystack[i: i + length2] == needle:
return i
return -1- Q:
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
输入：
s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
- A:
一个数组匹配的hash, 遍历就行
import collections
class Solution:
def findSubstring(self, s: str, words: List[str]) -> List[int]:
res = []
if not words:
return res
word_len = len(words[0])
win_len = word_len * len(words)
word_cnt = collections.Counter(words)
for left in range(word_len):
while left + win_len <= len(s):
temp = dict(word_cnt)
right = left + win_len
flag = True
while right > left:
cur_word = s[right - word_len: right]
if cur_word not in words or temp[cur_word] == 0:
flag = False
break
temp[cur_word] -= 1
right -= word_len
if not flag:
left = right
continue
res.append(left)
left += word_len
return res- Q:
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
- A:
设置两个标记位i, j, 从后向前遍历, 找到比i大且最接近i的数, 交换之后对i后面的进行升序排序
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
temp_nums = copy.deepcopy(nums)
temp_nums.sort(reverse=True)
if nums == temp_nums:
nums.sort()
else:
flag = False
for i in range(len(nums) - 2, -1, -1):
ans = 10000
index = len(nums)
for j in range(len(nums) - 1, i, -1):
if nums[i] < nums[j] and nums[j] - nums[i] < ans:
ans = nums[i] - nums[j]
index = j
if index != len(nums):
nums[index], nums[i] = nums[i], nums[index]
temp_nums = nums[i + 1:]
temp_nums.sort()
nums[i + 1:] = temp_nums
break- Q:
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例:
"()(()": 2
"()()": 4
- A:
利用栈, 初始化栈底元素为-1
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1]
ans = 0
for i in range(len(s)):
if s[i] == "(":
stack.append(i)
else:
j = stack.pop()
if stack == []:
stack.append(i)
else:
ans = ans if ans > i - stack[-1] else i - stack[-1]
return ans- Q:
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是 O(log n) 级别。
示例:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
- A:
先找到中间点, 再两边二分.
class Solution:
def search(self, nums: List[int], target: int) -> int:
def binary_search(arr, num):
begin = 0
end = len(arr) - 1
while begin <= end:
if begin == end:
return begin if arr[begin] == num else -1
mid = (begin + end) // 2
if arr[mid] == num:
return mid
elif arr[mid] < num:
begin = mid + 1
else:
end = mid
return -1
if nums == [] or target > nums[-1] and target < nums[0]:
return -1
if nums[0] < nums[-1]:
return binary_search(nums, target)
begin = 0
end = len(nums) - 1
j = 0
while begin <= end:
if begin == end:
j = begin
break
mid = (begin + end) // 2
if nums[mid] >= nums[0]:
if nums[mid] > nums[mid + 1]:
j = mid + 1
break
else:
begin = mid + 1
else:
if nums[mid] < nums[mid - 1]:
j = mid
break
else:
end = mid
if target <= nums[-1]:
ans = binary_search(nums[j:], target)
return ans if ans == -1 else ans + j
else:
return binary_search(nums[:j], target)- Q:
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值，返回 [-1, -1]。
示例:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]- A:
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
first, second = -1, -1
begin = 0
end = len(nums) - 1
flag = -1
while(begin <= end):
mid = (begin + end) // 2
if nums[mid] == target:
flag = mid
break
elif nums[mid] < target:
begin = mid + 1
else:
end = mid - 1
if flag == -1:
return [-1, -1]
if nums[0] == target:
first = 0
else:
begin = 0
end = flag
while begin <= end:
mid = (begin + end) // 2
if nums[mid] == target:
if nums[mid - 1] < target:
first = mid
break
else:
end = mid - 1
else:
begin = mid + 1
if nums[-1] == target:
second = len(nums) - 1
else:
begin = flag
end = len(nums) - 1
while begin <= end:
mid = (begin + end) // 2
if nums[mid] == target:
if nums[mid + 1] > target:
second = mid
break
else:
begin = mid + 1
else:
end = mid - 1
return [first, second]- Q:
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，
返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
示例:
输入: [1,3,5,6], 5
输出: 2- A:
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if nums == []:
return 0
begin = 0
end = len(nums) - 1
while begin <= end:
mid = (begin + end) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
begin = mid + 1
else:
end = mid - 1
if nums[mid] < target:
return mid + 1
else:
return mid- Q:
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
输入:
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: true- A:
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
n = len(board)
column = [[] for i in range(n)]
row = [[] for i in range(n)]
block = [[] for i in range(n)]
for i in range(len(board)):
for j in range(len(board)):
if board[i][j] == ".":
continue
if board[i][j] in column[j] or board[i][j] in row[i] or board[i][j] in block[i // 3 * 3 + j // 3]:
return False
else:
column[j].append(board[i][j])
row[i].append(board[i][j])
block[i // 3 * 3 + j // 3].append(board[i][j])
return True- Q:
编写一个程序，通过已填充的空格来解决数独问题。一个数独的解法需遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
空白格用 '.' 表示。- A:
from collections import defaultdict
class Solution:
def solveSudoku(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
def could_place(d, row, col):
"""
Check if one could place a number d in (row, col) cell
"""
return not (d in rows[row] or d in columns[col] or \
d in boxes[box_index(row, col)])
def place_number(d, row, col):
"""
Place a number d in (row, col) cell
"""
rows[row][d] += 1
columns[col][d] += 1
boxes[box_index(row, col)][d] += 1
board[row][col] = str(d)
def remove_number(d, row, col):
"""
Remove a number which didn't lead
to a solution
"""
del rows[row][d]
del columns[col][d]
del boxes[box_index(row, col)][d]
board[row][col] = '.'
def place_next_numbers(row, col):
"""
Call backtrack function in recursion
to continue to place numbers
till the moment we have a solution
"""
# if we're in the last cell
# that means we have the solution
if col == N - 1 and row == N - 1:
nonlocal sudoku_solved
sudoku_solved = True
#if not yet
else:
# if we're in the end of the row
# go to the next row
if col == N - 1:
backtrack(row + 1, 0)
# go to the next column
else:
backtrack(row, col + 1)
def backtrack(row = 0, col = 0):
"""
Backtracking
"""
# if the cell is empty
if board[row][col] == '.':
# iterate over all numbers from 1 to 9
for d in range(1, 10):
if could_place(d, row, col):
place_number(d, row, col)
place_next_numbers(row, col)
# if sudoku is solved, there is no need to backtrack
# since the single unique solution is promised
if not sudoku_solved:
remove_number(d, row, col)
else:
place_next_numbers(row, col)
# box size
n = 3
# row size
N = n * n
# lambda function to compute box index
box_index = lambda row, col: (row // n ) * n + col // n
# init rows, columns and boxes
rows = [defaultdict(int) for i in range(N)]
columns = [defaultdict(int) for i in range(N)]
boxes = [defaultdict(int) for i in range(N)]
for i in range(N):
for j in range(N):
if board[i][j] != '.':
d = int(board[i][j])
place_number(d, i, j)
sudoku_solved = False
backtrack()- Q:
「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意：整数序列中的每一项将表示为一个字符串。
示例:
输入: 4
输出: "1211"
解释：当 n = 3 时，序列是 "21"，其中我们有 "2" 和 "1" 两组，"2" 可以读作 "12"，
也就是出现频次 = 1 而 值 = 2；类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11"
组合在一起，也就是 "1211"。- A:
class Solution:
def countAndSay(self, n: int) -> str:
string = "1"
for i in range(n - 1):
ans = ""
char = string[0]
num = 0
for j in range(len(string)):
if j == len(string) - 1:
if string[j] == char:
ans += str(num + 1) + string[j]
else:
ans += str(num) + string[j - 1] + "1" + string[j]
break
if string[j] == char:
num += 1
else:
char = string[j]
ans += str(num) + string[j - 1]
num = 1
string = ans
return string- Q:
给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明：
所有数字（包括 target）都是正整数。
解集不能包含重复的组合。
输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
[7],
[2,2,3]
]- A:
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
if candidates == []:
return []
ans = []
def search(already_arr, arr, target):
if arr == []:
return False
num = target // arr[0]
for i in range(num + 1):
if arr[0] * i == target:
ans.append(already_arr + [arr[0]] * i)
else:
search(already_arr + [arr[0]] * i, arr[1:], target - arr[0] * i)
search([], candidates, target)
return ans- Q:
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
所求解集为:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]- A:
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
if candidates == []:
return []
candidates.sort()
ans = []
size = len(candidates)
def dfs(path, index, target):
if target == 0:
ans.append(path)
for i in range(index, size):
if candidates[i] > target:
return
if i > index and candidates[i] == candidates[i - 1]:
continue
dfs(path + [candidates[i]], i + 1, target - candidates[i])
dfs([], 0, target)
return ans- Q:
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]
进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。
首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。
你能想出一个仅使用常数空间的一趟扫描算法吗？- A:
class Solution:
def sortColors(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
# nums.sort()
begin = 0
end = len(nums) - 1
while begin < end:
while begin < len(nums) - 1 and nums[begin] == 0:
begin += 1
while end > 0 and nums[end] != 0:
end -= 1
if begin < end:
nums[begin], nums[end] = nums[end], nums[begin]
end = len(nums) - 1
while begin < end:
while begin < len(nums) - 1 and nums[begin] == 1:
begin += 1
while end > 0 and nums[end] == 2:
end -= 1
if begin < end:
nums[begin], nums[end] = nums[end], nums[begin]- Q:
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？- A:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.ans = []
def inorderTraversal(self, root: TreeNode) -> List[int]:
def search(tree):
if not tree:
return
if not tree.left and not tree.right:
self.ans.append(tree.val)
return
if not tree.left:
self.ans.append(tree.val)
search(tree.right)
return
if not tree.right:
search(tree.left)
self.ans.append(tree.val)
return
search(tree.left)
self.ans.append(tree.val)
search(tree.right)
search(root)
return self.ans- Q:
给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。
示例:
输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树：
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3- A:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def generateTrees(self, n: int) -> List[TreeNode]:
ans = []
nodes = [i + 1 for i in range(n)]
def build_bst(tree, left_arr, right_arr):
temp = []
if left_arr != []:
left_tree = []
for i in range(len(left_arr)):
left_tree += build_bst(left_arr[i], left_arr[:i], left_arr[i + 1:])
else:
left_tree = [None]
if right_arr != []:
right_tree = []
for i in range(len(right_arr)):
right_tree += build_bst(right_arr[i], right_arr[:i], right_arr[i + 1:])
else:
right_tree = [None]
for left_node in left_tree:
for right_node in right_tree:
temp_tree = TreeNode(tree)
temp_tree.left = left_node
temp_tree.right = right_node
temp.append(temp_tree)
return temp
for i in nodes:
ans += build_bst(i, nodes[:i - 1], nodes[i:])
return ans- Q:
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
进阶：
你可以运用递归和迭代两种方法解决这个问题吗？- A:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
# class Solution:
# def isSymmetric(self, root: TreeNode) -> bool:
# if not root:
# return True
# def symmetric(tree1 , tree2):
# if tree1 == tree2:
# return True
# if not tree1 or not tree2 or tree1.val != tree2.val:
# return False
# return symmetric(tree1.right, tree2.left) and symmetric(tree1.left, tree2.right)
# return symmetric(root.left, root.right)
from collections import deque
class Solution:
def isSymmetric(self, root: TreeNode) -> bool:
if not root or root.left == root.right:
return True
queue1 = deque()
queue1.append(root.left)
queue2 = deque()
queue2.append(root.right)
while queue1 and queue2:
tree1 = queue1.popleft()
tree2 = queue2.popleft()
if tree1 == tree2:
continue
if not tree1 or not tree2 or tree1.val != tree2.val:
return False
queue1.append(tree1.left)
queue1.append(tree1.right)
queue2.append(tree2.right)
queue2.append(tree2.left)
if queue1 == queue2:
return True
else:
return False- Q:
给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。- A:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def __init__(self):
self.flag = True
def isBalanced(self, root: TreeNode) -> bool:
if not root:
return True
def balance(tree):
if not tree.left and not tree.right:
return 0
if not tree.left:
height = balance(tree.right) + 1
if height > 1:
self.flag = False
return height
if not tree.right:
height = balance(tree.left) + 1
if height > 1:
self.flag = False
return height
height1 = balance(tree.left) + 1
height2 = balance(tree.right) + 1
if abs(height1 - height2) > 1:
self.flag = False
return height1 if height1 > height2 else height2
balance(root)
return self.flag- Q:
给定一个二叉树，原地将它展开为链表。
例如，给定二叉树
1
/ \
2 5
/ \ \
3 4 6
将其展开为：
1
\
2
\
3
\
4
\
5
\- A:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
from collections import deque
class Solution:
def flatten(self, root: TreeNode) -> None:
"""
Do not return anything, modify root in-place instead.
"""
if not root:
return None
def merge(tree):
if not tree.left and not tree.right:
return tree
if not tree.left:
tree.right = merge(tree.right)
return tree
if not tree.right:
tree.right = merge(tree.left)
tree.left = None
return tree
left_node = merge(tree.left)
right_node = merge(tree.right)
tree.right = left_node
tree.left = None
while left_node.right != None:
left_node = left_node.right
left_node.right = right_node
return tree
merge(root)- Q: 邻接表遍历图
- A:
- 解法一: DFS
""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = []): self.val = val self.neighbors = neighbors """ class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return None gragh_map = {} def search_node(node): if node.val not in gragh_map: gragh_map[node.val] = [nei_node.val for nei_node in node.neighbors] for i in node.neighbors: search_node(i) search_node(node) nodes = [0] for i in range(1, len(gragh_map) + 1): nodes.append(Node(i)) for i in range(1, len(gragh_map) + 1): nodes[i].neighbors = [nodes[j] for j in gragh_map[i]] return nodes[1]
- 解法二: BFS
""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = []): self.val = val self.neighbors = neighbors """ from collections import deque class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return None queue = deque([node]) hash_map = {} hash_map[node] = Node(node.val) while queue: temp_node = queue.popleft() if temp_node.neighbors: for neighbor in temp_node.neighbors: if neighbor not in hash_map: hash_map[neighbor] = Node(neighbor.val) queue.append(neighbor) hash_map[temp_node].neighbors.append(hash_map[neighbor]) return hash_map[node]
- Q: 求众数
Input: [3,2,3]
Output: 3- A:
- 解法一:
from collections import Counter class Solution: def majorityElement(self, nums: List[int]) -> int: c = Counter(nums) return c.most_common(1)[0][0]
- Boyer-Moore 投票
from collections import Counter class Solution: def majorityElement(self, nums: List[int]) -> int: ans = nums[0] num = 0 for i in nums: if num == 0: ans = i num = 1 else: num += 1 if ans == i else -1 return ans
- Q:
- A:
- 解法一: DFS
class Solution: def __init__(self): self.temp_arr = [] def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: if not prerequisites: return True # 建立邻接表 # 遍历所有节点, DFS, 记录每一个可行的节点 # 记录path, 当形成回环时返回false adjacency_matrices = [[] for i in range(numCourses)] for i, j in prerequisites: adjacency_matrices[i].append(j) ans = [] def search_end(node, path): if node not in ans and adjacency_matrices[node]: if node in path: return False path.append(node) for i in adjacency_matrices[node]: if not search_end(i, path): return False ans.append(node) return True for i in range(numCourses): if i not in ans and not search_end(i, []): return False return True
- 解法二: 拓扑排序
from collections import deque class Solution: def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool: if not prerequisites: return True # 拓扑排序, 建立一个队列, 不断的删除入度为0的节点 adajence_matrix = [[] for i in range(numCourses)] queue = deque() ans = [0] * numCourses for i, j in prerequisites: adajence_matrix[j].append(i) ans[i] += 1 for i in range(numCourses): if ans[i] == 0: queue.append(i) while queue: for node_number in adajence_matrix[queue.popleft()]: ans[node_number] -= 1 if ans[node_number] == 0: queue.append(node_number) if sum(ans) == 0: return True else: return False
- Q: 排课拓扑排序
- A:
from collections import deque
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
if numCourses == 0:
return []
adjacency_matrix = [[] for i in range(numCourses)]
ans = [0] * numCourses
queue = deque()
for i, j in prerequisites:
adjacency_matrix[j].append(i)
ans[i] += 1
for i in range(numCourses):
if ans[i] == 0:
queue.append(i)
result = []
while queue:
pop_number = queue.popleft()
result.append(pop_number)
for node_number in adjacency_matrix[pop_number]:
ans[node_number] -= 1
if ans[node_number] == 0:
queue.append(node_number)
if sum(ans) != 0:
return []
else:
return result- Q:
- A:
- 解法一:DP
class Solution: def lengthOfLIS(self, nums: List[int]) -> int: if nums == []: return 0 dp = [1] * len(nums) for i in range(1, len(nums)): for j in range(0, i): if nums[i] > nums[j] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 return max(dp)
- 解法二: 贪心+二分查找
class Solution: # 存储每个点的最大序列, 后面点的最大序列根据这个点之前所有点的组合生成 def lengthOfLIS(self, nums: List[int]) -> int: if nums == []: return 0 ans = [nums[0]] for i in range(1, len(nums)): if nums[i] > ans[-1]: ans.append(nums[i]) else: begin = 0 end = len(ans) - 1 mid = (begin + end) // 2 while begin < end: if nums[i] > ans[mid]: begin = mid + 1 else: end = mid mid = (begin + end) // 2 if nums[i] > ans[mid]: ans[mid + 1] = nums[i] else: ans[mid] = nums[i] return len(ans)
- Q: 最长回文串
- A:
from collections import Counter
class Solution:
def longestPalindrome(self, s: str) -> int:
if s == "":
return 0
hash_map = Counter(s)
ans = 0
for key, value in hash_map.items():
ans += hash_map[key] // 2
if (ans := ans * 2) < len(s):
ans += 1
return ans- Q: 寻找最大连接的岛屿数量
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
最大岛屿连接岛屿为6
- A:
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ans = []
height = len(grid)
width = len(grid[0])
def search_grid(i, j):
if i < 0 or j < 0 or i == height or j == width or grid[i][j] == 0:
return 0
else:
grid[i][j] = 0
return 1 + search_grid(i - 1, j)+ search_grid(i, j - 1) + search_grid(i + 1, j) + search_grid(i, j + 1)
for i in range(height):
for j in range(width):
if grid[i][j] == 1:
ans.append(search_grid(i, j))
if ans == []:
return 0
return max(ans)- Q: 三子棋
- A:
class Solution:
def validTicTacToe(self, board: List[str]) -> bool:
len_x = 0
len_o = 0
for i in range(3):
for j in range(3):
if board[i][j] == 'X':
len_x += 1
elif board[i][j] == 'O':
len_o += 1
if len_x < len_o or len_x > len_o + 1:
return False
if len_x + len_o > 9:
return False
flag_x = 0
flag_y = 0
mode = ["XXX"]
for i in range(3):
if board[i] in mode:
flag_x += 1
for j in range(3):
if board[0][j] + board[1][j] + board[2][j] in mode:
flag_x +=1
if board[0][0] + board[1][1] + board[2][2] in mode:
flag_x += 1
if board[0][2] + board[1][1] + board[2][0] in mode:
flag_x += 1
mode = ["OOO"]
for i in range(3):
if board[i] in mode:
flag_y += 1
for j in range(3):
if board[0][j] + board[1][j] + board[2][j] in mode:
flag_y += 1
if board[0][0] + board[1][1] + board[2][2] in mode:
flag_y += 1
if board[0][2] + board[1][1] + board[2][0] in mode:
flag_y += 1
if flag_x == 1 and flag_y == 1:
return False
elif flag_x == 1 and flag_y == 0:
if len_x == len_o:
return False
elif flag_x == 0 and flag_y == 1:
if len_x > len_o:
return False
return True- Q: 求最大公因子
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"- A:
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
if len(str1) < len(str2):
str1, str2 = str2, str1
if str2 != str1[: len(str2)]:
return ""
k = 1
n = len(str2)
while(k < n):
base = n // k
if str2[: base] * k == str2 and str2[: base] * (len(str1) // base) == str1:
return str2[:base]
k += 1
return ""- Q: 查询
words中["cat","bt","hat","tree"]那些可以被chars:"atach"组合 - A:
class Solution:
def countCharacters(self, words: List[str], chars: str) -> int:
chars_cnt = collections.Counter(chars)
ans = 0
for word in words:
word_cnt = collections.Counter(word)
for c in word_cnt:
if chars_cnt[c] < word_cnt[c]:
break
else:
ans += len(word)
return ans- Q:
含有重复数的数组，求这个数组的子集合的和中，最小不能得到的数,
比如[1,2,5]. 最小不能得到的是4- A:
arr = [1, 2, 3, 4, 5]
max_number = sum(arr)
result = [0] * (max_number + 1)
result[0] = max_number + 1
for i in arr:
result[i] += 1
def min_number(arr, count):
if sum(result) == 2 * max_number + 1:
return max_number + 1
if not arr:
return result.index(0)
front_num = result.index(0)
if min(arr) > front_num:
return front_num
result[arr[0] + count] = 1
if len(arr) == 1:
return min_number([], arr[0] + count)
else:
ans = [min_number(arr[1:], arr[0] + count)]
for i in range(1, len(arr)):
if arr[i] != arr[i - 1]:
if i == len(arr) - 1:
result[arr[-1] + count] = 1
ans.append(min_number(arr[:-1], arr[-1] + count))
else:
result[arr[i] + count]
ans.append(min_number(arr[:i] + arr[i + 1:], arr[i] + count))
return max(ans)
print(min_number(arr, 0))- Q:
保护伞芯片公司现在拥有一块特殊的芯片材料板,这块材料板可以看做一个
n*m大小的矩阵,矩阵中的每一个单元蕴含着不的能量。现在公司需要放置
若干块ab大小的芯片在这块材料板上,但是放芯片的前提是材料板有a*b大
小的空位置,并且这些位置的能量是一样的。为了满足矩形内每个单元的能
量是一样的这个要求,公司需要释放某些单格一定量的能量释放的量可以精
确控制。释放能量的代价是e1-e2(其中e>=e2e1表示释放前的能量e2表示
释放之后的能量)。放置一块芯片的代为矩形内释放的总能量之和。(保护伞
公司技术限制,能量只能释放出去而不能注入进去)现在公司按照如下策略去
放置芯片:1.找到可以放置下1块芯片所需要释放的最小能量,然后放置该
芯片(程序输出中用芯片的左上角坐标记录)2.如果有多个位置代价一样,那
么按照行小的先,如果行一样,按照列小的优先. 3.重复1步骤继续下一个芯
片直到整个面板无再放置芯片。注意,芯片之间不能重叠。现在你可以帮助公
司计算出可以放置芯片的总数和他们的位置及代价吗?
输入:
第一行有4个正整数n,m,a,b分别表示n*m大小的材料板和a*b大小的芯片
其中1<=a<=n<=10001<=b<=m<=1000下面n行每行有m个数字,表示对应
位置的能量每个单位的能量值不超过1,000,000,000。测试数据中33的数
据满足1<=n,m<=100。
输出描述:
输出包含k行,k表示按照公司的放置策略可以放置的芯片数量。下面k行每
行包含3个数字R1,,Cost分别表示放置第块芯片左上角的行,列以及放置
这个芯片的代价(需要释放的总能量之和,请注意数据范围不要溢出)
示例:
输入:
2 2 2 1
2 1
3 1
输出:
2
1 2 0
1 1 1
- A:
核心思想就是k表示每一个放上去的方块, k的总数是一定的, 按序放置的动态规划
n, m, a, b = [int(i) for i in input().split()]
kernel = []
for i in range(n):
kernel.append([int(i) for i in input().split()])
row_bias = n - n // a * a
column_num = m // b
row_num = n // a
row_arr = [row_bias] * column_num
ans = []
def search_min(k, column_bias, row_arr):
if k > column_num * row_num - 1:
return 0
if k % column_num == 0:
column_bias = m - m // b * b
temp_row_bias = row_arr[k % column_num]
y = k // column_num * a + (row_bias - temp_row_bias)
x = k % column_num * b + (m - m // b * b - column_bias)
min_x, min_y, min_cost = [-1] * 3
for i in range(temp_row_bias + 1):
for j in range(column_bias + 1):
row_arr[k % column_num] -= i
kernel_slice = [kernel[q][x: x + j + b] for q in range(y, y + i + a)]
min_slice = min(min(kernel_slice))
sum_slice = sum([sum(q) for q in kernel_slice])
slice_cost = sum_slice - min_slice * a * b
temp_cost = search_min(k + 1, column_bias - j, row_arr)
if min_cost == -1 or slice_cost + temp_cost < min_cost:
min_cost = temp_cost + slice_cost
min_x, min_y = x, y
ans.append([min_y + 1, min_x + 1, min_cost])
return min_cost
search_min(0, m - m // b * b, row_arr)
print(len(ans))
print(ans)- Q:
现有n个人,要从这n个人中选任意数量的人组成一只队伍,再在这些人中选出一名队长,求
不同的方案数对10+7取模的结果。如果两个方案选取的人的集合不同或选出的队长不同,
则认为这两个方案是不同的。
- A:
快速幂
# n * 2^(n - 1)
n = 5
M = 10 ** 9 - 7
result = 1
ans = n - 1
a = 2
while ans:
if ans & 1 == 1:
result *= a % M
a = a * a % M
ans >>= 1
print(n * result % M)- Q:
今天，度度熊和牛妹在玩取石子的游戏，开始的时候有几堆石头，第1堆有4个石头，两个人轮流动作，
度度熊先走，在每个回合，玩家选择一个非空堆，并从堆中移除-块石头。 如果一个玩家在轮到他之
前所有的石碓都是空的，或者如果在移动石头之后，存在两个堆包含相同数量的石头(可能为都为0)，
那么他就会输。假设两人都在游戏时选择最佳方式，度度熊和牛妹谁会赢?如果度度熊获胜，输出"man",
如果牛妹获胜，输出"woman" (输出不包含双引号)
输入描述:
第一行一个数表示T组数据(1≤T<10),
每组数据第一行一个数n,表示n堆石头(1≤n≤10^5)
第二行n个数，表示每堆中石头的个数。(0≤ai≤10^9)
输出描述:
每组一行如果度度熊获胜，输出“man", 如果牛妹获胜，输出"woman" (输出不包含双引号)
示例1:
输入:
2
1
1
输出:
"man"
````
- A:
````python
核心思想: 轮到自己时就选自己能赢的情况
import copy
def judge(arr):
hash_map = {}
for i in arr:
if i in hash_map:
return True
hash_map[i] = 1
return False
def who_win(arr, sex):
if sum(arr) == 0:
return not sex
if judge(arr):
return sex
if sex:
ans = True
for i in range(len(arr)):
if arr[i] != 0:
temp_arr = copy.deepcopy(arr)
temp_arr[i] -= 1
ans |= who_win(temp_arr, not sex)
else:
ans = False
for i in range(len(arr)):
if arr[i] != 0:
temp_arr = copy.deepcopy(arr)
temp_arr[i] -= 1
ans &= who_win(temp_arr, not sex)
return ans
ans = []
t = int(input())
# man: True women: False
for i in range(t):
n = int(input())
arr = [int(j) for j in input().split()]
if n == 1:
if arr[0] % 2 == 1:
ans.append("man")
else:
ans.append("women")
else:
if who_win(arr, True):
ans.append("man")
else:
ans.append("women")
for word in ans:
print(word)
````
<a id="I5"></a>
#### interview5. 百度2020实习生招聘-2
- Q:
````python
在浩着深邃的星空中，有若干个可以被视为质点的星球， 以及坐着飞船想要探索宇宙奥秘的度度熊。
我们假定银河是一-个nx m的区域，顶点在(0,0)和(n,m),度度熊从最左边任意一点进入，打算穿越
这片区域并从右边任意一点离开。在银河中分布着K个星球，每个星球以及银河的上下两个边缘都有引力，
处于安全考虑，度度熊要离他们越远越好。试求度度熟穿越银河的路径上，距离所有星球以及上下边界的
最小距离的最大值可以为多少?
输入描述:
第一行包含三个整数n,m,k(1<=n,m<=10^6, 1<=k<=6000).
接下来k行, 每行两个整数x_i, y_i表示一个点的坐标.
第二行n个数, 表示该排列.(1<=ai<=10^9)
输出描述:
一个实数表示答案, 保留4位小数
输入:
10 5 2
1 1
2 3
输出:
1.1180
- A:
核心思想: 你要通过一个点时, 必定从其上或其下通过, 通过任意两点连线时,
必定是从连线中点或和顶或底的中点通过.
import math
n, m, k = [int(i) for i in input().split()]
arr = []
for i in range(k):
arr.append([float(j) for j in input().split()])
ans = float(n) if float(n) > float(m) else float(m)
for x, y in arr:
distance = max(y / 2, (m - y) / 2)
if distance < ans:
ans = distance
for i in range(k):
for j in range(i + 1, k):
x1, y1 = arr[i]
x2, y2 = arr[j]
distance = math.sqrt((y2 - y1)**2 + (x2 - x1)**2) / 2
if distance < ans:
ans = distance
print("%.4f"%ans)
string = "abcdefghiihgfedcba"
length = len(string)
hash_map = {}
def search_longest(char):
max_len = 1
ans = char
for key, value in hash_map.items():
if ord(key) >= ord(char) and len(value) + 1 > max_len:
max_len = len(value) + 1
ans = char + value
return ans
for i in range(length - 1, -1, -1):
char = string[i]
ans = search_longest(char)
hash_map[char] = ans
print(search_longest("a")[1:])- Q:
厂长阿维需要根据工厂里每个员工的劳动技能等级来分配每天的工作任务。
一个工作任务只能由劳动技能等级大于等于该任务难度的员工来完成，且
同一天里一个员工只能对应一个工作任务, 一个工作任务只能由一个员工
来完成. 员工i的劳动技能等级由整数Wi来表示, 工作任务i的任务难度由
整数Ti来表示. 如何分配今天的工作任务.
输入描述:
第一行输入员工数N, N为整数, 且1<=N<=10^5;
第二行输入N个员工的劳动技能等级Wi, 以空格分隔, Wi为整数, 且
0<=Wi<=10^9;
第三行输入N个任务的任务难度Ti, 以空格分隔, Ti为整数, 且0<=Ti<=10^9;
第四行输入一个整数M, 且1<=M<=10^9;
输出描述:
输出一个整数, 该整数为所有可能的分配方式的数量除以M后所得的余数.
输入:
6
1 6 3 4 5 2
2 3 1 4 6 5
10
输出:
1- A:
N = int(input())
W = [int(i) for i in input().split()]
T = [int(i) for i in input().split()]
M = int(input())
def search(W, T):
if W == T:
return 1
elif W[-1] < T[-1]:
return 0
return (len(W[hash_map[T[-1]]:]) % M) * search(W[:-1], T[:-1]) % M
W.sort()
T.sort()
hash_map = {}
i, j = N - 1, N - 1
if T[i] > W[j]:
print(0)
else:
while i >= 0:
while j >= 0 and W[j] >= T[i]:
j -= 1
if T[i] not in hash_map:
hash_map[T[i]] = j + 1
i -= 1
print(search(W, T))- Q:
日常收快递留下一堆快递盒占地方。 现在有N个快递盒，盒子不做翻转， 每个
盒子有自己的长宽高数据，都以整数形式(L,W,H) 出现，将小子整理到大盒子
里面(小盒子的长宽高都小于大盒子)。要求快递盒一个套一个(即，打开一个大
盒子最多只能看到一个小盒子)，最多能整理多少个盒子打包到一起.
输入:
[[5,4,3], [5,4,5], [6,6,6]]
输出:
2
输入:
[[2,3,2],[2,2,3]]
输出:
1(全放不了就输出1)- A:
import copy
def maxBoxes(boxes):
if len(boxes) == 0:
return 1
boxes.sort(key=lambda x: x[0], reverse=True)
def search(big_boxes, boxes):
if not boxes:
return len(big_boxes)
ans = []
box = boxes[0]
for i in range(len(big_boxes)):
if big_boxes[i][0] > box[0] and big_boxes[i][1] > box[1] and big_boxes[i][2] > box[2]:
temp_boxes = copy.deepcopy(big_boxes)
temp_boxes[i] = box
ans.append(search(temp_boxes, boxes[1:]))
temp_boxes = copy.deepcopy(big_boxes)
temp_boxes.append(box)
ans.append(search(temp_boxes, boxes[1:]))
return min(ans)
num = search([], boxes)
if num == len(boxes):
return 1
return search([], boxes)
print(maxBoxes([[5,6,3],[5,4,4],[6,3,6]]))