給自己的目標(biāo)：[LeetCode](https://leetcode.com/ "Online Judge Platform") 上每日一題
在做題的過程中記錄下解題的思路或者重要的代碼碎片以便后來翻閱。
項(xiàng)目源碼：github上的Leetcode
16. 3SumClosest
題目：輸入一行數(shù)字和一個目標(biāo)數(shù)字，求出三個數(shù)相加最接近目標(biāo)的值。
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
思路與 3sum 一樣，都是先排序再前后取值，只不過目標(biāo)值從0變?yōu)橐斎氲闹怠?/p>
public class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int distance = Integer.MAX_VALUE;
int min = 0;
for (int i = 0; i < nums.length - 2; i++) {
if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
int start = i + 1, end = nums.length - 1, t = target - nums[i];
while (start < end) {
int value = nums[start] + nums[end];
if (value == t) {
return target;
} else if (value > t) {
end--;
if (distance > value - t) {
distance = value - t;
min = nums[i] + value;
}
} else {
start++;
if (distance > t - value) {
distance = t - value;
min = nums[i] + value;
}
}
}
}
}
return min;
}
}
17. Letter Combinations of a Phone Number
題目：求老式手機(jī)上按下數(shù)字鍵后所有的字符組合，按下0和1會導(dǎo)致數(shù)組為空。
手機(jī)鍵盤
Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
利用char的數(shù)字特性來找到鍵盤的規(guī)律，之后便是不斷循環(huán)添加字符。
public class Solution {
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>();
List<String> temp = new ArrayList<>();
for (int i = 0; i < digits.length(); i++) {
temp.clear();
temp.addAll(result);
result.clear();
char c = digits.charAt(i);
if (c <= '1' || c > '9') {
return result;
} else {
char start;
if (c <= '7') {
start = (char) ((c - '2') * 3 + 'a');
} else {
start = (char) ((c - '2') * 3 + 1 + 'a');
}
int size = (c == '7' || c == '9') ? 4 : 3;
if (temp.size() == 0) {
for (char k = start; k <start + size; k++) {
result.add(String.valueOf(k));
}
} else {
for (String aTemp : temp) {
for (char k = start; k < start + size; k++) {
result.add(aTemp + String.valueOf(k));
}
}
}
}
}
return result;
}
}
18. 4Sum
題目：給出一行數(shù)字和一個目標(biāo)值，求出其中4個數(shù)相加等于目標(biāo)值的所有組合。不能有重復(fù)。
For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
思路同 3sum 一樣，不過要在 3sum 上再套上一層循環(huán)。
public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 3; i++) {
if (i == 0 || i > 0 && nums[i] != nums[i - 1]) {
int t = target - nums[i];
threeSum(nums, t, result, i + 1);
}
}
return result;
}
public void threeSum(int[] nums, int target, List<List<Integer>> result, int k) {
for (int i = k; i < nums.length - 2; i++) {
if (i == k || (i > k && nums[i] != nums[i - 1])) {
int start = i + 1, end = nums.length - 1, t = target - nums[i];
while (start < end) {
if (nums[start] + nums[end] == t) {
result.add(Arrays.asList(nums[k-1], nums[start], nums[end], nums[i]));
while (start < end && nums[end] == nums[end - 1]) end--;
while (start < end && nums[start + 1] == nums[start]) start++;
end--;
start++;
} else if (nums[start] + nums[end] < t) {
start++;
} else {
end--;
}
}
}
}
}
}
19. Remove Nth Node From End of List
題目：輸入一串節(jié)點(diǎn)和一個數(shù)字n,n表示從尾部開始數(shù)起的第n個節(jié)點(diǎn)，這個節(jié)點(diǎn)將會從節(jié)點(diǎn)列表匯中刪除。
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
首先從頭到尾遍歷一遍獲取節(jié)點(diǎn)列表的長度，之后便是再從頭部開始找到要刪除的節(jié)點(diǎn)。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
if (head == null) return head;
int len = 0;
ListNode dummy = new ListNode(-1), pt = dummy;
dummy.next = head;
while (pt.next != null) {
pt = pt.next;
len++;
}
pt = dummy;
for (int cnt = len - n; cnt > 0; cnt--) pt = pt.next;
if (pt.next != null) {
pt.next = pt.next.next;
}
return dummy.next;
}
}
20. Valid Parentheses
題目：有效的括號，輸入一行只包含"(){}[]"的字符串，判斷是否有效（即括號能否左右對應(yīng)）
使用棧FILO的特性來匹配。
public class Solution {
public boolean isValid(String s) {
Stack<Character> p = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '(' || c == '{' || c == '[') {
p.push(c);
} else if (c == ')' || c == '}' || c == ']') {
if (p.size() == 0) {
return false;
}
if (c == ')' && p.pop() != '(') {
return false;
} else if (c == '}' && p.pop() != '{') {
return false;
} else if (c == ']' && p.pop() != '[') {
return false;
}
}
}
if (p.size() != 0) return false;
return true;
}
}
