双指针算法练习

27. 移除元素

题目

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

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以**「引用」**方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {print(nums[i]);
} 

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

答案

class Solution {public int removeElement(int[] nums, int val) {int slow = 0;for(int i=0;i<nums.length;i++){if(nums[i]!=val){nums[slow++] = nums[i];}}return slow;}
}

344. 反转字符串

题目

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

不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

答案

class Solution {public void reverseString(char[] s) {int left = 0;int right = s.length-1;while(left<right){char temp = s[left];s[left] = s[right];s[right] = temp;left++;right--;}}
}

替换数字

给定一个字符串 s，它包含小写字母和数字字符，请编写一个函数，将字符串中的字母字符保持不变，而将每个数字字符替换为number。

例如，对于输入字符串 “a1b2c3”，函数应该将其转换为 “anumberbnumbercnumber”。

对于输入字符串 “a5b”，函数应该将其转换为 “anumberb”

输入：一个字符串 s,s 仅包含小写字母和数字字符。

输出：打印一个新的字符串，其中每个数字字符都被替换为了number

样例输入：a1b2c3

样例输出：anumberbnumbercnumber

数据范围：1 <= s.length < 10000。

答案

import java.util.Scannerclass Main{public static void main(String[] args){Scanner scanner = new Scanner(System.in);String s = scanner.nextLine();StringBuilder sb = new StringBuilder();for(int i=0;i<s.length();i++){if(Character.isDigit(s.charAt(i))){sb.append("number");}else{sb.append(s.charAt(i);}}System.out.println(sb.toString());}  
}

151. 反转字符串中的单词

题目

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

答案

class Solution {public String reverseWords(String s) {char[] temp = s.toCharArray();int len = temp.length;char[] res = new char[len+1];int index = 0;for(int i=len-1;i>=0;i--){while(i>=0 && temp[i]==' ') i--;int right = i;while(i>=0 && temp[i]!=' ') i--;int left = i + 1;while(left<=right){res[index++] = temp[left];if(left==right){res[index++] = ' ';}left++;}}return new String(res,0,index-1);}
}

206. 反转链表

题目

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

答案

class Solution {public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode curr = head;ListNode post = null;while(curr!=null){post = curr.next;curr.next = pre;pre = curr;curr = post;}return pre;}
}

19. 删除链表的倒数第 N 个结点

题目

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

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

答案

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0,head);ListNode slow = dummy;ListNode fast = dummy;for(int i=0;i<=n;i++){fast = fast.next;}while(fast!=null){fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}

面试题 02.07. 链表相交

题目

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

图示两个链表在节点 c1 开始相交**：**

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

答案

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {List<ListNode> list = new ArrayList();while(headA!=null){list.add(headA);headA = headA.next;}while(headB!=null){if(list.contains(headB)){return headB;}headB = headB.next;}return null;}
}

142. 环形链表 II

题目

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

答案

public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow = head;ListNode fast = head;while(fast!=null && fast.next!=null){fast = fast.next.next;slow = slow.next;if(slow==fast){ListNode node1 = head;ListNode node2 = slow;while(node1!=node2){node1 = node1.next;node2 = node2.next;}return node1;}}return null;}
}

15. 三数之和

题目

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

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

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要

答案

class Solution {public List<List<Integer>> threeSum(int[] nums) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList();for(int i=0;i<nums.length;i++){if(nums[i] > 0){return res;}if(i>0 && nums[i]==nums[i-1]) continue;//if + continue 去重int left = i + 1;int right = nums.length - 1;while(left<right){int sum = nums[i] + nums[left] + nums[right];if(sum>0){right--;}else if(sum<0){left++;}else{res.add(Arrays.asList(nums[i],nums[left],nums[right]));while(left<right && nums[left]==nums[left+1]) left++;//while 去重while(left<right && nums[right]==nums[right-1]) right--;left++;right--;}}}return res;}
}

18. 四数之和

题目

给你一个由 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

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

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

答案

class Solution {public List<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> res = new ArrayList();for(int i=0;i<nums.length;i++){if(nums[i]>0 && nums[i]>target){//注意 num[i]>0return res;}if(i>0 && nums[i]==nums[i-1]){continue;}for(int j=i+1;j<nums.length;j++){if(j>i+1 && nums[j]==nums[j-1]){continue;}int left = j + 1;int right = nums.length - 1;while(left<right){long sum = nums[i] + nums[j] + nums[left] + nums[right];if(sum>target){right--;}else if(sum<target){left++;}else{res.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--;}}}}return res;}
}