今日主题，双指针。
11. 盛最多水的容器
问题描述
给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器。
解题思路-暴力解法
将数组中的元素两两组合，求出所有组合构成的容器可以容纳的水量。取其中的最大值返回。
代码实现-暴力解法
class Solution {
public int maxArea(int[] height) {
int maxArea = 0;
for(int i = 0; i < height.length - 1; i++){
for(int j = i + 1; j < height.length; j++){
int area = Math.min(height[i], height[j]) * (j - i);
if(area > maxArea){
maxArea = area;
}
}
}
return maxArea;
}
}
- 时间复杂度O(n^2)
- 空间复杂度O(1)
解题思路-双指针
经过观察可以发现，能容纳水的高度由较小的边界值决定。
我们可以利用头尾指针对数组进行遍历，然后每次都将较小的指针往内移动。
这是因为如果将较大的指针往内移动的话，所容纳的水量一定不会变多（最大高度不会超过较小的边界值，左右的宽度一定会缩小）。
代码实现-双指针
class Solution {
public int maxArea(int[] height) {
int left = 0, right = height.length -1, maxArea = 0;
while(left < right){
int h;
if(height[left] <= height[right]){
h = height[left];
left++;
}else{
h = height[right];
right--;
}
maxArea = Math.max(maxArea, h*(right - left + 1));
}
return maxArea;
}
}
75. 颜色分类
问题描述
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
解题思路
两次遍历。首先，统计nums数组中0、1、2的个数；然后，将元素0、1、2填入nums数组中的相应位置
代码实现
class Solution {
public void sortColors(int[] nums) {
//统计nums数组中0、1、2的个数
int[] colorNums = new int[3];
for(int i = 0; i < nums.length; i++){
colorNums[nums[i]]++;
}
//重新将元素0、1、2填入nums数组
int index = 0;
while(colorNums[0] > 0){
nums[index++] = 0;
colorNums[0]--;
}
while(colorNums[1] > 0){
nums[index++] = 1;
colorNums[1]--;
}
while(colorNums[2] > 0){
nums[index++] = 2;
colorNums[2]--;
}
}
}
解题思路2-双指针
也可以利用双指针实现一趟扫描。在遍历过程中不断将0交换至数组头部，将2交换至数组尾部
代码实现2-双指针
class Solution {
public void sortColors(int[] nums) {
int p0 = 0, p2 = nums.length -1;
int i = 0;
while(i <= p2){
//将0交换至数组头部
if(nums[i] == 0){
swap(nums, i, p0++);
i++;
}else if(nums[i] == 2){
//将2交换至数组尾部
//此时索引不自增，因为如果原来的nums[p2]==2时，需要继续将其交换至尾部
swap(nums, i, p2--);
}else{
i++;
}
}
}
public void swap(int[] nums, int i, int j){
if(i == j){
return;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
19. 删除链表的倒数第 N 个结点
问题描述
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
进阶：你能尝试使用一趟扫描实现吗？
解题思路
此题的关键在于如何通过一趟扫描找到第n个节点的前驱节点。
首先，让快指针比慢指针先走n个节点；然后fast、slow同时出发，fast到尾节点时，slow刚好在倒数第n-1个节点。
代码实现
/**
* 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 removeNthFromEnd(ListNode head, int n) {
//添加虚拟头节点dummyHead
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
ListNode fast = dummyHead, slow = dummyHead;
//fast节点先走n步
for(int i = 0; i < n; i++){
fast = fast.next;
}
//fast、slow同时出发，fast到尾节点时，slow刚好在倒数第n-1个节点
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
}
234. 回文链表
问题描述
请判断一个链表是否为回文链表。
解题思路
首先，利用快慢指针，拿到后半部分链表的头节点slow；
然后，反转后半部分链表；
最后，比较前后链表是否相同；
代码实现
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
//1.利用快慢指针，拿到后半部分链表的头节点slow
ListNode slow = head, fast = head;
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
if(fast != null){
slow = slow.next;
}
//2.反转后半部分链表
ListNode tail = reverse(slow);
//3.做比较
boolean isPalindrome = true;
while(tail != null){
if(head.val != tail.val){
isPalindrome = false;
}
head = head.next;
tail = tail.next;
}
return isPalindrome;
}
//反转链表
public ListNode reverse(ListNode head){
ListNode prev = null,cur = head;
while(cur != null){
ListNode temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}
