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)。
xxxxxxxxxx
import 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来表示,代替累加器。
xxxxxxxxxx
public 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;
}
逐个列举子字符串,看他们是不是回文字符串。加入一句优化,减少遍历次数,主要是针对前期就出现超长回文的情况。勉强通过。
xxxxxxxxxx
class 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 的时间复杂度,所以效率很低,这位作者专门写了中心拓展的函数
xxxxxxxxxx
class 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
}
}
xxxxxxxxxx
class 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 防止溢出
xxxxxxxxxx
class 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;
}
}
xxxxxxxxxx
class 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,很容易想到,不写了。
原理:一开始左指针指最左侧,右指针指最右侧,双侧指针尝试向内侧移动,直到重合。移动的原理是:最大矩形面积取决最短线段的长度和两指针间的距离。如果把指向长线段的指针向内侧移动,不但盛水高度没变,距离还变短了,面积自然减少,所以应当把短指针向内侧移动。反之把长指针向内侧移动。
xxxxxxxxxx
class 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;
}
}
xxxxxxxxxx
class 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)。所以可以先导入哈希表映射,然后遍历字符串。
xxxxxxxxxx
class 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,则左指针右移到与当前值不同,右指针左移到与当前值不同(去重)。直到左指针位置大于等于右指针,停止搜索。
xxxxxxxxxx
class 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;
}
}
xxxxxxxxxx
class 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);}
}
}
}
xxxxxxxxxx
class 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;
}
}
xxxxxxxxxx
class 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改成遍历到的数字,并继续进行。
xxxxxxxxxx
class 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)。
xxxxxxxxxx
class 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;
}
}
从最左侧列和最上侧列进行递推,很容易完成。
xxxxxxxxxx
class 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。