920打卡

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);
    }
}