【leetcode】-精选top面试
56. 合并区间
给出一个区间的集合,请合并所有重叠的区间。
示例 1:
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
通过次数72,050提交次数174,657
知识点:列表排序
a = [[8,10],[1,3],[2,6],[15,18]]
a.sort(key=lambda x: x[0]) # 此处的x就是每一个区间元素,默认用首元素排序,此处可以不写
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
if not intervals:
return []
intervals.sort() # 按照首元素升序排列
merged = []
merged.append(intervals[0])
for lst in intervals[1:]:
if lst[0] > merged[-1][1]:
merged.append(lst)
else:
merged[-1][1] = max(lst[1], merged[-1][1])
return merged
# 复习 列表去重
a = [1,5,8,3,2,1,5]
b = sorted(set(a), key=a.index)
b
[1, 5, 8, 3, 2]
c = list(set(a))
c.sort(key=a.index)
c
[1, 5, 8, 3, 2]
d= list(set(a)).sort(key=a.index) # 但是这样输出为空
d
1. 两数之和
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
方法1知识点:列表排序,反求索引,列表重复值不同索引 NlogN
方法2知识点:利用哈希表记录元素和索引,然后直接查target-当前值是否在dict中。O(N)O(N)
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
lst = sorted(nums)
l, r = 0, len(lst)-1
while l < r:
if lst[l] + lst[r] == target:
if lst[l] == lst[r]:
res = [x for x in range(len(nums)) if nums[x] == lst[l]] # 重复值索引
return res[:2]
else:
return [nums.index(lst[l]), nums.index(lst[r])]
elif lst[l] + lst[r] < target:
l += 1
else:
r -= 1
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
if not nums:
return []
back_dict = {}
for i in range(len(nums)): # 记录数值和索引
if back_dict.get(nums[i], -1) == -1:
back_dict[nums[i]] = [i]
else:
back_dict[nums[i]].append(i)
# print(back_dict)
for num in nums: # 可以归并到上面的循环中
if back_dict.get(target - num, -1) == -1:
continue
elif num != target-num:
print(num, 'here')
return [back_dict[num][0], back_dict[target-num][0]]
elif len(back_dict[num]) > 1:
return [back_dict[num][0], back_dict[num][1]]
2. 两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
知识点:链表。亮点:root的首元素实际上没有意义,只是为了开创,返回从next开始,好处是避免头部进位的讨论,简化代码。
解惑:链表赋值类似于list,数值是共享的,内存也是共享的。就是别名而已。
# 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:
carry = 0
root = ListNode(0)
temp = root
while l1 or l2:
a = b = 0
if l1:
a = l1.val
l1 = l1.next
if l2:
b = l2.val
l2 = l2.next
s = (a+b+carry) % 10
carry = (a+b+carry) // 10
node = ListNode(s)
temp.next = node
temp = node
if carry != 0:
node = ListNode(carry)
temp.next = node
return root.next
3. 无重复字符的最长子串
给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
思路1:方法一采用了动规的方法:状态转移:如果当前字符不在前一字符所在的窗口,则max加一,否则在前一窗口找到当前char的索引截断。
思路2:方法一种需要判断char是否在某个子字符串中,造成复杂度增加,考虑用哈希表和一个ignore抵达索引来换取时间。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
res = ret = 1
for i in range(1, len(s)):
if s[i] in s[i-res: i]:
res = res - (1+ s[i-res: i].index(s[i])) + 1
else:
res += 1
ret = max(ret, res)
return ret
class Solution(object):
def lengthOfLongestSubstring(self, s: str) -> int:
ignore_str_index_end = -1
dic = {}
max_length = 0
for i, c in enumerate(s):
# 索引都会大于等于0,新字符的索引为-1,否则为已经出现
# 第二个条件是因为ignore机制已经截断了重复char以及之前的char
if dic.get(c, -1) != -1 and dic[c] > ignore_str_index_end:
ignore_str_index_end = dic[c] # 无效推进
dic[c] = i
else:
dic[c] = i
max_length = max(i - ignore_str_index_end, max_length)
return max_length
7. 整数反转
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例 1:输入: 123 输出: 321
示例 2:输入: -123输出: -321
示例 3:输入: 120 输出: 21
注意:
假设我们的环境只能存储得下 32 位的有符号整数,则其数值范围为 [−231, 231 − 1]。请根据这个假设,如果反转后整数溢出那么就返回 0。
class Solution:
def reverse(self, x: int) -> int:
y, res = abs(x), 0
# 则其数值范围为 [−2^31, 2^31 − 1]
boundry = (1<<31) -1 if x>0 else 1<<31
while y != 0:
res = res*10 +y%10
if res > boundry :
return 0
y //=10
return res if x >0 else -res
3
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 “”。
示例 1:
输入: [“flower”,“flow”,“flight”]
输出: “fl”
示例 2:
输入: [“dog”,“racecar”,“car”]
输出: “”
解释: 输入不存在公共前缀。
思路1:逐个单词比较(推荐)
思路二:逐个index比较
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if len(strs) == 0:
return ''
s = strs[0] # 第一个单词
for i in range(1, len(strs)):
while strs[i].find(s) != 0 : # 只有是公共前缀才会返回0,否则返回索引或者-1
s = s[:-1]
if len(s) == 0:
break
return s
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
if not strs or not strs[0]:
return ""
strs.sort(key=len)
flag, i = False, 0
for i in range(0, len(strs[0])): # 不同index
for j in range(1,len(strs)): # 不同单词
if strs[j][i] != strs[0][i]:
flag = True
break
if flag:
i -= 1
break
return strs[0][:i+1]
'abc'.find('e')
-1
['a'][:-1][:-1]
[]
15. 三数之和
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
算法流程:
1特判,对于数组长度 nn,如果数组为 nullnull 或者数组长度小于 33,返回 [][]。
2对数组进行排序。
3遍历排序后数组:
若 nums[i]>0nums[i]>0:因为已经排序好,所以后面不可能有三个数加和等于 00,直接返回结果。
对于重复元素:跳过,避免出现重复解
令左指针 L=i+1L=i+1,右指针 R=n-1R=n−1,当 L<RL<R 时,执行循环:
当 nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]==0,循环,判断左界和右界是否和下一位置重复,
去除重复解。并同时将 L,RL,R 移到下一位置,寻找新的解
若和大于 0,说明 nums[R] 太大,R 左移
若和小于 0,说明 nums[L] 太小,L 右移
class Solution: # 1000ms
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
if (not nums or n < 3):
return []
nums.sort()
res = []
for i in range(n):
if (nums[i] > 0):
return res
if (i > 0 and nums[i] == nums[i - 1]):
continue
L, R = i + 1, n - 1
while (L < R):
if (nums[i] + nums[L] + nums[R] == 0):
res.append([nums[i], nums[L], nums[R]])
L = bisect.bisect_right(nums, nums[L])
R = bisect.bisect_left(nums, nums[R])
elif (nums[i] + nums[L] + nums[R] > 0):
R = R - 1
else:
L = L + 1
return res
class Solution: # 100ms
def threeSum(self, nums: List[int]) -> List[List[int]]:
ans = []
counts = {}
for i in nums:
counts[i] = counts.get(i, 0) + 1
nums = sorted(counts)
for i, num in enumerate(nums):
if counts[num] > 1:
if num == 0:
if counts[num] > 2:
ans.append([0, 0, 0])
else:
if -num * 2 in counts:
ans.append([num, num, -2 * num])
if num < 0:
two_sum = -num
left = bisect.bisect_left(nums, (two_sum - nums[-1]), i + 1)
for i in nums[left: bisect.bisect_right(nums, (two_sum // 2), left)]:
j = two_sum - i
if j in counts and j != i:
ans.append([num, i, j])
return ans
# 如果不用去重的话,可以用分治
def fun(l, r, num, lst, target=0):
if num == 1: # 边界条件
for k in range(l, r+1): # 确保r可以取到
if lst[k] == target:
return [lst[k]]
return []
res = []
for i in range(l, r+1):
rest = fun(i+1, r, num-1, lst, target=target-lst[i])
for cans in rest:
res.append([cans] + [lst[i]]) if isinstance(cans, int) else res.append(cans + [lst[i]])
return res
17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。
示例:
输入:“23”
输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。
思路:分治
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
back_dic = {
'2':['a', 'b', 'c'],
'3':['d', 'e', 'f'],
'4':['g', 'h', 'i'],
'5':['j', 'k', 'l'],
'6':['m', 'n', 'o'],
'7':['p', 'q', 'r', 's'],
'8':['t', 'u', 'v'],
'9':['w', 'x', 'y', 'z'],
}
def combine(lst1, lst2):
res = []
for i in lst1:
for j in lst2:
res.append(i+j)
return res
def for_ward(l=0):
if l == len(digits)-1:
return back_dic[digits[l]]
return combine(back_dic[digits[l]], for_ward(l+1))
return for_ward()
class Solution:
def letterCombinations(self, digits):
if not digits:
return []
back_dic = {
'2':['a', 'b', 'c'],
'3':['d', 'e', 'f'],
'4':['g', 'h', 'i'],
'5':['j', 'k', 'l'],
'6':['m', 'n', 'o'],
'7':['p', 'q', 'r', 's'],
'8':['t', 'u', 'v'],
'9':['w', 'x', 'y', 'z'],
}
global res
res = back_dic[digits[0]]
def combine(lst1, lst2):
ret = []
for i in lst1:
for j in lst2:
ret.append(i+j)
return ret
def for_ward(l=1):
if l == len(digits):
return
global res
res = combine(res, back_dic[digits[l]])
for_ward(l + 1)
for_ward()
return res
26. 删除排序数组中的重复项
给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
知识点:双指针
class Solution:
def removeDuplicates(self, nums) -> int:
l = len(nums)
if l < 2:
return l
now = left = count = 0
while now < l:
while now < l and nums[now]==nums[left]:
now += 1
if now < l:
nums[left + 1] = nums[now]
left += 1 # 每次移动之后两指针数据相同,保证now步进
count += 1
return count + 1
34. 在排序数组中查找元素的第一个和最后一个位置
给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果数组中不存在目标值,返回 [-1, -1]。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]
思路:二分
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums:
return [-1, -1]
if len(nums) == 1:
return [0, 0] if nums[0] == target else [-1, -1]
l, r = 0, len(nums) - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid
elif nums[mid] > target:
r = mid
else: # mid 就是目标值
while nums[l] != target:
if nums[l] < nums[mid]:
l += 1
if nums[l] == nums[mid]:
break
while nums[r] != target:
if nums[r] > nums[mid]:
r -= 1
if nums[r] == nums[mid]:
break
return [l, r]
if l + 1 == r or l == r : # 当目标值小于target 会出现第二种情况,当然也可以合并到开始作为特例:【2,2】-1
if nums[r] == target:
return [r, r]
if nums[l] == target:
return [l, l]
else:
return [-1, -1]
上一篇: 简单vue路由卫士例子
下一篇: python爬取抖音视频-完美亲测
推荐阅读
-
leetcode面试题17.04小白能回,通透,简易,res的思路
-
阿里P8架构总结:不得不会的124道精选的Java面试题分享
-
LeetCode 面试题56 - I. 数组中数字出现的次数
-
Leetcode刷题记录——面试题48. 最长不含重复字符的子字符串
-
top面试121.买卖股票的最佳时机
-
leetcode 160剑指offer面试题52. 两个链表的第一个公共节点(python3)
-
leetcode 面试题32 (剑指offer)- II. 从上到下打印二叉树 II(python3)
-
leetcode 113 剑指offer 面试题34. 二叉树中和为某一值的路径(python3)
-
leetcode 面试题32 - III. 从上到下打印二叉树 III(python3)
-
LeetCode刷题笔记(Top K Frequent Elements)