26、题目:删除排序数组中的重复项
要求:给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
题解代码如下:
class Solution {
public int removeDuplicates(int[] nums) {
int left = 0;
for (int right = 1; right < nums.length; right++) {
if (nums[right] != nums[left]) {
left++;
nums[left] = nums[right];
}
}
return left + 1;
}
}
27、题目:移除元素
要求:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
题解代码如下:
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
}
28、题目:实现strStr()
要求:给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例:
输入: haystack = "hello", needle = "ll"
输出: 2
输入: haystack = "aaaaa", needle = "bba"
输出: -1
题解代码如下:
public class Solution {
public int strStr(String haystack, String needle) {
if (null == haystack || null == needle) {
return -1;
}
if (0 == needle.length()) {
return 0;
}
char[] has = haystack.toCharArray();
char[] nes = needle.toCharArray();
int hL = has.length;
int nL = nes.length;
int range = hL - nL;
int left = 0;
char ne = nes[0];
while (left <= range) {
while (left < range && has[left] != ne) {
left++;
}
int right = 0;
while (left < hL && right < nL && has[left] == nes[right]) {
left++;
right++;
}
if (right == nL) {
return left - nL;
}
left = left - right + 1;
}
return -1;
}
}