第三天—双指针
283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
思路1：遍历数组元素，遇到非零的元素将它添加到数组的前端，之后将数组后面的清零。
public void moveZeroes(int[] nums) {
int index = 0;
for(int i=0;i<nums.length;i++){
if(nums[i] != 0){
nums[index] = nums[i];
index++;
}
}
for(int i = index; i < nums.length;i++){
nums[i] = 0;
}
}
思路2：利用两个指针，左边指针表示左边已经排好序，即不存在非零；右指针定位到非零元素，与左指针元素进行交换。
public void moveZeros(int[] nums){
int left = 0, right = 0, n = nums.length;
while(right < n){
if(num[right] != 0){
swap(nums,left,right);
left++;
}
right++;
}
}
public void swap(int[] nums,int i,int j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
167. 两数之和 II - 输入有序数组
给定一个已按照 升序排列 的整数数组numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers的下标 从1开始计数 ，所以答案数组应当满足1 <= answer[0] < answer[1] <= numbers.length。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
思路：根据已经排好序的前提下，利用头尾指针之和target进行判断，根据判断情况来移动头尾指针。
public int[] twoSum(int[] numbers, int target){
int left = 0, right = numbers.length - 1;
while(left < right){
int sum = numbers[left] + numbers[right];
if(sum == target) return new int[]{left + 1,right + 1};
else if(sum < target){
left++;
}else{
right--;
}
}
return new int[]{-1,-1};
}
参考：
同名公众号CodeJames
第四天—双指针
344.反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
思路：设置头尾指针指向字符数组的第一个和最后一个元素，交换两个指针所指向的元素，分别移动指针向中心靠拢。代码如下：
public void reverseString(char[] s){
int left = 0, right = s.length - 1;
while(left < right){
int tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
557. 反转字符串中的单词 III
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例：
输入："Let's take LeetCode contest"
输出："s'teL ekat edoCteeL tsetnoc"
**思路：**如示例所示，只是翻转了每个单词的顺序，而且每个单词用空格隔开；因此，可对整个字符串遍历，定位到每个单词的收尾，之后单词进行翻转。
public String reverseWord(String s){
StringBuilder res = new StringBuilder();
int n = s.length();
int i = 0;
while(i < n){
int start = i;
while(i < n && s.charAt(i) != ' '){
i++;
}
for(int t = i - 1;t >= start;t--){
res.append(s.charAt(t));
}
while(i < n && s.charAt(i) == ' '){
i++;
res.append(' ');
}
}
return res.toString();
}
参考：
欢迎分享，点个在读
同名公众号CodeJames
算法挑战第五天
876. 链表的中间结点
给定一个头结点为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.
**思路：**设置快慢指针，快指针走两步，慢指针走一步，当快指针遍历到尾部时，慢指针走到中点。
class Solution {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
**进阶：**你能尝试使用一趟扫描实现吗？
示例 1：
**思路：**由于单链表的特性，当删除结点时只能跳过后节点，因此，我们将slow结点往前移动一个节点；先让fast结点走n步，之后fast和slow同时走，直至到最后，此时slow结点的下一个节点指向倒数第n个节点。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = head;
ListNode slow = dummy;
while(n > 0){
fast = fast.next;
n--;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;
}
}
参考：
欢迎分享，点个在读
同名公众号CodeJames
关注交流
