top-10-algorithms-for-coding-interview 札记
一个牛人写的LeetCode上的解题思路： http://blog.****.net/u011095253?viewmode=contents
国内算法论坛一亩地：http://www.1point3acres.com/bbs/forum-84-4.html
Leetcode网站，IT公司 http://leetcode.com/
Crack code inteview: http://hawstein.com/posts/ctci-solutions-contents.html
十大算法：http://geek.****.net/news/detail/3722
top-10-algorithms-for-coding-interview 笔记
1. Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, /. Each operand may be an integer or another expression. <= Answer , this problem is simple.
Some examples:
["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6
2. Finding the longest palindromic substring(回文子串) is a classic problem of coding interview.
Some examples: ccabcbaceffe the longest palindromic substring is abcba.
Answer. 本题有三种方法，分别是最笨的方法，即逐一判断任何可能出现的子串是否为回文子串，然后找出最长者，这种方法中存在重复判断的问题，故可以考察采用动态规划算法，设P[i][j]为是否是回文子串，虽然时间复杂度降低，但空间复杂度上升为N*N，第三种方法是抓住回文子串的特性，或奇，或偶，以i为中心，判断可能出现的最长子串。
3.Word Break: Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words. Answer
For example, given s = “leetcode”, dict = ["leet", "code"]. Return true because “leetcode” can be segmented as “leet code”.
即使告诉你要使用动态规划，你知道怎么用吗？动态规划的初始状态是怎样的呢？该问题的动态规划方程是什么？，动态规划中记录重复子问题的数组，使得问题得以跳跃着前进。
4. Word Ladder Answer
6Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that: Only one letter can be changed at a time Each intermediate word must exist in the dictionary For example, Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog", return its length 5. Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.5. Median of Two Sorted Arrays Java Answer
There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
6. Regular Expression Matching Answer
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") return false
isMatch("aa","aa") return true
isMatch("aaa","aa") return false
isMatch("aa", "a*") return true
isMatch("aa", ".*") return true
isMatch("ab", ".*") return true
isMatch("aab", "c*a*b") return true
7 Two Sum, 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. Answer
For example:
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2