16. 最接近的三數(shù)之和
給定一個(gè)包括 n 個(gè)整數(shù)的數(shù)組 nums 和 一個(gè)目標(biāo)值 target。找出 nums 中的三個(gè)整數(shù)，使得它們的和與 target 最接近。返回這三個(gè)數(shù)的和。假定每組輸入只存在唯一答案。
示例：
輸入：nums = [-1,2,1,-4], target = 1
輸出：2
解釋：與 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int n = nums.length;
int best = 10000000;
// 枚舉 a
for (int i = 0; i < n; ++i) {
// 保證和上一次枚舉的元素不相等
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 使用雙指針枚舉 b 和 c
int j = i + 1, k = n - 1;
while (j < k) {
int sum = nums[i] + nums[j] + nums[k];
// 如果和為 target 直接返回答案
if (sum == target) {
return target;
}
// 根據(jù)差值的絕對(duì)值來更新答案
if (Math.abs(sum - target) < Math.abs(best - target)) {
best = sum;
}
if (sum > target) {
// 如果和大于 target，移動(dòng) c 對(duì)應(yīng)的指針
int k0 = k - 1;
// 移動(dòng)到下一個(gè)不相等的元素
while (j < k0 && nums[k0] == nums[k]) {
--k0;
}
k = k0;
} else {
// 如果和小于 target，移動(dòng) b 對(duì)應(yīng)的指針
int j0 = j + 1;
// 移動(dòng)到下一個(gè)不相等的元素
while (j0 < k && nums[j0] == nums[j]) {
++j0;
}
j = j0;
}
}
}
return best;
}
}
15. 三數(shù)之和
給你一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums，判斷 nums 中是否存在三個(gè)元素 a，b，c ，使得 a + b + c = 0 ？請(qǐng)你找出所有滿足條件且不重復(fù)的三元組。
注意：答案中不可以包含重復(fù)的三元組。
示例：
給定數(shù)組 nums = [-1, 0, 1, 2, -1, -4]，
滿足要求的三元組集合為：
[
[-1, 0, 1],
[-1, -1, 2]
]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
int n = nums.length;
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<List<Integer>>();
// 枚舉 a
for (int first = 0; first < n; ++first) {
// 需要和上一次枚舉的數(shù)不相同
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 對(duì)應(yīng)的指針初始指向數(shù)組的最右端
int third = n - 1;
int target = -nums[first];
// 枚舉 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚舉的數(shù)不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保證 b 的指針在 c 的指針的左側(cè)
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指針重合，隨著 b 后續(xù)的增加
// 就不會(huì)有滿足 a+b+c=0 并且 b<c 的 c 了，可以退出循環(huán)
if (second == third) {
break;
}
if (nums[second] + nums[third] == target) {
List<Integer> list = new ArrayList<Integer>();
list.add(nums[first]);
list.add(nums[second]);
list.add(nums[third]);
ans.add(list);
}
}
}
return ans;
}
}
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> ans = new ArrayList<>();
for(int i = 0;i<n;i++){
if(nums[i]>0){
return ans;
}
if(i>0&&nums[i]==nums[i-1]){
continue;
}
int target = -nums[i];
int j= i+1,k=n-1;
while(j<k){
int sum = nums[j]+nums[k];
if(sum==target){
List<Integer> list=new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
ans.add(list);
int k0=k-1;
while(j<k0&&nums[k0]==nums[k]){
k0--;
}
k=k0;
int j0=j+1;
while(j0<k&&nums[j0]==nums[j]){
j0++;
}
j=j0;
}else if(sum>target){
int k0=k-1;
while(j<k0&&nums[k0]==nums[k]){
k0--;
}
k=k0;
}else{
int j0=j+1;
while(j0<k&&nums[j0]==nums[j]){
j0++;
}
j=j0;
}
}
}
return ans;
}
}
80. 刪除排序數(shù)組中的重復(fù)項(xiàng) II
class Solution {
public int removeDuplicates(int[] nums) {
int n = nums.length;
if (n <= 2) {
return n;
}
int slow = 2, fast = 2;
while (fast < n) {
if (nums[slow - 2] != nums[fast]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
}
82. 刪除排序鏈表中的重復(fù)元素 II
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode ans = new ListNode(-1);
ListNode pre = ans;
pre.next=head;
ListNode start = head;
ListNode end = head;
while(pre.next!=null){
while(end.next!=null&&end.next.val==start.val){
end=end.next;
}
if(start==end){
start = start.next;
end = end.next;
pre = pre.next;
}else{
pre.next = end.next;
start = end.next;
end=end.next;
}
}
return ans.next;
}
}
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return head;
}
ListNode dummy = new ListNode(0, head);
ListNode cur = dummy;
while (cur.next != null && cur.next.next != null) {
if (cur.next.val == cur.next.next.val) {
int x = cur.next.val;
while (cur.next != null && cur.next.val == x) {
cur.next = cur.next.next;
}
} else {
cur = cur.next;
}
}
return dummy.next;
}
}
1209. 刪除字符串中的所有相鄰重復(fù)項(xiàng) II
public String removeDuplicates(String s, int k) {
Stack<Integer> counts = new Stack<>();
char[] sa = s.toCharArray();
int j = 0;
for (int i = 0; i < s.length(); ++i, ++j) {
sa[j] = sa[i];
if (j == 0 || sa[j] != sa[j - 1]) {
counts.push(1);
} else {
int incremented = counts.pop() + 1;
if (incremented == k) {
j = j - k;
} else {
counts.push(incremented);
}
}
}
return new String(sa, 0, j);
}
public String removeDuplicates(String s, int k) {
StringBuilder sb = new StringBuilder(s);
Stack<Integer> counts = new Stack<>();
for (int i = 0; i < sb.length(); ++i) {
if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) {
counts.push(1);
} else {
int incremented = counts.pop() + 1;
if (incremented == k) {
sb.delete(i - k + 1, i + 1);
i = i - k;
} else {
counts.push(incremented);
}
}
}
return sb.toString();
}
442. 數(shù)組中重復(fù)的數(shù)據(jù)
class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> res = new ArrayList<>();
for (int i = 0; i < nums.length; ++i) {
int index = Math.abs(nums[i])-1;
if (nums[index] < 0)
res.add(Math.abs(nums[i]));
nums[index] = -nums[index];
}
return res;
}
}
402. 移掉K位數(shù)字
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> deque = new LinkedList<Character>();
int length = num.length();
for (int i = 0; i < length; ++i) {
char digit = num.charAt(i);
while (!deque.isEmpty() && k > 0 && deque.peekLast() > digit) {
deque.pollLast();
k--;
}
deque.offerLast(digit);
}
for (int i = 0; i < k; ++i) {
deque.pollLast();
}
StringBuilder ret = new StringBuilder();
boolean leadingZero = true;
while (!deque.isEmpty()) {
char digit = deque.pollFirst();
if (leadingZero && digit == '0') {
continue;
}
leadingZero = false;
ret.append(digit);
}
return ret.length() == 0 ? "0" : ret.toString();
}
}
287. 尋找重復(fù)數(shù)
public class Solution {
public int findDuplicate(int[] nums) {
int len = nums.length;
int left = 1;
int right = len - 1;
while (left < right) {
// 在 Java 里可以這么用，當(dāng) left + right 溢出的時(shí)候，無符號(hào)右移保證結(jié)果依然正確
int mid = (left + right) >>> 1;
int cnt = 0;
for (int num : nums) {
if (num <= mid) {
cnt += 1;
}
}
// 根據(jù)抽屜原理，小于等于 4 的個(gè)數(shù)如果嚴(yán)格大于 4 個(gè)
// 此時(shí)重復(fù)元素一定出現(xiàn)在 [1, 4] 區(qū)間里
if (cnt > mid) {
// 重復(fù)元素位于區(qū)間 [left, mid]
right = mid;
} else {
// if 分析正確了以后，else 搜索的區(qū)間就是 if 的反面
// [mid + 1, right]
left = mid + 1;
}
}
return left;
}
}
220. 存在重復(fù)元素 III
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
TreeSet<Integer> set = new TreeSet<>();
for (int i = 0; i < nums.length; ++i) {
// Find the successor of current element
Integer s = set.ceiling(nums[i]);
if (s != null && s <= nums[i] + t) return true;
// Find the predecessor of current element
Integer g = set.floor(nums[i]);
if (g != null && nums[i] <= g + t) return true;
set.add(nums[i]);
if (set.size() > k) {
set.remove(nums[i - k]);
}
}
return false;
}
39. 組合總和
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
public class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Deque<Integer> path = new ArrayDeque<>();
dfs(candidates, 0, len, target, path, res);
return res;
}
/**
* @param candidates 候選數(shù)組
* @param begin 搜索起點(diǎn)
* @param len 冗余變量，是 candidates 里的屬性，可以不傳
* @param target 每減去一個(gè)元素，目標(biāo)值變小
* @param path 從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑，是一個(gè)棧
* @param res 結(jié)果集列表
*/
private void dfs(int[] candidates, int begin, int len, int target, Deque<Integer> path, List<List<Integer>> res) {
// target 為負(fù)數(shù)和 0 的時(shí)候不再產(chǎn)生新的孩子結(jié)點(diǎn)
if (target < 0) {
return;
}
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
// 重點(diǎn)理解這里從 begin 開始搜索的語意
for (int i = begin; i < len; i++) {
path.addLast(candidates[i]);
// 注意：由于每一個(gè)元素可以重復(fù)使用，下一輪搜索的起點(diǎn)依然是 i，這里非常容易弄錯(cuò)
dfs(candidates, i, len, target - candidates[i], path, res);
// 狀態(tài)重置
path.removeLast();
}
}
}
406. 根據(jù)身高重建隊(duì)列
class Solution {
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, new Comparator<int[]>() {
public int compare(int[] person1, int[] person2) {
if (person1[0] != person2[0]) {
return person2[0] - person1[0];
} else {
return person1[1] - person2[1];
}
}
});
List<int[]> ans = new ArrayList<int[]>();
for (int[] person : people) {
ans.add(person[1], person);
}
return ans.toArray(new int[ans.size()][]);
}
}
