算法通关村第三关-白银挑战双指针思想

大家好我是苏麟 , 今天带来算法第三关 .

双指针思想

这里介绍一种简单但非常有效的方式一一双指针。所谓的双指针其实就是两个变量，不一定真的是指针。双指针思想简单好用，在处理数组、字符审等场景下很常见。

例如下图 :

快指针总是比慢指针先走 , 总是在慢指针的前面 , 等到结尾的时候慢指针可能与快指针指向同一个地方 , 也可能快指针走到末尾就直接结束了 …

快慢指针

快慢指针就是双指针的一种实现 , 定义两个指针同时指向一个节点例如头节点,虚拟节点等 , 快指针比慢指针多走了几步 . 下面我们来用一个题目来理解快慢指针 :

删除倒数第K个元素

描述 :

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点

题目 :

LeetCode 删除链表的倒数第N个节点 :

分析 :

首先创建一个虚拟节点(哨兵节点) , 虚拟节点下一节点指向头节点这样我们移动元素的时候比较方便 , 用快慢指针的方式slow节点和fast节点指向虚拟节点 , fast指针比倒数第n个元素多走一步流出删除的节点 , 这样slow.next = slow.next.next 就删除了倒数第n个节点最后返回newNode.next节点也就是head节点 但是直接返回head节点会有一点问题 , 这里有什么问题 ?小伙伴们自己思考一下 .

例 : 1,2 删除倒数第一个元素

解析 :

/**
 * 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) {
        ListNode newNode = new ListNode(-100);
        newNode.next = head;
        ListNode slow = newNode;
        ListNode fast = newNode;
        for(int i = 0;i<= n ;i++){
            fast = fast.next;
        } 
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return newNode.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

这样就实现了快慢指针 , 小伙伴们自己练习练习 …

删除元素专题

移除元素

题目 :

LeetCode 27.移除元素 :

27. 移除元素
​​

分析 :

快慢指针 :

定义两个指针slow和fast，初始值都是0。Slow之前的位置都是有效部分，fast表示当前要访问的元素。

这样遍历的时候，fast不断向后移动:

如果nums[fast]的值不为val，则将其移动到nums[slow++]
如果nums[fast]的值为val，则fast继续向前移动，slow先等待

​​​​

这样，前半部分是有效部分，后半部分是无效部分

解析 :

class Solution {
    public int removeElement(int[] nums, int val) {
        int slow=0;

        for(int fast = 0;fast < nums.length; fast++){
            if(nums[fast] != val){
            nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

元素奇偶移动专题

描述 :

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。
返回满足此条件的 任一数组 作为答案。

题目 :

LeetCode 905. 按奇偶排序数组 :

按奇偶排序数组

分析 :

我们可以采用对撞型双指针的方法，图示中的对撞型基本一致，只不过比较的对象是奇数还是偶数。如下图所示:
维护两个指针 left=0和 right=arr.ength-1，left从0开始逐个检查每个位置是否为偶数，如果是则跳过如果是奇数则停下来。然后right从右向左检查，如果是奇数则跳过偶数则停下来。然后交换array[left]和array[right]。之后再继续巡循环，直到left> =right。

解析 :

class Solution {
    public int[] sortArrayByParity(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            if((nums[left] % 2) > (nums[right] % 2)){
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
            if(nums[left] % 2 == 0){
                left++;
            }
            if(nums[right] % 2 > 0){
                right--;
            }
        }
        return nums;
    }
} 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

汇总区间

描述 :

给定一个 无重复元素 的 有序 整数数组 nums 。

返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。

题目 :

LeetCode 228.汇总区间 :

228.汇总区间

分析 :

这个题使用双指针也可以非常方便的处理，慢指针指向每个区间的起始位置，快指针从慢指针位置开始向后遍历直到不满足连续递增(或快指针达到数组边界)，则当前区间结束;然后将 slow指向更新为 fast + 1，作为下一个区间的开始位置fast继续向后遍历找下一个区间的结束位置，如此循环，直到输入数组遍历完毕 .

解析 :

// LeetCode
class Solution {
    public List<String> summaryRanges(int[] nums) {
        ArrayList<String> al = new ArrayList<>();

        int slow = 0;

        for(int fast = 0;fast < nums.length ; fast++){
            if(fast + 1 == nums.length || nums[fast] + 1 != nums[fast + 1]){
                StringBuffer s = new StringBuffer();
                s.append(nums[slow]);
                if(slow != fast){
                    s.append("->").append(nums[fast]);
                }
                al.add(s.toString());   
                slow = fast + 1;
            }
        }
        return al;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

轮转数组

描述 :

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

题目 :

牛客 NC110 旋转数组:

这里牛客给出了数组长度我们直接用就可以了 .

LeetCode 189.轮转数组 :

189.轮转数组

分析 :

这个题怎么做呢?你是否想到可以逐次移动来实现? 理论上可以，但是实现的时候会发现要处理的情况非常多，比较难搞。这里介绍一种简单的方法: 两轮翻转

方法如下:
1.首先对整个数组实行翻转，例如[1,2,3,4,5,6,7] 我们先将其整体翻转成[7,6,5,4,3,2,1].

2.从 k 处分隔成左右两个部分，这里就是根据k将其分成两组 [7,6,5] 和[4,3,2,1].

3.最后将两个再次翻转就得到[5,6,7] 和[1,2,3,4]，最终结果就是[5,6,7,1,2,3,4].

解析 :

// LeetCode
class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        exchange(nums, 0 , nums.length -1);
        exchange(nums, 0 , k -1 );
        exchange(nums, k, nums.length -1);
    }
    public void exchange(int[] arr , int left , int right){
        while(left <= right){
            int temp =arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这期就到这里 , 下期见 !