• 【代码随想录】双指针法刷题

    双指针法刷题

    移除元素

    题目：27. 移除元素 - 力扣（LeetCode）

    给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

    快慢指针：

    public int removeElement(int[] nums, int val) {
	int l = 0;
	for (int r = 0; r < nums.length; r++)
		if (nums[r] != val) nums[l++] = nums[r];
	return l;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    删除有序数组中的重复项

    题目：26. 删除有序数组中的重复项 - 力扣（LeetCode）

    给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

    快慢指针：

    public int removeDuplicates(int[] nums) {
	int l = 1;
	for (int r = 1; r < nums.length; r++) 
		if (nums[r] != nums[l - 1]) nums[l++] = nums[r];
	return l;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    移动零

    题目：283. 移动零 - 力扣（LeetCode）

    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

    快慢指针：

    class Solution {
    public void moveZeroes(int[] nums) {
        for (int l = 0, r = 0; r < nums.length; r++)
            if (nums[r] != 0) swap(nums, l++, r);
    }
    void swap(int[] nums, int i, int j) {
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    不使用交换的双指针：

    public void moveZeroes(int[] nums) {
	int l = 0;
	// 将非 0 元素按顺序放到前面
	for (int r = 0; r < nums.length; r++)
		if (nums[r] != 0) nums[l++] = nums[r];
	// 后面全部赋 0
	while (l < nums.length) nums[l++] = 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    比较含退格的字符串*

    题目：844. 比较含退格的字符串 - 力扣（LeetCode）

    给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

    输入：s = "ab#c", t = "ad#c"
输出：true
解释：s 和 t 都会变成 "ac"。

    • 1
    • 2
    • 3

    从前往后重构字符串：

    class Solution {
    public boolean backspaceCompare(String s, String t) {
        return getString(s).equals(getString(t));
    }

    public String getString(String s) {
        StringBuilder sb = new StringBuilder();
        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] != '#') sb.append(cs[i]);
            else if (sb.length() > 0) sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    从后往前重构字符串：

    class Solution {
    public boolean backspaceCompare(String s, String t) {
        return getString(s).equals(getString(t));
    }

    private String getString(String s) {
        StringBuilder sb = new StringBuilder();
        char[] cs = s.toCharArray();
        int size = 0; // '#' 数量
        for (int i = cs.length - 1; i >= 0; i--) {
            if (cs[i] == '#') size++; 
            else if (size == 0) sb.append(cs[i]); 
            else size--;
        }
        return sb.toString();
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    O(1) 空间复杂度做法：比较难。。。

    有序数组的平方

    题目：977. 有序数组的平方 - 力扣（LeetCode）

    给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

    输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

    • 1
    • 2
    • 3
    • 4
    public int[] sortedSquares(int[] nums) {
	int[] res = new int[nums.length];
	int l = 0, r = nums.length - 1;
	for (int i = nums.length - 1; i >= 0; i--) {
		if (nums[l] + nums[r] < 0) { // 左边绝对值大
			res[i] = nums[l] * nums[l++];
		} else { // 右边绝对值大
			res[i] = nums[r] * nums[r--];
		}
	}
	return res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    反转字符串

    题目：344. 反转字符串 - 力扣（LeetCode）

    编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

    使用位运算进行交换操作：

    public void reverseString(char[] s) {
	int size = s.length - 1;
	for (int i = 0; i < s.length / 2; i++) {
		int j = size - i;
		s[i] ^= s[j];
		s[j] ^= s[i];
		s[i] ^= s[j];
	}
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    一般可以将 反转字符数组 抽取成模板（经常会用到这个函数）

    class Solution {
    public void reverseString(char[] s) {
        reverse(s, 0, s.length - 1);
    }
	// 反转字符数组
    void reverse(char[] cs, int l, int r) {
        while (l < r) {
            cs[l] ^= cs[r];
            cs[r] ^= cs[l];
            cs[l++] ^= cs[r--];
        }
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13

    替换空格

    请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

    题目：剑指 Offer 05. 替换空格 - 力扣（LeetCode）

    public String replaceSpace(String s) {
	StringBuilder sb = new StringBuilder();
	for (char c : s.toCharArray()) {
		if (c != ' ') sb.append(c);
		else sb.append("%20");
	}
	return sb.toString();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    反转链表：递归 + 迭代 + 头插法

    题目：206. 反转链表 - 力扣（LeetCode）

    给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

    双指针：

    public ListNode reverseList(ListNode head) {
	ListNode cur = head, pre = null;
	while (cur != null) {
		ListNode tmp = cur.next;
		cur.next = pre;
		pre = cur;
		cur = tmp;
	}
	return pre;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    递归：

    public ListNode reverseList(ListNode head) {
	if (head == null || head.next == null) return head;
	ListNode node = reverseList(head.next);
	head.next.next = head;
	head.next = null;
	return node;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7

    头插法：空间 O(n)

    public ListNode reverseList(ListNode head) {
	ListNode res = null;
	for (ListNode x = head; x != null; x = x.next)
		res = new ListNode(x.val, res);
	return res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

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

    题目：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

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

    快慢指针：

    • 快指针先走 n 步，然后和慢指针同时开始走
    • 当快指针指向最后一个节点，此时慢指针指向的便是要删除的节点（的前一个节点）
    public ListNode removeNthFromEnd(ListNode head, int n) {
	if (head == null || head.next == null) return null;
	ListNode fast = head, slow = head;
	while (n-- > 0) fast = fast.next; // 快指针先走 n 步
	if (fast == null) return head.next; // 删除第一个节点
	while (fast.next != null) {
		fast = fast.next;
		slow = slow.next;
	}
	slow.next = slow.next.next;
	return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    快慢指针 + 虚拟头节点：

    一般使用虚拟头节点可以不用处理特殊情况

    public ListNode removeNthFromEnd(ListNode head, int n) {
	ListNode vn = new ListNode(0, head); // 虚拟头节点
	ListNode slow = vn, fast = vn;
	while (n-- > 0) fast = fast.next; // 快指针先走 n 步
	while (fast.next != null) {
		fast = fast.next;
		slow = slow.next;
	}
	slow.next = slow.next.next;
	return vn.next;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    递归：

    class Solution {
    int cur = 0;
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) return null;
        head.next = removeNthFromEnd(head.next, n);
        cur++;
        if (cur == n) return head.next;
        return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    环形链表：快慢指针

    题目：141. 环形链表 - 力扣（LeetCode）

    给你一个链表的头节点 head ，判断链表中是否有环。

    快慢指针：

    public boolean hasCycle(ListNode head) {
	ListNode slow = head, fast = head;
	while (fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
		if (slow == fast) return true;
	}
	return false;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    哈希：

    public boolean hasCycle(ListNode head) {
	Set<ListNode> set = new HashSet<>();
	while (head != null && !set.contains(head)) {
		set.add(head);
		head = head.next;
	}
	return head != null;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    环形链表 II**

    题目：142. 环形链表 II - 力扣（LeetCode）

    给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

    快慢指针 判断环 + 找环入口：

    public ListNode detectCycle(ListNode head) {
	ListNode slow = head, fast = head;
	// 快慢指针判断是否有环
	while (fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
		if (slow == fast) { // 有环, 找环的起始点
			fast = head; // 快指针从头开始
			while (fast != slow) {
				fast = fast.next;
				slow = slow.next;
			}
			return fast;
		}
	}
	return null;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    哈希：

    public ListNode detectCycle(ListNode head) {
	Set<ListNode> set = new HashSet<>();
	while (head != null && !set.contains(head)) {
		set.add(head);
		head = head.next;
	}
	return head;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    链表相交*

    题目：面试题 02.07. 链表相交 - 力扣（LeetCode）

    给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

    双指针：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	ListNode curA = headA, curB = headB;
	int lenA = 0, lenB = 0;
	// 求链表 A 的长度
	while (curA != null) { 
		lenA++; 
		curA = curA.next; 
	}
	// 求链表 B 的长度
	while (curB != null) { 
		lenB++; 
		curB = curB.next; 
	}
	curA = headA;
	curB = headB;
	// 链表 A 更长则让 A 多走, B 更长则让 B 多走，保证 A B 从同一位置开始比较
	if (lenA > lenB) for (int i = 0; i < lenA - lenB; i++) curA = curA.next;
	else for (int i = 0; i < lenB - lenA; i++) curB = curB.next;
	// 逐个比较 A 和 B 
	while (curA != null) {
		if (curA == curB) return curA;
		curA = curA.next;
		curB = curB.next;
	}
	return curA;
}

    • 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

    巧妙做法：

    • a 走完走 b，b 走完走 a，如果有相交点，必然会遇到
    • 如果没有相交点，最终会在相遇在 null
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	ListNode h1 = headA, h2 = headB;
	while (h1 != h2) {
		h1 = (h1 == null) ? headB : h1.next;
		h2 = (h2 == null) ? headA : h2.next;
	}
	return h1;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    哈希：

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
	Set<ListNode> set = new HashSet<>();
	ListNode p = headA;
	while (p != null) {
		set.add(p);
		p = p.next;
	}
	p = headB;
	while (p != null) {
		if (set.contains(p)) return p;
		p = p.next;
	}
	return null;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    三数之和**

    题目：15. 三数之和 - 力扣（LeetCode）

    给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

    **注意：**答案中不可以包含重复的三元组。

    思路：

    1. 排序数组
    2. 定义 i, j, k 三个指针。遍历 i，将问题转化成在 i 之后的数组中寻找 nums[j] = nums[k] = -nusm[i]
    3. 注意寻找同时要去重
    public List<List<Integer>> threeSum(int[] nums) {
	List<List<Integer>> res = new ArrayList<>();
	int n = nums.length;
	Arrays.sort(nums);
	// 剪枝: 最小的数 > 0 或 最大的数 < 0, 不可能和为 0
	if (nums[0] > 0 || nums[n - 1] < 0) return res;
	// 转化成两数之和: 寻找 nums[j] + nums[k] = -nums[i]
	for (int i = 0; i < n; i++) {
		 if (nums[i] > 0) break; // 不可能找到和为 0 的三元组
		 if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
		 // 两数之和寻找方法: 双指针, j 从前开始, k 从后开始
		 int j = i + 1, k = n - 1, target = -nums[i];
		 while (j < k) {
			if (nums[j] + nums[k] < target) j++;
			else if (nums[j] + nums[k] > target) k--;
			else {
				res.add(Arrays.asList(nums[i], nums[j], nums[k]));
				while (j < k && nums[j] == nums[j + 1]) j++; // 去重
				while (j < k && nums[k] == nums[k - 1]) k--; // 去重
				j++;
				k--;
			}
		 }
	}
	return res;
}

    • 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

    四数之和

    题目：18. 四数之和 - 力扣（LeetCode）

    给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

    • 0 <= a, b, c, d < n
    • a、b、c 和 d 互不相同
    • nums[a] + nums[b] + nums[c] + nums[d] == target

    你可以按 任意顺序 返回答案 。

    public List<List<Integer>> fourSum(int[] nums, int target) {
	List<List<Integer>> res = new ArrayList<>();
	int n = nums.length;
	if (n < 4) return res;
	Arrays.sort(nums);
	// 处理越界的情况: 正 + 正 = 负 
	if (nums[0] > 0 && target <= 0 || nums[n - 1] < 0 && target >= 0) return res;

	for (int i = 0; i < n - 3; i++) {
		if (i > 0 && nums[i] == nums[i - 1]) continue; // 去重
		// 剪枝: 当前情况的最小和 > target 或 最大和 < target
		if ((long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break;
		if ((long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1] < target) continue;
		for (int j = i + 1; j < n - 2; j++) {
			if (j > i + 1 && nums[j] == nums[j - 1]) continue; // 去重
			// 剪枝: 当前情况的最小和 > target 或 最大和 < target
			if ((long) nums[i] + nums[j] + nums[j + 1] + nums[j + 2] > target) break;
			if ((long) nums[i] + nums[j] + nums[n - 2] + nums[n - 1] < target) continue;
			// 两数之和
			int k = j + 1, l = n - 1;
			while (k < l) {
				int sum = nums[i] + nums[j] + nums[k] + nums[l];
				if (sum < target) k++;
				else if (sum > target) l--;
				else {
					res.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
					while (k < l && nums[k] == nums[k + 1]) k++; // 去重
					while (k < l && nums[l] == nums[l - 1]) l--; // 去重
					k++;
					l--;
				}
			}
		}
	}
	return res;
}

    • 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
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    分割线 -----

    无重复字符的最长子串*

    题目：3. 无重复字符的最长子串 - 力扣（LeetCode）

    给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

    双指针：

    public int lengthOfLongestSubstring(String s) {
	char[] cs = s.toCharArray();
	int[] map = new int[128]; // 字符 与 出现次数
	int res = 0;
	for (int l = 0, r = 0; r < cs.length; r++) {
		map[cs[r]]++; // 访问字符
		while (map[cs[r]] > 1) map[cs[l++]]--;
		res = Math.max(res, r - l + 1);
	}
	return res;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
  • 相关阅读:
    【炫丽】从0开始做一个WPF+Blazor对话小程序
    智慧社区解决方案
    磺酸修饰/单分散氢氧化钙/聚苯乙烯微球/载对苯二酚聚苯乙烯-二乙烯苯交联微球的性能
    2023年上半年上午易错题（软件设计师考试）
    为什么估计的参数具有渐进高斯性？M-estimateor的渐进高斯性推导
    GLIBC中的Symbol Versioning
    实验室LIMS管理系统能够解决那些企业难题
    前端用JavaScript实现桑基图（Sankey图）
    docker环境搭建gitlab服务
    wow-singleton文件说明
  • 原文地址：https://blog.csdn.net/weixin_43734095/article/details/126733734