26.删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。
示例1: 给定数组nums = [1,1,2]，函数应该返回新的长度2,并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。
示例2: 给定nums = [0,0,1,1,1,2,2,3,3,4]，函数应该返回新的长度5,并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。你不需要考虑数组中超出新长度后面的元素。
解题思路：
- 当数组长度为0或1时，直接返回数组长度即可
- 定义一个数组下标变量，并初始化为1，用来表示无重复子数组长度
- 从第二个元素开始遍历数组，只要不与无重复子数组中最后一个元素相等，就将该元素添加到子数组尾部，子数组长度加1
- 返回子数组长度
代码如下：
public int removeDuplicates(int[] nums) {
if (nums.length < 2) {
return nums.length;
}
int index = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] != nums[index-1]) {
nums[index++] = nums[i];
}
}
return index;
}
791. 自定义字符串排序
字符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前。
返回任意一种符合条件的字符串T。
示例:
输入: S = "cba"，T = "abcd"
输出: "cbad"
解释: S中出现了字符 "a", "b", "c", 所以 "a", "b", "c" 的顺序应该是 "c", "b", "a".
由于 "d" 没有在S中出现, 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的输出。
注意:
S的最大长度为26，其中没有重复的字符。
T的最大长度为200。
S和T只包含小写字符。
解题思路：
- 遍历t中的每个字符，将其转化为对应的ASCII码，统计其出现次数，并按ASCII值作为下标，将次数存入int数组中
- 定义StringBuilder对象，用来追加字符
- 遍历s中的每个字符，取其ASCII值，作为下标定位到int数组中的某个元素，从而找到该字符在t中出现的次数
- 以字符出现的次数作为循环次数，每次将该字符追加到StringBuilder中，循环完后将次数清0
- 从字符a到字符z开始遍历，将t中出现的其他字符按步骤4的方式也追加到StringBuilder中
- 返回StringBuilder中的字符串
代码如下：
public String customSortString(String s, String t) {
int[] count = new int[26];
for (char c: t.toCharArray()) {
count[c - 'a']++;
}
StringBuilder ans = new StringBuilder();
for (char c: s.toCharArray()) {
for (int i = 0; i < count[c - 'a']; ++i) {
ans.append(c);
}
count[c - 'a'] = 0;
}
for (char c = 'a'; c <= 'z'; ++c) {
for (int i = 0; i < count[c - 'a']; ++i) {
ans.append(c);
}
}
return ans.toString();
}
1004. 最大连续1的个数 III
给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1] 数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= A.length <= 20000
0 <= K <= A.length
A[i] 为 0 或 1
解题思路：
- 当数组大小等于k时，直接返回k即可；
- 右指针每次右移一位，统计当前窗口中0的个数（+(a[right]^1)，表示：遇0则加1,遇1则加0）；
- 当0的个数大于k时，左指针需要左移，移除的元素若等于0，则0的个数减1；
- 当右指针移到数组最后一个元素后，结束循环，返回右指针-左指针，即为最大连续1的个数。
代码如下：
public int longestOnes(int[] a, int k) {
int length = a.length;
if (k == length) {
return k;
}
int left = 0;
int right = 0;
int zeros = 0;
while (right < length) {
zeros += a[right] ^ 1;
if (zeros > k && a[left++] == 0) {
--zeros;
}
++right;
}
return right - left;
}
