# 字符串和数组

## 字符串

Leetcode 224

Leetcode 227

### 字符串操作

#### Multiply Strings

Leetcode 43字符串乘法

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Leetcode 445无符号字符串加法

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.

What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

### Longest Substring with At Least K Repeating Characters

Leetcode 395

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:

Leetcode 151

Leetcode 76

#### Decoded String at Index

Leetcode 884

An encoded string S is given. To find and write the decoded string to a tape, the encoded string is read one character at a time and the following steps are taken:

If the character read is a letter, that letter is written onto the tape.
If the character read is a digit (say d), the entire current tape is repeatedly written d-1 more times in total.
Now for some encoded string S, and an index K, find and return the K-th letter (1 indexed) in the decoded string.

#### Longest Palindromic Substring

Leetcode 5

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

Leetcode 468

## 数组

### 数组操作

#### Increasing Triplet Subsequence

Leetcode 334

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.

#### Contiguous Array

Leetcode 525

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

#### 4Sum II

Leetcode 454

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

#### Largest Number

Leetcode 179

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

Note: The result may be very large, so you need to return a string instead of an integer.

#### First Missing Positive

Leetcode 41

Given an unsorted integer array, find the smallest missing positive integer.

#### Find the Duplicate Number

Leetcode 287

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.

#### Find All Duplicates in an Array

Leetcode 442

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

#### Longest Substring Without Repeating Characters

Leetcode 3

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

#### 连续子数组的最大值

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

### 双指针

#### Minimum Size Subarray Sum

Leetcode 209

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

#### 3Sum

Leetcode 15

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.

#### 3Sum Closest

Leetcode 16

Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

#### Super Ugly Number

Leetcode 313

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k.

#### Remove Duplicates from Sorted Array II

Leetcode 80

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

#### Trapping Rain Water

Leetcode 42

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

# 队列

## Shortest Subarray with Sum at Least K

Leetcode 862

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

## Sliding Window Maximum

Leetcode 239

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.

Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for non-empty array.

Could you solve it in linear time?

# 链表

## LRU Cache（双端链表list）

Leetcode 146

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.

Could you do both operations in O(1) time complexity?

list是stl的双端链表，链表指针可以用O(1)时间删除，但是随机访问时间慢

## Insertion Sort List

Leetcode 147

Sort a linked list using insertion sort. Algorithm of Insertion Sort:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
It repeats until no input elements remain.

## Sort List

Leetcode 148

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

## Remove Duplicates from Sorted List II

Leetcode 82

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

## Reorder List

Leetcode 143

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Leetcode 92

Reverse a linked list from position m to n. Do it in one-pass.

Note: 1 ≤ m ≤ n ≤ length of list.

# 栈

## 132 Pattern

Leetcode 456

Given a sequence of n integers a1, a2, …, an, a 132 pattern is a subsequence ai, aj, ak such that i < j < k and ai < ak < aj. Design an algorithm that takes a list of n numbers as input and checks whether there is a 132 pattern in the list.

Note: n will be less than 15,000.

## Next Greater Element II

Leetcode 503

Given a circular array (the next element of the last element is the first element of the array), print the Next Greater Number for every element. The Next Greater Number of a number x is the first greater number to its traversing-order next in the array, which means you could search circularly to find its next greater number. If it doesn’t exist, output -1 for this number.

## Binary Search Tree Iterator

Leetcode 173

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

## Verify Preorder Serialization of a Binary Tree

Leetcode 331

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.

For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.

Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.

You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.

# HashTable

## Max Points on a Line

Leetcode 149

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

# 桶

## Contains Duplicate III

Leetcode 220

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

# 树

## Populating Next Right Pointers in Each Node II

Leetcode 117

Given a binary tree

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.

## Count Complete Tree Nodes

Leetcode 222

Given a complete binary tree, count the number of nodes.

Note:

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

## Delete Node in a BST

Leetcode 450

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.
Note: Time complexity should be O(height of tree).

## Serialize and Deserialize BST

Leetcode 449

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

# 前缀树

## Implement Trie (Prefix Tree)

Leetcode 208

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

## Maximum XOR of Two Numbers in an Array

Leetcode 421

Given a non-empty array of numbers, a0, a1, a2, … , an-1, where 0 ≤ ai < 231.

Find the maximum result of ai XOR aj, where 0 ≤ i, j < n.

Could you do this in O(n) runtime?

## Word Search II

Leetcode 212

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.

# 堆

## TopK

### Kth Largest Element in an Array

Leetcode 215

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.

### Top K Frequent Elements

Leetcode 347

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

### Find K Pairs with Smallest Sums

Leetcode 373

You are given two integer arrays nums1 and nums2 sorted in ascending order and an integer k.

Define a pair (u,v) which consists of one element from the first array and one element from the second array.

Find the k pairs (u1,v1),(u2,v2) …(uk,vk) with the smallest sums.

## Find Median from Data Stream

Leetcode 295

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,
[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.

## Sliding Window Median

Leetcode 480

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.