LeetCode算法代码笔记（1-5）

给自己的目标：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一题

在做题的过程中记录下解题的思路或者重要的代码碎片以便后来翻阅。
项目源码：github上的Leetcode

1. Two Sum

题目：给出一个数组和一个目标值，求数组内两个值相加与目标值相等的下标。假设唯一解。

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

使用 HashMap 做存储，value为num值，key为目标值减去value后需要的值。

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        HashMap<Integer,Integer> hashMap = new HashMap<>();
        for (int i=0;i<nums.length;i++){
            if(hashMap.containsKey(nums[i])){
                answer[0] = hashMap.get(nums[i]);
                answer[1] = i;
                break;
            }
            else{
                hashMap.put(target - nums[i],i);
            }
        }
        return answer;
    }
}

2. Add Two Numbers

题目：输入两个链表，链表中的值一一相加，输出链表。

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

由于会出现链表不同长和进位的情况，所以开头要做好为空的处理。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            if (l1 == null && l2 == null)
                return null;
            if (l1 == null)
                l1 = new ListNode(0);
            if (l2 == null)
                l2 = new ListNode(0);
        }
        ListNode result = new ListNode(0);
        result.val = (l1.val + l2.val) % 10;
        int off = (l1.val + l2.val) / 10;
        if (l1.next != null) {
            l1.next.val += off;
        } else if ((l2.next != null)) {
            l2.next.val += off;
        } else if (off > 0) {
            l1.next = new ListNode(off);
        }
        result.next = addTwoNumbers(l1.next, l2.next);
        return result;
    }
}

3. Longest Substring Without Repeating Characters

题目：最长不重复子串

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. 

Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

贪心算法，需要一个Map记录字符最后出现的位置。同时还有一个 index 记录不重复字符串的开头以便计算长度和 max 最大值。

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int curIndex = 0;
        int max = 0;
        Map<Character, Integer> charMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (charMap.containsKey(s.charAt(i))) {
                curIndex = Math.max(charMap.get(s.charAt(i)) + 1, curIndex);
            }
            charMap.put(s.charAt(i), i);
            max = Math.max(max, i - curIndex + 1);
        }
        return max;
    }
}

4. Median of Two Sorted Arrays

题目：给出两个有序数组，合并后求中心值。

nums1 = [1, 3]
nums2 = [2]
The median is 2.0

nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5

给出两个指针分别指向两个数组的开头，当nums1上的 数小于nums2时，nums上的指针向后移一位，一直到两个长度和的中间值。

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        double sum = 0;
        boolean flag = (m + n) % 2 == 1;
        int median = (m + n) / 2;
        int i = 0, j = 0;
        int x1 = 0;
        for (int k = 0; k <= n + m; k++) {
            if (i < m && j < n && nums1[i] <= nums2[j]) {
                x1 = nums1[i];
                i++;
            } else if (i < m && j < n && nums1[i] > nums2[j]) {
                x1 = nums2[j];
                j++;
            } else if (i >= m) {
                x1 = nums2[j];
                j++;
            } else if (j >= n) {
                x1 = nums1[i];
                i++;
            }
            if (flag) {
                if (k == median) {
                    sum = x1 * 1.0;
                    break;
                }
            } else {
                if (k == median - 1) {
                    sum += x1;
                } else if (k == median) {
                    sum += x1;
                    sum = sum / 2.0;
                    break;
                }
            }
        }
        return sum;
    }
}

5. Longest Palindromic Substring

题目：最长回文子串。string长度最大为1000

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"

回文有两种：（1）中间存在单个字符，如 bab；（2）左右对称，如 bb。
所以求回文时要把两种形式都要考虑进去。
求回文的方法：取中间一个值或中间两个相等的值分别向左向右循环比较。递归求解。

public class Solution {
    private int index,max;
    public String longestPalindrome(String s) {
        int len = s.length();
        if (len < 2) return s;

        for (int i = 0; i < s.length() - 1; i++) {
            extendPalindrome(s, i, i);
            extendPalindrome(s, i, i + 1);
        }

        return s.substring(index, index + max);
    }
    
    private void extendPalindrome(String s,int begin,int end){
        while (begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)) {
            begin--;
            end++;
        }
        if (end - begin - 1 > max) {
            max = end - begin - 1;
            index = begin + 1;
        }
    }
}