- 来源于leetcode题库
3,31,48,56,146,208,215,238,399
3.无重复字符的最长子串
-
题目描述
- 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
- enumerate() 函数
- 用于将一个可遍历的数据对象(如列表、元组或字符串)组合为一个索引序列，同时列出数据和数据下标，一般用在 for 循环当中。
普通for循环
i = 0
seq = ['one', 'two', 'three']
for element in seq:
... print i, seq[i]
... i +=1
...
输出：
0 one
1 two
2 three
for循环使用enumerate函数
seq = ['one', 'two', 'three']
for i, element in enumerate(seq):
...print i, element
...
输出：
0 one
1 two
2 three
- 题解：
class Solution:
#以字符串的值为key，以下标为value
def lengthOfLongestSubstring(self, s: str) -> int:
#初始化
start,res,newdic=-1,0,{}
#按循环顺序，把s中的元素挨个放到新的newdic里去
for i,c in enumerate(s):
#如果c已经在newdic中且下标比start大
if c in newdic and newdic[c]>start:
start=newdic[c]#重新定位start指针
newdic[c]=i#给这个重复字母赋上顺序值
#newdic里还没有这个重复字母，且不需要重新定位指针
else:
newdic[c]=i
res=max(res,i-start) #更新最大子串长度
return res
31.
-
题目描述
- 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
- 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
示例
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
- 题解
48.旋转图像
-
题目描述
- 给定一个 n × n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
- 给定一个 n × n 的二维矩阵表示一个图像。
示例
给定 matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
原地旋转输入矩阵，使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
- 题解
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
'''
分层平移的策略，左上角坐标为(pos1,pos1),右上角(pos1,pos2)
左下角作为(pos2,pos1),右下角(pos2,pos)
'''
pos1,pos2 = 0,len(matrix)-1
while pos1<pos2:
add = 0
while add < pos2-pos1: # 有偏移量
#左上角为0块，右上角为1块，右下角为2块，左下角为3块
temp = matrix[pos2-add][pos1]
matrix[pos2-add][pos1] = matrix[pos2][pos2-add]
#3 = 2
matrix[pos2][pos2-add] = matrix[pos1+add][pos2]
#2 = 1
matrix[pos1+add][pos2] = matrix[pos1][pos1+add]
#1 = 0
matrix[pos1][pos1+add] = temp
#0 = temp
add = add+1
pos1 = pos1+1
pos2 = pos2-1
56.合并区间
- 题目描述
- 给出一个区间的集合，请合并所有重叠的区间。
- 示例
示例 1:
输入: intervals = [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入: intervals = [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。
- 题解
- 来源于题解区大佬
莲子熊猫
- 来源于题解区大佬
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 本题要点为先按左边界排序
if len(intervals) == 0:
return []
res = []
# 先按区间左边界值由小到大排序
intervals.sort(key=lambda x: x[0])
for inter in intervals:
# 如果结果集最后一个元素的右边界比新加入区间的左边界小，直接加入结果集
if len(res) == 0 or res[-1][1] < inter[0]:
res.append(inter)
else: # 否则，说明新加入的和结果集最后一个区间有重合，更新区间右边界即可
res[-1][1] = max(res[-1][1], inter[1])
return res
146.LRU缓存机制
-
题目描述
- 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
- 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
示例
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得关键字 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
- 题解
- 来源于题解区大佬
liye
- 来源于题解区大佬
class ListNode:
# 用哈希表和双链表实现
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = {}
# 新建两个节点 head 和 tail
self.head = ListNode()
self.tail = ListNode()
# 初始化链表为 head <-> tail
self.head.next = self.tail
self.tail.prev = self.head
# 因为get与put操作都可能需要将双向链表中的某个节点移到末尾，所以定义一个方法
def move_node_to_tail(self, key):
# 先将哈希表key指向的节点拎出来，为了简洁起名node
# hashmap[key] hashmap[key]
# | |
# V --> V
# prev <-> node <-> next pre <-> next ... node
node = self.hashmap[key]
node.prev.next = node.next
node.next.prev = node.prev
# 之后将node插入到尾节点前
# hashmap[key] hashmap[key]
# | |
# V --> V
# prev <-> tail ... node prev <-> node <-> tail
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key: int) -> int:
if key in self.hashmap:
# 如果已经在链表中了久把它移到末尾（变成最新访问的）
self.move_node_to_tail(key)
res = self.hashmap.get(key, -1)
if res == -1:
return res
else:
return res.value
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
# 如果key本身已经在哈希表中了就不需要在链表中加入新的节点
# 但是需要更新字典该值对应节点的value
self.hashmap[key].value = value
# 之后将该节点移到末尾
self.move_node_to_tail(key)
else:
if len(self.hashmap) == self.capacity:
# 去掉哈希表对应项
self.hashmap.pop(self.head.next.key)
# 去掉最久没有被访问过的节点，即头节点之后的节点
self.head.next = self.head.next.next
self.head.next.prev = self.head
# 如果不在的话就插入到尾节点前
new = ListNode(key, value)
self.hashmap[key] = new
new.prev = self.tail.prev
new.next = self.tail
self.tail.prev.next = new
self.tail.prev = new
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
208.
- 题目描述
- 实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
- 示例
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
- 题解
- 来源于题解区大佬
powcai
- 来源于题解区大佬
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.lookup = {}
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
tree = self.lookup
for a in word:
if a not in tree:
tree[a] = {}
tree = tree[a]
# 单词结束标志
tree["#"] = "#"
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
tree = self.lookup
for a in word:
if a not in tree:
return False
tree = tree[a]
if "#" in tree:
return True
return False
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
tree = self.lookup
for a in prefix:
if a not in tree:
return False
tree = tree[a]
return True
# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)
215.数组中第k个最大元素
-
题目描述
- 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4题解
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
# 堆排序
def adjust_heap(idx, max_len):
left = 2 * idx + 1
right = 2 * idx + 2
max_loc = idx
if left < max_len and nums[max_loc] < nums[left]:
max_loc = left
if right < max_len and nums[max_loc] < nums[right]:
max_loc = right
if max_loc != idx:
nums[idx], nums[max_loc] = nums[max_loc], nums[idx]
adjust_heap(max_loc, max_len)
# 建堆
n = len(nums)
for i in range(n // 2 - 1, -1, -1):
adjust_heap(i, n)
#print(nums)
res = None
for i in range(1, k + 1):
#print(nums)
res = nums[0]
nums[0], nums[-i] = nums[-i], nums[0]
adjust_heap(0, n - i)
return res
238.除自身以外数组的乘积
-
题目描述
- 给你一个长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例
输入: [1,2,3,4]
输出: [24,12,8,6]
- 题解
- 来源于题解区大佬
krahets
- 来源于题解区大佬
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
'''
res数组列为乘积形式(当前位置数字不相乘可以等价为乘1)
res[0] = 1 * nums[1] * nums[2] ... * nums[n-1]
res[1] = nums[0] * 1 * nums[2] ... * nums[n-1]
...
res[n-1] = nums[0] * nums[1] ... * nums[n-2] * 1
经过上述排列可发现矩阵主对角线上全为1，分别计算矩阵的上三角和下三角，并存储值
'''
res, p, q = [1], 1, 1
for i in range(len(nums) - 1): # 下三角
p *= nums[i]
res.append(p)
for i in range(len(nums) - 1, 0, -1): # 上三角
q *= nums[i]
res[i - 1] *= q
return res
399.
题目描述
示例
题解
