## Description: 链表数之和

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

## 扩展问题

What if the the digits in the linked list are stored in non-reversed order? For example:

$(3 \to 4 \to 2) + (4 \to 6 \to 5) = 8 \to 0 \to 7 (3→4→2)+(4→6→5)=8→0→7$

# 003. Longest Substring Without Repeating Characters

## Description: 寻找无重复字符的最长子串

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Example 2:

Example 3:

Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

## 解法二: 前后两个指示变量

• 如果超尾字符与当前子串中的字符不重复, 那么将超尾字符加入到当前子串中,并将length加1
• 如果超尾字符与当前子串中的字符重复, 利用哈希表查的重复字符的所在位置, 将当前子串的首字符直接跳向该重复字符的下一个位置( 这样可以保证只遍历一遍 ), 并将包括重复字符在内的之前所有字符都从哈希表中删除(之前的字符不再可能组成更长的子串了), 同时将超尾字符加入, length赋予新值: 超尾位置-重复位置-1;
• 判断首字符与超尾字符是否相等, 如果相等, 将超尾字符加1, 并将length置为1
• 看当前length是否比maxlength大, 并重复以上过程,直到超尾字符超出size

# 005. Longest Palindromic Substring

## Description: 最大回文子串

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Output: “bab”
Note: “aba” is also a valid answer.
Example 2:

Input: “cbbd”
Output: “bb”

## 解法三： 扩展中心法

• 分别检查奇数和偶数的情况, 这样多检查一次(虽然多检查一次, 但和下面的检查总次数差不多, 因为下面虽然只检查一次, 但次数较多)
• 向字符内插入特殊符号 ‘#’, 这样不管偶数奇数, 都可以当做奇数处理, 缺点是占用了额外的 $O(n)$ 空间.

## 解法五: 马拉车(Manacher) 算法

There is even an O(n), O(n) algorithm called Manacher’s algorithm, explained here in detail. However, it is a non-trivial algorithm, and no one expects you to come up with this algorithm in a 45 minutes coding session. But, please go ahead and understand it, I promise it will be a lot of fun.

• P: P 为最大右边界下标值, 对应的是所有已检测的回文子串中, 右边界下标最大的那个
• P_center: 该值是P对应的回文子串的中心下标
• max_len: 对应当前最大回文子串的半径(aba的半径为1, a的半径为0)
• max_index: 对应当前最大回文子串的中心下标

• P>i, 说明 i 在 P 的范围内, 可以利用前面的计算结果
• P<=i, 说明 i 不在 P 的范围内, 无法利用前面的计算结果, 只能逐个判断

# 008. String to Integer (atoi)

## 解法一: 考虑多种情况

• +123 dd // 返回123
• +123d // 返回123
• d-123 // 返回0
• -123+ //返回-123
• -123+4 // 返回-123
• 323123423423423 // 返回INT_MAX
• -1231238923894234 // 返回INT_MIN
• 1234-5 // 返回1234

# 011. Container With Most Water

## Description

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The below vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

# 015. 3Sum

## Description: 三数和为零

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:

## 解法一: 固定一个数, 剩余两个数用双指针法求

1. 对整个数组排序, $O(nlogn)$;
2. 固定下标 i, 令下标j=i+1, 令 k=nums.size()-1.
3. 如果 nums[i] 为正数, 说明不可能组成和为零的三元组, 直接返回当前结果;
4. 为了消除重复, 对于相同的相邻元素, 我们只选其中的一个参与组合. 注意: 这里的重复是指三元组的值的重复, 而不是下标重复, 也就是说, 对于下标不同但值相同的元素, 也算作重复.
5. 重复(2)(3)(4)过程直到循环终止.

# 017. Letter Combinations of a Phone Number

## Description: 九键字母组合

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
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:

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

## C++

### 解法一: 递归

*空间复杂度:
$O(4^n)$

### 解法二: 非递归

*空间复杂度:
$O(4^n)$

# 019. Remove Nth Node From End of List

## Description: 移除链表的倒数第 N 个字符

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Note:
Given n will always be valid.

Could you do this in one pass?

# 022. Generate Parentheses

## 解法二: 回溯

• 为了保证当前string内左括号数量多于右括号数量, left_rest一定要小于right_rest
• 如果left_rest = right_rest = 0, 则说明此时没有可以添加的括号了.

## 解法四: 用栈来模拟递归

1. 右括号不能比左括号多;
2. 弹出右括号, 直到遇到第一个左括号, 如果左括号改成右括号仍然合法, 则把它改成右括号; 否则, 左括号继续弹出;
3. 改完之后一个劲加左括号, 直到所有可以用的左括号都加完为止; 然后再一个劲的加右括号, 直到加完位置;
4. 循环一直执行到不能弹出括号为止, 即直到栈为空.

# 029. Divide Two Integers

## Description: 实现除法

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.
Return the quotient after dividing dividend by divisor.
The integer division should truncate toward zero.

Example 1:

Example 2:

Note:
Both dividend and divisor will be 32-bit signed integers.
The divisor will never be 0.
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: $[−2^{31}, 2^{31 − 1}]$. For the purpose of this problem, assume that your function returns 2^{31 − 1} when the division result overflows.

## 解法二: 左移法

• 当被除数为 INT_MIN, 除数为 -1 时, 此时的返回值为 INT_MAX+1. (根据题目要求, 溢出时刻直接返回 INT_MAX)
• 当除数为 0 时, 也应该看做是溢出情况.
• 处理上面情况最方便的方法使用 long 长整型, 而不是 unsigned int 无符号类型. 因为 unsigned int 类型在进行乘以 2 的操作时, 很容易也溢出, 最终造成程序的死循环, 为了防止溢出, 最好使用 long, 具体请看代码.

# 031. Next Permutation

## Description: 实现 next_permutation 函数逻辑

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place and use only constant extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

## 解法一: next_permutation 实现

STL中的 next_permutation 函数和 prev_permutation 两个函数提供了对于一个特定排列P, 求出其后一个排列P+1和前一个排列P-1的功能.

next_permutation 的实现方法如下:

• 从后往前 找第一个小于后一个数的元素 nums[i]: nums[i]<nums[i+1]
• 从后往前 找第一个大于 nums[i] 的数 nums[j]: nums[j]>nums[i]
• 交换 nums[i]nums[j]
• i 之后的元素逆置(reverse)

# 033. Search in Rotated Sorted Array

## Description: 在循环有序数组中查找元素

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of $O(log n)$.

Example 1:

Example 2:

# 034. Find First and Last Position of Element in Sorted Array

## Description: 在有序数组中查找目标的开始位置和结束位置

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Example 2:

## 解法三: STL 函数

• lower_bound() 函数返回首个 不小于 target 的迭代器, 如果数组中所有元素 都小于 target, 则会返回超尾迭代器.
• upper_bound() 函数返回首个 大于 target 的迭代器, 如果数组中所有元素 都小于等于 target, 则会返回超尾迭代器.
• 注意 upper_bound() 返回的迭代器是首个 大于 目标值的迭代器, 因此需要将其减一才是我们要找的 target 的终止位置.

# 036. Valid Sudoku

## Description: 验证一个矩阵是否是数独数据

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

# 046. Permutations

## Description: 不含重复数字的全排列

Given a collection of distinct integers, return all possible permutations.

Example:

Input: [1,2,3]
Output:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

## 解法三: 利用C++的内置函数 next_permutation

STL中的 next_permutation 函数和 prev_permutation 两个函数提供了对于一个特定排列P, 求出其后一个排列P+1和前一个排列P-1的功能.

## 解法四: 自己实现 next_permutation

prev_permutation 实现:

next_permutation python 实现:

prev_permutation python 实现

# 047. Permutations II

## 解法一: 递归+set

set 插入元素的时间复杂度为 $O(logn)$, $n$ 为当前 set 的大小.

python 实现:

# 048. Rotate Image

## Description: 图片旋转 90 度

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

## 解法一: 逆置+转置

clockwise rotate
first reverse up to down, then swap the symmetry

# 049. Group Anagrams

## Description: 找出同字母的异序词, 并按字母分组输出

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.

# 050. Pow(x, n)

## Descriptin

Implement pow(x, n), which calculates x raised to the power n (x^n).

Example 1:

Input: 2.00000, 10
Output: 1024.00000
Example 2:

Input: 2.10000, 3
Output: 9.26100
Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25
Note:

-100.0 < x < 100.0
n is a 32-bit signed integer, within the range $[−2^{31}, 2^{31} − 1]$

## 解法二: 非递归

n 要么为偶数, 要么为奇数, 我们每一次都将 n 的值减半, 并且将 x 与自身相乘, 每次当 n 为奇数时, 我们都将 res 与 x 相乘, 最终, res 的值就是我们要求的幂乘. 举例来说,

# 054. Spiral Matrix

## Description

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example 1:

Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

# 055. Jump Game

## Description

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

# 056. Merge Intervals

## Description

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

## 解法三: 不使用sort

//TODO, 未细看, 但时间复杂度应该会高于 O(nlogn)
https://leetcode.com/problems/merge-intervals/discuss/153979/Elegant-c++-solutions.-One-without-modifying-intervals-and-one-inplace

# 062. Unique Paths

## Description

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

# 073. Set Matrix Zeroes

## Description

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input:
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]
Example 2:

Input:
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

# 075. Sort Colors

## Description

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with a one-pass algorithm using only constant space?

# 077. Combinations

## Description: 输出所有的组合

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

TODO: 未看懂

# 078. Subsets

## Description

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

## 解法二: 回溯

Subsets II (contains duplicates) : https://leetcode.com/problems/subsets-ii/

Permutations : https://leetcode.com/problems/permutations/

Permutations II (contains duplicates) : https://leetcode.com/problems/permutations-ii/

Combination Sum : https://leetcode.com/problems/combination-sum/

Combination Sum II (can’t reuse same element) : https://leetcode.com/problems/combination-sum-ii/

Palindrome Partitioning : https://leetcode.com/problems/palindrome-partitioning/

# 079. Word Search

## Description: 判断指定单词是否存在于字符矩阵中

Given a 2D board and a word, find if the word exists in the grid.

The word can 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.

Example:

board =
[
[‘A’,’B’,’C’,’E’],
[‘S’,’F’,’C’,’S’],
[‘A’,’D’,’E’,’E’]
]

Given word = “ABCCED”, return true.
Given word = “SEE”, return true.
Given word = “ABCB”, return false.

# 090. Subsets II

## Description: 含重复元素的数组的子集

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

# 091. Decode Ways

## Description

A message containing letters from A-Z is being encoded to numbers using the following mapping:

‘A’ -> 1
‘B’ -> 2

‘Z’ -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: “12”
Output: 2
Explanation: It could be decoded as “AB” (1 2) or “L” (12).
Example 2:

Input: “226”
Output: 3
Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

# 094. Binary Tree Inorder Traversal

## Description

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Follow up: Recursive solution is trivial, could you do it iteratively?

# 098. Validate Binary Search Tree

## Description

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:

Input:
2
/ \
1 3
Output: true
Example 2:

5

/ \
1 4
/ \
3 6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node’s value
is 5 but its right child’s value is 4.

# 103. Binary Tree Zigzag Level Order Traversal

## Description

Given a binary tree, return the zigzag level order traversal of its nodes’ values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its zigzag level order traversal as:
[
[3],
[20,9],
[15,7]
]

# 105. Construct Binary Tree from Preorder and Inorder Traversal

## Description: 根据先序和中序遍历构造二叉树

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.(如果没有该条件则通常无法还原唯一的二叉树)

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
Return the following binary tree:

## 解法二: 迭代

1. 先将 preorder[i] 压入栈中, 如果当前 preorder 的元素与 inorder 中的元素不匹配, 则将 preorder 中的值构造成节点压入栈中, 并且新构造的节点一定是栈顶的左孩子. 重复该过程直到元素值匹配为止: preorder[i] = inorder[index]
2. 当先序和中序的值匹配时, 则将节点出栈, 直到不再匹配为止.
3. TODO: 该解法还没彻底搞清, 暂时搁置

# 116. Populating Next Right Pointers in Each Node

## Description

Given a binary tree

right;
}
Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.
Recursive approach is fine, implicit stack space does not count as extra space for this problem.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).
Example:

Given the following perfect binary tree,

1

/ \
2 3
/ \ / \
4 5 6 7
After calling your function, the tree should look like:

1 -> NULL

/ \
2 -> 3 -> NULL
/ \ / \
4->5->6->7 -> NULL

## Description

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 1:

Example 2:

## 解法一: BFS

• 这里的图和树不太一样, 这里图没有链表指针来指示, 因此, 在每次将某一个单词入队列以后, 都需要在单词列表中删除掉这个单词(或者额外设置标记也行), 以防止重复搜索
• 题目给的是没有重复单词的单词表, 因此推荐使用 set 结构来进行删除 (erase) 操作, vector 结构的删除 (erase) 操作的时间复杂度较高.

# 130. Surrounded Regions

## Descriptioin

Given a 2D board containing ‘X’ and ‘O’ (the letter O), capture all regions surrounded by ‘X’.

A region is captured by flipping all ‘O’s into ‘X’s in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X
After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X
Explanation:

Surrounded regions shouldn’t be on the border, which means that any ‘O’ on the border of the board are not flipped to ‘X’. Any ‘O’ that is not on the border and it is not connected to an ‘O’ on the border will be flipped to ‘X’. Two cells are connected if they are adjacent cells connected horizontally or vertically.

# 134. Gas Station

## Description

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:

Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:

Input:
gas = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.

# 138. Copy List with Random Pointer

## Description

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

# 139. Word Break

## Description

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

The same word in the dictionary may be reused multiple times in the segmentation.
You may assume the dictionary does not contain duplicate words.
Example 1:

Input: s = “leetcode”, wordDict = [“leet”, “code”]
Output: true
Explanation: Return true because “leetcode” can be segmented as “leet code”.
Example 2:

Input: s = “applepenapple”, wordDict = [“apple”, “pen”]
Output: true
Explanation: Return true because “applepenapple” can be segmented as “apple pen apple”.
Note that you are allowed to reuse a dictionary word.
Example 3:

Input: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
Output: false

# 142. Linked List Cycle II

## Description: 求链表中环的开始节点

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

Can you solve it without using extra space?

# 144. Binary Tree Preorder Traversal

## Description: 先根遍历

Given a binary tree, return the preorder traversal of its nodes’ values.

Example:

Output: [1,2,3]
Follow up: Recursive solution is trivial, could you do it iteratively?

# 148. Sort List

## Description

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Example 2:

# 150. Evaluate Reverse Polish Notation

## Description

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

Division between two integers should truncate toward zero.
The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.
Example 1:

Input: [“2”, “1”, “+”, “3”, ““]
Output: 9
Explanation: ((2 + 1)
3) = 9
Example 2:

Input: [“4”, “13”, “5”, “/“, “+”]
Output: 6
Explanation: (4 + (13 / 5)) = 6
Example 3:

Input: [“10”, “6”, “9”, “3”, “+”, “-11”, ““, “/“, ““, “17”, “+”, “5”, “+”]
Output: 22
Explanation:
((10 (6 / ((9 + 3) -11))) + 17) + 5
= ((10 (6 / (12 -11))) + 17) + 5
= ((10 (6 / -132)) + 17) + 5
= ((10
0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

# 152. Maximum Product Subarray

## Description

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

# 162. Find Peak Element

## Description: 局部最大值

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.
Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5
Explanation: Your function can return either index number 1 where the peak element is 2,
or index number 5 where the peak element is 6.

## 解法一: $O(n)$ 复杂度

$O(n)$ 的时间复杂度, 不合符题目要求, 仅仅记录一下.

## 解法二: $O(logn)$ 复杂度

• If num[i-1] < num[i] > num[i+1], then num[i] is peak
• If num[i-1] < num[i] < num[i+1], then num[i+1…n-1] must contains a peak
• If num[i-1] > num[i] > num[i+1], then num[0…i-1] must contains a peak
• If num[i-1] > num[i] < num[i+1], then both sides have peak

# 166. Fraction to Recurring Decimal

## Description: 无限循环小数

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”
Example 2:

Input: numerator = 2, denominator = 1
Output: “2”
Example 3:

Input: numerator = 2, denominator = 3
Output: “0.(6)”

# 179. Largest Number

## Description: 排列数字使其字符串形式的数字为最大

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

Input: [10,2]
Output: “210”
Example 2:

Input: [3,30,34,5,9]
Output: “9534330”

# 200. Number of Islands

## Description: 区块的个数

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1
Example 2:

Input:
11000
11000
00100
00011

Output: 3

# 207. Course Schedule

## Description: 课程表 / 判断有向图是否存在环

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:
Input: 2, [[1,0]]
Output: true
Explanation:
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

Example 2:
Input: 2, [[1,0],[0,1]]
Output: false
Explanation:
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

# 208. Implement Trie (Prefix Tree)

## Description: 实现字典树(前缀树)

Implement a trie with insert, search, and startsWith methods.

Example:

## 解法一

https://www.cnblogs.com/grandyang/p/4491665.html

# 210. Course Schedule II

## Description: 判断有向图是否有环, 若无环, 则返回拓扑序列

There are a total of n courses you have to take, labeled from 0 to n-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

Example 1:
Input: 2, [[1,0]]
Output: [0,1]
Explanation:
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So the correct course order is [0,1] .

Example 2:
Input: 4, [[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3] or [0,2,1,3]
Explanation:
There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0. So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3] .

# 215. Kth Largest Element in an Array

## Description: 找出无序数组中第k大的数

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

## 解法二: 部分排序(nth_element)

http://www.voidcn.com/article/p-qyrpnkse-gx.html

nth_element算法将重新排列区间[first, last)的序列元素, 算法执行完毕后, 会使得

• 第 $k$ 个位置的元素在最终的算法执行完毕后, 和整个区间完全排序后该位置的元素相同.
• 这个新的nth元素之前的所有元素均 <= (>=) nth元素之后的所有元素.
但是该算法并不保证位于第 $k$ 个元素两边区间的元素有序. 该算法和 partial_sort 算法之间一个很大的区别在于: nth_element对于除第 $k$ 位置的元素之外的区间元素的顺序不做保证, 而partial_sort排序后会使得前 $m$ 个数的子区间是有序的. 正因为如此, 在需要无序的前 top_k 个值时, nth_element 相对于 partial_sort 要更快.(只需要找第 $k$ 个值, 其前面的元素即为 top_k, 时间复杂度为 $O(n)$). 如果需要有序, 也可以先使用 nth_element, 再对前 k 个数组排序, 总的复杂度为 $O(n+klogk)$

# 227. Basic Calculator II

## Description: 基本计算器(二)

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

Example 1:

Input: “3+2*2”
Output: 7
Example 2:

Input: “ 3/2 “
Output: 1
Example 3:

Input: “ 3+5 / 2 “
Output: 5

# 230. Kth Smallest Element in a BST

## Description: 找出二叉搜索树中的最小元素

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

Example 2:

What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

# 236. Lowest Common Ancestor of a Binary Tree

## Description: 查找二叉树中任意两个节点的公共祖先

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:

Example 2:

Note:

• All of the nodes values will be unique.
• p and q are different and both values will exist in the binary tree.

## 解法一: 递归

• pq分别处于当前节点的左子树 右子树之中.
• p为当前节点, q处于当前节点的左子树 右子树之中
• q为当前节点, p处于当前节点的左子树 右子树之中

**注意, 题目中说了p, q一定存在, 并且树中节点都是唯一的, 因此, 下面的代码无需对p, q进行存在性检查.

## 解法二: 迭代(存储父节点)

1. 从根节点开始遍历整个树(任意一种遍历算法都可以, 只要能找到pq即可);
2. 直到找到节点pq之前, 将所有节点的父节点都保存在字典(hash)中;
3. 一旦我们找到了qq, 我们就将所有p的祖先节点放入了一个集合(set)当中;
4. 然后, 我们反向遍历q的祖先节点, 当找到一个存在时集合中的祖先节点时, 该节点就是第一个公共的租店节点, 也就是 LCA node, 将其返回.

## 解法三: 迭代(不存储父节点)

1. 从根节点开始;
2. (root, root_state)压入栈中, root_state定义了根节点的剩余的子节点是否可以被遍历;
3. 当栈非空时, 查看栈顶元素(parent_node, parent_state);
4. 在遍历parent_node的任何子节点之前, 首先确认parent_node是否是节点pq;
5. 当首次找到pq时, 将标志变量one_node_found设置为True. 同时根据栈中的节点跟踪 LCA (栈中的所有元素都是当前节点的祖先);
6. 当再次找到pq时, 说明我们已经将两个节点都找到了, 此时返回 LCA node.
7. 无论何时访问parent_node的子节点, 都需要将(parent_node, updated_parent_state)更新到栈中.
8. A node finally gets popped off from the stack when the state becomes BOTH_DONE implying both left and right subtrees have been pushed onto the stack and processed. If one_node_found is True then we need to check if the top node being popped could be one of the ancestors of the found node. In that case we need to reduce LCA_index by one. Since one of the ancestors was popped off

Whenever both p and q are found, LCA_index would be pointing to an index in the stack which would contain all the common ancestors between p and q. And the LCA_index element has the lowest ancestor common between p and q.

# 238. Product of Array Except Self

## Description: 计算数组内其他元素之积(不能使用除法)

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Example:

Note: Please solve it without division and in O(n).

Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

# 240. Search a 2D Matrix II

## Description: 矩阵搜索

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

Integers in each row are sorted in ascending from left to right.
Integers in each column are sorted in ascending from top to bottom.

Example:

Given target = 5, return true.

Given target = 20, return false.

# 279. Perfect Squares

## Description: 找到最少的平方和个数

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

Example 1:

Example 2:

## 解法一: 四平方和定理(最优)

• 如果 $n$ 可以被 4 整除, 那么 $n$ 和 $n/4$ 的最少平方和数字个数相同.
• 如果 $n \% 8=7$, 那么 $n$ 的最少平方和个数一定为 4.

1. 循环整除 4, 降低 $n$ 的大小;
2. 判断是否有 $n \% 8 =7$, 如果有, 则直接返回 4;
3. 查看 $n$ 是否能够拆分成两个数(其中一个可以为0), 如果可以, 则返回 !!i + !!j, 即返回正整数的个数. 此处需要注意, i 需要从 0 开始遍历, 因为对于 $3^2+4^2 = 0^2 + 5^2 = 25$ 来说, 我们希望返回的是后者(即返回最少的平方和个数);
4. 如果上面都不行, 则只可能反正 3(因为 $n>0$).

## 解法二: DP

1. 申请 $n+1$ 大小的 DP 数组, 并令 dp[0]=0, 令其他元素为 INT_MAX, dp[i] 的值代表组成数字 $i$ 所需的最少的平方和数字个数;
2. 由于我们已经求得 dp[0] 的值, 因此, 对于 j=1, 2, ... 来说, 我们可以顺势求得 dp[0+j*j] = dp[0]+1=1.
3. 对于已经求得的 dp[i], 我们可以求得 dp[i+j*j] = min(dp[i+j*j], dp[i]+1), 这里的 min 是为了保证组成数字的平方和个数最少.
4. 最终, 返回 dp.back() 即为组成 $n$ 的最少的平方和个数.

## 解法三: DP

1. 申请只含有一个元素的 DP 数组 dp[0]=0;
2. 根据 dp[0] 的值计算 dp[1].(计算方法和解法二类似, 具体请看代码)
3. 根据 dp[0]~dp[i-1] 的值计算 dp[i].
4. i==n 时, 返回 dp[i].

## 解法四: 递归

http://www.cnblogs.com/grandyang/p/4800552.html

# 287. Find the Duplicate Number

## Description: 寻找重复元素

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Example 2:

Note:

• You must not modify the array (assume the array is read only).
• You must use only constant, O(1) extra space.
• Your runtime complexity should be less than O(n2).
• There is only one duplicate number in the array, but it could be repeated more than once.

## 解法三: Floyd 的乌龟和兔子(Floy 判圈算法)

Floyd’s Tortoise and Hare, 该算法是用来判断链表中是否含有环的. 对于此题, 我们换一个角度来解读, 数组中总共有 $n+1$ 个数, 这些数都是 $[1,n]$ 中的正整数, 因此, 至少会存在一个重复的数, 根据题目的假设, 有且仅有一个重复的数字, 那么, 我们假设该数字为 $k$, 于是, 我们可以将该数组表示成下面的形式(表中的 $x$ 代表该元素的值不为 $k$ ):

# 289. Game of Life

## Description: 游戏人生

According to the Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

1. Any live cell with fewer than two live neighbors dies, as if caused by under-population.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by over-population..
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Write a function to compute the next state (after one update) of the board given its current state. The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously.

Example:

1. Could you solve it in-place? Remember that the board needs to be updated at the same time: You cannot update some cells first and then use their updated values to update other cells.
2. In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches the border of the array. How would you address these problems?

## 解法一: 状态机

0: 从 0 到 0;
1: 从 1 到 1:
2: 从 1 到 0;
3: 从 0 到 1;

1. 常数空间复杂度: 正如解法一
2. 无边界限制: 修改边界空间条件, 使其变成 “循环” 二维矩阵.

# 300. Longest Increasing Subsequence

## Description: 求最长递增序列(可以不连续)的长度

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

Note:

• There may be more than one LIS combination, it is only necessary for you to return the length.
• Your algorithm should run in O(n2) complexity.

Could you improve it to O(n log n) time complexity?

## 解法四: DP+二分搜索(最优)

1. 初始时, 令 dp[] 数组为空, 即 dp=[];
2. 对于每一个元素 num, 我们查找 numdp 数组中的 upper_bound 迭代器(首个大于 num 的元素的迭代器), 假设取名为 upper;(注意, dp 数组是有序的, 所以这里的查询复杂度为 $O(logn)$)
3. 查看 upper-1 指向的元素是否和 num 相等, 如果相等, 则说明该元素已经存在, 那么就跳过该元素, 重新回到步骤2;
4. 如果 num 大于 dp 数组内的所有元素, 则将 num 添加进 dp 数组; 否则, 就将 dp 数组中大于 num 的第一个元素的值赋为 num.
5. 重复步骤2,3,4, 直到遍历完数组为止.

dp=[],初始时, 数组为空;
dp=[4], 遍历元素4, 加入到数组中;
dp=[4,10], 遍历元素10, 10大于所有元素, 将其添加到数组中;
dp=[3,10], 遍历元素3, 发现第一个大于3的值为4, 将其赋值为3;
dp=[3,4], 遍历元素4, 发现第一个大于4的的值为10, 将其赋值为4;
dp=[3,4,10], 遍历元素10, 10大于所有元素, 将其添加到数组中;
dp=[3,4,10], 遍历元素3, 3在数组中已经存在, 跳过该元素;
dp=[2,4,10], 遍历元素2, 发现第一个大于2个值为3, 将其赋值为2.

# 322. Coin Change

## Description: 硬币凑面额

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Example 2:

# 324. Wiggle Sort II

## Description: “驼峰” 排序

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

Example 1:

Example 2:

Note:
You may assume all input has valid answer.

Can you do it in O(n) time and/or in-place with O(1) extra space?

## 解法二: partition

• 大于 mid, 将大于 mid 的元素放在数组开始的奇数位上面;
• 小于 mid, 将小于 mid 的元素放在数组的偶数位上面;
• 等于 mid, 用所有等于 mid 的元素填充剩下的位置.

nth_element()(该函数在 C++17 后不是 $O(n)$, 而是 $O(nlogn)$, 但是在 C++11 中仍然是 $O(n)$):

1. 先令 even_i 指向数组的最后一个偶数位(从0位开始, 0算作偶数位), 令 odd_i 指向第一个奇数位(下标为1). 我们从最后一个偶数位元素(用下标 i 指示)开始进行判断;
2. 如果 nums[i]<mid, 则将 nums[i]nums[even_i] 交换, 交换后, even_i 不可再被访问, 令 even_i -= 2, 同时注意, 由于刚开始的时候 ieven_i 是相等的, 故也要令 i -= 2, 当 i<0 以后, 要令 i 指向最后一个奇数位.
3. 如果 nums[i]>mid, 则将 nums[i]nums[odd_i] 交换, 同时令 odd_i += 2, 注意, 此时, i 指向的数字是交换后的原来 odd_i 指向的数字, 因此, 我们需要对该数字进行判断, 故不能改变 i 的值.
4. 如果和 mid 相等, 则无需进行交换填充, 令其保存原值即可, 判断下一个元素, 令 i -=2, 同时还要判断 i 是否小于 0, 若小于, 则需令 i 指向最后的奇数位.

nth_element():

partition:

# 328. Odd Even Linked List

## Description: 奇偶链表

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

Example 2:

Note:
The relative order inside both the even and odd groups should remain as it was in the input.
The first node is considered odd, the second node even and so on …

# 334. Increasing Triplet Subsequence

## Description: 递增的三元子序列

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Example 2:

## 解法一: 用辅助变量指向 min 和 mid

1. 是否小于等于 min, 若满足, 则令 min=num;
2. 若不满足(1), 则说明 num > min, 判断 num 是否小于等于 mid, 若满足, 责令 mid=num;(此时 mid 一定大于 min, 且下标也大于 min 下标)
3. 若不满足(1)(2), 则说明 num 不仅大于 min, 而且大于 mid, 同时 num 的下标也大于前两者, 由此, 我们找到了一个满足条件的递增三元组子序列, 可直接返回 true. 否则, 重复以上步骤直至遍历完数组
4. 如果遍历完整个数组后, 仍然找不到符合条件的序列, 则说明不存在这样的序列, 返回 false.

# 341. Flatten Nested List Iterator

## Description: 将嵌套的多维列表展开成一维

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:

Example 2:

## 解法一: 栈

PS: 这道题可以在初始化时将列表全部展开并存储, 这样 hasNext() 就可以达到 $O(1)$ 的时间复杂度, 但是, 这是很不好的! 因为实际实现迭代器时, 我们往往只在需要的时候才会对元素进行展开, 这样可以获得最大的平均效率

# 347. Top K Frequent Elements

## Description: 寻找频率最高的 k 个数字

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Example 2:

Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

# 378. Kth Smallest Element in a Sorted Matrix

## Description: 找到半有序数组中的第 k 小的元素

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

Note:
You may assume k is always valid, 1 ≤ k ≤ n2.

## 解法一: 堆

1. 利用将矩阵中每一行的首元素(也就是第一列元素, 同理, 这里也可以用第一行元素)构造一个最小堆(这一步的复杂度小于 $O(nlogn)$), 堆中的元素是一个 pair, 其中 first 为元素的值, second 又是一个 pair, 存储着值的行列坐标 (i, j)
2. 将最小堆中的一个元素弹出(弹出的是当前堆最小的元素), 然后再将弹出元素的同一行的下一个元素(通过元素坐标获取)压入堆, 压入后, 堆会自动排序, 使得最小的元素位于堆顶.
3. 重复步骤(2) k-1 次以后. 我们已经弹出了整个矩阵的最小的 k-1 个元素, 那么现在堆顶中的元素就是第 k 小的元素, 将其返回即可

## 解法二: 二分查找

1. 获取矩阵中元素的最小值 low 和最大值 high
2. mid = (high+low)/2, 然后我们利用 upper_bound() 函数来查找矩阵中第一个大于 mid 的元素(耗时 $O(logn)$), 接着计算这个元素之前的元素数量. 对矩阵的每一行重复这个步骤, 并将所有的元素数量累加起来
3. 如果累加元素数 count < k, 说明, mid 的值较小, 我们令 low=mid+1, 否则, 说明 count>=k, 我们令 high=mid, 注意, 这里的赋值关系最好不要改动, 并且要知道为什么令 high=mid, 而不是 mid-1.
4. 重复上述过程直至 low=high, 此时, lowhigh 的值就是矩阵中第 k 小的值

# 380. Insert Delete GetRandom O(1)

## Description: 常数时间复杂度的插入,删除,和随机获取

Design a data structure that supports all following operations in average O(1) time.

• insert(val): Inserts an item val to the set if not already present.
• remove(val): Removes an item val from the set if present.
• getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Example:

## 解法一: 哈希表+数组

• 插入: 用数组的 push_back() 存储新来的元素, 同时存入哈希表, key 为元素值, val 为元素在数组中的下标;
• 删除: 先用哈希表获取元素的下标, 然后将数组中的该元素和数组的最后一个元素交换, 接着用 pop_back() 删除该元素, 然后用 erase() 从哈希表中删除该元素, 最后在哈希表中更新被交换元素的下标;
• 获取随机元素: 利用 C++ 的内置随机函数 rand() 来获取随机数. 但是注意, rand() 对生成的随机数质量无法保证, 在 C++11 中, 已经建议使用随机数生成设施来替换 rand(). 另外注意: 如果想要使用 srand() 来播种, 那么不能将该语句放在 getRandom() 函数中, 因为重复播种会使得每次生成的随机数都一样, 正确的做法是将其放在构造函数中, 只进行一次播种.

# 384. Shuffle an Array

## Description: 打乱数组

Shuffle a set of numbers without duplicates.

Example:

## 解法一: 随机交换

• shuffle: 打乱时, 遍历数组的下标, 然后随机生成一个下标, 令二者指向的元素交换. 更多分析请看Knuth shuffle算法
• reset: 直接返回缓存的原始数组

# 395. Longest Substring with At Least K Repeating Characters

## Description

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Example 2: