原题

https://leetcode.com/problems/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.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

原题

https://leetcode.com/problems/trapping-rain-water/

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.

思路

使用双指针，分别从两头往最高处逼近。每次经过刷新左边和右边的最高值，该处结果等于最高值与当前值的差。

原题

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

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

Follow up:

Could you do this in one pass?

思路

使用两个指针fast以及slow，fast先出发，slow相隔n位再出发。当fast走到尽头时slow跳过下一指针即可。

原题

https://leetcode.com/problems/generate-parentheses/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

思路

使用动态规划，分析子问题：每次加括号要么加在外面，要么加在旁边。

原题

https://leetcode.com/problems/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, and you may not use the same element twice.

思路

使用hashmap查表，拿到数字首先查找余值是否在表内，若在的话直接返回表内的对应值。接着将数字以及index存入表内。

原题

https://leetcode.com/problems/container-with-most-water/

Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). nvertical 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.

思路

贪心算法，从左右两边开始，从短的一边往中间缩进并记录最大值。由于短板效应从短的一边往中间缩进是最有利的。

原题

https://leetcode.com/problems/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.

思路

马拉车方法 (Manacher’s Algorithm) 利用回文的性质减少运算。