1.逆序字符串
题目描述
给定一个字符串，要求原地把它逆序。
1
2
| 输入：hello world
输出：dlrow olleh
|
解题思路
用两个指针（下标）p、q 分别指向首尾，交换两个位置的字符，然后 p 往后走、q 往前走，直到 p >= q 相遇为止。
char 数组用 strlen 算出长度，注意 q = arr + size - 1 指向最后一个有效字符（不是 '\0'）。
代码
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
| #define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stdlib.h>
#include <string.h>
using namespace std;
void Reverse(char arr[], int size)
{
char* p = arr;
char* q = arr + size - 1;
while (p < q)
{
char ch = *p;
*p = *q;
*q = ch;
p++;
q--;
}
}
int main()
{
char arr[] = "hello world";
Reverse(arr, strlen(arr));
cout << arr << endl;
}
|
二、调整数组使偶数在左、奇数在右
题目描述
给定一个整型数组，要求把偶数调整到数组左边，奇数调整到右边，不要求保持原来的相对顺序。
1
2
| 输入：3 8 1 6 5 2
输出：2 6 8 1 5 3（顺序任意，只要偶数都在左半边）
|
解题思路
同样是首尾双指针，但判断条件和方向要对应上：
p 从左边出发，它的任务是找奇数（偶数就跳过，说明这个位置放对了）q 从右边出发，它的任务是找偶数（奇数就跳过）- 两个条件都不满足时，说明
p 指着奇数、q 指着偶数，交换即可
代码
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
| #define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
void AdjustArr(int arr[], int size)
{
int* p = arr;
int* q = arr + size - 1;
while (p < q)
{
if ((*p) % 2 == 0)
{
p++;
continue;
}
if ((*q) % 2 == 1)
{
q--;
continue;
}
int t = *p;
*p = *q;
*q = t;
p++;
q--;
}
}
int main()
{
int arr[10] = {0};
srand(time(0));
for (int i = 0; i < 10; i++)
{
arr[i] = rand() % 100;
}
for (int i = 0; i < 10; i++)
{
cout << arr[i] << " ";
}
cout << endl;
AdjustArr(arr, 10);
for (int i = 0; i < 10; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}
|
三、力扣27.移除元素
题目描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
- 更改
nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
- 返回
k。
用户评测
评测机将使用以下代码测试您的解决方案：
1
2
3
4
5
6
7
8
9
10
11
12
| int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。
int k = removeElement(nums, val); // 调用你的实现
assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
|
如果所有的断言都通过，你的解决方案将会 通过。
输入输出样例
示例 1：
1
2
3
4
| 输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
|
示例 2：
1
2
3
4
5
| 输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
|
说明/提示
提示：
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100
解题思路
为什么返回数值是整数，但输出的答案是数组？
因为输入数组是以引用的方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
原地说明空间复杂度O(1)，不能使用原数组以外的内存空间。
根据示例中输出的数组样式，我们需要把非val的元素调整到数组左边来，并且不需要管右边的val元素，所以不需要交换，只需要赋值
和上面两题类似，使用双指针思想，同时考虑到可能传入空数组，用两个下标代替指针
右边的q找非val，左边的p找val，找到了则赋值，没找到则跳过
最后返回p即可
代码
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| #define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <stdlib.h>
#include <vector>
using namespace std;
class Solution {
public:
int removeElement(vector<int>& nums, int val)
{
int p = 0;
int q = (int)nums.size() - 1;
while (p <= q)
{
if (nums[q] == val)
{
q--;
continue;
}
if (nums[p] != val)
{
p++;
continue;
}
nums[p] = nums[q];
p++;
q--;
}
return p;
}
};
int main()
{
int n;
cout << "输入数组个数n:" << endl;
cin >> n;
vector<int> nums(n);
cout << "输入数组元素:" << endl;
for (int i = 0; i < n; i++)
cin >> nums[i];
Solution sol;
int val;
cout << "输入要排除的元素val" << endl;
cin >> val;
int k = sol.removeElement(nums, val);
cout << k << " nums = [";
for (int i = 0; i < k; i++)
cout << nums[i] << ",";
}
|