LeetCode热题 HOT1-50

1、两数之和

经典两数之和，可以通过暴力枚举解决（时间复杂度O(n^2)），当然也可以通过哈希表，hashtable.containsKey()，来选择判断x和target-x

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

2、两数相加

遍历两个链表，逐位计算它们的和

class Solution {
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    
        ListNode root = new ListNode(0);
            ListNode curNode = root;
            int carry = 0;
            while (l1 != null || l2 != null || carry != 0) {
    
                int l1val = l1 != null ? l1.val : 0;
                int l2val = l2 != null ? l2.val : 0;
                int sumval = l1val + l2val + carry;
                carry = sumval / 10;

                ListNode sumNode = new ListNode(sumval % 10);
                curNode.next = sumNode;
                curNode = sumNode;

                if (l1 != null) {
    
                    l1 = l1.next;
                }
                if (l2 != null) {
    
                    l2 = l2.next;
                }
            }
            return root.next;
    }
}

3、无重复字符的最长子串

通过滑动窗口来做，start是当前字符的前一个相同字符的位置加一，然后res存储最大的长度。

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        //字符上一次出现的位置
        int[] last = new int[128];
        for(int i=0;i<128;i++){
    
            last[i] = -1;
        }
        int n = s.length();
        int res = 0;
        //滑动窗口开始的位置
        int start = 0;
        for(int i=0;i<n;i++){
    
            int index = s.charAt(i);
            start = Math.max(start,last[index] + 1);
            res = Math.max(res,i-start+1);
            last[index] = i;
        }
        return res;
    }
}

5、最长回文子串

找到字符串s中的最长回文子串。

class Solution {
    
    public String longestPalindrome(String s) {
    
        int size = s.length();
        boolean[][] dp = new boolean[size][size];
        int max = 1;
        int left = 0;
        int right = 0;
        if(size<2){
    
            return s;
        }
        for(int i=0;i<size;i++){
    
            dp[i][i] = true;
        }
        char[] str = s.toCharArray();
        for(int L=2;L<=size;L++){
    
            for(int i=0;i<size;i++){
    
                int j = i+L-1;
                if(j>=size){
    
                    break;
                }
                if(str[i]!=str[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>max){
    
                    max = j-i+1;
                    left = i;
                    right = j;
                }
            }  
        }
        return s.substring(left,right+1);
    }
}