leetCode进阶算法题+解析（一）
咳咳，这一个文集叫做leetcode进阶。因为之前那个文集刷的都是简单的题目。目前为止简单的刷完了，开始刷中等的了，所以单独提出来算leetcode进阶的。然后就酱，开始刷题吧。
两数相加
题目：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
思路：手有点抖，看似题目很简单，但是标签是中等，哎呀呀~~~说正经的思路，就是两个node挨个节点相加，如果有进位进到下一个节点上。我去尝试实现了。
有点小兴奋啊，中等难度的题也一次过了， 而且性能超过百分之九十九，飘了飘了~~哈哈，我直接贴代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode res = new ListNode(0);
ListNode cur = res;
int sum = 0;
while(l1!=null && l2!=null){
sum += l1.val+l2.val;
cur.next = new ListNode(sum%10);
if(sum/10==1){
sum = 1;
}else{
sum = 0;
}
l1 = l1.next;
l2 = l2.next;
cur = cur.next;
}
//说明l2是null
while(l1!=null){
sum +=l1.val;
cur.next = new ListNode(sum%10);
if(sum/10==1){
sum = 1;
}else{
sum = 0;
}
l1 = l1.next;
cur = cur.next;
}
while(l2!=null){
sum +=l2.val;
cur.next = new ListNode(sum%10);
if(sum/10==1){
sum = 1;
}else{
sum = 0;
}
l2 = l2.next;
cur = cur.next;
}
if(sum!=0) cur.next = new ListNode(1);
return res.next;
}
}
说一下上面的代码：首先1,2都不为空则正常相加，有进位则进位。其次当1,2有一个为空了则只要单边不断往后接。最后都接完了如果sum不是0说明最后留了一个进位，所以最后还要追加1，就这样。
其实感觉也没那么难，继续下一题吧。
无重复字符的最长子串
题目：给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
思路：这道题看着很简单，目前的打算就是数组下标代替值，然后如果大于1说明重复出现了，这个时候的长度就是最大的长度。然后目前没有好办法怎么处理，只能一个字符一个字符的截取然后比较了，先去试试思路可行不，然后再优化。
emmmm....看了demo我以为都是小写字母的，结果测试案例什么都出来了。不过问题不大，就是从原来的26长度数组变成了134.另外字符串截取可行但是性能太低，第一版本代码先贴出来，我去试试char[]处理：
class Solution {
public int lengthOfLongestSubstring(String s) {
int count = 0;
while(s.length()>count){
char[] c = s.toCharArray();
count = Math.max(getCount(c), count);
s = s.substring(1);
}
return count;
}
public int getCount(char[] c) {
int[] d = new int[134];
for(int i = 0;i<c.length;i++) {
d[c[i]]++;
if(d[c[i]]>1) return i;
}
return c.length;
}
}
哪怕用数组代替了性能还是不行，我总记得有这样的方法可以获取数组某下标开始到某下标结束的元素，但是想不起来了。第二版本的代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
int count = 0;
char[] c = s.toCharArray();
int l = c.length;
for(int i = 0;i<l-count;i++){
char[] c2 = Arrays.copyOfRange(c, i, l);
count = Math.max(getCount(c2), count);
}
return count;
}
public int getCount(char[] c) {
int[] d = new int[134];
for(int i = 0;i<c.length;i++) {
d[c[i]]++;
if(d[c[i]]>1) return i;
}
return c.length;
}
}
看了排名第一的代码，确实更加精巧。我这里只是单纯的用数组下标代替数值然后值表示有没有。但是人家用数组下标代替数值，数组的值代替元素出现的下标。同时因为下标不能为负数，所以先都设置成负数值，通过值的取值 范围判断有没有。说真的，这种思路是我第一次见。然后也算是学到了一招。不过这样写会让逻辑更加复杂，我是每次都要从后一个元素判断，会做很多无用的功，而人家是从重复元素的后一个判断，除了服之外没什么好说的。学到了。我先附上代码再一点点把我自己的理解附上：
class Solution {
public int lengthOfLongestSubstring(String s) {
int nums[] = new int[128];
for(int i=0;i<128;i++)
nums[i] = -1;
//l是第一个非重复元素的下标。
//cur是当前计数器的值
int l=0,max=0,curLen=0,sLen = s.length();
for(int i=0;i<sLen;i++) {
int index = s.charAt(i);
if(nums[index]<l) {
nums[index] = i;
curLen++;
} else {
max = curLen>max? curLen:max;
curLen -= nums[index]-l;
l = nums[index]+1;
nums[index] = i;
}
}
return curLen>max? curLen:max;
}
}
首先这是一种我不习惯的方式。很多变量在一行声明。咱们一个个说：
l是第一个非重复元素的下标。因为下标肯定是越来越往后增加的，所以判断重复的标志就是新的元素没有被赋值，也就是还是最开始的-1.小于l。
max就是当前计数器的最大值。
curLen就是正在计算的计数器
sLen是整个数组的长度。
这里我觉得稍微费解的就是l。但是理解好了用起来也是得心应手的。
这个题的主思路就是从第一个字符开始遍历，如果遇到重复元素了，则从第一个重复元素后面开始继续计算。而这个cur要减去第一个重复元素及之前值的计数。
比如 1 2 3 4 5 7 3 8 9 6
如果在7后面又遍历到3了。和第一个3重复了，这个时候要做的是：
- 计数器cur在技术到7的时候值是6
- 遍历到第二个3走else分支，判断最大值和当前cur哪个大，如果cur大，max替换为cur的值，也就是6
- 这个时候我们计算到第一个3出现在下标为2的时候，所以一共是3个元素（因为下标从0开始，2是三个元素）也就是cur -= 3。但是要注意把之前的重复元素去了的同时要把现在这个元素加上。所以还要加1.这个下标-1+1就化简为下标，另外还要减去起始下标l。同时将 字典数组nums中3原本的位置的值从2改成6（第二个3下标是6）。并且这个时候计数器的第一个元素是第4个元素。也就是3后面的4. 这个时候计数的数组是 4， 5， 7，3
- 接着继续往下计算，如果不重复继续计数加，重复继续刚刚的计算。
（因为本例子没重复，所以计数到4 5 7 3 8 9 6一共cur是7） - 最后遍历完成，因为cur=7 大于max6.所以返回cur7.
然后这道题差不多就这样了，学到的最主要的就是原来数组不仅仅能用于map，下标代表值数组代表状态 。 其实还可以用的更灵活，下标，数值范围，和数值代表三个意思。真的开阔视野了，大爱~~~~好了，下一题了。
最长回文子串
题目：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
思路：目前的思路是一个个去试，回文串的标志就是中心位要么AA，要么ABA。所以遇到两个相同的字符或者两个隔一位相同的字母就往外扩散到左右不等，然后判断长度。我去尝试实现。
这个题写到心疼自己。。就是从思路到实现用了俩小时，一次次尝试，感觉 后期都麻木了，纯粹面对测试案例编程。反正好赖是实现了，我贴下代码：
class Solution {
public String longestPalindrome(String s) {
if(s.length()==0) return "";
String res = s.charAt(0)+"";
char[] c = s.toCharArray();
for(int i = 0;i<c.length-1;i++ ){
if(s.charAt(i)==s.charAt(i+1)){
String temp = getRes(c, i, i+1);
if(res.length()<temp.length()) res = temp;
}
if(i<c.length-2 && s.charAt(i)==s.charAt(i+2)) {
String temp = getRes(c, i, i+2);
if(res.length()<temp.length()) res = temp;
}
}
return res;
}
public String getRes(char[] c,int l,int r) {
int n = 0;
if(r-l == 2) n =1;
while(l>=0 && r<c.length) {
if(c[l]==c[r]) {
n += 2;
l--;
r++;
}else {
return new String(c,l+1,n);
}
}
return new String(c,l+1,n);
}
}
然后性能不太好，只超过了百分之六十的人，但是我觉得还可以优化优化，顺便附上我一次次尝试的截图：
不断尝试才正确
然后我去优化啦。
在我死不要脸一点点改，一遍遍提交，终于从20ms进化到10ms，超过百分之75的人了，可喜可贺可喜可贺~~然后剩下的直接看排名第一的代码吧，我自己这个思路感觉到了上限了。顺便把10ms的代码贴上来：
class Solution {
public String longestPalindrome(String s) {
if(s.length()==0) return "";
String res = s.charAt(0)+"";
char[] c = s.toCharArray();
int i = 0;
while(i<c.length-1 && i<c.length-(res.length()/2)){
if(s.charAt(i)==s.charAt(i+1)){
String temp = getRes(c, i, i+1, 0);
if(res.length()<temp.length()) res = temp;
}
if(i<c.length-2 && s.charAt(i)==s.charAt(i+2)) {
String temp = getRes(c, i, i+2, 1);
if(res.length()<temp.length()) res = temp;
}
i++;
}
return res;
}
public String getRes(char[] c,int l,int r,int n) {
while(l>=0 && r<c.length) {
if(c[l]==c[r]) {
n += 2;
l--;
r++;
}else {
return new String(c,l+1,n);
}
}
return new String(c,l+1,n);
}
}
然后我去看排名第一的代码了，看了意思思路顿时打开了，我这来回来去都是字符串比较，其实可以直接起始下标比较，最后求出字符串就行了，我先去改造我自己的代码了。
改造完成，8ms，超过百分之九十二的人：
class Solution {
public String longestPalindrome(String s) {
if(s.length()==0) return "";
int[] res = new int[2];
res[1] = 1;
char[] c = s.toCharArray();
int i = 0;
while(i<c.length-1){
if(s.charAt(i)==s.charAt(i+1)){
getRes(c, i, i+1, res);
}
if(i<c.length-2 && s.charAt(i)==s.charAt(i+2)) {
getRes(c, i, i+2, res);
}
i++;
}
return s.substring(res[0],res[1]);
}
public void getRes(char[] c,int l,int r,int[] res) {
while(l>=0 && r<c.length) {
if(c[l]==c[r]) {
l--;
r++;
}else {
break;
}
}
if(res[1]-res[0]>(r-l-2)) return;
res[1] = r;
res[0] = l+1;
}
}
然后其实这个方法我觉得就可以了，但是还附上性能第一的代码分享下:
class Solution {
public String longestPalindrome(String s) {
if(s == null || s.length()==0){
return "";
}
int sLength = s.length();
if(sLength == 1){
return s;
}
char[] chars = s.toCharArray();
int[] result = new int[2];
for(int i = 0; i < sLength ;i++){
i = explore(chars,i,result);
}
return s.substring(result[0] + 1, result[1]);
}
private int explore(char[] chars, int i ,int [] result){
int l =i;
int r = i;
int length = chars.length;
while ((r+1) < length && chars[r+1] == chars[r]){
r++;
}
int re =r;
while(l>=0 && r < length && chars[l] == chars[r]){
l--;
r++;
}
if((r-l) > (result[1]- result[0])){
result[0]= l;
result[1]= r;
}
return re;
}
}
然后这道题就这样了，下一题。
Z字形变换
题目：将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：
L C I R
E T O E S I I G
E D H N
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);
示例 1:
输入: s = "LEETCODEISHIRING", numRows = 3
输出: "LCIRETOESIIGEDHN"
示例 2:
输入: s = "LEETCODEISHIRING", numRows = 4
输出: "LDREOEIIECIHNTSG"
解释:
L D R
E O E I I
E C I H N
T S G
思路：感觉这个题暂时打算排排坐分字符的方法来做。。。一共几行就几个数组，然后一个个字符填充元素，1-最后然后到再拐上来。。。反正思路是有了，我先去写代码再说。
写完回来了，思路没问题，而且之前写的时候我就在猜题目能不能那么不要脸，结果真的能。。。居然还能换成1行。。。所以通过测试案例还特意加了第一行代码，我先贴出答案：
class Solution {
public String convert(String s, int numRows) {
if(numRows==1) return s;
StringBuffer[] d = new StringBuffer[numRows];
for(int i = 0; i<numRows;i++){
d[i] = new StringBuffer();
}
char[] c = s.toCharArray();
int i = 0;
int n = 0;
boolean flag = true;
while(i<c.length){
if(flag){
d[n].append(c[i]);
n++;
if(n==numRows){
flag = false;
n -= 2;
}
}else{
d[n].append(c[i]);
n--;
if(n==-1){
flag = true;
n += 2;
}
}
i++;
}
StringBuffer res = new StringBuffer();
for(int j = 0; j<numRows;j++){
res.append(d[j]);
}
return res.toString();
}
}
如图，本来打算用数组型数组来写的，但是后来发现还要记每个数组的下标。所以换成了stringBuffer。。但是性能不太好，感觉我也尽力了啊，反正凭我的代码我觉得也没啥优化的地方了，只能改思路了，我再想想吧。不对，好像这个n可以用余数来表示。。我做过类似的。。n%num,这样最大是num-1。最小是0。。好像是这样，我去改。
回来了，这个思路有点问题，因为这样比余是不断0，1，2，3，0，1，2，3，0，1，2，3的循环，，我要调整下看看怎么让他按照这个题的顺序来，我去改改。改来改去没改明白，自己倒是优化了，但是性能没好啊：
class Solution {
public String convert(String s, int numRows) {
if(numRows==1) return s;
StringBuffer[] d = new StringBuffer[numRows];
for(int i = 0; i<numRows;i++){
d[i] = new StringBuffer();
}
char[] c = s.toCharArray();
int i = 0;
int n = 0;
boolean flag = true;
while(i<c.length){
d[n].append(c[i]);
if(flag && n!=numRows-1){
n++;
}else if(flag && n==numRows-1){
flag = false;
n--;
}else if(!flag && n!=0){
n--;
}else {
flag = true;
n++;
}
i++;
}
for(int j = 1; j<numRows;j++){
d[0].append(d[j]);
}
return d[0].toString();
}
}
我直接看下排行第一的代码吧：
果然是思路问题，我这种一个个往上追加的思路就不好，人家是直接挑出来各行的元素，然后直接凑，我还要遍历。但是仍然觉得我的方法不应该这么差啊，毕竟时间复杂度也是O（n）,,咳咳，言归正传，我直接贴代码：
class Solution {
public String convert(String s, int numRows) {
if(s==null||numRows<=1||s.length()<=numRows) return s;
int divsor=numRows*2-2; //字符间隔
int STRLEN=s.length();
char[] words=new char[STRLEN];
int p=0;
for(int i=0;i<STRLEN;i=i+divsor){ //第一行
words[p++]=s.charAt(i);
}
for (int i = 0; i < numRows - 2; i++) { //中间各行
for(int j=i+1,k=divsor-(i+1);j<STRLEN;j=j+divsor,k=k+divsor){
//中间各行都是在一个周期（T=divsor）内插入两个字符
words[p++]=s.charAt(j);
if(k<STRLEN) words[p++]=s.charAt(k);
}
}
for(int i=numRows-1;i<STRLEN;i=i+divsor){ //最后一行
words[p++]=s.charAt(i);
}
return String.copyValueOf(words);
}
}
其实看了就能明白，所谓的z字形也是有规律的，就是列数乘2-2就是一个竖一个斜的元素数。剩下的可以看作是第二个竖斜，第三个竖斜以此类推。最后不足一组的是最后一组竖斜。然后首位元素的个数也是有规律的，每一个周期除了首尾都是两个字符。首尾是一个。这些都在心里算清楚后可以如上代码中这样，给你个下标就知道是哪一排的元素了，然后这道题就这样吧。
今天是第一天专门刷中等的题，只能说对得起这个难度，之前简单的可以一天十几道，今天刷了一天才四道，除了第一题简单点剩下每道题都在1个小时以上的思考时间，让我想起了刚刚刷算法的时候了，重在坚持吧，希望以后越来越好！
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！！！
