iyidgnaw
5/12/2018 - 1:46 AM

## Summary of LeetCode

(use four # to declare the title of each problem.use two # to declare the tag)

## Array

#### 48. Rotate Image

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

Rotate the image by 90 degrees (clockwise).

Follow up: Could you do this in-place?

``````zip(*matrix)
``````

#### 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

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.

#### 167. Two Sum II - Input array is sorted

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

#### 219. Contains Duplicate

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

#### 442. 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?

#### 26. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array nums = `[1,1,2]`,

Your function should return length = `2`, with the first two elements of nums being `1` and `2` respectively. It doesn't matter what you leave beyond the new length.

``````int i = 0;
for (int n : nums)
if (i == 0 || n > nums[i-1])
nums[i++] = n;
return i;
``````

i只有在每次出现了非重复元素时才后移，因此最后i指向的位置，就是下一个非重复元素将要被放置的位置，也就是“完成整理区”的右边界，恰好也是非重复元素的个数。

#### 80. Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates": What if duplicates are allowed at most twice?

For example, Given sorted array nums = `[1,1,1,2,2,3]`,

Your function should return length = `5`, with the first five elements of nums being `1`, `1`, `2`, `2` and `3`. It doesn't matter what you leave beyond the new length.

#### 27. Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example: Given input array nums = `[3,2,2,3]`, val = `3`

Your function should return length = 2, with the first two elements of nums being 2.

#### 283.Move Zeroes

Given an array `nums`, write a function to move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.

For example, given `nums = [0, 1, 0, 3, 12]`, after calling your function, `nums` should be `[1, 3, 12, 0, 0]`.

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

#### 209. 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.

For example, given the array `[2,3,1,2,4,3]` and `s = 7`, the subarray `[4,3]` has the minimal length under the problem constraint

#### 349. Intersection of Two Arrays

• use hashset to hash one of the array, build up a new arraylist to store the element existing in both array.

• if one element is found in another array, add it to the arraylist and then delete the key in the hashset.

使用python的话可以简单一些，将两个list转成set。set可以采用&操作来获取交集，然后再用list()转回list。

#### 350. Intersection of Two Arrays II

• use HashMap to hash the (key,value) pair in which the key is the content and the value is the time of appearance of such content.

• In the go through process ,every time we detect whether it is in the hashmap and the appearing time is bigger than 0

• We use the "value" in hashmap as a counter of the appearance of the key.

• To update the time of appearance, we just put new (key,value) pair into the hashmap. the new value is updated from the value before.(we use get() method to get the past value of such key.)

``````HashMap <Integer,Integer> hs
= new HashMap <Integer,Integer>();
for (int i=0;i<nums1.length;i++){
if (hs.containsKey(nums1[i]))
hs.put(nums1[i],hs.get(nums1[i])+1);
else
hs.put(nums1[i],1);
}
``````

#### 345. Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1: Given s = "hello", return "holle".

Example 2: Given s = "leetcode", return "leotcede".

Note: The vowels does not include the letter "y".

#### 238. Product of Array Except Self

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

Solve it without division and in O(n).

For example, given `[1,2,3,4]`, return `[24,12,8,6]`.

Ans:从左右两侧分别逼近所求值

#### 268. Missing Number

Given an array containing n distinct numbers taken from `0, 1, 2, ..., n`, find the one that is missing from the array.

For example, Given nums = `[0, 1, 3]` return `2`.

#### 163. Missing Ranges

Given a sorted integer array where the range of elements are in the inclusive range [lower, upper], return its missing ranges.

For example, given `[0, 1, 3, 50, 75]`, lower = 0 and upper = 99, return `["2", "4->49", "51->74", "76->99"].`

#### 414. Third Maximum Number

Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).

#### 46. Permutations

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

For example, `[1,2,3]` have the following permutations:

``````[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]
``````

``````def all_perms(elements):
if len(elements) <=1:
yield elements
else:
for perm in all_perms(elements[1:]):
for i in range(len(elements)):
# nb elements[0:1] works in both string and list contexts
yield perm[:i] + elements[0:1] + perm[i:]
``````

``````[1,2,3]
[2,1,3]
[2,3,1]
[1,3,2]
[3,1,2]
[3,2,1]
``````

1 使用for循环来遍历generator时返回的是list包含的结果，所以在此处是二维list。

2 使用yield，但是配合了for循环所有就是执行到所有yield结束。

3 每次的invariant实际是数组的长度，所以每次elements[0:1]实际是当前的第一个元素。

#### 15. 3Sum

Given an array S of n integers, are there elements a, b, c in S 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.

``````For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]
``````

#### 16. 3Sum Closet

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

``````    For example, given array S = {-1 2 1 -4}, and target = 1.

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

#### 18. 4Sum

Given an array S of n integers, are there elements a, b, c, and d in S 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.

``````For example, given array S = [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]
]
``````

4Sum比3Sum来说，就是在最外层i的基础上再增加一个k作为外层循环，其余均不变。

#### 454. 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 231 - 1.

Example:

``````Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

``````

#### 259. 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets `i, j, k` with `0 <= i < j < k < n` that satisfy the condition `nums[i] + nums[j] + nums[k] < target`.

For example, given nums = `[-2, 0, 1, 3]`, and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

``````[-2, 0, 1]
[-2, 0, 3]

``````

Follow up: Could you solve it in O(n2) runtime?

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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

``````while l1 or l2 or carry:
``````

``````carry, val = divmod(v1+v2+carry, 10)
``````

divmod语句可以同时获得结果和余数。

``````cur.next = head
cur= temp
temp = temp.next
``````

#### 24. Swap Nodes In Pairs

For example, Given `1->2->3->4`, you should return the list as `2->1->4->3`.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

First = cur.next

second = cur.next.next

First.next = second.next

second.next = first

cur.next = second

Cur = first

• use two pointer to find out the middle point of the linked list and reverse the first or second half. Then compare.

#### 21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

`````` while(l1!=null&&l2!=null){
if (l1.val<=l2.val){
cur.next = l1;
l1 = l1.next;
}
else{
cur.next =l2;
l2 = l2.next;
}
cur = cur.next;
}
``````

Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

#### 142. Linked List Cycle II

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.

2*（A+N） = A+B+N

A+N = B

#### 160. Intersection of Two Linked Lists

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

``````A:          a1 → a2
↘
c1 → c2 → c3
↗
B:     b1 → b2 → b3

``````

begin to intersect at node c1.

Notes:

• If the two linked lists have no intersection at all, return `null`.
• The linked lists must retain their original structure after the function returns.
• You may assume there are no cycles anywhere in the entire linked structure.
• Your code should preferably run in O(n) time and use only O(1) memory.

#### 237. Delete Node in a linked list

！！！把当前节点的val置为下一个节点的val，再把当前节点的next指向next.next！！！

#### 203. Remove Linked List Elements

Remove all elements from a linked list of integers that have value val.

Example *Given:* 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 *Return:* 1 --> 2 --> 3 --> 4 --> 5

#### 19. Remove Nth Node From End of List

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

For example,

``````   Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.
``````

#### 86. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example, Given `1->4->3->2->5->2` and x = 3, return `1->2->2->4->3->5`.

#### 147. Insertion Sort List

Sort a linked list using insertion sort.

pre每次都从dummy出发，最终指向比当前元素小的最大位置。

cur指向当前遍历的元素

temp用来存储cur的下一个元素，因为要把cur插入到已排序列中，所以要存储cur的下一个节点

``````dummy = ListNode(0)
pre = dummy
while(cur!=None):
temp = cur.next
while pre.next!=None and pre.next.val<cur.val:
pre = pre.next
cur.next = pre.next
pre.next = cur
cur = temp
pre = dummy
return dummy.next
``````

## Dynamic Programming

#### 264. Ugly Number II

Write a program to find the `n`-th ugly number.

Ugly numbers are positive numbers whose prime factors only include `2, 3, 5`. For example, `1, 2, 3, 4, 5, 6, 8, 9, 10, 12` is the sequence of the first `10` ugly numbers.

Note that `1` is typically treated as an ugly number, and n does not exceed 1690.

#### 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

#### 121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Answer:The logic to solve this problem is same as "max subarray problem" using `Kadane's Algorithm`. Since no body has mentioned this so far, I thought it's a good thing for everybody to know.

All the straight forward solution should work, but if the interviewer twists the question slightly by giving the difference array of prices, Ex: for `{1, 7, 4, 11}`, if he gives `{0, 6, -3, 7}`, you might end up being confused.

Here, the logic is to calculate the difference (`maxCur += prices[i] - prices[i-1]`) of the original array, and find a contiguous subarray giving maximum profit. If the difference falls below 0, reset it to zero.

``````    public int maxProfit(int[] prices) {
int maxCur = 0, maxSoFar = 0;
for(int i = 1; i < prices.length; i++) {
maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]);
maxSoFar = Math.max(maxCur, maxSoFar);
}
return maxSoFar;
}
``````

#### 122. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

#### 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

``````for money in nums:
temp = skip
skip = max(rob,skip)
rob = money+temp
``````

#### 243. Shortest Word Distance

Given a list of words and two words word1 and word2, return the shortest distance between these two words in the list.

For example, Assume that words = `["practice", "makes", "perfect", "coding", "makes"]`.

Given word1 = `“coding”`, word2 = `“practice”`, return 3. Given word1 = `"makes"`, word2 = `"coding"`, return 1.

#### 255. Paint house

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n*3 cost matrix. For example, `costs[0][0]` is the cost of painting house 0 with color red; `costs[1][2]` is the cost of painting house 1 with color green, and so on... Find the minimum cost to paint all houses.

Note: All costs are positive integers.

``````f[n] = cost + min(f[n+1:]+f[:n])
``````

``````prev = [now[i] + min(prev[:i]+prev[i+1:]) for i in range(3)]

#prev is the backup value for last iter.
#prev[:i]+prev[i+1:] is the list of value except the cost of current i.
``````

#### 276. Paint Fence

There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note: n and k are non-negative integers.

``````same ,diff= k,k*(k-1)
while(n>2):
temp = same
same = diff
diff = (temp+same)*(k-1)
n-=1
``````

#### 55. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array `[-2,1,-3,4,-1,2,1,-5,4]`, the contiguous subarray `[4,-1,2,1]` has the largest sum = `6`.

``````for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
``````

#### 152. Maximum Product Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest product.

For example, given the array `[2,3,-2,4]`, the contiguous subarray `[2,3]` has the largest product = `6`.

``````for i in nums[1:]:
temp = max_value
max_value = max(i*max_value,i*min_value,i)
min_value = min(i*temp,i*min_value,i)
pre_max = max(max_value,pre_max)
#g中存储最小值，f中存储最大值，res中存储当前的最大结果
#另外要注意，每一轮的第一项更新之前要先用temp备份好。
``````

#### 416. Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

``````Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
``````

``````f[N][target]
#每一个单元格中的值为放入前N个元素是否能够达到target的值，初始化为一个True和target个False
``````

​ 0 1 2 3 4 5 6

init T F F F F F F

``````f[n] = (f[n] or f[n-i])
``````

2 T F T F F F F

2 T F T F T F F

3 T F T T T F F

5 T F T T T T F

#### 338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example: For `num = 5` you should return `[0,1,1,2,1,2]`.

dp[0] = 0;

dp[1] = dp[1-1] + 1;

dp[2] = dp[2-2] + 1;

dp[3] = dp[3-2] +1;

dp[4] = dp[4-4] + 1;

dp[5] = dp[5-4] + 1;

dp[6] = dp[6-4] + 1;

dp[7] = dp[7-4] + 1;

dp[8] = dp[8-8] + 1; ..

#### 139. Word Break

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. You may assume the dictionary does not contain duplicate words.

For example, given s = `"leetcode"`, dict = `["leet", "code"]`.

Return true because `"leetcode"` can be segmented as `"leet code"`.

UPDATE (2017/1/4): The wordDict parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

``````      for w in wordDict:
if w == s[i-len(w)+1:i+1] and (d[i-len(w)] or i-len(w) == -1):
d[i] = True
``````

#### 279. Perfect Squares

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

For example, given n = `12`, return `3` because `12 = 4 + 4 + 4`; given n = `13`, return `2` because `13 = 4 + 9`.

``````for j in range(i*i,len(dp)):
dp[j] = min(dp[j],dp[j-i*i]+1)
``````

#### 120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.

For example, given the following triangle

``````triangle = [
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
``````

The minimum path sum from top to bottom is `11` (i.e., 2 + 3 + 5 + 1 = 11).

``````f= [
[0],
[0,0],
[0,0,0],
[0,0,0,0]
]
``````

``````f[i][j] = triangle[i][j] + min(f[i-1][j-1],f[i-1][j])
``````

#### 62. Unique Paths

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?

``````f[i][j] = f[i-1][j]+f[i][j-1]
``````

``````f = [
[1,1,1,1,1,1,1]
[1,0,0,0,0,0,0]
[1,0,0,0,0,0,0]
]
``````

#### 64. Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

``````f[i][j] = grid[i][j]+min(f[i-1][j],f[i][j-1])
``````

``````f = [
[1,2,8,15,24,45]
[3,0,0,0,0,0]
[8,0,0,0,0,0]
]
``````

#### 322. Coin Change

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: coins = `[1, 2, 5]`, amount = `11` return `3` (11 = 5 + 5 + 1)

Example 2: coins = `[2]`, amount = `3` return `-1`.

#### 343. Integer Break

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

For example, given n = 2, return 1 (2 = 1 + 1); given n = 10, return 36 (10 = 3 + 3 + 4).

Note: You may assume that n is not less than 2 and not larger than 58.

``````f(n) = max(k*(n-k),k*f(n-k)| 1<=k<=n/2)
``````

#### 221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

For example, given the following matrix:

``````1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

``````

Return 4.

``````dp[i][j] == 1
``````

``````dp[i][j] = min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j])+1
``````

#### 300. Longest Increasing Subsequence

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

For example, Given `[10, 9, 2, 5, 3, 7, 101, 18]`, The longest increasing subsequence is `[2, 3, 7, 101]`, therefore the length is `4`. Note that 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.

## Hash

#### 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.

Example:

``````Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

``````

UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.

#### 49. Group Anagrams

Given an array of strings, group anagrams together.

For example, given: `["eat", "tea", "tan", "ate", "nat", "bat"]`, Return:

``````[
["ate", "eat","tea"],
["nat","tan"],
["bat"]
]
``````

Note: All inputs will be in lower-case.

Trick，设置一个index指针指向新的二元列表中的一个新元素，然后将key对应的value设置为这个index，由此通过字典的映射，就可以知道这个元素将被添加到哪一个list中。

#### 202. Happy Number

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

**Example: **19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

#### 136. Single Number

Given an array of integers, every element appears twice except for one. Find that single one.

Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

``````result^=i
``````

122 = 1

#### 325. Maximum Size Subarray Sum Equals K

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.

Example 1:

Given nums = `[1, -1, 5, -2, 3]`, k = `3`, return `4`. (because the subarray `[1, -1, 5, -2]` sums to 3 and is the longest)

Example 2:

Given nums = `[-2, -1, 2, 1]`, k = `1`, return `2`. (because the subarray `[-1, 2]` sums to 1 and is the longest)

Follow Up: Can you do it in O(n) time?

## String

#### 5. 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.

Example:

``````Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

``````

Example:

``````Input: "cbbd"

Output: "bb"
``````

aab+b=aabb 2->4

aa+a = aaa 2->3

#### 12. Integer To Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

M = ["", "M", "MM", "MMM"]

#### 14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Given two binary strings, return their sum (also a binary string).

For example, a = `"11"` b = `"1"` Return `"100"`.

• 使用int将字符串转化为整形数时，可以附加一个转换的进制参数。

如果附加的参数为2的话，那么也就是按照二进制将字符串转化为实际数值，所以会返回一个2

``````int("10",2) = 2
int("10") = 10
``````
• 二进制加法：

``````"{0:b}".format(i1+i2)
# https://docs.python.org/3.6/library/stdtypes.html#str.format
``````

#### 344. Reverse String

• toCharArray convert the String into char[], and then use StringBuilder to append each char from the end. Then use toString() to convert back to String.

#### 383. Ronsom Note

Given an arbitrary ransom note string and another string containing letters from all the magazines, write a function that will return true if the ransom note can be constructed from the magazines ; otherwise, it will return false.

Each letter in the magazine string can only be used once in your ransom note.

Note: You may assume that both strings contain only lowercase letters.

``````canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true
``````

#### 13. Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

“CM” = -100+1000 = 900

#### 151. Reverse word in a string

Given an input string, reverse the string word by word.

For example, Given s = "`the sky is blue`", return "`blue is sky the`".

``````return " ".join(s.split()[::-1])
``````

## Others

#### 155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Ans: 在stack的基础上，每次push的时候判断是否出现了更小的元素，如果出现，那么先将现在的min备份（push）然后再push当前传入的元素。同理在pop的时候，如果当前元素就是最小的元素,那么要将self.min设置为再一次pop出的元素(因为刚才的次最小值已经备份在了这个元素的前一个位置)

#### 20. Valid Parentheses

Given a string containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid.

The brackets must close in the correct order, `"()"` and `"()[]{}"` are all valid but `"(]"` and `"([)]"` are not.

#### 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:

``````[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
``````

（（（）））

（（）然后继续执行（，到达

（（）（））然后再返回添加右

#### 60. Permutation Sequence

The set `[1,2,3,…,*n*]` contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3):

1. `"123"`
2. `"132"`
3. `"213"`
4. `"231"`
5. `"312"`
6. `"321"`

Given n and k, return the kth permutation sequence.

Note: Given n will be between 1 and 9 inclusive

k／(n-1)!的除数就是起始的数字

## Backtracking

#### 79. Word Search

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.

For example, Given board =

``````[
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word = "ABCCED", -> returns true,
word = "SEE", -> returns true,
word = "ABCB", -> returns false.
``````

nested function传入i j k.

k是一个指针，指向当前需要的word中字符

recur DFS时k指针的位置要向后移动，因为当前的k位置的字符已经得到了匹配。

#### 39. Combination Sum

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

• All numbers (including target) will be positive integers.
• The solution set must not contain duplicate combinations.

For example, given candidate set `[2, 3, 6, 7]` and target `7`, A solution set is:

``````[
[7],
[2, 2, 3]
]
``````

#### Combinations

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

For example, If n = 4 and k = 2, a solution is:

``````[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
``````

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example: Given `"25525511135"`,

return `["255.255.11.135", "255.255.111.35"]`. (Order does not matter)

#### 78. Subsets

Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example, If nums = `[1,2,3]`, a solution is:

``````[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
``````

``````res += [item+[num] for item in res]
``````

#### 131. Palindrome Partitioning

Given a string s, partition s such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of s.

For example, given s = `"aab"`, Return

``````[
["aa","b"],
["a","a","b"]
]
``````