使用滑动窗口算法解决一些问题
在Leetcode上做到了一道题。
题目
给你两个长度相同的字符串,s
和 t
。
将 s
中的第 i
个字符变到 t
中的第 i
个字符需要 |s[i] - t[i]|
的开销(开销可能为 0),也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost
。在转化字符串时,总开销应当小于等于该预算,这也意味着字符串的转化可能是不完全的。
如果你可以将 s
的子字符串转化为它在 t
中对应的子字符串,则返回可以转化的最大长度。
如果 s
中没有子字符串可以转化成 t
中对应的子字符串,则返回 0。
解答
删去其中繁杂的题干,题意大概是从一个自然数串中,找出最长的和小于 maxCost
的串。此题可以用滑动窗口的思路解决。
滑动窗口
定义一个左指针 leftPtr
,一个右指针 rightPtr
,开始时将两个指针都置于最左边。右侧指针每次向右移动一格,判断左指针所处的位置是否符合题意。如果不符合,将其向右移动,直到符合题意为止。存储最大的符合题意的距离,即为答案。
简单说来,可以理解成右指针拉着左指针向右动,它们之间用一根线(maxCost
)相连。如果线足够长(rightPtr - leftPtr <= maxCost
),左指针就不会动,否则它也会跟着向右移。
代码
class Solution {
public int equalSubstring(String s, String t, int maxCost) {
int length = s.length();
int[] cost = new int[length];
for (int i = 0; i < length; i++) {
cost[i] = Math.abs(s.charAt(i) - t.charAt(i));
}
int rightPtr = 0, leftPtr = 0, max = 0, nowCost = 0;
while (rightPtr < length) {
nowCost += cost[rightPtr];
while (nowCost > maxCost) {
nowCost -= cost[leftPtr];
leftPtr++;
}
if (rightPtr - leftPtr + 1 > max) {
max = rightPtr - leftPtr + 1;
}
rightPtr++;
}
return max;
}
}
给定一个用字符数组表示的 CPU 需要执行的任务列表。其中包含使用大写的 A - Z 字母表示的26 种不同种类的任务。任务可以以任意顺序执行,并且每个任务都可以在 1 个单位时间内执行完。CPU 在任何一个单位时间内都可以执行一个任务,或者在待命状态。
然而,两个相同种类的任务之间必须有长度为 n 的冷却时间,因此至少有连续 n 个单位时间内 CPU 在执行不同的任务,或者在待命状态。
你需要计算完成所有任务所需要的最短时间。
示例 1:
输入: tasks = ["A","A","A","B","B","B"], n = 2 输出: 8 执行顺序: A -> B -> (待命) -> A -> B -> (待命) -> A -> B.
注:
- 任务的总个数为 [1, 10000]。
- n 的取值范围为 [0, 100]。
#include <vector> #include <algorithm> #include <iostream> using namespace std; struct numCD { int num; int cd = 0; }; bool cmp(numCD &n1, numCD &n2) { return n1.num > n2.num; } class letter { private: numCD num[26]; int n, time; public: letter(vector<char> &tasks, int n) { this->n = n + 1; time = tasks.size(); for (auto &i : num) { i.num = 0; } for (char c:tasks) { num[c - 'A'].num++; } sort(num, num + 26, cmp); } bool get() { if (time == 0) return false; sort(num, num + 26, cmp); for (int x = 0; x <= 25; x++) { if (num[x].num == 0) { break; } if (!num[x].cd) { num[x].num--; num[x].cd = n; time--; break; } } for (int x = 0; x < 25; x++) { if (num[x].cd) { num[x].cd--; } } return true; } }; class Solution { public: int leastInterval(vector<char> &tasks, int n) { letter l(tasks, n); int ans = 0; while (l.get()) { ans++; } return ans; } };
垃圾代码,别看了
假设你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 i ,都有一个胃口值 gi ,这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 j ,都有一个尺寸 sj 。如果 sj >= gi ,我们可以将这个饼干 j 分配给孩子 i ,这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子,并输出这个最大数值。
注意:
你可以假设胃口值为正。
一个小朋友最多只能拥有一块饼干。
示例 1:
输入: [1,2,3], [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干,3个孩子的胃口值分别是:1,2,3。 虽然你有两块小饼干,由于他们的尺寸都是1,你只能让胃口值是1的孩子满足。 所以你应该输出1。
示例 2:
输入: [1,2], [1,2,3] 输出: 2 解释: 你有两个孩子和三块小饼干,2个孩子的胃口值分别是1,2。 你拥有的饼干数量和尺寸都足以让所有孩子满足。 所以你应该输出2.
#include <vector> #include <algorithm> using namespace std; class Solution { public: int findContentChildren(vector<int> &g, vector<int> &s) { if (s.empty()) return 0; sort(g.begin(), g.end()); sort(s.begin(), s.end()); int seat = -1, num = 0; for (int child:g) { seat++; while (seat < s.size() && child > s[seat]) { seat++; } if (seat == s.size()) break; num++; } return num; } };
从胃口小的孩子开始分配,如果胃口小的孩子没饼干吃,那胃口大的左佑就只能饿着了。
给定一个已按照升序排列 的有序数组,找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值index1 和 index2,其中 index1 必须小于 index2。
说明:
- 返回的下标值(index1 和 index2)不是从零开始的。
- 你可以假设每个输入只对应唯一的答案,而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
class Solution { public: vector<int> twoSum(vector<int> &numbers, int target) { int i = 0, j = numbers.size() - 1; while (target != numbers[i] + numbers[j]) { if (target > numbers[i] + numbers[j]) { i++; } else { j--; } } vector<int> ans; ans.push_back(i + 1); ans.push_back(j + 1); return ans; } };
https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/
给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。
示例 1:
输入: [1,3,4,2,2]
输出: 2
示例 2:
输入: [3,1,3,4,2] 输出: 3
说明:
- 不能更改原数组(假设数组是只读的)。
- 只能使用额外的 O(1) 的空间。
- 时间复杂度小于 O(n2) 。
- 数组中只有一个重复的数字,但它可能不止重复出现一次。
class Solution { public: int findDuplicate(vector<int> &nums) { int i = 1, j = nums.size() - 1; while (i != j) { int m = (i + j) / 2, count = 0; for (int num:nums) { if (num <= m) count++; } if (count > m) { j = m; } else { i = m + 1; } } return i; } };
/* * 5,1,2,3,4,5,5,7,8,9,10,11 * 在1-11中寻找 * 重复的数是6或更小嘛? * 数一数发现,<=6的数有7个,说明重复的数<=6 * 那去1-6中寻找 * 重复的数<=3嘛? * <=3的数只有三个,没问题,重复的数比3大 * 在4-5中寻找 * 重复的数<=4嘛? * 比4小的数有四个,重复的数比4大 * 所以,重复的数是5 */