使用滑动窗口算法解决一些问题

在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. 任务的总个数为 [1, 10000]。
2. 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;
    }
};

垃圾代码，别看了

https://leetcode-cn.com/problems/task-scheduler/

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值  g_i ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 s_j  。如果  s_j >= g_i   ，我们可以将这个饼干 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;
    }
};

从胃口小的孩子开始分配，如果胃口小的孩子没饼干吃，那胃口大的左佑就只能饿着了。

https://leetcode-cn.com/problems/assign-cookies/

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值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

说明：

1. 不能更改原数组（假设数组是只读的）。
2. 只能使用额外的 O(1) 的空间。
3. 时间复杂度小于 O(n²) 。
4. 数组中只有一个重复的数字，但它可能不止重复出现一次。

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
 */