\344. Reverse String

Easy

Write a function that reverses a string. The input string is given as an array of characters char[].

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

You may assume all the characters consist of printable ascii characters.

\14. Longest Common Prefix

Easy

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

If there is no common prefix, return an empty string "".

Example 1:

1
2

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

1
2
3

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

\3. Longest Substring Without Repeating Characters

Medium

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

Example 1:

1
2
3

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3.

Example 2:

1
2
3

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

1
2
3
4

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
             Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

\380. Insert Delete GetRandom O(1)

Medium

1501109Share

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

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

\71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. For more information, see: Absolute path vs relative path in Linux/Unix

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

\1131. Maximum of Absolute Value Expression

Medium

Given two arrays of integers with equal lengths, return the maximum value of:

1

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

where the maximum is taken over all 0 <= i, j < arr1.length.

Example 1:

1
2

Input: arr1 = [1,2,3,4], arr2 = [-1,4,5,6]
Output: 13

Example 2:

1
2

Input: arr1 = [1,-2,-5,0,10], arr2 = [0,-2,-1,-7,-4]
Output: 20

Constraints:

• 2 <= arr1.length == arr2.length <= 40000
• -10^6 <= arr1[i], arr2[i] <= 10^6

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

教材：图解HTTP

分享一下自己做的笔记。share my note about studying HTTP

首先这是一篇对于动态规划进一步归纳总结的文章，所以一些对于动态规划的基本概念我就不介绍了。如果还有对动态规划不太了解的地方，可以看看这里。

dp的本质是：当前的分析要建立在过往分析的基础上。所以过往分析一定要做到两点，一个是全，一个是优。

对于全：如果对过往分析的成果保存不全（比如：用新数据覆盖了，或者根本没存）那么信息的缺失一定会导致结果的局限性，且不能达到最优。

对于优：即存下来的东西一定要是最优的结果。但是很多人在找动态转移方程时就会犯一个错误，为了优而放弃了全，用最优的新数据覆盖了后面可能还会需要用到的数据。在我看来这是DP用不好的重要原因之一。

所以为了兼顾优和全，储存DP结果的这个list的一定要构造好。把需要做到全的结果，当成需要存储的一个维度，这样一般就可以解决上面这个问题。

中文详细参考这里。英文here。两篇文章写的很好，讲解也很详细，然后我也将从3W(What, Why, How)角度开始讲解。