KK's blog

LeetCode 2074 Reverse Nodes in Even Length Groups

You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

The 1<sup>st</sup> node is assigned to the first group. The 2<sup>nd</sup> and the 3<sup>rd</sup> nodes are assigned to the second group.
The 4<sup>th</sup>, 5<sup>th</sup>, and 6<sup>th</sup> nodes are assigned to the third group, and so on.

Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

Example 1:

Input: head = [5,2,6,3,9,1,7,3,8,4]
Output: [5,6,2,3,9,1,4,8,3,7]
Explanation:
- The length of the first group is 1, which is odd, hence no reversal occurrs.
- The length of the second group is 2, which is even, hence the nodes are reversed.
- The length of the third group is 3, which is odd, hence no reversal occurrs.
- The length of the last group is 4, which is even, hence the nodes are reversed.

Example 2:

Input: head = [1,1,0,6]
Output: [1,0,1,6]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 1. No reversal occurrs.

Example 3:

Input: head = [2,1]
Output: [2,1]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the last group is 1. No reversal occurrs.

Example 4:

Input: head = [8]
Output: [8]
Explanation: There is only one group whose length is 1. No reversal occurrs.

Constraints: The number of nodes in the list is in the range [1, 10<sup>5</sup>].
* 0 <= Node.val <= 10<sup>5</sup>

题目大意：

把链表分成1,2,3..n大小的组。若该组大小为偶数，反转链表。

解题思路：

一开始考虑分奇偶组来处理，但忽略了最后一组也可能为偶数。用stack来，先做统计，若为偶数，就出栈且反转。
后来为了程序更加简洁，就独立一个函数出来按组处理。而每组用迭代将后续节点一个个加到上一组末节点和首节点之间。

解题步骤：

1. 按组处理
2. 每组先统计个数，如果为偶数，反转链表

start(group n) -> end(group n+1, head of group n+1 will become new tail after reversed) -> …
不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> … -> end(group n+1) -> NodeA （前状态） -> …

注意事项：

1. 若最后一组不满为偶数，也要逆转。
2. 反转链表时，个数为这组大小减一，因为该组的首节点不用反转。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
	group, cur = 2, head
	while cur.next:
		cur = self.process_one_group(cur, group)
		group += 1
	return head

def process_one_group(self, tail_of_last: ListNode, n: int) -> ListNode:
	cur, count = tail_of_last, 0
	while cur.next and count < n:
		cur = cur.next
		count += 1
	if count % 2 == 0:
		start, end = tail_of_last, tail_of_last.next
		for i in range(count - 1):
			# delete the node
			moved_node, end.next = end.next, end.next.next
			# insert the moved_node
			start.next, moved_node.next = moved_node, start.next
	cur = tail_of_last
	for i in range(count):
		cur = cur.next
	return cur

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

LeetCode 275 H-Index II

Given an array of integers citations where citations[i] is the number of citations a researcher received for their i<sup>th</sup> paper and citations is sorted in an ascending order, return compute the researcher’s h-index.

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

If there are several possible values for h, the maximum one is taken as the h-index.

You must write an algorithm that runs in logarithmic time.

Example 1:

**Input:** citations = [0,1,3,5,6]
**Output:** 3
**Explanation:** [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, their h-index is 3.

Example 2:

**Input:** citations = [1,2,100]
**Output:** 2

Constraints:

• n == citations.length
• 1 <= n <= 10<sup>5</sup>
• 0 <= citations[i] <= 1000
• citations is sorted in ascending order.

题目大意：

一个人的学术文章有n篇分别被引用了n次及以上，那么H指数就是n

解题思路：

数组有序，论文数从小到大有序(符合引用次数的论文数从右向左递减)，引用次数由小到大排序，所以只要从右向左遍历数组，数值和索引相交的值就是所求。

解题步骤：

二分法可提高效率，用的是

注意事项：

1. 此题是寻找单一目标，所以等号可以并入任一个if statement，但循环出来后，start必须先比较，因为贪婪法，下标越向左，越容易获得更大的结果。从这一意义上看，此题接近于first_position

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def hIndex(self, citations: List[int]) -> int:
	if citations is None or len(citations) == 0:
		return 0
	start, end = 0, len(citations) - 1
	while start + 1 < end:
		mid = start + (end - start) // 2
		if citations[mid] >= len(citations) - mid:
			end = mid
		else:
			start = mid
	if citations[start] >= len(citations) - start:
		return len(citations) - start
	if citations[end] >= len(citations) - end:
		return len(citations) - end
	return 0

算法分析：

时间复杂度为O(logn)，空间复杂度O(1)。

数组题

LeetCode 001 Two Sum
LeetCode 2073 Time Needed to Buy Tickets

整数题

LeetCode 007 Reverse Integer

整洁题

LeetCode 273 Integer to English Words
LeetCode 054 Spiral Matrix
LeetCode 048 Rotate Image
LeetCode 166 Fraction to Recurring Decimal
LeetCode 008 String to Integer (atoi) 合法整数
LeetCode 065 Valid Number 合法小数指数

Map

LeetCode 003 Longest Substring Without Repeating Characters

LinkedList

注意事项： [4步]

• fake_node
• while it or it.next
• 删除节点.next = None
• it = it.next

快慢指针找循环，找中点(注意中位数有1-2个, 用fast是否为None来判断)
LeetCode 142 Linked List Cycle II
LeetCode 234 Palindrome Linked List
反转LL及其模板
LeetCode 206 Reverse Linked List
LeetCode 092 Reverse Linked List II
其他：
LeetCode 021 Merge Two Sorted Lists
LeetCode 002 Add Two Numbers
LeetCode 138 Copy List with Random Pointer
LeetCode 023 Merge k Sorted Lists

Stack

递减栈
适用条件： 数组元素之间大小关系(包括相等)且顺序不能变，可以动态处理(一个个处理)
Stack
LeetCode 503 Next Greater Element II
LeetCode 042 Trapping Rain Water
LeetCode 316 Remove Duplicate Letters
LeetCode 1209 Remove All Adjacent Duplicates in String II
LeetCode 239 Sliding Window Maximum

BST的非递归遍历

BST的非递归中序，前序，后序遍历
LeetCode 272 Closest Binary Search Tree Value II
Iterator题目基本是List转Stack
LeetCode 173 Binary Search Tree Iterator

Heap

Heap
LeetCode 347 Top K Frequent Elements
LeetCode 253 Meeting Rooms II endTime的Heap (最常见)
LeetCode 218 The Skyline Problem 高度的Heap
Heap + BFS
LeetCode 264 Ugly Number II
LeetCode 373 Find K Pairs with Smallest Sums
LeetCode 378 Kth Smallest Element in a Sorted Matrix

数据结构

题目大多都是HashMap + LL 或 HashMap + List
LeetCode 1429 First Unique Number
LeetCode 380 Insert Delete GetRandom O(1)
LeetCode 146 LRU Cache
LeetCode 460 LFU Cache
Trie
LeetCode 588 Design In-Memory File System
LeetCode 211 Design Add and Search Words Data Structure search含TrieNode参数 + DFS
LeetCode 212 Word Search II search含TrieNode参数
Iterator
LeetCode 251 Flatten 2D Vector
LeetCode 281 Zigzag Iterator
LeetCode 341 Flatten Nested List Iterator
LeetCode 173 Binary Search Tree Iterator
数组二分法:
LeetCode 981 Time Based Key-Value Store
LeetCode 2080 Range Frequency Queries
其他：
LeetCode 155 Min Stack

Two pointers

同向双指针： 应用条件需要连续一段达到target，然后连续一段达不到target，梅花间竹
Two pointers
LeetCode 243 Shortest Word Distance
LeetCode 209 Minimum Size Subarray Sum
LeetCode 438 Find All Anagrams in a String
LeetCode 076 Minimum Window Substring
LeetCode 340 Longest Substring with At Most K Distinct Characters 最长类型
LeetCode 395 Longest Substring with At Least K Repeating Characters 最长类型
相向双指针
Hash(value -> index, value -> count)适用条件： 数组元素之间的关系，相加相减等于target，复杂度为O(n)
LeetCode 1010 Pairs of Songs With Total Durations Divisible by 60 value -> count变体
Two points适用条件： 数组元素之间的关系，相加相减等于target，元素相等或有序，复杂度为O(n)
回文题首先考虑用相向双指针
LeetCode 125 Valid Palindrome
LeetCode 680 Valid Palindrome II

Sorting

Quick sort
Partition的应用, O(1)空间且注意循环外处理最后一部分：
LeetCode 283 Move Zeroes
LeetCode 443 String Compression
LeetCode 075 Sort Colors
LeetCode 696 Count Binary Substrings
LeetCode 041 First Missing Positive
Quick select
Merge sort
LeetCode 244 Shortest Word Distance II
LeetCode 315 Count of Smaller Numbers After Self
LeetCode 493 Reverse Pairs
Bucket sort
LeetCode 347 Top K Frequent Elements
LeetCode 2080 Range Frequency Queries

Binary Search

Binary Search
LeetCode 278 First Bad Version
LeetCode 153 Find Minimum in Rotated Sorted Array
LeetCode 033 Search in Rotated Sorted Array
LeetCode 540 Single Element in a Sorted Array
LeetCode 275 H-Index II
Binary Select
适用条件：试某个数接近于最优解，全部试一遍就是*logn的复杂度
LeetCode 378 Kth Smallest Element in a Sorted Matrix
LeetCode 004 Median of Two Sorted Arrays

Tree

检查方法： None, 一个节点，两个节点(只有左或右)，三个节点
nonlocal方法，不用定义全局变量见LeetCode 543 Diameter of Binary Tree
LeetCode 104 Maximum Depth of Binary Tree
LeetCode 230 Kth Smallest Element in a BST
LeetCode 114 Flatten Binary Tree to Linked List
LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
LeetCode 314 Binary Tree Vertical Order Traversal
方法：用Map记录子节点到父节点关系等价于形成双向Tree
LeetCode 1650 Lowest Common Ancestor of a Binary Tree III
LeetCode 236 Lowest Common Ancestor of a Binary Tree
LeetCode 863 All Nodes Distance K in Binary Tree

BFS

适用条件： 可行性，最大和最小值且每个点不能重复访问
注意事项： [3步]建图没有边的节点也要加到邻接表, 输入参数不等于迭代参数, 返回-1,
图BFS
LeetCode 200 Number of Islands 连通集问题, 对所有节点BFS
LeetCode 1048 Longest String Chain 多源最长路劲，对所有节点BFS
LeetCode 1197 Minimum Knight Moves
LeetCode 133 Clone Graph
LeetCode 297 Serialize and Deserialize Binary Tree
LeetCode 127 Word Ladder
LeetCode 301 Remove Invalid Parenthesess
LeetCode 055 Jump Game
LeetCode 1654 Minimum Jumps to Reach Home
LeetCode 286 Walls and Gates 多始点一次BFS
LeetCode 490 The Maze 一组节点作为一层的BFS
LeetCode 815 Bus Routes 一组节点作为一层的BFS
[LeetCode 1293 Shortest Path in a Grid with Obstacles Elimination] 多状态BFS
拓扑排序
LeetCode 210 Course Schedule II
LeetCode 310 Minimum Height Trees
LeetCode 269 Alien Dictionary

DFS

适用条件： 种数(优先用DP，次选用DFS)，可行性
图DFS/填位法
排列
LeetCode 526 Beautiful Arrangement
组合
LeetCode 039 Combination Sum
LeetCode 077 Combinations
LeetCode 216 Combination Sum III
LeetCode 017 Letter Combinations of a Phone Number 填位法
LeetCode 051 N-Queens 填位法
LeetCode 037 Sudoku Solver 填位法, 单边DFS + 循环DFS
LeetCode 093 Restore IP Addresses 分割型，结果分组型DFS
LeetCode 291 Word Pattern II 分割型, 单边DFS + 循环DFS
LeetCode 079 Word Search 图DFS + 分割型
LeetCode 126 Word Ladder II 图DFS
记忆性搜索
LeetCode 140 Word Break II 分割型
LeetCode 095 Unique Binary Search Trees II Catalan型DFS
LeetCode 241 Different Ways to Add Parentheses Catalan型DFS

DP

适用条件： 最值，种数，可行性。输入数据有序,暴力法非多项式
注意事项： [5步]多1, 初始化, 多1, 少1, 答案
DP
LeetCode 070 Climbing Stairs 单序列型
LeetCode 091 Decode Ways 单序列型
LeetCode 198 House Robber 单序列型
LeetCode 377 Combination Sum IV 数值到个数DP
LeetCode 322 Coin Change 数值到个数DP
LeetCode 518 Coin Change 2 数值到个数DP(元素无序)
LeetCode 063 Unique Paths II 坐标型DP
LeetCode 064 Minimum Path Sum 坐标型DP
LeetCode 221 Maximal Square 坐标型DP
LeetCode 174 Dungeon Game 坐标型DP
LeetCode 718 Maximum Length of Repeated Subarray 匹配型DP
LeetCode 300 LIS 匹配型DP
LeetCode 139 Word Break 匹配型DP
LeetCode 072 Edit Distance 匹配型DP
LeetCode 044 Wildcard Matching 匹配型DP
LeetCode 010 Regular Expression Matching 匹配型DP
LeetCode 516 Longest Palindromic Subsequence 区间型DP
LeetCode 312 Burst Balloons 区间型DP
Karat 002 Longest Common Continuous Subarray 打印路径
LeetCode 300 Longest Increasing Subsequence 打印路径
LeetCode 368 Largest Divisible Subset 打印路径
LeetCode 1143 Longest Common Subsequence 打印路径
多状态DP需要同时赋值
LeetCode 152 Maximum Product Subarray 多状态DP
LeetCode 926 Flip String to Monotone Increasing 多状态DP
LeetCode 256 Paint House 多状态DP
多状态DP-fg双函数(g为累计DP) - 和前状态不能相邻
LeetCode 337 House Robber III 多状态DP-fg双函数
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown 多状态DP-fg双函数
Floyd
LeetCode 329 Longest Increasing Path in a Matrix

其他

动态计算连接数，其他均用BFS
Union Find
LeetCode 721 Accounts Merge
[双向BFS]LeetCode 127 Word Ladder
[线段树]LeetCode 729 My Calendar I

最大的k个/最大的前k个数(无序数值数组)

LeetCode 347 Top K Frequent Elements
优先考虑Heap，因为Heap支持动态和静态数据。适用范围最广，动态包括Data stream，不将整个数组读入从而优化复杂度
LeetCode 295 Find Median from Data Stream
LeetCode 378 Kth Smallest Element in a Sorted Matrix
Binary select，数值法计算个数，不能用于动态，实现较复杂
LeetCode 004 Median of Two Sorted Arrays
Quick select, binary select的特殊版，只能用于一维数组

数组区间内动态最大值最小值或保留数组顺序(数值数组)

由于保留顺序，首选stack
LeetCode 2104 Sum of Subarray Ranges

二维坐标最短距离

BFS首选，然后DP。若状态转移是无序用BFS，否则DP(可从上到下，从左到右)
BFS
LeetCode 1197 Minimum Knight Moves
LeetCode 909 Snakes and Ladders
DP
LeetCode 174 Dungeon Game 坐标型DP

累计思想

将相连的批量计算提高效率或者满足累计条件
LeetCode 032 Longest Valid Parentheses 统计左括号个数保证其一直为非负数
LeetCode 134 Gas Station 保证gas一直为非负数
数组的presum
加入presum[0] = 0
LeetCode 696 Count Binary Substrings
LeetCode 560 Subarray Sum Equals K
LeetCode 238 Product of Array Except Self
子矩阵的presum
同数组，presum矩阵大小为长度 + 1

1
2
3

res = presum[x][y] - left - top + diag

presum[i][j] = row_sum + (presum[i - 1][j] if i > 0 else 0)

LeetCode 304 Range Sum Query 2D - Immutable
LeetCode 427 Construct Quad Tree

括号题或者字符串运算题

括号题或者字符串运算题优先用Stack
LeetCode 020 Valid Parentheses
LeetCode 032 Longest Valid Parentheses
LeetCode 1249 Minimum Remove to Make Valid Parentheses 括号下标
LeetCode 678 Valid Parenthesis String
LeetCode 022 Generate Parentheses
LeetCode 071 Simplify Path
字符串运算题
LeetCode 227 Basic Calculator II
LeetCode 224 Basic Calculator
LeetCode 394 Decode String

游戏题

数据结构设计 + 模拟
[LeetCode 348 Design Tic-Tac-Toe] 设计游戏
LeetCode 051 N-Queens 求游戏所有解
LeetCode 037 Sudoku Solver 求游戏是否有解

区间重合题

条件区间重合且区间始点有序。用端点排序法(更常用)或Heap(处理重合情况下的计算)
LeetCode 253 Meeting Rooms II
LeetCode 056 Merge Intervals
LeetCode 759 Employee Free Time
LeetCode 1235 Maximum Profit in Job Scheduling
LeetCode 871 Minimum Number of Refueling Stops
LeetCode 218 The Skyline Problem 端点排序法 + Heap

所有子串和子数组

用presum, stack, DP
LeetCode 560 Subarray Sum Equals K
LeetCode 696 Count Binary Substrings
LeetCode 907 Sum of Subarray Minimums
LeetCode 2104 Sum of Subarray Ranges
Leetcode 828 Count Unique Characters of All Substrings of a Given String

26字母存储法

条件，若题目含所有字母，且求最值，需要存储每个字母对应的结果
LeetCode 395 Longest Substring with At Least K Repeating Characters
LeetCode 1857 Largest Color Value in a Directed Graph

水王法

candidate取首元素，遍历每一个元素，若candidate不符合条件就换成当前元素为candidate
LeetCode 169 Majority Element
LeetCode 277 Find the Celebrity
LeetCode 134 Gas Station

Word相关题目

DFS: word pattern, word search
BFS: word ladder
DP: word break

算法思路：

定义： 栈里元素维持由栈底到栈顶从大到小的顺序叫递减栈。跟最小堆一样，递减栈的栈首元素最小。

反之是递增栈，不过此法因为用递减栈比较多，所以统称递减栈。通常是将下标而不是值放入到栈中，这样还可以知道元素间的距离。

应用：

1. 数组不能打乱顺序且求极值

注意事项：

1. 跟最小堆一样，当元素大于栈顶元素的时候才倒逼栈内元素出栈。

Python代码：

1
2
3
4
5
6

stack = []
for i in range(len(li)):
	while stack and li[i] > li[stack[-1]]:
		index = stack.pop()

	stack.append(i)

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

LeetCode 017 Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:

**Input:** digits = "23"
**Output:** ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:

**Input:** digits = ""
**Output:** []

Example 3:

**Input:** digits = "2"
**Output:** ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4
• digits[i] is a digit in the range ['2', '9'].

题目大意：

在拨号键盘上按下了几个键，问能打出来的字符串的所有组合是多少。。

递归法解题思路：

DFS的典型题目。

与Java的区别：

1. 直接用Str作为临时结果，不需要用char array，因为str可以含有array的性质

注意事项：

1. 输入值为空的情况
2. 终止条件记得return
3. 用常量

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

DIGIT2CHAR = {
    '0': '',
    '1': '',
    '2': 'abc',
    '3': 'def',
    '4': 'ghi',
    '5': 'jkl',
    '6': 'mno',
    '7': 'pqrs',
    '8': 'tuv',
    '9': 'wxyz',
}

class Solution(TestCases):

    def letterCombinations(self, digits: str) -> List[str]:
        result = []
        if digits == '':
            return result
        self.dfs(digits, 0, '', result, DIGIT2CHAR)
        return result

    def dfs(self, digits, start, path, result, DIGIT2CHAR):
        if start == len(digits):
            result.append(path)
            return
        for letter in DIGIT2CHAR[digits[start]]:
            self.dfs(digits, start + 1, path + letter, result, DIGIT2CHAR)

迭代法解题思路：

第二种方法，用迭代法，三种循环，输入数字串的每个数字，每个数字对应的字符加到当前的结果字符串列表中。

注意事项：

1. 要[‘’]而不是[]否则循环不会进行

1
2
3
4
5
6
7

def letterCombinations(self, digits: str) -> List[str]:
	if digits == '':
		return []
	result = ['']
	for d in digits:
		result = [s + c for s in result for c in DIGIT2CHAR[d]]
	return result

算法分析：

这是NP问题。时间复杂度为O(4n)，空间复杂度O(1)。