这里总结一些leetcode上比较经典的与数据结构相关的例题与思路，因为部分数据结构更偏向与搜索或贪心类型，该类题目就不再本部分总结…
字符串和数组
字符串和数组是比较典型的线性表结构，由于比较好访问，所以通常会在该类数据结构上设计搜索和dp类型的题目。
搜索和动规类型的题目会另做讨论，本部分主要总结比较典型反映字符串和数组属性的题目，例如线性表操作或双指针等。
字符串
表达式求值
表达式求值是一类比较考察细节的题目，一般会涉及括号，四则运算，小数和空格，所以在写的时候要注意思路清晰，以下提供一个模板：
模板
1 

Basic Calculator
1  Implement a basic calculator to evaluate a simple expression string. 
1  class Solution { 
Basic Calculator II
1  Implement a basic calculator to evaluate a simple expression string. 
1  class Solution { 
字符串操作
Multiply Strings
Leetcode 43字符串乘法
Given two nonnegative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
1  Example 1: 
1  class Solution { 
Add Two Numbers II
Leetcode 445无符号字符串加法
You are given two nonempty linked lists representing two nonnegative 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.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
1  Example: 
1  /** 
带符号字符串加减法模板
1 

字符串双指针题目
双指针有两种用法，第一种是用于更新原字符串，另一种是用于搜索。一般而言，快指针不光可以表示原本字符串上的位置，同时还可以表示扩展字符串后的位置。
Longest Substring with At Least K Repeating Characters
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:
1  Input: 
Example 2:
1  Input: 
1  class Solution { 
Reverse Words in a String
1  Given an input string, reverse the string word by word. 
1  class Solution { 
Minimum Window Substring
1  Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n). 
1  class Solution { 
Decoded String at Index
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 d1 more times in total.
Now for some encoded string S, and an index K, find and return the Kth letter (1 indexed) in the decoded string.
1  Example 1: 
1  class Solution { 
Longest Palindromic Substring
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
1  Example 1: 
1  // 最长回文数的最常见算法为O(n2)，还有优化版本，但是需要讲解数学逻辑，之后更新... 
字符串处理
此部分会不断更新…
Validate IP Address
1  Write a function to check whether an input string is a valid IPv4 address or IPv6 address or neither. 
1  // 此方法主要是用于练习字符串处理，如果想要寻找更加高效的算法请在leetcode discuss区寻找 
数组
数组操作
Increasing Triplet Subsequence
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 ≤ n1 else return false.
Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.
1  Example 1: 
1  class Solution { 
Contiguous Array
Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.
1  Example 1: 
Note: The length of the given binary array will not exceed 50,000.
1  class Solution { 
4Sum II
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 2^{31}  1.
1  Example: 
1  class Solution { 
Largest Number
Given a list of non negative integers, arrange them such that they form the largest number.
1  Example 1: 
Note: The result may be very large, so you need to return a string instead of an integer.
1  class Solution { 
First Missing Positive
Given an unsorted integer array, find the smallest missing positive integer.
1  Example 1: 
1  class Solution { 
Find the Duplicate Number
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.
1  Example 1: 
1  class Solution { 
Find All Duplicates in an Array
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?
1  Example: 
1  class Solution { 
Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
1  Example 1: 
1  class Solution { 
连续子数组的最大值
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,3,2,7,15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
1  class Solution { 
整数中1出现的次数（从1到n整数中1出现的次数）
牛客网
因为此题细节较多，为了多加练习，在此处也做整理
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
1  class Solution { 
双指针
Minimum Size Subarray Sum
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.
1  Example: 
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
1  class Solution { 
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.
1  Example: 
1  class Solution { 
3Sum Closest
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.
1  Example: 
The sum that is closest to the target is 2. (1 + 2 + 1 = 2).
1  // 3Sum的扩展版本 
丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
1  class Solution { 
Super Ugly Number
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.
1  Example: 
1  class Solution { 
Remove Duplicates from Sorted Array II
Given a sorted array nums, remove the duplicates inplace 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 inplace with O(1) extra memory.
1  Example 1: 
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:
1  // nums is passed in by reference. (i.e., without making a copy) 
1  class Solution { 
Trapping Rain Water
Given n nonnegative 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!
1  Example: 
1  class Solution { 
构建乘积数组
给定一个数组A[0,1,…,n1],请构建一个数组B[0,1,…,n1],其中B中的元素B[i]=A[0]A[1]…A[i1]A[i+1]…A[n1]。不能使用除法。
1  class Solution { 
队列
队列通常的应用一般包括单调队列等，这里只列出一部分单调队列题目，之后不断补充…
Shortest Subarray with Sum at Least K
Return the length of the shortest, nonempty, contiguous subarray of A with sum at least K.
If there is no nonempty subarray with sum at least K, return 1.
1  Example 1: 
1  class Solution { 
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.
1  Example: 
Note:
You may assume k is always valid, 1 ≤ k ≤ input array’s size for nonempty array.
Follow up:
Could you solve it in linear time?
1  class Solution { 
链表
LRU Cache（双端链表list）
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.
Follow up:
Could you do both operations in O(1) time complexity?
1  Example: 
list是stl的双端链表，链表指针可以用O(1)时间删除，但是随机访问时间慢
1  typedef list<int>::iterator Iter; 
Insertion Sort List
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.
1  Example 1: 
1  /** 
Sort List
Sort a linked list in O(n log n) time using constant space complexity.
1  Example 1: 
1  /** 
1  // 快排版本 
Remove Duplicates from Sorted List II
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
1  Example 1: 
1  /** 
Reorder List
Given a singly linked list L: L0→L1→…→Ln1→Ln,
reorder it to: L0→Ln→L1→Ln1→L2→Ln2→…
You may not modify the values in the list’s nodes, only nodes itself may be changed.
1  Example 1: 
1  /** 
Reverse Linked List II
Reverse a linked list from position m to n. Do it in onepass.
Note: 1 ≤ m ≤ n ≤ length of list.
1  Example: 
1  /** 
栈
132 Pattern
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.
1  Example 1: 
1  class Solution { 
Next Greater Element II
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 traversingorder 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.
1  Example 1: 
1  class Solution { 
Binary Search Tree Iterator
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.
1  /** 
Verify Preorder Serialization of a Binary Tree
One way to serialize a binary tree is to use preorder traversal. When we encounter a nonnull node, we record the node’s value. If it is a null node, we record using a sentinel value such as #.
1  _9_ 
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”.
1  Example 1: 
1  class Solution { 
HashTable
哈希表通常用来记录一些中间状态从而实现O(1)，这里提供一些比较典型的例子，之后不断补充…
Max Points on a Line
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.
1  Example 1: 
1  /** 
桶
Contains Duplicate III
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.
1  Example 1: 
1  class Solution { 
树
最近公共祖先
1 

指定节点距离叶子节点最近的距离
此题是之前面试中一道题，题目意思是如果指定一个值（若存在则唯一存在），寻找距离此节点最近叶子节点的距离，因为此题的细节比较多，所以这里也列出来
例如：按前序遍历的树 1,2,3,4,5,#,#,#,6,7,#,#,8,9,#,10,#,#,11,#,#,#,12,#,#
1 

Populating Next Right Pointers in Each Node II
Given a binary tree
1  struct TreeLinkNode { 
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.
1  Note: 
1  /** 
Count Complete Tree Nodes
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.
1  Example: 
1  /** 
Delete Node in a BST
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).
1  Example: 
1  /** 
Serialize and Deserialize BST
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.
1  /** 
前缀树
Implement Trie (Prefix Tree)
Implement a trie with insert, search, and startsWith methods.
1  Example: 
1  struct TrieNode { 
Maximum XOR of Two Numbers in an Array
Given a nonempty array of numbers, a0, a1, a2, … , an1, 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?
1  Example: 
1  struct TrieNode { 
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.
1  Example: 
1  struct TrieNode { 
堆
TopK
Kth Largest Element in an Array
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.
1  Example 1: 
1  class Solution { 
Top K Frequent Elements
Given a nonempty array of integers, return the k most frequent elements.
1  Example 1: 
1  class Solution { 
Find K Pairs with Smallest Sums
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.
1  Example 1: 
1  class Solution { 
Find Median from Data Stream
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.
1  Example: 
1  class MedianFinder { 
Sliding Window Median
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.
1  Examples: 
1  class Solution { 
Design Twitter
Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:
postTweet(userId, tweetId): Compose a new tweet.
getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.
follow(followerId, followeeId): Follower follows a followee.
unfollow(followerId, followeeId): Follower unfollows a followee.
1  Example: 
1  struct tweet { 
实际中应该使用的是对已经排序了的数组使用多路归并，思路是堆中存放的是路角标和列角标的pair：
1 
