移动零

题目

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

请注意 ,必须在不复制数组的情况下原地对数组进行操作。

  1. 示例 1:输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]
  2. 示例 2:输入: nums = [0] 输出: [0]
分析一: 我们可以把这道题视为排序的变形:0为大数,其他为小数。我们需要将0排在后面且保持非零数的顺序不变,所以应该选择稳定的排序算法。
我们使用插入排序 :从头遍历数组,遇到0即将其删去,然后插入到末尾。
1
2
3
4
5
6
7
8
9
class Solution {
public:
void moveZeroes(vector<int>& nums){
int flag=0;
while(flag<nums.size() && nums[flag]!=0) flag++;
for(int i=flag+1;i<nums.size();i++)
if(nums[i]!=0) swap(nums[flag++],nums[i]);
}
};
jugdge1

不对劲!!!这个算法肯定不行!寻找其他思路。

分析二: 我们刚才其实忽略了一点:对于非零数的排序必须是稳定的,而对于0的排序则可以不稳定。所以我们可以借鉴快速排序的思想(但有修改):
使用两个指针,第一个指针始终指向第一个0,第二个指针遍历数组。若第二个指针指向的数不是0,则交换两指针指向的值,然后第一个指针前移;否则第一个指针不移动。
1
2
3
4
5
6
7
8
9
class Solution {
public:
void moveZeroes(vector<int>& nums){
int flag=0;
while(flag<nums.size() && nums[flag]!=0) flag++;
for(int i=flag+1;i<nums.size();i++)
if(nums[i]!=0) swap(nums[flag++],nums[i]);
}
};
judge2

总结

回顾排序算法://todo

两数之和Ⅱ - 输入有序数组

题目

给定一个已按照非递减顺序排列 的整数数组 numbers ,请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ,所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。

你可以假设每个输入有且仅有唯一的答案 ,而且你不可以重复使用相同的元素。

  1. 示例 1:输入:numbers = [2,7,11,15], target = 9 输出:[1,2]
  2. 示例 2:输入:numbers = [2,3,4], target = 6 输出:[1,3]
  3. 示例 3:输入:numbers = [-1,0], target = -1 输出:[1,2]
思路: 根据之前的经验,我们需要寻找一个中间值,将待查找数的分为两份。 1. 第一个想法是找到target/2 的位置,它将数组分为两份:左边的小,右边的大,然后左右两边分别一个for循环。然而其时间复杂度依旧为$O(n)$​​,在某组奇葩的测试样例上运行超时。​ 2. 第二个想法(看了答案之后)是使用双指针向中间靠拢 。如果两个指针指向的值之和小于target,则左指针右移;如果两个指针指向的值之和大于target,则右指针左移。该做法把数组两端值之和作为中间值
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int i=0,j=nums.size()-1;
while(i<j){
if(nums[i]+nums[j]==target) return {i+1,j+1};
else if(nums[i]+nums[j]<target) i++;
else j--;
}
return {0};
}
};
judge

总结

有序数组使用双指针指向其首尾 也是很常见的模型。

特点之一是左指针右移和增大;右指针左移和减小

反转字符串

题目

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

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

  1. 示例 1:输入:s = [“h”,”e”,”l”,”l”,”o”] 输出:[“o”,”l”,”l”,”e”,”h”]
  2. 示例 2:输入:s = [“H”,”a”,”n”,”n”,”a”,”h”] 输出:[“h”,”a”,”n”,”n”,”a”,”H”]
1
2
3
4
5
6
7
class Solution {
public:
void reverseString(vector<char>& s) {
for(int i=0,j=s.size()-1;i<j;i++,j--)
swap(s[i],s[j]);
}
};

当然也可以直接用STL中的reverse()函数

1
2
3
4
5
6
class Solution {
public:
void reverseString(vector<char>& s) {
reverse(s.begin(),s.end());
}
};
judeg

总结

和上面的题一样,双指针向中间靠拢直至二者相遇。

反转字符串中的单词Ⅲ

题目

给定一个字符串 s ,你需要反转字符串中每个单词的字符顺序,同时仍保留空格和单词的初始顺序。

  1. 示例 1:输入:s = “Let’s take LeetCode contest” 输出:”s’teL ekat edoCteeL tsetnoc”
  2. 示例 2:输入: s = “God Ding” 输出:”doG gniD”

思路:一个一个单词地交换就行了。把直接传参改为引用传参空间开销会小一些。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
string reverseWords(string& s) {
int length = s.length();
int i = 0;
while (i < length) {
int start = i;
while (i < length && s[i] != ' ') {
i++;
}
int left = start, right = i - 1;
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
while (i < length && s[i] == ' ') i++;
}
return s;
}
};
judge

链表的中间结点

题目

给定一个头结点为 head 的非空单链表,返回链表的中间结点

如果有两个中间结点,则返回第二个中间结点。

  1. 示例 1:输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5])
  2. 示例 2:输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6])
方法一: 先遍历一遍链表,得到结点个数;第二次指针移动到链表中间即可。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
ListNode* middleNode(ListNode* head) {
int n=0;
for(ListNode* p=head;p!=nullptr;p=p->next) n++;
n=n/2+1;
ListNode* p=head;
for(int i=1;i<n;i++) p=p->next;
return p;
}
};
judge

方法二:快慢指针 。慢指针每移动一步,快指针就移动两步。这样快指针到尾的时候慢指针正好再链表中间。
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode* slow=head,*fast=head;
while(fast!=nullptr && fast->next!=nullptr){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
};
judge

总结

掌握这道题快慢指针 的方法。

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

题目

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

  1. 示例二:输入:head = [1,2,3,4,5], n = 2 输出:[1,2,3,5]
  2. 示例 2:输入:head = [1], n = 1 输出:[]
  3. 示例 3:输入:head = [1,2], n = 1 输出:[1]
思路一: 先遍历一遍链表,得到链表结点个数。第二次遍历的时候再删除倒数第N个结点。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
int i=0;
for(ListNode* p=head;p!=nullptr;p=p->next) i++;
ListNode* p=head;
if(n==i) return p->next;
for(int j=1;j<i-n;j++) p=p->next;
if(p->next!=nullptr) p->next=p->next->next;
return head;
}
};
judge

思路二: 使用快慢指针。一个指针再前,另一个指针在其后N个结点的位置处。两个指针一起移动,直至前指针到达表尾。没想到……被前面快慢指针的思维固化了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0, head);
ListNode* first = head;
ListNode* second = dummy;
for (int i = 0; i < n; ++i) {
first = first->next;
}
while (first) {
first = first->next;
second = second->next;
}
second->next = second->next->next;
ListNode* ans = dummy->next;
delete dummy;
return ans;
}
};
总结

快慢指针

两个指针一起移动:

  1. 快指针比慢指针每次移动的步数更长;
  2. 快指针在前,慢指针在后。