Leet Code Report0002 基于链表的大数加法1 [Unchecked] Big Integer法2 统一位数的模拟进位加法3 ***模拟进位加法 + 实时处理0003 最长不重复字母字符串1 HashSet求解2 ***滑动窗口（不定长线段）0005 最长回文字符串1 暴力求解2 ***中心拓展法0006 Z变换1 找规律0007 数字颠倒1 字符串反转0009 判断回文数1 字符串法0010 盛水最多的容器1 暴力求解2 ***双指针法0012 数字转罗马数字1 函数处理法0013 罗马数字转数字1 哈希表映射0014 ***三数之和等于零1 双指针法 + 去重0022 ***生成有效括号1 ***平衡+递归0026 删除数组重复元素1 计算不同的元素2 计算相同的元素0053 ***[简单]最大子序列之和1 DP0121 买卖股票的最佳时机1 暴力搜索2 滑动窗口0062-0063 不同路径1 DP
方法：先将数据结构中的数据逐个读取，写进StringBuilder，然后构建BigInteger，用封装类计算加法。
注意：本题在leetcode中不能用BigInteger，而且在用ArrayList代替ListNode
import java.lang.reflect.Array;import java.math.*;import java.util.*;public class LeetCode2 { public static void main(String[] args){ ArrayList<Integer> arr1 = new ArrayList<Integer>(Arrays.asList(1, 3, 5)); ArrayList<Integer> arr2 = new ArrayList<Integer>(Arrays.asList(2, 9, 9)); ArrayList<Integer> arr3 = new ArrayList<Integer>(); while(arr1.size() < arr2.size()){arr1.add(0);} while(arr2.size() < arr1.size()){arr2.add(0);} StringBuilder sb1 = new StringBuilder(""); StringBuilder sb2 = new StringBuilder(""); for (int x=0; x < arr1.size(); x++) { sb1.append(arr1.get(x).toString()); sb2.append(arr2.get(x).toString()); } BigInteger bint1 = new BigInteger(sb1.toString()); BigInteger bint2 = new BigInteger(sb2.toString()); for(int x = sb3.length()-1; x >= 0; x--) { System.out.print(sb3.charAt(x)); }}}位数统一后模拟进位加法，逐个相加。
ximport java.math.*;import java.util.*;public class LeetCode2 { public static void main(String[] args){ ListNode l1 = new ListNode(1); ListNode l2 = new ListNode(9); l2.next = new ListNode(9); addTwoNumbers(l1, l2); } public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { //unite digits ListNode tmp1 = l1; ListNode tmp2 = l2; while(tmp1.next != null || tmp2.next != null) { tmp1 = tmp1.next == null? tmp1.next = new ListNode(0): tmp1.next; tmp2 = tmp2.next == null? tmp2.next = new ListNode(0): tmp2.next; } //add numbers tmp1 = l1; tmp2 = l2; int sum = l1.val + l2.val; int flag = sum/10; ListNode l3 = new ListNode(sum >= 10 ? sum % 10 : sum ); ListNode tmp3 = l3; while(tmp1.next != null) { tmp1 = tmp1.next; tmp2 = tmp2.next; sum = tmp1.val + tmp2.val; tmp3 = (tmp3.next = new ListNode(sum+flag >= 10? (sum+flag) % 10: sum+flag)); flag = (sum+flag)/10; } if(flag == 1) { tmp3.next = new ListNode(1); } tmp3 = l3; System.out.print(tmp3.val); while(tmp3.next != null) { tmp3 = tmp3.next; System.out.print(tmp3.val); } return l3; }}class ListNode { int val; ListNode next; ListNode(int val){ this.val = val; }}不使用额外循环统一位数，在参与计算时用或条件，如果两个链表长度不一，先遍历到终点的链表每次连接一个val=0的节点，这个操作相当于统一位数。此答案不论在时间还是空间上都能超过90%的已提交答案。
xxxxxxxxxx public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode tmp1 = l1; ListNode tmp2 = l2; int sum = l1.val + l2.val; int flag = sum/10; ListNode l3 = new ListNode(sum >= 10 ? sum % 10 : sum ); ListNode tmp3 = l3; while(tmp1.next != null || tmp2.next != null) { tmp1 = tmp1.next == null? new ListNode(0) : tmp1.next; tmp2 = tmp2.next == null? new ListNode(0) : tmp2.next; sum = tmp1.val + tmp2.val; tmp3 = (tmp3.next = new ListNode(sum+flag >= 10? (sum+flag) % 10: sum+flag)); flag = (sum+flag)/10; } if(flag == 1) { tmp3.next = new ListNode(1); } tmp3 = l3; return l3; }}方法效率低下，时间复杂度O(n^2)。
xxxxxxxxxximport java.util.*;public class LeetCode3 { public static void main(String[] args) { String str = "pwwkew"; char c; int j; int counter, max = 0; HashSet<Character> hs = new HashSet<Character>(); for(int i = 0; i < str.length(); i++) { c = str.charAt(i); counter = 0; for(j = i; j < str.length(); j++) { System.out.print(str.charAt(j)); if (hs.contains(str.charAt(j))) {System.out.print("Cont:"+str.charAt(j));hs.clear();break;} counter++; hs.add(str.charAt(j)); } System.out.println(); if (counter > max) { max = counter; } } System.out.print(max); }}end指针向后移动，用HashMap记录字符最后一次出现的位置。如果遇到重复且重复的字符在start指针的后面，start指针指向上一次该字符出现位置的下一个位置，作为搜索的起始位置。这样的话无重复的字符串的长度就可以用end - start + 1来表示，代替累加器。
xxxxxxxxxxpublic int lengthOfLongestSubstring(String s) { HashMap<Character, Integer> map = new HashMap<Character, Integer>(); char c; int counter = 0; int len = s.length(); for(int start = 0, end = 0; end < len; end++) { c =s.charAt(end); if(map.containsKey(c)){ start = Math.max(map.get(c) + 1, start); } map.put(c, end); counter = Math.max(counter, end - start + 1); } return counter;}逐个列举子字符串，看他们是不是回文字符串。加入一句优化，减少遍历次数，主要是针对前期就出现超长回文的情况。勉强通过。
xxxxxxxxxxclass Solution { public String longestPalindrome(String s) { int len = s.length(); int count = 0; String tmpstr = ""; String tgtstr = ""; for(int x=0; x<len; x++) { if (x+count > len) {break;} //已知最大时count，则x位置超过count就不必继续查找 for(int y=x+1; y<len+1; y++) { tmpstr = s.substring(x,y); if (count <= tmpstr.length() && isPalindrome(tmpstr)) { count = tmpstr.length(); tgtstr = tmpstr; } } } return tgtstr; } private static boolean isPalindrome(String str) { int len = str.length(); for(int x = 0; x < len/2; x++) { if (str.charAt(x) != str.charAt(len-x-1)) { return false; } } return true; }}以某个字母为中心向两侧对称拓展，以某两个字母为中心向两侧对称拓展，取最大字符串长度，计算起点终点位置截取字符串。
我写的时候用自定义方法isPalindrome()判断，判断一次就要增加 len/2 的时间复杂度，所以效率很低，这位作者专门写了中心拓展的函数
xxxxxxxxxxclass Solution {public String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; System.out.println(i+"\t"+len); } } return s.substring(start, end + 1);}private int expandAroundCenter(String s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { L--; R++; } return R - L - 1; //要注意L多减了一次，R多加了一次，所以才会是R-L-1}}xxxxxxxxxxclass Solution { public String convert(String s, int numRows) { if(numRows == 1) { return s; } int p; int len = s.length(); boolean insert; StringBuilder sb = new StringBuilder(""); for(int x=0; x<numRows; x++) { p = x; insert = true; while(p < len) { sb.append(s.charAt(p)); if (x == 0 || x == numRows-1) { p += numRows*2-2; insert = p > len ? true : false; continue; } if (insert==false) { p += 2*x; insert = true; } else { p += numRows*2-x*2-2; insert = false; } } } return sb.toString(); }}数字的绝对值转化为字符串，逆序写入StringBuilder后，添加符号，然后转成数字，用 try catch 防止溢出
xxxxxxxxxxclass Solution { public int reverse(int x) { StringBuilder sb = new StringBuilder(""); String s = Integer.toString(Math.abs(x)); for(int k = s.length()-1; k>=0; k--) { sb.append(s.charAt(k)); } if (x<0) { sb.insert(0, "-"); } int res = 0; try { res = Integer.parseInt(sb.toString()); } catch(Exception e) { res = 0; } return ((res>=0 && x<=0) || (res<=0 && x>=0)) ? 0 : res; }}xxxxxxxxxxclass Solution { public boolean isPalindrome(int x) { if(x<0){return false;} String str =Integer.toString(x); int len = str.length(); for(int i=0; i<len/2; i++){ if(str.charAt(i) != str.charAt(len-i-1)) { return false; } } return true; }}双for遍历结合Math.max, Math.min，很容易想到，不写了。
原理：一开始左指针指最左侧，右指针指最右侧，双侧指针尝试向内侧移动，直到重合。移动的原理是：最大矩形面积取决最短线段的长度和两指针间的距离。如果把指向长线段的指针向内侧移动，不但盛水高度没变，距离还变短了，面积自然减少，所以应当把短指针向内侧移动。反之把长指针向内侧移动。
xxxxxxxxxxclass Solution { public int maxArea(int[] height) { int maxarea = 0; int lp = 0; int rp = height.length-1; while(lp != rp) { maxarea = Math.max(maxarea, Math.min(height[lp], height[rp])*(rp-lp)); if (height[lp] < height[rp]) { lp ++; } else { rp --; } } return maxarea; }}xxxxxxxxxxclass Solution { public String intToRoman(int num) { StringBuilder sb = new StringBuilder(""); num = (num >= 1000 ? modify(num, "", "", "M", sb) : num); //处理完就是100-1000了 num = (num >= 100 ? modify(num, "M", "D", "C", sb) : num); //处理完就是10-100了 num = (num >= 10 ? modify(num, "C", "L", "X", sb) : num); //处理完就是1-10了 num = (modify(num, "X", "V", "I", sb)); //处理完就是0了 return sb.toString(); } private static int modify(int num, String tenMod, String halfMod,String oneMod, StringBuilder sb) { /* 格式处理函数 参数解释： num： 传入的数字 tenMod： 当前数量级表示 单位10 的修饰符 halfMod： 当前数量级表示 单位5 的修饰符 oneMod： 当前数量级表示 单位1 的修饰符 sb： 传入的StringBuilder ID 如果当前为100-1000的量级，则tenMod为表示1000的String，halfMod为表示500的String，oneMod为表示100的String，以此类推 */ if (num == 0) {return 0;} //如果数字是0不用处理 int div = 1; while(num/div != 0){div *= 10;} //获取数量级 int count = num/(div/10); //获取有几个当前量级的 单位1 int p = count; num -= count * div/10; switch (p) { case 4: sb.append(oneMod+halfMod);break; //如果有4个单位1，表示方法为 单位1表示符 + 单位5表示符 case 9: sb.append(oneMod+tenMod);break; //如果有9个单位1，表示方法为 单位1表示符 + 单位10表示符 default: { if (p<4) { //小于4个 单位1，直接append 4个单位1 while(p>0) {sb.append(oneMod);p--;} } else { //其余情况就是大于5小于9的，则先append 1个单位5，然后剩下的append单位 1 sb.append(halfMod); while(p>5) {sb.append(oneMod);p--;} } } } return num; }}罗马数字的原理：如果左侧的字符表示的数字大于右侧，则数字加上左侧（如XI），反之减去左侧（如IV，5-1=4）。所以可以先导入哈希表映射，然后遍历字符串。
xxxxxxxxxxclass Solution { public int romanToInt(String s) { int number = 0; char c, nextc; int cint, nint; int len = s.length(); HashMap<Character, Integer> map = new HashMap<Character, Integer>(); map.put('I',1); map.put('V',5); map.put('X',10); map.put('L',50); map.put('C',100); map.put('D',500); map.put('M',1000); for(int i = 0; i < len; i++) { c = s.charAt(i); nextc = (i < len-1 ? s.charAt(i+1) : ' '); if (nextc != ' ') { cint = map.get(c); nint = map.get(nextc); number = cint >= nint ? number + cint : number - cint; } else {number += map.get(c);} } return number; }}遍历数组，作为第一个数字。遍历过程中选定第一个数字右侧的数字为左指针指向的内容，最后数字为右指针指向的内容。原理和最大盛水容器差不多，如果双指针指向的数字相加小于零，则说明左侧指针指的数字偏小，向右侧移动，反之右侧指针向左侧移动，如果三数相加等于0，则左指针右移到与当前值不同，右指针左移到与当前值不同（去重）。直到左指针位置大于等于右指针，停止搜索。
xxxxxxxxxxclass Solution { public List<List<Integer>> threeSum(int[] nums) { int len = nums.length; List<List<Integer>> res = new ArrayList<List<Integer>>(); if (len<3) {return res;} Arrays.sort(nums); int Lp,Rp,sum; for(int x=0; x < len; x++) { if(nums[x]>0) {break;} if(x>0 && nums[x]==nums[x-1]) {continue;} //去重 Lp = x+1; Rp = len-1; while(Lp < Rp) { sum = nums[Lp]+nums[Rp]+nums[x]; if(sum <0){Lp += 1;} else if (sum == 0){ res.add(new ArrayList<Integer>(Arrays.asList(nums[x],nums[Lp],nums[Rp]))); while(Lp < len-1 && nums[Lp]==nums[Lp+1]){Lp++;} //去重 while(Rp > 0 && nums[Rp] == nums[Rp-1]){Rp--;} //去重 Lp++; Rp--; } else {Rp -= 1;} } } return res; }}xxxxxxxxxxclass Solution { public List<String> generateParenthesis(int n) { ArrayList<String> li = new ArrayList<String>(); backTrace(0,0,n,new String(),li); return li; } private static void backTrace(int open, int close, int max, String cur, List<String> li){ if(cur.length() == max * 2){ li.add(cur); } else { if(open<max) {backTrace(open+1, close, max, cur+'(', li);} if(close<open) {backTrace(open, close+1, max, cur+')', li);} } }}
xxxxxxxxxxclass Solution { public int removeDuplicates(int[] nums) { int count=0; for(int i=1; i<nums.length; i++) { if (nums[i]!=nums[i-1]) { count ++; nums[count] = nums[i]; } } return count+1; }}xxxxxxxxxxclass Solution { public int removeDuplicates(int[] nums) { int count=0; for(int i=1; i<nums.length; i++) { if (nums[i]==nums[i-1]) { count ++; } else { nums[i-count] = nums[i]; } } return nums.length-count; }}
从第一个数字开始算起，如果遇到sum为负数，则直接舍弃，因为前面部分不可能出现更大的结果了，直接把sum改成遍历到的数字，并继续进行。
xxxxxxxxxxclass Solution { public int maxSubArray(int[] nums) { int ans = nums[0]; int sum = 0; for(int num: nums) { if(sum > 0) { sum += num; } else { sum = num; } ans = Math.max(ans, sum); } return ans; }}
双for循环，第一个for遍历买到的股票价格，第二个for遍历卖出的股票价格，并用一个max变量保存，时间复杂度O(n^2)。代码省略。
用两个指针lpos rpos，如果此时卖出亏钱，则左指针右移，否则右指针右移，用一个变量记录最大价格。时间复杂度O (n)。
xxxxxxxxxxclass Solution { public int maxProfit(int[] prices) { int lpos, rpos; lpos = rpos = 0; int ans = 0; while(rpos < prices.length){ if(prices[rpos] < prices[lpos]){ lpos += 1; } else { ans = Math.max(ans, prices[rpos]-prices[lpos]); rpos += 1; } } return ans; }}
从最左侧列和最上侧列进行递推，很容易完成。
xxxxxxxxxxclass Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for(int i=0; i<m; i++){dp[i][0] = 1;} for(int i=0; i<n; i++){dp[0][i] = 1;} for(int i=1; i<m; i++){ for(int j=1; j<n; j++){ dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; }}第二题给出了障碍物矩阵，如果某地有障碍则在矩阵中表示为1。解法和第一题类似，只不过Dp时要增加条件，并且在第一行和第一列Dp时，若遇到障碍则应当引发短路，令接下来的Dp全部赋值为0。