LeetCode 刷题以及自己的思路

刷题记录，code代表题目顺序

code1

class Solution { public int[] twoSum(int[] nums, int target) { int res[]=new int[2]; int len=nums.length; for(int i=0;i<len;i++){ for(int j=i+1;j<len;j++){ if(nums[i]+nums[j]==target){ res[0]=i; res[1]=j; } } } return res; } }

code2

public class Code2 { static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public static void main(String[] args) { // TODO Auto-generated method stub ListNode t=new ListNode(8); ListNode t1=new ListNode(5); //测试代码 t= addTwoNumbers(t1, t); while (t!=null) { System.out.println(t.val); t=t.next; } } private boolean flag=false; private static int topInt=0; public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { //找到头节点出队,相加 ListNode l3=null; ListNode temp=null; ListNode temp2=null; ListNode head=null; boolean flag=false; while (l1!=null||l2!=null||flag!=false) { int val1=0; int val2=0; if(l1!=null) { val1=l1.val; }else { val1=0; } if(l2!=null) { val2=l2.val; }else { val2=0; } if(l1==null) { l1=null; }else { l1=l1.next; } if(l2==null) { l2=null; }else { l2=l2.next; } if(flag) { val1=val1+1+val2; flag=false; }else { val1=val1+val2; } if(val1>=10) { flag=true; } val1=val1%10; if(l3==null) { l3=new ListNode(val1); //l3.val=val1; l3.next=null; head=l3; }else { ListNode tl3=new ListNode(val1); //tl3.val=val1; tl3.next=null; head.next=tl3; head=tl3; } } return l3; } }

code3

class Solution { public static void main(String[] args) { //模拟动态规划做此题 lengthOfLongestSubstring("abcd"); } private static char[] charas; public static int lengthOfLongestSubstring(String s) { charas=new char[s.length()]; charas=s.toCharArray(); if(s.length()<=0) return 0; int k=1; for(int i=1;i<s.length();i++) { //k的变化要么变长，要么不变；变长——只会在末尾，且长度为k+1 if(isSubstring(i,k)) { k++; } } System.out.println(k); return k; } private static boolean isSubstring(int i, int k) { // TODO Auto-generated method stub int flag=0; for(int j=(i-k);j<=i;j++) { for(int jk=j+1;jk<=i;jk++) { if(charas[j]==charas[jk]) { return false; } } } return true; } }

code4

没做出来

code5

public class Code5 { public static void main(String[] args) { // TODO Auto-generated method stub String string="bb"; string=longestPalindrome(string); System.out.println(string); } private static char[] arr; private static int extend=0; public static String longestPalindrome(String s) { //arr=new char[s.length()]; arr=s.toCharArray(); int start=0; int index=0; int k=1; if(s.length()<=0) return ""; if(s.length()>=2) { if(arr[0]==arr[1]) k=2; else { k=1; } } for(int i=2;i<s.length();i++) { if(getSub(i, k)==1) { k++; index=i; continue; } if(getSub(i, k)==2) { k+=2; index=i; continue; } //否则并未产生最长子串，无需更新 } //System.out.println("k:"+k); //System.out.println("index:"+index); if(index==0) s=(String) s.subSequence(index, index+k); else { s=(String) s.subSequence(index-k+1, index+1); } return s; } private static int getSub(int i, int step) { //step代表长度为step的回文子串 //System.out.println(i+" "+step); int flag=1; int count=step+1; int begin=i-count+1; int end=i; //同时做两次扩张，第一次k+1,第二次k+2,假定不可能同时成立 while (begin<end) { if(arr[begin++]!=arr[end--]) { flag=-1; break; } } if(flag==1) return 1; flag=1; count=step+2; begin=i-count+1; if(begin<0) return 0; end=i; while (begin<end) { if(arr[begin++]!=arr[end--]) { flag=-1; break; } } if(flag==1) return 2; return 0; } }

code6

public class Code6 { public static void main(String[] args) { // TODO Auto-generated method stub Code6 code6=new Code6(); code6.convert("abc", 3); } public String convert(String s, int numRows) { if(s.length()<=2||numRows<=1) return s; int size=(int)( s.length()/2); if(s.length()%2!=0) size++; char[] ori=new char[s.length()]; ori=s.toCharArray(); char[] res=new char[s.length()]; int[][] arr=new int[numRows][size]; for(int i=0;i<numRows;i++) for(int j=0;j<size;j++) arr[i][j]=-1; //将转化后的数组用矩阵存储 int x=0,y=0; // System.out.println(size); for(int i=0;i<s.length();i++) { //将每个字符放入排序数组 if( Move(i,numRows)==1) { //竖直运动 arr[x][y]=i; x++; }else { // System.out.println("x"+y); arr[x][y]=i; y++; x--; } } int temp=0; for(int i=0;i<numRows;i++) { for(int j=0;j<size;j++) { if(arr[i][j]<0) continue; else { //System.out.println(arr[i][j]); res[temp]=ori[arr[i][j]]; temp++; } } } s=String.valueOf(res); //System.out.println(s); return s; } private int Move(int i,int num) { if(i%(2*num-2)<(num-1)) { return 1; } return 0; } }

Code25

public class Code25 { static class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } public static void main(String[] args) { // TODO Auto-generated method stub ListNode node1=new ListNode(1); ListNode node2=new ListNode(2); ListNode node3=new ListNode(3); ListNode node4=new ListNode(4); ListNode node5=new ListNode(5); node1.next=node2; node2.next=node3; node3.next=node4; node4.next=node5; Code25 code25=new Code25(); ListNode tem=node2; //tem=code25.reverseList(node1, 2); tem=code25.reverseKGroup(node1, 2); // int len=0; while (tem!=null) { System.out.println(""+tem.val); tem=tem.next; // len++; } //System.out.println(len); } private ListNode reverseKGroup(ListNode head, int k) { int len=0; ListNode tem=head; while (tem!=null) { tem=tem.next; len++; } // System.out.println("len"+len); head= finalLists(head,k,len); return head; } private ListNode finalLists(ListNode head, int k, int len) { // 如果len==k,直接调用reverse，否则每K个节点调用 ListNode res=new ListNode(); if(len<k) { return head; } else { ListNode tem=head; ListNode end=head; for(int i=1;i<k;i++) { end=end.next; } // System.out.println("end"+end.val); for(int i=1;i<=k;i++) { tem=tem.next; } res= reverseList(head, k); head.next=finalLists(tem, k, len-k); // System.out.println("tem"+tem.val); return res; } } private ListNode getNode(ListNode head,int n) { ListNode tem=head; while (n>=0) { tem=tem.next; n--; } return tem; } private ListNode reverseList(ListNode head,int k) { //递归反序,代表首节点是head，末尾节点到首节点共k个 //如果两个节点直接反序，如果一个节点不需要 if(k==1) return head; if(k==2) { ListNode end=head.next; ListNode temp=end.next; head.next=temp; end.next=head; return end; } else { ListNode tem=head; ListNode end=head; for(int i=1;i<k;i++) { end=end.next; } tem=head; for(int i=1;i<k/2;i++) { tem=tem.next; } ListNode tem1=tem.next; reverseList(head, k/2); reverseList(tem1, k-k/2); tem1.next=tem; head.next=null; return end; } } }

Code121

public int maxProfit(int[] prices) { int maxpro=0; for (int i = 0; i < prices.length; i++) { for(int j=i+1;j<prices.length;j++) { int profit=prices[j]-prices[i]; if(profit>maxpro) maxpro=profit; } } return maxpro; }

Code155

import java.util.ArrayList; import java.util.List; import java.util.Stack; public class MinStack { //千万不要用min去作为最小的数返回，会出bug Stack<Integer> stack; Stack<Integer> origin;//实际操作的元素 public static void main(String[] args) { // TODO Auto-generated method stub MinStack minStack=new MinStack(); minStack.push(2); minStack.push(0); minStack.push(3); minStack.push(0); minStack.pop(); minStack.pop(); minStack.pop(); System.out.println(minStack.getMin()); } /** initialize your data structure here. */ public MinStack() { stack=new Stack<Integer>(); origin=new Stack<Integer>(); } public void push(int x) { origin.push(x); stack.push(Math.min(stack.peek(), x)); } public void pop() { origin.pop(); stack.pop(); } public int top() { int res=origin.peek(); return res; } public int getMin() { int res=stack.peek(); return res; } /** * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(x); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */ }

code124 解题思路： 1.想好遍历顺序，我用的是后序遍历。 2.题目要求：一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。所以，一条路径从每个节点出发有3种情况，可以左-中-右、左-中、右-中**；对于左-中-父即为其父亲节点的左-中**，这一点我卡了很久，导致我这道题做了很久。 3.递归体设计：应当设计为经过该点的最大左/右子树的路径长度，而利用全局变量记录最大路径和，当所有的点经过遍历，最大路径即被求出来了。

public class Code124 { public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } //经过改点的最长路径和 private int pathSum=Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { //前序遍历整棵树 resgetMaxSum(root); return pathSum; } private int resgetMaxSum(TreeNode root) { // TODO Auto-generated method stub if(root==null) return 0; else { int countl=Math.max(0, resgetMaxSum(root.left)); int countr=Math.max(0, resgetMaxSum(root.right));//利用0作为路径取舍 int count=countl+countr+root.val;//计算经过该点的最长路径 pathSum=Math.max(pathSum, count); return Math.max(countl+root.val,countr+root.val);//想好resgetMaxSum的意义是什么 } } }