432.All O`one Data Structure 解法：http://www.cnblogs.com/grandyang/p/6012229.html
数据结构： struct Bucket { int value; unordered_set keys; }; list bucketList; //list内维护一个value从小到大的顺序链接的链表 //通过key迅速找到存储有value和拥有此值的unordered_set unordered_map< string,list::iterator> bucketsOfMap;
200.Number of Islands http://blog.csdn.net/u014056175/article/details/48368799 孤岛数量问题？深度搜索把岛内土地走一遍
310.Minimum Height Trees 题目是告诉你节点数和其中每条边的俩节点 让你找使得其成为最小高度树的根节点。
思路： The basic idea is “keep deleting leaves layer-by-layer, until reach the root.”
Specifically, first find all the leaves, then remove them. After removing, some nodes will become new leaves. So we can continue remove them. Eventually, there is only 1 or 2 nodes left. If there is only one node left, it is the root. If there are 2 nodes, either of them could be a possible root.
Time Complexity: Since each node will be removed at most once, the complexity is O(n). 从每个叶子结点出发，开始剪掉叶子，然后有些内部节点也会成为新的叶子结点。直到遇到根节点或者2个节点。
496.Next Greater Element I 503.Next Greater Element II 给一个vector，找出每一个数 按下标顺序遍历时候第一个大于它的数。 第一题是不可以从结尾回到开头继续找，找不到就返回-1. 第二题是允许循环遍历的找，即结尾+1则回到开头。
思路是：准备一个stack装还没找到的，遍历一个数则看这个数跟stack中的数字比较。
unordered_map<int,int> m; stack<int> s; for(int i=0;i<nums.size();++i) { while(!s.empty() && nums[i]>s.top()) { m[s.top()]=nums[i]; s.pop(); } s.push(nums[i]); }556.Next Greater Element III 这里是给定一个数字n，然后找出比它大的最小数，其中找到的数须由n的那些数字构成。 比如n=1243,则会找到1324. 如果n=4321，返回-1. 注意点： 1、使用to_string和stol会更加方便简洁！ to_string(1243) –> string s(“1243”) s[0]=’1’ stol(s) —> long next = 1243 2、一个巧妙的方法 59876 –>5 (9876) –> 5 (6789) –>（找第一个比5大的） (65)789 定位到5（如何定位？s[i]>=s[i+1]） –>排序？（reverse） –>(交换)（本身reverse后已经排好序） 3、检验得到的数字是不是比INT_MAX大？ 4、特殊例子 第一个，长度为1，如个位数1、2、3、4…… 第二个，11，22，33，44，5555……
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.
思路：双指针。！
22.Generate Parentheses (成对圆括号)
For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]想过用栈，然后联系到了递归，使用一个变量来控制匹配左右括号，左括号来了+1，右括号来了-1，不能小于0。然后看了下代码真特么简洁。 多使用了一个n来控制其不能无限递归。。
class Solution { public: vector<string> generateParenthesis(int n) { vector<string> res; addingpar(res, "", n, 0); return res; } void addingpar(vector<string> &v, string str, int n, int m){ if(n==0 && m==0) { v.push_back(str); return; } if(m > 0){ addingpar(v, str+")", n, m-1); } if(n > 0){ addingpar(v, str+"(", n-1, m+1); } } };27.Remove Element (给一个数组和val，将数组中的val去掉，顺序不变) 26 Remove Duplicates from Sorted Array （从一个排好序的数组中移除相同的数字只保留一个） 思路差不多，都是设一个变量来保存待更新的位置，遍历的时候一个个更新。
int count=0; //下一次更新的位置 for(int i=1;i<nums.size();++i) { if(nums[i]!=nums[count]) { ++count; nums[count]=nums[i]; } } int cnt=0; for(int i=0;i<nums.size();++i) { if(nums[i]==val) { ++cnt; } else { nums[i-cnt]=nums[i]; } }29.Divide Two Integers 不用乘法除法和取余来计算两数相除。。 解释的很清楚了 https://leetcode.com/problems/divide-two-integers/#/solutions
15=3*4+3; 需要注意的问题： 1、传入参数为int,int 我们后面在代码中使用了
long int dvd = labs(dividend); long int dvs = labs(divisor);免去了超出范围的困扰？
2、
int res = 0; while (dvd >= dvs) { long long temp = dvs, multiple = 1; while (dvd >= (temp << 1)) { temp <<= 1; multiple <<= 1; } dvd -= temp; res += multiple; }temp指代当前能减的最大值，通过while循环求得。 multiple来指代当前减掉除数的倍数，初始为1，因为dvd>=dvs，至少为1，通过while循环更新。
31 Next Permutation 实现下一个排列，将数字重新排列成数字的下一个更大排列。 如果这种安排是不可能的，它必须将其重新排列为尽可能低的顺序（即以升序排序）。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 2,4,3,1 –> 3,1,2,4
不多说，跟找出“比a更大的最小数b，其中得满足组成b和a的数字要相同”的题目没区别
33 Search in Rotated Sorted Array Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). 也就是在诸如4 5 6 7 0 1 2之类的旋转数组中找个数。。
1、普通方法： 根据数字增长规律，其中nums[size-1]
lo=0,hi=size-1; mid=(lo+hi)/2; midIndex = (mid+minIndex)%size这里很巧妙
34.Search for a Range Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. 二分法了……记录一下。 solution中有个先2分法找起始位置，然后再找末尾位置。 一般人是先找到一个位置后，然后2边扩展……。。
35.Search Insert Position Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array. Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0 二分法： 附代码：
int lef=0,righ=nums.size(); if(righ==0) { return 0; } do { int mid=(lef+righ)/2; if(target > nums[mid]) lef=mid+1; else righ=mid; }while(lef<righ); return righ;36 Valid Sudoku 检查数独是否合法就行。 A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
设置3个二维数组来分别检测行，列和3*3小方框内是否合法。O(N* N)
38.Count and Say the count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 is read off as “one 1” or 11. 11 is read off as “two 1s” or 21. 21 is read off as “one 2, then one 1” or 1211.
递归。
void digui(string& s,int times,int n) { if(n==times) { return; } int cnt=1; char c=s[0]; int i=1; char temp; string res(""); for(;i<s.size();++i) { temp=s[i]; if(temp==c) { ++cnt; } else { res.push_back(cnt+'0'); res.push_back(c); c=temp; cnt=1; } } res.push_back(cnt+'0'); res.push_back(c); s=res; return digui(s,times+1,n); }39.Combination Sum 在候选set中选出一些数使他们和为target，候选数均为正数。 given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ]
利用到了回溯算法： http://blog.csdn.net/jarvischu/article/details/16067319
class Solution { void combinationSum(vector<vector<int>>& res,vector<int>& combination,int target,vector<int>& candidates,int begin) { if(!target) //叶子结点判断（什么时候结束） { res.push_back(combination); return; } for(int i=begin;i<candidates.size() && target>=candidates[i];++i) //某节点的子节点 { combination.push_back(candidates[i]); //深入某子节点 combinationSum(res,combination,target-candidates[i],candidates,i); combination.pop_back(); //从某子节点回来 } } public: vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); vector<vector<int> > res; vector<int> combination; combinationSum(res,combination,target,candidates,0); return res; } };40 Combination Sum II 与39类似，但每个数只能选一次，且答案不可重复。 given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] //瞧！这里候选数有2个1，按39的做法会返回两次[1,2,5]，但这里只能返回一次
void combinationSum2(std::vector<int> &candidates, int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin) { if (!target) { res.push_back(combination); return; } for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) '''C++ if (i == begin || candidates[i] != candidates[i - 1]) ''' { combination.push_back(candidates[i]); combinationSum2(candidates, target - candidates[i], res, combination, i + 1); combination.pop_back(); } }216.Combination Sum III 在1-9中找k个数字，使他们和为n，其中不可重复！（只能选一次） 跟之前2道一样。
class Solution { void combinationSum(vector<vector<int> >& res,vector<int>& combination,int begin,int target,int k) { if(k<0) { return; } if(target==0 && k==0) { res.push_back(combination); return; } for(int i=begin;i<10 && target>=i;++i) { combination.push_back(i); combinationSum(res,combination,i+1,target-i,k-1); combination.pop_back(); } } public: vector<vector<int>> combinationSum3(int k, int n) { if(k<0 || k>9 || n>45) { return vector<vector<int> >(); } vector<vector<int> > res; vector<int> combination; combinationSum(res,combination,1,n,k); return res; }46 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] ] 这是我Accept的代码：
class Solution { void permutationVec(vector<vector<int> >& res,vector<bool>& index,vector<int>& nums,vector<int> combination,int k) { if(!k) //判断叶子结点 { res.push_back(combination); return; } for(int i=0;i<index.size();++i) //遍历某节点的子节点 { if(index[i]) //该节点还未遍历。深入子节点 { index[i]=false; //深入该子节点，标记正在访问，已加入combination combination.push_back(nums[i]); permutationVec(res,index,nums,combination,k-1); combination.pop_back(); //回到该子节点 index[i]=true; //标记该节点结束了访问，未加入combination } } } public: vector<vector<int>> permute(vector<int>& nums) { int siz=nums.size(); vector<bool> index(siz,1); vector<vector<int> > res; vector<int> combination; permutationVec(res,index,nums,combination,siz); return res; } };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?
void rotate(vector<vector<int>>& matrix) { int n = matrix.size(); int a = 0; int b = n-1; while(a<b){ for(int i=0;i<(b-a);++i){ swap(matrix[a][a+i], matrix[a+i][b]); swap(matrix[a][a+i], matrix[b][b-i]); swap(matrix[a][a+i], matrix[b-i][a]); } ++a; --b; } }图示来解释解法技法！
54.Spiral Matrix Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example, Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] You should return [1,2,3,6,9,8,7,4,5].
55.Jump Game ven an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example: A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
class Solution { public: bool canJump(vector<int>& nums) { int n=nums.size(); int reach=0; int i=0; for(;i<n&&i<=reach;++i) { reach=max(reach,i+nums[i]); } return i==n; } };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):
“123” “132” “213” “231” “312” “321” Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive. 一个图片足够描述解法思路了。。
61.Rotate List Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
要考虑的问题： 1、给的list是空的？ 2、给的k值为0？ 3、给的k值超过list的长度？（此时应该k=k%list的长度）
题目本身没有难度。
