給自己的目標(biāo)：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一題
在做題的過(guò)程中記錄下解題的思路或者重要的代碼碎片以便后來(lái)翻閱。
項(xiàng)目源碼：github上的Leetcode
1. Two Sum
題目：給出一個(gè)數(shù)組和一個(gè)目標(biāo)值，求數(shù)組內(nèi)兩個(gè)值相加與目標(biāo)值相等的下標(biāo)锁孟。假設(shè)唯一解澳腹。
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
使用 HashMap 做存儲(chǔ)煎谍，value為num值砰粹，key為目標(biāo)值減去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
題目：輸入兩個(gè)鏈表枕磁，鏈表中的值一一相加渡蜻，輸出鏈表。
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
由于會(huì)出現(xiàn)鏈表不同長(zhǎng)和進(jìn)位的情況计济，所以開(kāi)頭要做好為空的處理茸苇。
/**
* 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
題目：最長(zhǎng)不重復(fù)子串
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.
貪心算法，需要一個(gè)Map記錄字符最后出現(xiàn)的位置沦寂。同時(shí)還有一個(gè) index 記錄不重復(fù)字符串的開(kāi)頭以便計(jì)算長(zhǎng)度和 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
題目：給出兩個(gè)有序數(shù)組，合并后求中心值传藏。
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
給出兩個(gè)指針?lè)謩e指向兩個(gè)數(shù)組的開(kāi)頭腻暮，當(dāng)nums1上的 數(shù)小于nums2時(shí)，nums上的指針向后移一位毯侦，一直到兩個(gè)長(zhǎng)度和的中間值西壮。
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
題目：最長(zhǎng)回文子串。string長(zhǎng)度最大為1000
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Input: "cbbd"
Output: "bb"
回文有兩種：（1）中間存在單個(gè)字符叫惊，如 bab款青；（2）左右對(duì)稱(chēng)，如 bb霍狰。
所以求回文時(shí)要把兩種形式都要考慮進(jìn)去抡草。
求回文的方法：取中間一個(gè)值或中間兩個(gè)相等的值分別向左向右循環(huán)比較。遞歸求解蔗坯。
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;
}
}
}
