Python常见算法和数据结构练习
发布于 2019-08-29 · 本文总共 39459 字 · 阅读大约需要
113 分钟
数组
数组中重复的数字
description
面试题03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
限制：
2 <= n <= 100000
solutions
class Solution(object):
def findRepeatNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
# 排序；O(nlgn);O(1)
nums = sorted(nums)
pre = None
for i in range(len(nums)):
if pre == nums[i]:
return pre
pre = nums[i]
# 哈希表；O(n);O(n)
# hash_map = {}
# for num in nums:
# if num in hash_map:
# return num
# else:
# hash_map[num] = 1
# ；O(n);O(1)
# for i in range(len(nums)):
# while i != nums[i]:
# if nums[nums[i]] == nums[i]:
# return nums[i]
# nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
二维数组中的查找
description
面试题04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
solutions
best solution
O(m+n)
class Solution(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
if not matrix or not matrix[0]:
return False
col_len = len(matrix)
row_len = len(matrix[0])
i = 0
j = row_len -1
while i < col_len and j >= 0:
if matrix[i][j] == target:
return True
elif matrix[i][j] > target:
j -= 1
else:
i += 1
return False
binary search
mlgn
class Solution1(object):
def findNumberIn2DArray(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
# matrix = list(zip(matrix))
if not matrix or not matrix[0]:
return False
col_len = len(matrix)
row_len = len(matrix[0])
def binary_find(arr):
l,r = 0, len(arr)-1
while l <= r:
mid = (l + r) / 2
if target < arr[mid]:
r = mid - 1
elif target > arr[mid]:
l = mid + 1
else:
return True
return False
for i in range(col_len):
if matrix[i][row_len-1] >= target:
res = binary_find(matrix[i])
if res:
return True
else:
continue
return False
violence solution
m*n
class Solution2(object):
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
for nums in matrix:
for num in nums:
if num == target:
return True
return False
链表
1.反转链表
https://leetcode.com/problems/reverse-linked-list/
206. Reverse Linked List
Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?
206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
solutions
1.迭代
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
pre, cur = None, head
while cur:
tmp = cur.next
pre, cur.next = cur, pre
cur = tmp
return pre
2.递归
class Solution1(object):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
p = self.reverseList(head.next)
head.next.next = head
head.next = None
return p
2.环形链表
https://leetcode.com/problems/linked-list-cycle
description
141. 环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
141. Linked List Cycle
Given a linked list, determine if it has a cycle in it.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the slow node.
Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the fast node.
Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
solutions
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return False
fast, slow = head.next, head
while fast and fast.next and slow:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
3.两两交换链表中的节点
https://leetcode.com/problems/swap-nodes-in-pairs
description
24. Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.
24. 两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例:
给定 1->2->3->4, 你应该返回 2->1->4->3.
solutions
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
node1 = head
node2 = head.next
p = self.swapPairs(head.next.next)
node2.next = node1
node1.next = p
return node2
简化
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def swapPairs(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
res = head.next
head.next = self.swapPairs(head.next.next)
res.next = head
return res
4.环形链表 II
https://leetcode.com/problems/linked-list-cycle-ii
description
142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
说明：不允许修改给定的链表。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：tail connects to node index 1
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0
输出：tail connects to node index 0
解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1
输出：no cycle
解释：链表中没有环。
进阶：
你是否可以不用额外空间解决此题？
142. Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
Follow-up:
Can you solve it without using extra space?
solutions
哈希表
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
node_map = {}
while head:
if head in node_map:
return head
else:
node_map[head] = head
head = head.next
return None
快慢指针
假设有环，且入口之前有a个节点，环有b个节点 相遇时，快指针走了2s路程，慢指针走s路程， 2s - s = nb,即s=n*b
要找到a，快指针回到head，再次相遇时走了a+m*b的路程，即是入口
class Solution1(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = head
fast = head
while slow and fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if not slow or not fast or not fast.next :
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
# print(fast)
return slow
K个一组翻转链表
https://leetcode.com/problems/reverse-nodes-in-k-group/
description
25. K个一组翻转链表
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
示例：
给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5
说明：
你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
25. Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
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
Note:
Only constant extra memory is allowed.
You may not alter the values in the list's nodes, only nodes itself may be changed.
solutions
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def reverseList(self, head, k):
"""
:type head: ListNode
:rtype: ListNode
"""
t = head
tmp, pre, cur = None, None, head
while cur and k > 0:
tmp = cur.next
pre, cur.next = cur, pre
cur = tmp
k -= 1
return pre, t
def reverseKGroup(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
cur = head
dummy = ListNode(0)
dummy.next = head
n = 0
pre, cur = head, head
tail = dummy
while 1:
if n % k == 0 and n / k > 0:
fast = cur
kk = k
while fast and kk > 0:
fast = fast.next
kk -= 1
h, t = self.reverseList(pre, k)
tail.next = h
t.next = cur
pre = cur
tail = t
if not cur:
break
cur = cur.next
n += 1
return dummy.next
堆栈、队列
用栈实现队列
https://leetcode.com/problems/implement-queue-using-stacks/
description
232. 用栈实现队列
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
232. Implement Queue using Stacks
Implement the following operations of a queue using stacks.
push(x) -- Push element x to the back of queue.
pop() -- Removes the element from in front of queue.
peek() -- Get the front element.
empty() -- Return whether the queue is empty.
Example:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // returns 1
queue.pop(); // returns 1
queue.empty(); // returns false
Notes:
You must use only standard operations of a stack -- which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).
solutions
class MyQueue(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.stack_in = []
self.stack_out = []
def push(self, x):
"""
Push element x to the back of queue.
:type x: int
:rtype: None
"""
self.stack_in.append(x)
def pop(self):
"""
Removes the element from in front of queue and returns that element.
:rtype: int
"""
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
res = self.stack_out.pop()
return res
def peek(self):
"""
Get the front element.
:rtype: int
"""
if not self.stack_out:
while self.stack_in:
self.stack_out.append(self.stack_in.pop())
res = self.stack_out[-1] if self.stack_out else None
return res
def empty(self):
"""
Returns whether the queue is empty.
:rtype: bool
"""
return not self.stack_in and not self.stack_out
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
用队列实现栈
https://leetcode.com/problems/implement-stack-using-queues/
description
225. Implement Stack using Queues
Implement the following operations of a stack using queues.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
empty() -- Return whether the stack is empty.
Example:
MyStack stack = new MyStack();
stack.push(1);
stack.push(2);
stack.top(); // returns 2
stack.pop(); // returns 2
stack.empty(); // returns false
Notes:
You must use only standard operations of a queue -- which means only push to back, peek/pop from front, size, and is empty operations are valid.
Depending on your language, queue may not be supported natively. You may simulate a queue by using a list or deque (double-ended queue), as long as you use only standard operations of a queue.
You may assume that all operations are valid (for example, no pop or top operations will be called on an empty stack).
225. 用队列实现栈
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
solutions
class MyStack(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.queue = collections.deque()
def push(self, x):
"""
Push element x onto stack.
:type x: int
:rtype: None
"""
self.queue.append(x)
for _ in range(len(self.queue) - 1):
self.queue.append(self.queue.pop())
def pop(self):
"""
Removes the element on top of the stack and returns that element.
:rtype: int
"""
return self.queue.pop()
def top(self):
"""
Get the top element.
:rtype: int
"""
res = self.pop()
self.push(res)
return res
def empty(self):
"""
Returns whether the stack is empty.
:rtype: bool
"""
return len(self.queue) == 0
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
有效的括号
https://leetcode.com/problems/valid-parentheses/description/
description
20. Valid Parentheses
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.
Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
solutions
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
left = ['(', '{', '[']
right = [')', '}', ']']
h_map = {}
for i in range(len(right)):
h_map[right[i]] = left[i]
stack_ = []
for i in range(len(s)):
if s[i] in left:
stack_.append(s[i])
else:
if not stack_ or stack_[-1] != h_map[s[i]]:
return False
stack_.pop()
if not stack_:
return True
return False
堆
数据流中的第K大元素
https://leetcode.com/problems/kth-largest-element-in-a-stream/
description
703. 数据流中的第K大元素
设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。
示例:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。
703. Kth Largest Element in a Stream
Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.
Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.
Example:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
Note:
You may assume that nums' length ≥ k-1 and k ≥ 1.
solutions
import heapq
class KthLargest(object):
def __init__(self, k, nums):
"""
:type k: int
:type nums: List[int]
"""
self.k = k
self.h = nums
heapq.heapify(self.h)
for i in range(len(nums) - k):
heapq.heappop(self.h)
def add(self, val):
"""
:type val: int
:rtype: int
"""
if len(self.h) < self.k:
heapq.heappush(self.h, val)
else:
if self.h[0] < val:
heapq.heappop(self.h)
heapq.heappush(self.h, val)
# Your KthLargest object will be instantiated and called as such:
# obj = KthLargest(k, nums)
# param_1 = obj.add(val)
滑动窗口最大值
description
239. 滑动窗口最大值
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
进阶：
你能在线性时间复杂度内解决此题吗？
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:
滑动窗口的位置 最大值
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
提示：
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
239. Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
Follow up:
Could you solve it in linear time?
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Constraints:
1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length
solutions
暴力破解
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or not k:
return []
res = []
for i in range(len(nums)-k+1):
res.append(max(nums[i:i+k]))
return res
单调队列
class Solution1(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if not nums or not k:
return []
res = []
q = []
maxs = []
for i in range(len(nums)):
num = nums[i]
q.append(num)
while maxs and num > maxs[-1]:
maxs.pop()
maxs.append(num)
# print(maxs)
if len(q) >= k:
res.append(maxs[0])
val = q.pop(0)
if val == maxs[0]:
maxs.pop(0)
return res
哈希表
两数之和
https://leetcode.com/problems/two-sum/
description
1. 两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
solutions
哈希
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
num_dict = dict()
for i, num in enumerate(nums):
if num_dict.get(target - num) is not None:
return num_dict[target - num], i
num_dict[num] = i
return None
双指针法
class Solution1(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# hash_map = {}
# for num in nums:
# if num in hash_map:
# return [hash_map[num], num]
# else:
# hash_map[target-num] = num
# return []
i, j = 0, len(nums) - 1
while i < j:
sum_ = nums[i] + nums[j]
if sum_ > target:
j -= 1
elif sum_ < target:
i += 1
else:
return [nums[i], nums[j]]
三数之和
https://leetcode.com/problems/3sum/
description
15. 3Sum
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
15. 三数之和
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]
solutions
class Solution(object):
def twoSum(self, nums, target):
tg_map = {}
res = []
for num in nums:
if num in tg_map:
res.append([num, target - num])
else:
tg_map[target - num] = num
return res
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
length = len(nums)
res = []
res_dict = {}
if length < 3:
return []
if len(set(nums)) == 1:
if nums[0] == 0:
return [[0,0,0]]
return []
for i in range(length):
j = i + 1
target = 0 - nums[i]
tg_list = self.twoSum(nums[j:], target)
for tg in tg_list:
new_ = sorted([nums[i], tg[0], tg[1]])
key = "".join([str(x) for x in new_])
res_dict[key] = new_
for k, value in res_dict.items():
res.append(value)
return res
4sum
https://leetcode.com/problems/4sum/
description
18. 四数之和
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：
答案中不可以包含重复的四元组。
示例：
给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
满足要求的四元组集合为：
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
18. 4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Example:
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
solutions
class Solution(object):
def twoSum(self, nums, target):
res = []
hash_map = {}
for i in range(len(nums)):
if nums[i] in hash_map:
res.append((hash_map[nums[i]], nums[i]))
else:
hash_map[target -nums[i]] = nums[i]
return res
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
res = []
nums.sort()
pre = None
for i in range(len(nums)):
for j in range( i +1, len(nums)):
sum_ = nums[i] + nums[j]
if pre == (nums[i], nums[j]):
continue
t_s = self.twoSum(nums[ j +1:], target - sum_)
if not t_s:
continue
for t in t_s:
new_res = sorted((nums[i], nums[j], t[0], t[1]))
if new_res not in res:
res.append(new_res)
pre = (nums[i], nums[j])
return res
group-anagrams
https://leetcode.com/problems/group-anagrams/
description
49. 字母异位词分组
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
49. Group Anagrams
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
All inputs will be in lowercase.
The order of your output does not matter.
solutions
import collections
class Solution(object):
def groupAnagrams(self, strs):
"""
:type strs: List[str]
:rtype: List[List[str]]
"""
hash_map = collections.defaultdict(list)
for word in strs:
# key = "".join(sorted(word))
key = tuple(sorted(word))
hash_map[key].append(word)
return hash_map.values()
树
验证二叉搜索树
https://leetcode.com/problems/validate-binary-search-tree
description
98. 验证二叉搜索树
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:
输入:
2
/ \
1 3
输出: true
示例 2:
输入:
5
/ \
1 4
/ \
3 6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
根节点的值为 5 ，但是其右子节点值为 4 。
98. Validate Binary Search Tree
Given a binary tree, determine if it is a valid binary search tree (BST).
Assume a BST is defined as follows:
The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.
Example 1:
2
/ \
1 3
Input: [2,1,3]
Output: true
Example 2:
5
/ \
1 4
/ \
3 6
Input: [5,1,4,null,null,3,6]
Output: false
Explanation: The root node's value is 5 but its right child's value is 4.
solution
# 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 isValidBST(self, root):
"""
:type root: TreeNode
:rtype: bool
"""
# self.vals = []
# def dfs(root):
# if not root:
# return True
# dfs(root.left)
# self.vals.append(root.val)
# dfs(root.right)
# dfs(root)
# for i in range(1, len(self.vals)):
# if self.vals[i] <= self.vals[i-1]:
# return False
# return True
self.res = True
self.pre = None
def dfs(root):
if not root:
return True
if not dfs(root.left):
return False
if self.pre is not None and root.val <= self.pre:
return False
self.pre = root.val
if not dfs(root.right):
return False
return True
return dfs(root)
二叉搜索树的最近公共祖先
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/
description
235. Lowest Common Ancestor of a Binary Search Tree
Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given binary search tree: root = [6,2,8,0,4,7,9,null,null,3,5]
Example 1:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.
Example 2:
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.
Note:
All of the nodes' values will be unique.
p and q are different and both values will exist in the BST.
235. 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]
示例 1:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6
解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。
solutions
递归
# 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 lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
val_root = root.val
p_val = min(p.val, q.val)
q_val = max(p.val, q.val)
if val_root > q_val:
return self.lowestCommonAncestor(root.left, p, q)
elif val_root < p_val:
return self.lowestCommonAncestor(root.right, p, q)
else:
return root
迭代
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution1(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
p_val = min(p.val, q.val)
q_val = max(p.val, q.val)
while root:
val_root = root.val
if val_root > q_val:
root = root.left
elif val_root < p_val:
root = root.right
else:
return root
二叉树的最近公共祖先
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
description
236. Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
Note:
All of the nodes' values will be unique.
p and q are different and both values will exist in the binary tree.
236. 二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
示例 1:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
示例 2:
输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
说明:
所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉树中。
solution
递归
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution1(object):
def lowestCommonAncestor(self, root, p, q):
"""
:type root: TreeNode
:type p: TreeNode
:type q: TreeNode
:rtype: TreeNode
"""
# print(root, p, q)
if not root:
return None
if root.val == p.val or root.val == q.val:
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right:
return root
if not left:
return right
return left
二叉树遍历
前序、中序、后序的统一模板处理：
stack_t = [(0, root)]
res = []
while stack_t:
c, node = stack_t.pop()
if node:
if c == 0:
# 按先进后出的顺序入栈，以下为“左、中、右”，中序遍历
stack_t.append((0, node.right))
stack_t.append((1, node))
stack_t.append((0, node.left))
else:
res.append(node.val)
return res
二叉树的前序遍历
https://leetcode.com/problems/binary-tree-preorder-traversal/
description
144. 二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
144. Binary Tree Preorder Traversal
Given a binary tree, return the preorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?
solutions
递归
# 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 preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# if not root:
# return []
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) if root else []
迭代
class Solution1(object):
def preorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack_t = [root]
res = []
while stack_t:
node = stack_t.pop()
if node:
res.append(node.val)
if node.right:
stack_t.append(node.right)
if node.left:
stack_t.append(node.left)
return res
二叉树的后序遍历
description
145. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
145. Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [3,2,1]
Follow up: Recursive solution is trivial, could you do it iteratively?
solutions
递归
# 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 postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val] if root else []
迭代
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution1(object):
def postorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
# return self.postorderTraversal(root.left) + self.postorderTraversal(root.right) + [root.val] if root else []
stack_t = [root]
res = []
while stack_t:
node = stack_t.pop()
if node:
res.append(node.val)
if node.left:
stack_t.append(node.left)
if node.right:
stack_t.append(node.right)
return res[::-1]
二叉树中序遍历
description
94. 二叉树的中序遍历
给定一个二叉树，返回它的中序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,3,2]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
94. Binary Tree Inorder Traversal
Given a binary tree, return the inorder traversal of its nodes' values.
Example:
Input: [1,null,2,3]
1
\
2
/
3
Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?
solutions
递归
# 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 inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
return self.inorderTraversal(root.left) + [root.val] + self.inorderTraversal(root.right) if root else []
迭代
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution1(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack_t = [(0, root)]
res = []
while stack_t:
c, node = stack_t.pop()
if node:
if c == 0:
stack_t.append((0, node.right))
stack_t.append((1, node))
stack_t.append((0, node.left))
else:
res.append(node.val)
return res
迭代1(不推荐)
class Solution1(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.vals = []
stack = []
cur = root
while cur or stack:
while cur:
stack.append(cur)
cur = cur.left
cur = stack.pop()
self.vals.append(cur.val)
cur = cur.right
print(self.vals)
return self.vals
BFS&DFS
二叉树的层次遍历
https://leetcode.com/problems/binary-tree-level-order-traversal/
description
102. Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
102. 二叉树的层次遍历
给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]
solutions
# 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 levelOrder(self, root):
"""
:type root: TreeNode
:rtype: List[List[int]]
"""
res = []
def deep_trave(root, deepth, res=[]):
if not root:
return res
if len(res) < deepth + 1:
res.append([root.val])
else:
res[deepth].append(root.val)
deep_trave(root.left, deepth + 1, res)
deep_trave(root.right, deepth + 1, res)
return res
res = deep_trave(root, 0, res=res)
return res
二叉树的最大深度
https://leetcode.com/problems/maximum-depth-of-binary-tree/
description
104. 二叉树的最大深度
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7]，
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
104. Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
solutions
递归
# 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 maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1 if root else 0
迭代
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution1(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
stack = []
if root:
stack.append((1, root))
deepth = 0
while stack:
cur, node = stack.pop()
deepth = max(deepth, cur)
if node.left:
stack.append((cur+1, node.left))
if node.right:
stack.append((cur+1, node.right))
return deepth
二叉树的最小深度
https://leetcode.com/problems/minimum-depth-of-binary-tree/
description
111. Minimum Depth of Binary Tree
Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度 2.
solutions
迭代
# 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 minDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def deep_trave(root):
if not root:
return 0
if not root.left:
return deep_trave(root.right) + 1
if not root.right:
return deep_trave(root.left) + 1
return min(deep_trave(root.left), deep_trave(root.right)) + 1
return deep_trave(root)
括号生成
https://leetcode.com/problems/generate-parentheses/
descriptions
22. Generate Parentheses
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
22. 括号生成
给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。
例如，给出 n = 3，生成结果为：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
solutions
回溯
class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
self.vals = []
def bk(res, l, r):
if l == 0 and r == 0:
val = "".join(res)
self.vals.append(val)
else:
new_res = res[:]
if l > 0:
bk(new_res+["("], l-1, r)
if r > l and r > 0:
bk(new_res + [")"], l, r-1)
bk([], n, n)
return self.vals
递归
class Solution1(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""
if n == 0:
return []
if n == 1:
return ["()"]
vals = self.generateParenthesis(n-1)
res = []
for i in range(len(vals)):
for j in range(len(vals[i])):
new_p = vals[i][:j] + "()" + vals[i][j:]
if new_p not in res:
res.append(new_p)
return res
图
字典树
实现 Trie (前缀树)
https://leetcode.com/problems/implement-trie-prefix-tree/
description
208. 实现 Trie (前缀树)
实现一个 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
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
208. Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
Example:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // returns true
trie.search("app"); // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app"); // returns true
Note:
You may assume that all inputs are consist of lowercase letters a-z.
All inputs are guaranteed to be non-empty strings.
solutions
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
tree = self.root
for w in word:
if tree is None or not tree.get(w):
tree[w] = {}
tree = tree.get(w)
tree["end"] = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
tree = self.root
for w in word:
tree = tree.get(w)
if tree is None:
print(tree)
tree = tree.items()
# return False
return True if tree.get("end") else False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
tree = self.root
for w in prefix:
tree = tree.get(w)
if tree is None:
return False
return True
word-search-ii
https://leetcode.com/problems/word-search-ii/
description
212. 单词搜索 II
给定一个二维网格 board 和一个字典中的单词列表 words，找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
输入:
words = ["oath","pea","eat","rain"] and board =
[
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
输出: ["eat","oath"]
说明:
你可以假设所有输入都由小写字母 a-z 组成。
提示:
你需要优化回溯算法以通过更大数据量的测试。你能否早点停止回溯？
如果当前单词不存在于所有单词的前缀中，则可以立即停止回溯。什么样的数据结构可以有效地执行这样的操作？散列表是否可行？为什么？ 前缀树如何？如果你想学习如何实现一个基本的前缀树，请先查看这个问题： 实现Trie（前缀树）。
212. Word Search II
Given a 2D board and a list of words from the dictionary, find all words in the board.
Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.
Example:
Input:
board = [
['o','a','a','n'],
['e','t','a','e'],
['i','h','k','r'],
['i','f','l','v']
]
words = ["oath","pea","eat","rain"]
Output: ["eat","oath"]
Note:
All inputs are consist of lowercase letters a-z.
The values of words are distinct.
solutions
class Trie(object):
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
def insert(self, word):
"""
Inserts a word into the trie.
:type word: str
:rtype: None
"""
tree = self.root
for w in word:
if tree is None or not tree.get(w):
tree[w] = {}
tree = tree.get(w)
tree["end"] = True
def search(self, word):
"""
Returns if the word is in the trie.
:type word: str
:rtype: bool
"""
tree = self.root
for w in word:
tree = tree.get(w)
if tree is None:
return False
return True if tree.get("end") else False
def startsWith(self, prefix):
"""
Returns if there is any word in the trie that starts with the given prefix.
:type prefix: str
:rtype: bool
"""
tree = self.root
for w in prefix:
tree = tree.get(w)
if tree is None:
return False
return True
class Solution(object):
def findWords(self, board, words):
"""
:type board: List[List[str]]
:type words: List[str]
:rtype: List[str]
"""
add_list = [(1, 0), (-1, 0), (0, 1), (0, -1)]
col_len = len(board)
if not col_len or not words or not board[0]:
return []
row_len = len(board[0])
trie = Trie()
max_length = 0
for word in words:
trie.insert(word)
if len(word) > max_length:
max_length = len(word)
self.w = []
def dfs(res, i, j):
if i < 0 or j < 0 or i >= col_len or j >= row_len or board[i][j] == "":
if trie.search(res) and res not in self.res:
self.res.append(res)
else:
tmp = board[i][j]
board[i][j] = ""
for add_i, add_j in add_list:
if len(res) < max_length and trie.startsWith(res + str(tmp)):
dfs(res + str(tmp), i + add_i, j + add_j)
board[i][j] = tmp
self.res = []
for i in range(col_len):
for j in range(row_len):
if board[i][j] in trie.root:
# print(board[i][j], trie.root)
dfs("", i, j)
return sorted(self.res)
并查集
并查集 (union & find) 是⼀种树型的数据结构， 用于处理理⼀些不交集(Disjoint Sets)的合并及查询问题。
-
Find: 确定元素属于哪⼀个子集。 它可以被⽤用来确定两个元素是否 属于同⼀子集。
-
Union: 将两个⼦集合并成同⼀个集合。
number-of-islands
https://leetcode.com/problems/number-of-islands/
friend-circles
https://leetcode.com/problems/friend-circles/
LRU Cache
https://www.sqlpassion.at/archive/2018/01/06/understanding-the-meltdown-exploit-in-my-own-simple-words/
https://zh.wikipedia.org/wiki/快取文件置換機制
https://en.wikipedia.org/wiki/Cache_replacement_policies
LRU缓存机制
https://leetcode.com/problems/lru-cache/
146. LRU缓存机制
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
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
146. LRU Cache
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
solutions
import collections
class LRUCache(object):
def __init__(self, capacity):
"""
:type capacity: int
"""
self.vals = collections.OrderedDict()
self.remains = capacity
def get(self, key):
"""
:type key: int
:rtype: int
"""
res = -1
if key in self.vals:
res = self.vals.pop(key)
self.vals[key] = res
return res
def put(self, key, value):
"""
:type key: int
:type value: int
:rtype: None
"""
# # print(self.vals, self.remains, key, value, "0")
# if key in self.vals:
# self.vals[key] = self.vals.pop(key)
# if key not in self.vals:
# if self.remains > 0:
# self.remains -= 1
# else:
# self.vals.popitem(last=False)
# self.vals[key] = value
# # print(self.vals, self.remains, key, value, "1")
if key in self.vals:
self.vals.pop(key)
else:
if self.remains > 0:
self.remains -= 1
else:
self.vals.popitem(last=False)
self.vals[key] = value
分治、递归、回溯
二分查找
位运算
贪心算法
动态规划
refs
collabedit.com
coderpad.io
https://www.jianshu.com/p/9c5c3f839c47
https://blog.csdn.net/s1314_JHC/article/details/78233055
https://mp.weixin.qq.com/s/3LR-iVC4zgj0tGhZ780PcQ
https://mp.weixin.qq.com/s/FFsvWXiaZK96PtUg-mmtEw
https://mp.weixin.qq.com/s/A3dLW92SNag8lw7vrQiEHQ