1. 两数相加（02）
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
思想： 遍历， 考虑进位和链表空的情况
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode res = new ListNode(0); ListNode cur = res; int cnt =0; while (l1!=null || l2!=null){ int num1= l1 ==null?0:l1.val; int num2 = l2 ==null ?0 : l2.val; int sum = num1+num2+cnt; cnt = sum/10; cur.next =new ListNode(sum%10); if (l1!=null) l1 = l1.next; if (l2!=null) l2 = l2.next; cur = cur.next; } if (cnt>0){ cur.next = new ListNode(cnt); } return res.next; } }
2. 无重复的最长子串（03）
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思想：左右指针，规律是当出现重复的字符时左指针向右移动， 集合去除原指针位置所在元素
class Solution { public int lengthOfLongestSubstring(String s) { int max =0; HashSet<Character> set = new HashSet<>(); int right = -1; int n= s.length(); // for (int left = 0; left <n ; left++) { if(left!=0){ set.remove(s.charAt(left-1)); } //左指针前进一步 while (right+1<n && !set.contains(s.charAt(right+1))){ set.add(s.charAt(right+1)); right++; } //右指针定位到与前面任意一个字符重复的地方 max = Math.max(max,right-left+1); } return max; } }
3. 寻找两个正序数组的中位数（04）
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n))
思想：二分查找
如果 A[k/2−1]<B[k/2−1]，则比 A[k/2−1] 小的数最多只有 A 的前 k/2−1个数和 B 的前 k/2−1个数，即比 A[k/2−1]小的数最多只有 k−2个，因此 A[k/2−1] 不可能是第 kkk 个数，A[0]到 A[k/2−1]也都不可能是第 k 个数，可以全部排除；如果 A[k/2−1]>B[k/2−1]，则可以排除 B[0]到 B[k/2−1]；如果 A[k/2−1]=B[k/2−1]，则可以归入第一种情况处理。
如果 A[k/2−1]或者 B[k/2−1]越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 k 的值，而不能直接将 k减去 k/2。
如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 k 小的元素。
如果 k=1，我们只要返回两个数组首元素的最小值即可。
class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int length1 =nums1.length; int length2 =nums2.length; int totalLength = length1+length2; if (totalLength%2==1){ int midIndex = totalLength/2; double median = getKth(nums1,nums2,midIndex+1); return median; }else { int midIndex = totalLength/2; double median = getKth(nums1,nums2,midIndex+1)+getKth(nums1,nums2,midIndex); return median/2; } } private double getKth(int[] nums1, int[] nums2, int k) { int len1= nums1.length; int len2 = nums2.length; int id1 = 0,id2 =0; while (true){ //边界,说明有一个数组已经为空，那么第k个大的就是排在另一个数组里的第k个元素 if (id1==len1){ return nums2[id2+k-1]; } if(id2==len2){ return nums1[id1+k-1]; } //k==1只需要比较首元素谁最小即可 if (k==1){ return Math.min(nums1[id1],nums2[id2]); } // 二分缩小查找 int half = k/2; int newid1 = Math.min(id1+half,len1)-1; //不能超出数组大小， int newid2 =Math.min(id2+half,len2)-1; int pivot1 = nums1[newid1] ,pivot2 = nums2[newid2]; if (pivot1<pivot2){ k = k - (newid1-id1+1); //至少排除了 k/2个元素 id1 = newid1+1; }else { k = k- (newid2-id2+1); id2 = newid2+1; } } } }
4. 最长回文子串（05）
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
思想： 如果去掉首尾字母是回文字符串，那么首尾字母相同他也是回文字符串
class Solution { public String longestPalindrome(String s) { int len = s.length(); if(len<2) return s; int maxLen = 1; int begin = 0; boolean[][] dp = new boolean[len][len] ; // 表示从i-j 是否是回文串 for (int i = 0; i < len ; i++) { dp[i][i] = true; } char[] chars = s.toCharArray(); //从子串开始递推，找最大的长度 for (int L = 2; L <= len; L++) { for (int i = 0; i < len; i++) { int j = i+L-1; if(j>=len){ break; } if(chars[i] != chars[j]){ dp[i][j] = false; }else { if(j-i<3){ dp[i][j] =true; }else { dp[i][j] = dp[i+1][j-1]; } } if(dp[i][j] && j-i+1>maxLen){ maxLen=j-i+1; begin = i; //记录回文子串的起始位置 } } } return s.substring(begin,maxLen+begin); } }