- 删除排序链表中的重复元素 II
存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除链表中所有存在数字重复情况的节点，只保留原始链表中 没有重复出现 的数字。
返回同样按升序排列的结果链表。
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
输入：head = [1,1,1,2,3]
输出：[2,3]
用i，j两个指针进行搜索，同时设置prei指针记录i的前驱位置。循环过程中，j先向后一格，若与i相同，则继续向后移动，直到走过了所有重复的节点。将prei.next指向j（删除了中间的重复），i也指向j。之后进入下一次循环，j再向后移动，直到结尾。
答案返回的是头节点的位置，如果链表开头就是重复的数字，则需要调整头节点的位置到删除重复后的prei位置。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur=new ListNode(0,head);
ListNode i=new ListNode(1);
ListNode prei=new ListNode(0);
ListNode j=new ListNode(1);
j=head;i=head;
if(j==null){
return null;
}
int flag=0;
while(j.next!=null){
j=j.next;
if(i.val==j.val){
while(j.val==i.val&&j.next!=null){
j=j.next;
}
if(j.next==null&&j.val==i.val)//直到结尾的所有节点都是重复的
{
prei.next=null;}
else{prei.next=j;}//不是特殊情况的话，则让prei指向不在重复的节点位置
if(flag==0){cur=prei;//开始位置是重复的数字，移动头节点的位置到prei
flag=1;}
i=j;
}
else{
flag=1;
prei=i;
i=i.next;
}
}
return cur.next;
}
}
- 比较含退格的字符串
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
注意：如果对空文本输入退格字符，文本继续为空。
输入：S = “ab#c”, T = “ad#c”
输出：true
解释：S 和 T 都会变成 “ac”。
输入：S = “ab##”, T = “c#d#”
输出：true
解释：S 和 T 都会变成 “”。
退格可以反向使用双指针进行遍历，遇到#，设置skip变量+1，当遇到字母时，跳过skip值的格数。
class Solution {
public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {//找s中第一个需要比较的字母
if (S.charAt(i) == '#') {
skipS++;
i--;
} else if (skipS > 0) {
skipS--;
i--;
} else {
break;
}
}
while (j >= 0) {//找t中第二个需要比较的字母
if (T.charAt(j) == '#') {
skipT++;
j--;
} else if (skipT > 0) {
skipT--;
j--;
} else {
break;
}
}
if (i >= 0 && j >= 0) {
if (S.charAt(i) != T.charAt(j)) {
return false;
}
} else {
if (i >= 0 || j >= 0) {
return false;
}
}
i--;
j--;
}
return true;
}
}
- 区间列表的交集
给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。
输入：firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]]
输出：[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
观察可发现，交集等于，两个范围中左端较大值和右端较小的值，之后右端较小的切换下一个范围继续参与比较。
class Solution {
public int[][] intervalIntersection(int[][] A, int[][] B) {
List<int[]> ans = new ArrayList();
int i = 0, j = 0;
while (i < A.length && j < B.length) {
int lo = Math.max(A[i][0], B[j][0]);
int hi = Math.min(A[i][1], B[j][1]);
if (lo <= hi)
ans.add(new int[]{lo, hi});
if (A[i][1] < B[j][1])
i++;
else
j++;
}
return ans.toArray(new int[ans.size()][]);
}
}
- 盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
盛水的值等于底的长度×左右两端较低的高度值，双指针初始在两端，搜索过程中会减小底的值，为了获取最大值，需要提高height才有更大的可能。
若左边的的右侧一条边大于当前左边，则将其向右移动（反之右边）。
class Solution {
public int maxArea(int[] height) {
int size = height.length;
int left=0, right=size-1;
int ans = 0;
while(left < right){
ans = Math.max(ans, (right-left)*Math.min(height[left], height[right]));
if(height[left] > height[right]) --right;
else ++left;
}
return ans;
}
}
- 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
输入：nums = []
输出：[]
将三个数的和为0转化为两个数的和等于另一个数的负数，首先保证该数组有序，为了避免结果出现重复，则当前搜索的值不能与上一个相同。
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) {
// 需要和上一次枚举的数不相同，确定第一个数
if (first > 0 && nums[first] == nums[first - 1]) {
continue;
}
// c 对应的指针初始指向数组的最右端
int third = n - 1;
int target = -nums[first];
// 枚举 b
for (int second = first + 1; second < n; ++second) {
// 需要和上一次枚举的数不相同
if (second > first + 1 && nums[second] == nums[second - 1]) {
continue;
}
// 需要保证 b 的指针在 c 的指针的左侧
while (second < third && nums[second] + nums[third] > target) {
--third;
}
// 如果指针重合，随着 b 后续的增加
// 就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
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;
}
}