LeetCode 027 Remove Element 题解

题意

给一个字符串,要求就地(in-place)移除其中所有值为val的元素,返回新字符串长度。大于该长度的空间内的内容不影响题目判定。

分析

题目思路比较简单,用两个指针一个指向当前字符,一个指向最后一个字符。左边指针不断右移,右边指针不断左移。题目的细节比较多,比如要确保tail指针指向的值不为val。再就是不断地检查当前值,若为val则将其移向队尾。

C代码:

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
int fixTail(int *nums, int tail, int val)
{
while(nums[tail] == val)
{
tail--;
if(tail == -1) return -1;
}
return tail;
}
int removeElement(int* nums, int numsSize, int val) {
if(numsSize == 0) return 0;
int head = 0, tail = fixTail(nums, numsSize - 1, val);
if(tail == -1) return 0;
while(head <= tail)
{
if(nums[head] == val)
{
int tmp = nums[tail];
nums[tail] = nums[head];
nums[head] = tmp;
tail = fixTail(nums, tail, val);
}
head++;
}
return tail + 1;
}

fixTail函数用于处理tail指针,确保其指向的值不为val.另外需要判定一些长度为0的情况。


版权声明

The Bloom of Youth by KUANG Qi is licensed under a Creative Commons BY-NC-ND 4.0 International License.
况琪创作并维护的锦瑟华年博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证

本文首发于The Bloom of Youth | 锦瑟华年博客( http://kuangqi.me ),版权所有,侵权必究。

本文永久链接:http://kuangqi.me/programming/leetcode-remove-element/