左右指针 主要解决数组中的问题：如二分查找
盛最多水的容器
//给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
// 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。
// 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
//
// 说明：你不能倾斜容器，且 n 的值至少为 2。
//
//
//
//
//
// 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
//
//
//
// 示例：
//
// 输入：[1,8,6,2,5,4,8,3,7]
//输出：49
// Related Topics 数组 双指针
package leetcode.editor.cn;
//Java：盛最多水的容器
/**
* 容纳的水容量是由 两个指针质量的数字中的较小值*指针之间的距离 决定的。
* 双指针代表的是可以作为容器边界的所有位置的范围。
* 双指针指向数组的左右边界，表示数组中所有的位置都可以作为容器的边界。
* 每次将对应的数字较小的那个指针往另一个指针的方向移动一个位置，就表示我们认为这个指针不可能再作为容器的边界了。
*
*
*/
public class P11ContainerWithMostWater {
public static void main(String[] args) {
Solution solution = new P11ContainerWithMostWater().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
/**
* N
* 1
*
* @param height
* @return
*/
public int maxArea(int[] height) {
int n = height.length;
int ans = 0;
int l = 0, r = n - 1;
while (l < r) {
int area = Math.min(height[l], height[r]) * (r - l);
ans = Math.max(area, ans);
if (height[l] < height[r]) {
l++;
} else {
r--;
}
}
return ans;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
三数之和
//给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
//
// 注意：答案中不可以包含重复的三元组。
//
//
//
// 示例：
//
// 给定数组 nums = [-1, 0, 1, 2, -1, -4]，
//
//满足要求的三元组集合为：
//[
// [-1, 0, 1],
// [-1, -1, 2]
//]
//
// Related Topics 数组 双指针
package leetcode.editor.cn;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
//Java：三数之和
public class P15ThreeSum {
public static void main(String[] args) {
Solution solution = new P15ThreeSum().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
int n = nums.length;
Arrays.sort(nums);
for (int i = 0; i < n - 2; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++; //去重
}
while (left < right && nums[right] == nums[right - 1]) {
right--; //去重
}
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return ans;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
四数之和
//给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
//
// 注意：
//
// 答案中不可以包含重复的四元组。
//
// 示例：
//
// 给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。
//
//满足要求的四元组集合为：
//[
// [-1, 0, 0, 1],
// [-2, -1, 1, 2],
// [-2, 0, 0, 2]
//]
//
// Related Topics 数组 哈希表 双指针
package leetcode.editor.cn;
import sun.security.provider.Sun;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
//Java：四数之和
public class P18FourSum {
public static void main(String[] args) {
Solution solution = new P18FourSum().new Solution();
// TO TEST
solution.fourSum(new int[]{0, 0, 0, 0}, 0);
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<>();
//先排序
Arrays.sort(nums);
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
// //排序后的第一个数大于0，直接返回
// 0 0 0 0 不成立
// if (nums[i] > 0) {
// return ans;
// }
//重复数字 指针下移
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int left = j + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) {
left++; //重复指针右移
}
while (left < right && nums[right] == nums[right - 1]) {
right--; //重复指针左移
}
left++;
right--;
} else if (sum > target) {
right--;
} else {
left++;
}
}
}
}
return ans;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
最接近三数之和
//给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。
//
// 例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.
//
//与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
//
// Related Topics 数组 双指针
package leetcode.editor.cn;
import java.util.Arrays;
import java.util.Map;
//Java：最接近的三数之和
public class P16ThreeSumClosest {
public static void main(String[] args) {
Solution solution = new P16ThreeSumClosest().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int threeSumClosest0(int[] nums, int target) {
Arrays.sort(nums);
int answer = nums[0] + nums[1] + nums[2];
for (int i = 0; i < nums.length; i++) {
int start = i + 1;
int end = nums.length - 1;
while (start < end) {
int sum = nums[start] + nums[end] + nums[i];
if (Math.abs(target - sum) < Math.abs(target - answer)) {
answer = sum;
}
if (sum < target) {
start++;
} else if (sum > target) {
end--;
} else {
return answer;
}
}
}
return answer;
}
public int threeSumClosest(int[] nums, int target) {
//记录最接近target的值
Arrays.sort(nums);
int answer = nums[0] + nums[1] + nums[2];
int n = nums.length;
for (int i = 0; i < n; i++) {
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (Math.abs(target - sum) < Math.abs(target - answer)) {
answer = sum;
}
if (sum < target) {
left++; // 三数和偏小，往右移
} else if (sum > target) {
right--; // 三数和偏大，往左移
} else {
return target;
}
}
}
return answer;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
快慢指针 主要解决链表中的问题：典型的判定链表中是否包含环
删除链表的倒数第N个节点
//给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
//
// 示例：
//
// 给定一个链表: 1->2->3->4->5, 和 n = 2.
//
//当删除了倒数第二个节点后，链表变为 1->2->3->5.
//
//
// 说明：
//
// 给定的 n 保证是有效的。
//
// 进阶：
//
// 你能尝试使用一趟扫描实现吗？
// Related Topics 链表 双指针
package leetcode.editor.cn;
import java.util.List;
//Java：删除链表的倒数第N个节点
public class P19RemoveNthNodeFromEndOfList{
public static void main(String[] args) {
Solution solution = new P19RemoveNthNodeFromEndOfList().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 两次遍历算法
* 删除末尾的第n个元素 就是删除从列表开头起数的第 L-n+1 个节点，其中L是列表的长度。
* 我们将添加一个哑结点作为辅助，该节点位于列表头部。
* 哑结点用来简化某些极端的情况。例如表中只含有一个节点，或者需要删除列表的头部。
* 在第一次遍历中，我们找到列表的长度L，然后设置一个指向哑结点的指针，并移动它遍历列表，直至它到达第 L-N 个节点那里。
* 我们把第 L-N 个节点的next指针重新链接点第 L-n+2个节点，完成这个算法。
* @param head
* @param n
* @return
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
int length = 0;
ListNode first = head;
while (first != null) {
length++;
first = first.next;
}
length -= n;
first = dummy;
while (length > 0) {
length--;
first = first.next;
}
first.next = first.next.next;
return dummy.next;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
相交链表
//编写一个程序，找到两个单链表相交的起始节点。
//
// 如下面的两个链表：
//
//
//
// 在节点 c1 开始相交。
//
//
//
// 示例 1：
//
//
//
// 输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
//输出：Reference of the node with value = 8
//输入解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
//
//
//
//
// 示例 2：
//
//
//
// 输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
//输出：Reference of the node with value = 2
//输入解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
//
//
//
//
// 示例 3：
//
//
//
// 输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
//输出：null
//输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
//解释：这两个链表不相交，因此返回 null。
//
//
//
//
// 注意：
//
//
// 如果两个链表没有交点，返回 null.
// 在返回结果后，两个链表仍须保持原有的结构。
// 可假定整个链表结构中没有循环。
// 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
//
// Related Topics 链表
package leetcode.editor.cn;
//Java：相交链表
// https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/zhi-yao-wo-men-you-jiao-ji-zhong-hui-zai-yi-qi-by-/
public class P160IntersectionOfTwoLinkedLists {
public static void main(String[] args) {
Solution solution = new P160IntersectionOfTwoLinkedLists().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode0(ListNode headA, ListNode headB) {
ListNode nodeA = headA;
ListNode nodeB = headB;
int index = 0;
while (nodeA != null && nodeB != null) {
if (nodeA.val != nodeB.val) {
index++;
if (index % 2 == 0) {
nodeA = nodeA.next;
} else {
nodeB = nodeB.next;
}
} else {
return nodeA;
}
}
return null;
}
/**
* 走到尽头见不到你，于是走过你来时的路，等到相遇时才发现，你也走过我来时的路。
*
* @param myRoad
* @param yourRoad
* @return
*/
public ListNode getIntersectionNode1(ListNode myRoad, ListNode yourRoad) {
if (myRoad == null || yourRoad == null) {
return null;
}
// 我走我的路
ListNode me = myRoad;
// 你走你的路
ListNode you = yourRoad;
// 也许某一刻不能相顾
while (me != you) {
// 一直往前走
me = me.next;
you = you.next;
// 除非生命到老，我们彼此结束
if (me == null && you == null) {
return null;
}
// 踏上彼此走过的旅程
if (me == null) me = yourRoad;
if (you == null) you = myRoad;
}
// 只要我们有交集，终会在一起
ListNode ourRoad = you; // || ourRoad = me;
return ourRoad;
}
/**
* a + c + b = b + c + a 同步向前直到相交处
* @param headA
* @param headB
* @return
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode na = headA;
ListNode nb = headB;
while (na != nb) {
na = na == null ? headB : na.next;
nb = nb == null ? headA : nb.next;
}
return na;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
判定链表中是否含有环 环形链表I
//给定一个链表，判断链表中是否有环。
//
// 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
//
//
//
// 示例 1：
//
// 输入：head = [3,2,0,-4], pos = 1
//输出：true
//解释：链表中有一个环，其尾部连接到第二个节点。
//
//
//
//
// 示例 2：
//
// 输入：head = [1,2], pos = 0
//输出：true
//解释：链表中有一个环，其尾部连接到第一个节点。
//
//
//
//
// 示例 3：
//
// 输入：head = [1], pos = -1
//输出：false
//解释：链表中没有环。
//
//
//
//
//
//
// 进阶：
//
// 你能用 O(1)（即，常量）内存解决此问题吗？
// Related Topics 链表 双指针
package leetcode.editor.cn;
//Java：环形链表
public class P141LinkedListCycle{
public static void main(String[] args) {
Solution solution = new P141LinkedListCycle().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* 快慢指针
* 如果不包含环，跑的快的那个指针最终会遇到null，是说明不含环
* 如果含有环，快指针最终会超慢指针一圈，和慢指针相遇，说明链表含有环
*
* @param head
* @return
*/
public boolean hasCycle(ListNode head) {
ListNode fast, slow;
fast = slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
return true;
}
}
return false;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
环形链表 II
//给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//
// 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
//
// 说明：不允许修改给定的链表。
//
//
//
// 示例 1：
//
// 输入：head = [3,2,0,-4], pos = 1
//输出：tail connects to node index 1
//解释：链表中有一个环，其尾部连接到第二个节点。
//
//
//
//
// 示例 2：
//
// 输入：head = [1,2], pos = 0
//输出：tail connects to node index 0
//解释：链表中有一个环，其尾部连接到第一个节点。
//
//
//
//
// 示例 3：
//
// 输入：head = [1], pos = -1
//输出：no cycle
//解释：链表中没有环。
//
//
//
//
//
//
// 进阶：
//你是否可以不用额外空间解决此题？
// Related Topics 链表 双指针
package leetcode.editor.cn;
//Java：环形链表 II
public class P142LinkedListCycleIi {
public static void main(String[] args) {
Solution solution = new P142LinkedListCycleIi().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* 头结点到环入口长度 A ，环入口到相遇位置长度 B ，环长 L
* 慢指针走 A + B ，快指针走 A + L + B 有 (A+B)*2 = A+B+L则 A=L-B
* 故将其中一指针指向头结点，同速度重新一起跑，则在环入口处两指针相遇
* @param head
* @return
*/
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
do {
//如果无环返回 null
if (fast == null || fast.next == null) {
return null;
}
fast = fast.next.next;
slow = slow.next;
} while (fast != slow);
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
链表的中间结点
//给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
//
// 如果有两个中间结点，则返回第二个中间结点。
//
//
//
// 示例 1：
//
// 输入：[1,2,3,4,5]
//输出：此列表中的结点 3 (序列化形式：[3,4,5])
//返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。
//注意，我们返回了一个 ListNode 类型的对象 ans，这样：
//ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
//
//
// 示例 2：
//
// 输入：[1,2,3,4,5,6]
//输出：此列表中的结点 4 (序列化形式：[4,5,6])
//由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
//
//
//
//
// 提示：
//
//
// 给定链表的结点数介于 1 和 100 之间。
//
// Related Topics 链表
package leetcode.editor.cn;
//Java：链表的中间结点
public class P876MiddleOfTheLinkedList{
public static void main(String[] args) {
Solution solution = new P876MiddleOfTheLinkedList().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
/**
* 快慢指针遍历链表
* 长度为奇数时，slow落在正中。长度为偶数时，slow在中间偏右。
* @param head
* @return
*/
public ListNode middleNode(ListNode head) {
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
链表中倒数第k个节点
//输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。
//
//
//
// 示例：
//
// 给定一个链表: 1->2->3->4->5, 和 k = 2.
//
//返回链表 4->5.
// Related Topics 链表 双指针
package leetcode.editor.cn;
//Java：链表中倒数第k个节点 LCOF
public class P面试题22LianBiaoZhongDaoShuDiKgeJieDianLcof{
public static void main(String[] args) {
Solution solution = new P面试题22LianBiaoZhongDaoShuDiKgeJieDianLcof().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head, slow = head;
//k-- 返回的k。 执行k次
while (k-- > 0) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
数组中的最长山脉
//我们把数组 A 中符合下列属性的任意连续子数组 B 称为 “山脉”：
//
//
// B.length >= 3
// 存在 0 < i < B.length - 1 使得 B[0] < B[1] < ... B[i-1] < B[i] > B[i+1] > ... > B[B.length - 1]
//
//
// （注意：B 可以是 A 的任意子数组，包括整个数组 A。）
//
// 给出一个整数数组 A，返回最长 “山脉” 的长度。
//
// 如果不含有 “山脉” 则返回 0。
//
//
//
// 示例 1：
//
// 输入：[2,1,4,7,3,2,5]
//输出：5
//解释：最长的 “山脉” 是 [1,4,7,3,2]，长度为 5。
//
//
// 示例 2：
//
// 输入：[2,2,2]
//输出：0
//解释：不含 “山脉”。
//
//
//
//
// 提示：
//
//
// 0 <= A.length <= 10000
// 0 <= A[i] <= 10000
//
// Related Topics 双指针
package leetcode.editor.cn;
//Java：数组中的最长山脉
public class P845LongestMountainInArray {
public static void main(String[] args) {
Solution solution = new P845LongestMountainInArray().new Solution();
// TO TEST
}
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public int longestMountain(int[] A) {
if (A.length < 3) {
return 0;
}
int ans = 0;
int start = 0;
while (start <= A.length - 2) {
//end尝试延伸这个山脉
int end = start;
if (A[end] < A[end + 1]) { //山脉一开始必须是严格上升的，否则直接让start+1，进入下一轮
while (end + 1 < A.length && A[end] < A[end + 1]) { //一直上升到不再上升为止
end++;
} //此时end的下一个元素已经不比end执行的元素严格大了
if (end + 1 < A.length && A[end] > A[end + 1]) { //山脉要求最高点后立即严格下降
while (end + 1 < A.length && A[end] > A[end + 1]) {
end++;
}// 下降到不再严格下降为止，这时候start和end所包含的区间就是一座山峰了
ans = Math.max(ans, end - start + 1); //尝试更新ans
start = end; //尝试寻找下一座山脉，这里体现了start的跳跃性，类似于KMP模式匹配
} else { //如果是平着的，或者到了末尾，就开始下一轮。因为这一段没有山峰。因为山峰必须为严格下降
start = end + 1;
}
} else {
start++;
}
}
return ans;
}
}
//leetcode submit region end(Prohibit modification and deletion)
}
网友评论