leetcode算法思想快速一览

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

整理了一下思路，想深入了解还得多去写，无奈时间紧迫的情况下抛砖引玉也不失为下策：

1.Two Sum Easy
给出一个数组，找出其中两个和为目标值的坐标。
思路：

[1]排序。
和为目标值，一般的思路是先排序，然后取两点坐标分别从首尾向中间移动。若和为目标值则返回两点坐标。若和大于目标值，右端坐标值-1，反之左端坐标值+1；
[2]因为需要返回坐标值。需要对键值对进行按值排序。以保留原始坐标。

2.Add Two Numbers Medium
有两个反向存储数字的链表，求他们的和。
思路：

[1]这种需要求和，进位频繁的工作选取一个全局变量来存储临时的和。（比如两个数的个位分别是9和8，那么先不必考虑进位，这个全局变量的值就是17，运算完成后，和的个位值为全局变量%10, 然后执行全局变量 /= 10,得出全局变量的剩余值。在计算十位的时候要加上这个剩余值。）
[2]这道题主要还顺带考察了链表的用法。
[3]注意while循环自带逻辑判断。这两个链表的长度不一，所以循环结构可以这样写：
while(链表1当前节点不为空且链表2当前节点不为空) ;//两个链表都还有值
while(链表1当前节点不为空); //链表2已空
while(链表2当前节点不为空); //链表1已空
if(全局变量 > 0) //如果全局变量>0 说明有进位操作，还需要加长结果链表

3.Longest Substring Without Repeating Characters Medium
找出一个字符串的最长子串，这个字串满足的条件是不出现重复字符。
思路：

[1]一次循环就搞定，不要多次遍历字符串。
[2]怎样标志一个字符是否出现过。因为字符的数量是有限的，一般256个标志位就能标志基本ASC码的所有字符。
[3]求最长、最大值的思路，是创建一个值用来保存这个“最大值”，每有可能是最大值的值产生的时候，让这个值和原有的最大值进行比较取二者的最大值作为新的最大值。
[4]解题思路。创建一个int类型的数组 charView[256]，其中的每个值都初始化成-1。
创建变量 start（目前而言正在判断的字符串的开始坐标） maxlength（得知的最长字符串的长度）
从给出的字符串的第一个字符到最后一个字符逐个遍历。当前坐标为i start初始化为0
如果charView[str[i]] 的值小于0 说明该字符一次都没出现过，start值不变（即当前所计算的字符串还没出现重复字符，继续计算下去） maxlength = max(i-start, maxlength);然后将charView[str[i]]赋值为i
如果charView[str[i]] 的值大于0 说明该字符出现过。那么我就判断这个值是否在start值的左边（start > i），如果在则说明他对我们当前判断的字符串没有影响，我们不必改变start的值，正常maxlength = max(i-start, maxlength)计算，并将charView[str[i]]赋值为i
如果这个值在start值的右边(start < i)，那么说明我们当前计算的字符串出现了重复（就是这个str[i]字符）。我们将start值赋值为i，然后继续去遍历。
最后返回maxlength。

4.Median of Two Sorted Arrays Hard
这题看似简单其实很恶啊，大意就是给出两个已经排序好的数组，找出两个数组所有元素中的中位数。
思路：

[1]设数组1的长度为m 数组2的长度为n总数就是m+n 我们就是要找两个数组中第m+n/2大的元素的值。我们设m+n/2为k
[2]如果a1[k/2-1]大于a2[k/2-1]，那么a2[0]到a2[k/2-1]的所有值当中都不可能有中值。原因如下。
就算取a2[0]~a2[k/2-1]当中最大的值作为中值a2[k/2-1]，那么需要从a1中取出k/2+1个数排在a2[k/2-1]的左边才能凑够k个数，让a2[k/2]成为两数组第k大的元素。然而a1中取出k/2个最小的元素当中已经有比a2[k/2-1]大的元素了，所以并不能凑齐k-1个比a2[k/2]小的数。
[3]上述是理想情况下(k/2-1既小于a1的长度也小于a2的长度)。如果不是，那么就用短的数组的长度代替这个值进行相同的判断。
[4]然后将删除不可能的元素的两个数组重新判断，这回要找的是第 k -(k/2-1)或这 k-短的那个数组长度大的值。删除元素的数组的长度和首指针都进行更新。

findKth方法写的非常经典。更能看出这道题的解题思路：
1. 保持A是短的那一个数组，B是长的
2. 平分k, 一半在A，一半在B （如果A的长度不足K/2,那就pa就指到最后一个）
3. 如果pa的值 < pb的值，那证明第K个数肯定不会出现在pa之前，递归，把A数组pa之前的砍掉，同理递归砍B数组。
4. 递归到 m == 0 （短的数组用完了）就返回 B[k - 1], 或者k == 1（找第一个数）就返回min(A第一个数，B第一个数）。

double findKth(int a[], int m , int b[], int n, int k){if(m > n)return findKth(b,n,a,m,k);)];)], b[]);, m), pb = k-pa;] < b[pb-])return findKth(a + pa, m - pa, b, n, k - pa);] > b[pb - a])return findKth(a, m, b + pb, n - pb, k - pb);else];;}double findMid(int A[], int m, int B[], int n){int total = m + n;if(total & 0x1){+);}else{return(findKth(A,m,B,n, total/) + findKth(A,m,B,n, total/ + )) / ;}}

5.Longest Palindromic Substring Medium
求一个字符串的最长回文子字符串。
(manachar算法解题思路)
[1]明确需求。回文字符串的可能性有两种，一种是形如abcba这种奇数回文字符串，另一种则是adda这种偶数回文字符串。为了统一算法，我们将一种特殊字符穿插在字符串当中构造成：
#a#b#c#b#a# 和 #a#b#b#a# 这样所有的回文字符串就都成了奇数回文字符串
[2]这道题的一般思路是假设每一个字符都是回文字符串的中位字符。那么就是从头遍历到尾。看看满足每个字符作为中位符的回文字符串有多长。
[3]如何去判断一个字符串是否是回文字符串？我们的判断方式是从中间开始像两端递推。例如str[i]，如果str[i-1] == str[i+1]那么 str[i-1,i+1]就是回文字符串，那么就继续判断str[i-2]和str[i+2]...直到相等或者达到数组边界。这个最大差参与maxlength的计算。
[4]如何去动态规划减少遍历的范围？我们的做法是保留目前所获得的最长的回文字符串的右边界。如果当前所遍历的字符的坐标位置不大于这个右边界，那么他和目前所获得最长回文字符串是按照中值对称的。如果以他的对称所对应的字符为中值所生成的回文字符串没有
超越最长回文字符串的左边界，那么这个字符就可以pass掉了。他和他的对称值一样，都不是最长的。即便到了左边界值，我们也可以用这个差值来进行递推回文字符串的长度初始值。这样就减少了遍历的数量。
[5]我们求出的结果要除去其中的特殊字符，实际长度为(maxlength-1)/2

6.ZigZag Conversion Easy

将一个字符串z字形状的分解成几个字符串

[1]一次遍历
[2]以从一个纵向延伸的开始点为分割点做循环。即纵轴坐标为0,1,2,...rows-1, rows-2,rows-3 ... 2,1 一次循环结束。

string convert(string s, int nRows){ ) return s; string res[nRows]; , j, gap = nRows-; while(i < s.size()){ ; i < s.size() && j < nRows; ++j) res[j] += s[i++]; ; --j) res[j] += s[i++]; } string str = ""; ; i < nRows; ++i) str += res[i]; return str;}

7.Reverse Integer Easy

将一个整数反转

[1]主要考虑反转过程中不要出现整数溢出的情况
[2]对原整数进行 / 10 计算，直到其结果为0

int reverse(int x) { const int max = 0x7fffffff; //int最大值 const int min = 0x80000000; //int最小值 ; ) { ; sum = sum * + temp; if (sum > max || sum < min) //溢出处理 { sum = sum > ? max : min; return sum; } x /= ; } return sum;}

8.String to Integer (atoi) Easy

字符串转化成Int类型。

[1]考虑字符串的前部的空格，要去除。从第一个有效字符开始处理

[2]考虑正负

[3]考虑int值越界的情况

[4]考虑出现不是数字的非法字符

int atoi(const char *str) { ; ,i=; ,flag2=; while(str[i]!='\0' && str[i]==' ') i++;//开头空格舍弃 if(str[i]=='-') flag1++,i++; else if(str[i]=='+') flag2++,i++; for(; str[i]!='\0'; i++) { ') { ) { cur=cur*-(str[i]-');//这里是减法，因为cur符号是负号了 ) ; } ) cur=-str[i]+',flag1++;//将负数的符号记录到cur里 else { cur=cur*+(str[i]-'); ) ; } } else break; } num=(int)cur; return num;}

9.Palindrome Number Easy

判断一个int是否为回文数。

[1]负数pass掉。
[2]个位数全部是回文数。，
[3]只能利用位数标志了即最高位 while( number != 0) { number /= 10; count ++;}
[4]左边是pow(10,count-1) 右边是pow(10,1),同时取余比较即可

Regular Expression Matching Hard

Container With Most Water Medium

Integer to Roman Medium

Roman to Integer Easy

Longest Common Prefix Easy

3Sum Medium

3Sum Closest Medium

Letter Combinations of a Phone Number Medium

4Sum Medium

Remove Nth Node From End of List Easy

Valid Parentheses Esay