给你一个整数数组 arr ，以及 a、b 、c 三个整数。请你统计其中好三元组的数量

如果三元组 (arr[i], arr[j], arr[k]) 满足下列全部条件，则认为它是一个 好三元组

0 <= i < j < k < arr.length

|arr[i] - arr[j]| <= a

|arr[j] - arr[k]| <= b

|arr[i] - arr[k]| <= c

其中 |x| 表示 x 的绝对值

返回 好三元组的数量 

1
2
3
4
5
6
7
输入：arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
输出：4
解释：一共有 4 个好三元组：[(3,0,1), (3,0,1), (3,1,1), (0,1,1)]

输入：arr = [1,1,2,2,3], a = 0, b = 0, c = 1
输出：0
解释：不存在满足所有条件的三元组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
	int res = 0;
	for (int i = 0; i < arr.size() - 2; i++)
	{
		for (int j = i + 1; j < arr.size() - 1; j++)
		{
			for (int k = j + 1; k < arr.size(); k++)
			{
                //使用abs()需引用cmath头文件
				if (abs(arr[i] - arr[j]) <= a && abs(arr[j] - arr[k]) <= b && abs(arr[i] - arr[k]) <= c)
				{
					res++;
				}
			}
		}
	}
	return res;
}

给你一个由 不同 整数组成的整数数组 arr 和一个整数 k

每回合游戏都在数组的前两个元素（即 arr[0] 和 arr[1] ）之间进行。比较 arr[0] 与 arr[1] 的大小，较大的整数将会取得这一回合的胜利并保留在位置 0 ，较小的整数移至数组的末尾。当一个整数赢得 k 个连续回合时，游戏结束，该整数就是比赛的 赢家

返回赢得比赛的整数

题目数据 保证 游戏存在赢家

1
2
3
4
5
6
7
8
9
输入：arr = [3,2,1], k = 10
输出：3
解释：3 将会在前 10 个回合中连续获胜
    
输入：arr = [1,9,8,2,3,7,6,4,5], k = 7
输出：9
    
输入：arr = [1,11,22,33,44,55,66,77,88,99], k = 1000000000
输出：99
1
2
3
4
5
6
//vector操作
a.erase(a.begin()+1,a.begin()+3); //包前不包后，删除第1、2个元素
a.insert(a.begin()+1,5); //在a的第1个元素（从第0个算起）的位置插入数值5
a.insert(a.begin()+1,3,5); //在a的第1个元素（从第0个算起）的位置插入3个数，其值都为5
a.back(); //返回a的最后一个元素
a.front(); //返回a的第一个元素
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
27
28
29
30
//按命题逻辑操作vector，遇到超长数组同时超大K值时会超时

int getWinner(vector<int>& arr, int k) {
	int num = 0;
	int res = arr[0];
	if (k > arr.size())
	{
		k = arr.size();
	}
	
	while (num < k)
	{
		if (arr[0] > arr[1])
		{
			num++;
			int temp = arr[1];
			arr.erase(arr.begin() + 1, arr.begin() + 2);
			arr.push_back(temp);
		}
		else
		{
			num = 1;
			int temp = arr[0];
			res = arr[1];
			arr.erase(arr.begin(), arr.begin() + 1);
			arr.push_back(temp);
		}
	}
	return res;
}
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
27
28
29
30
//trick，不用按题述方式操作vector，从前向后遍历即可
int getWinner(vector<int>& arr, int k) {
        int num = 0;
	    int res = arr[0];
	    if (k > arr.size())
	    {
	    	k = arr.size();
	    }
	    for(int i = 0; i < arr.size(); i++)
        {
            if(arr[i]>arr[i+1])
            {
                //直接修改arr[i+1]的值为arr[i]，这样继续和后面比较时仍是类似命题中的：上一组的较大者和新数值比较
                arr[i+1] = arr[i];
                num++;
            }
            else
            {
                //当遇到前者小于后者的情况，看此时的num值是否满足大于等于k的要求，符合即作为结果返回
                if(num >= k)
                {
                    return arr[i];
                }
                //不符合则设置num为1，不设置为0的原因是因为已经淘汰掉上一个值，已经赢了一回合
                res = arr[i+1];
                num = 1; 
            }
        }
	    return res;
    }

给你一个 n x n 的二进制网格 grid，每一次操作中，你可以选择网格的 相邻两行 进行交换

一个符合要求的网格需要满足主对角线以上的格子全部都是 0

请你返回使网格满足要求的最少操作次数，如果无法使网格符合要求，请你返回 -1

主对角线指的是从 (1, 1) 到 (n, n) 的这些格子

1
2
3
4
5
6
7
8
9
输入：grid = [[0,0,1],[1,1,0],[1,0,0]]
输出：3

输入：grid = [[0,1,1,0],[0,1,1,0],[0,1,1,0],[0,1,1,0]]
输出：-1
解释：所有行都是一样的，交换相邻行无法使网格符合要求

输入：grid = [[1,0,0],[1,1,0],[1,1,1]]
输出：0
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
//贪心
//从第一行开始，如果该行的后缀0满足条件，那么直接跳过进入下一行（因为需要的后缀0个数是从大到小的顺序（理解这一点非常重要），所以不必担心前面的会抢后面的，自己不够用的时候放心的去抢后面的，因为当前行的需求（优先级）比后面都高）
//如果该行后缀0个数不满足条件，那么就往下遍历找到最先（贪心，这是最小次数）满足条件的行，一行一行换上来，记录交换的次数
int minSwaps(vector<vector<int>>& grid) {
    vector<int> resV;
	int res = 0;
    int n = grid.size();
    //统计每行后缀0个数，存到resV中
	for (int i = 0; i < n; i++)
	{
		int num = 0;
		for (int j = 0; j < grid[i].size(); j++)
		{
			if (grid[i][j] == 0)
			{
			    num++;
			}
			else 
			{
			    num = 0;
			}
		}
		resV.push_back(num);
	}
    for(int i = 0; i < n - 1; i++)
    {
        //如果当前行的后缀0个数够用，直接往下遍历，不用担心抢了后面的，因为当前行的需求量比后面的都高
        if(resV[i] >= n - i - 1)
        continue;
        else
        {
            int j = i + 1;
            while(resV[j] < n - i - 1 )
            {
                j++;
                //找到最后都没有找到满足个数的后缀0，就直接退出
                if(j == n)
                    return -1;
            }
            //while之后到这里说明找到了一行满足当前行的后缀0的个数需求，把找到的行一行一行的往上换，换到当前行，每次swap的同时更新交换次数
            for(int m = j; m > i; m--)
            {
                swap(resV[m], resV[m - 1]);
                res++;
            }    
        }
    }
    return res;
}

5484. 找出第 N 个二进制字符串中的第 K 位

1
2
3
4
5
6
7
8
9
10
输入：n = 3, k = 1
输出："0"
解释：S3 为 "0111001"，其第 1 位为 "0" 

输入：n = 4, k = 11
输出："1"
解释：S4 为 "011100110110001"，其第 11 位为 "1"

输入：n = 1, k = 1
输出："0"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
private:
// invert处理    
char ch_not(char ch) {
        if(ch == '0') { return '1'; }
        else          { return '0'; }
    }
public:
    char findKthBit(int n, int k) {
        if(n == 1) { return '0'; }
        // 1左移n-1位，pow(2, n-1)
        int mid = (1<<(n-1));
        if(k == mid) { return '1'; }
        if(k < mid) { return findKthBit(n-1, k); }
        // k > mid的情况需要把k挪到对称位置：(1<<n) - k，并进行invert
        return ch_not(findKthBit(n-1, (1<<n) - k)); 
    }

5483. 整理字符串

1
2
3
4
5
6
7
8
9
10
11
12
输入：s = "leEeetcode"
输出："leetcode"
解释：无论你第一次选的是 i = 1 还是 i = 2，都会使 "leEeetcode" 缩减为 "leetcode"

输入：s = "abBAcC"
输出：""
解释：存在多种不同情况，但所有的情况都会导致相同的结果。例如：
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""

输入：s = "s"
输出："s"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string makeGood(string s) {
int i = 0;
while (i != s.length() - 1)
{
    for (i = 0; i < s.length() - 1; i++)
    {
        if (abs(s[i] - s[i + 1]) == 32)
        {
            s.erase(i, 2);
            i = 0;
            break;
        }
    }
    if(s.empty())
    {
        return "";
    }
}
return s;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//William Lin版
string makeGood(string s)
{
    bool ch = 1;
    while(ch)
    {
        ch = 0;
        string t = s;
        //size()返回类型是size_t, (unsigned) 和后面的int相减可能会溢出
        for(int i = 0; i < (int)s.size() - 1; i++)
        {
            if(s[i] + 32 == s[i + 1] || s[i + 1] + 32 == s[i])
            {
                //string的substr()使用，带首不带尾，单个参数默认从参数位置取到末尾
                t = s.substr(0, i) + s.substr(i + 2);
            	ch = 1;
                break;
            }
        }
        s = t;
    }
    return s;
}

5468. 第 k 个缺失的正整数

1
2
3
4
5
6
7
输入：arr = [2,3,4,7,11], k = 5
输出：9
解释：缺失的正整数包括 [1,5,6,8,9,10,12,13,...]

输入：arr = [1,2,3,4], k = 2
输出：6
解释：缺失的正整数包括 [5,6,7,...]
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
27
28
29
int findKthPositive(vector<int>& arr, int k) {
    int init = 0;
    int res = 0;
    int resNum = 0;
    res = arr[0] - init -1;
    if(res >= k)
    {
        return k;
    }
    int i = 1;
    while(i < arr.size() && res < k)
    {
        if(res + arr[i] - arr[i-1] - 1 < k)
        {
            res += arr[i] - arr[i-1] - 1;
        }
        else
        {
            resNum = arr[i-1] + (k - res); 
            res = k;
        }
        i++;
    }
    if(i == arr.size() && res < k)
    {
        resNum = arr.back() + (k - res);
    }
    return resNum;
}

5469. K 次操作转变字符串

1
2
3
4
5
6
7
8
9
10
11
输入：s = "input", t = "ouput", k = 9
输出：true
解释：第 6 次操作时，我们将 'i' 切换 6 次得到 'o' 。第 7 次操作时，我们将 'n' 切换 7 次得到 'u'

输入：s = "abc", t = "bcd", k = 10
输出：false
解释：我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 'a' 切换成 'b' ，但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母

输入：s = "aab", t = "bbb", k = 27
输出：true
解释：第 1 次操作时，我们将第一个 'a' 切换 1 次得到 'b' 。在第 27 次操作时，我们将第二个字母 'a' 切换 27 次得到 'b'
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//结果出现的位置有数组首之前，数组中间，数组末尾之后，分别处理
//创建一个数组存储每一位需要的操作数，将操作数按大小排好，一次遍历去对应k值看是否满足要求
//addNum记录某个操作数出现的次数，比如6在某一位上出现一次，某另一位的操作数也是6，那么操作数只能选择6 + 26，第三次出现时操作数为6 + 26 * 2

bool canConvertString(string s, string t, int k) {
        if (s.length() != t.length())
        {
            return false;
        }
        vector<int> resV;
        int temp = 0;
        vector<int> addNum(26, 0);
        for (int i = 0; i < s.length(); i++)
        {
            if (t[i] - s[i] >= 0)
            {
                temp = t[i] - s[i];
                addNum[temp] += 1;
            }
            else
            {
                temp = t[i] - 'a' + 'z' - s[i] + 1;
                addNum[temp] += 1;
            }
            //操作数为0是可以重复的，不需要加重叠次数*26
            if (temp != 0)
            {
                int pushNum = temp + 26 * (addNum[temp] - 1);
                resV.push_back(pushNum);
            }
            else
            {
                resV.push_back(temp);
            }
        }
        sort(resV.begin(), resV.end());
        while (!resV.empty() && resV.back() != 0)
        {
            if (k > resV.back())
            {
                k = resV.back() - 1;
                resV.pop_back();
            }
            else if (k == resV.back())
            {
                resV.pop_back();
                k--;
            }
            else
            {
                return false;
            }
        }
        return true;
    }

1546. 和为目标值的最大数目不重叠非空子数组数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：nums = [1,1,1,1,1], target = 2
输出：2
解释：总共有 2 个不重叠子数组（加粗数字表示） [1,1,1,1,1] ，它们的和为目标值 2 

输入：nums = [-1,3,5,1,4,2,-9], target = 6
输出：2
解释：总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的

输入：nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出：3

输入：nums = [0,0,0], target = 0
输出：3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 贪心
int maxNonOverlapping(vector<int>& nums, int target)
{
    set<int> s;
    //初始时累计值为0，保证在{-1, 3, 5, 1}中找target=6时能找去掉-1, 3，找到{5, 1}
    s.insert(0);
    int ps = 0, ans = 0;
    //一个替代遍历vector中每个值的方法（不关注下标时可使用）
    for(int a : nums)
    {
        //记录到每个当前值的累计值，其中的两个值相减就是两者之间的子数组中的各个值和
        ps += a;
        //注意理解ps - target的含义，是在当前位置根据target找前面是否有能截断而得到要的子数组的位置
        if(s.find(ps - target != s.end()))
        {
            ++ans;
            s.clear();
        }
        s.insert(ps);
    }
    return ans;
}