力扣OJ（1001-1400）_力扣题库

1025. 除数博弈

博弈

1026. 节点与其祖先之间的最大差值

剑指 Offer II 054. 所有大于等于节点的值之和

1033. 移动石子直到连续

三枚石子放置在数轴上，位置分别为 a，b，c。

每一回合，你可以从两端之一拿起一枚石子（位置最大或最小），并将其放入两端之间的任一空闲位置。形式上，假设这三枚石子当前分别位于位置 x, y, z 且 x < y < z。那么就可以从位置 x 或者是位置 z 拿起一枚石子，并将该石子移动到某一整数位置 k 处，其中 x < k < z 且 k != y。

当你无法进行任何移动时，即，这些石子的位置连续时，游戏结束。

要使游戏结束，你可以执行的最小和最大移动次数分别是多少？以长度为 2 的数组形式返回答案：answer = [minimum_moves, maximum_moves]

示例 1：

输入：a = 1, b = 2, c = 5
输出：[1, 2]
解释：将石子从 5 移动到 4 再移动到 3，或者我们可以直接将石子移动到 3。
示例 2：

输入：a = 4, b = 3, c = 2
输出：[0, 0]
解释：我们无法进行任何移动。

提示：

1 <= a <= 100
1 <= b <= 100
1 <= c <= 100
a != b, b != c, c != a

思路：找规律即可


class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        int x[3]={a,b,c};
        sort(x,x+3);
        vector<int>ans(2);
        ans[0]=(x[1]-x[0]>1)+(x[2]-x[1]>1)-(x[1]-x[0]==2&&x[2]-x[1]>=2||x[1]-x[0]>=2&&x[2]-x[1]==2),ans[1]=x[2]-x[0]-2;
        return ans;
    }
};

1035. 不相交的线

题目：

我们在两条独立的水平线上按给定的顺序写下 A 和 B 中的整数。

现在，我们可以绘制一些连接两个数字 A[i] 和 B[j] 的直线，只要 A[i] == B[j]，且我们绘制的直线不与任何其他连线（非水平线）相交。

以这种方法绘制线条，并返回我们可以绘制的最大连线数。

示例 1：

输入：A = [1,4,2], B = [1,2,4]
输出：2
解释：
我们可以画出两条不交叉的线，如上图所示。
我们无法画出第三条不相交的直线，因为从 A[1]=4 到 B[2]=4 的直线将与从 A[2]=2 到 B[1]=2 的直线相交。
示例 2：

输入：A = [2,5,1,2,5], B = [10,5,2,1,5,2]
输出：3
示例 3：

输入：A = [1,3,7,1,7,5], B = [1,9,2,5,1]
输出：2

提示：

1 <= A.length <= 500
1 <= B.length <= 500
1 <= A[i], B[i] <= 2000

代码：


class Solution {
public:    
    int ans[505][505];
    Solution()
    {
        memset(ans,-1,sizeof(ans));
    }
    int maxUncrossedLines(vector<int>& A, vector<int>& B) {
        return maxUncrossedLines(A,B,A.size()-1,B.size()-1);
    }
    int maxUncrossedLines(vector<int>& A, vector<int>& B,int ka,int kb) {
        if(ka<0||kb<0)return 0;
        if(ans[ka][kb]>=0)return ans[ka][kb];
        if(A[ka]==B[kb])return ans[ka][kb]=maxUncrossedLines(A,B,ka-1,kb-1)+1;
        return ans[ka][kb]=max(maxUncrossedLines(A,B,ka,kb-1),maxUncrossedLines(A,B,ka-1,kb));
    }
};

1038. 从二叉搜索树到更大和树

1039. 多边形三角剖分的最低得分

rust

1040. 移动石子直到连续 II

双指针双指针、多指针_nameofcsdn的博客-CSDN博客_双指针

1042. 不邻接植花

1044. 最长重复子串

给你一个字符串 s ，考虑其所有重复子串：即 s 的（连续）子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回任意一个可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

示例 1：

输入：s = "banana"
输出："ana"
示例 2：

输入：s = "abcd"
输出：""

提示：

2 <= s.length <= 3 * 104
s 由小写英文字母组成


class Solution{
public:
	string longestDupSubstring(string s) {
		return GetlongestDupSubstring(s);
	}
};

1049. 最后一块石头的重量 II

背包

1046. 最后一块石头的重量

rust

1052. 爱生气的书店老板

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些时候，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3
输出：16
解释：书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

示例 2：

输入：customers = [1], grumpy = [0], minutes = 1
输出：1

提示：

n == customers.length == grumpy.length
1 <= minutes <= n <= 2 * 104
0 <= customers[i] <= 1000
grumpy[i] == 0 or 1


class Solution {
public:
    int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int minutes) {
        int s=0,s2=0,s3;
        for(int i=0;i<customers.size();i++){
            if(grumpy[i]==0)s+=customers[i],customers[i]=0;
            if(i<minutes)s2+=customers[i];
        }
        s3=s2;
        for(int i=minutes;i<customers.size();i++){
            s2+=customers[i]-customers[i-minutes];
            s3=max(s3,s2);
        }
        return s+s3;
    }
};

1054. 距离相等的条形码

贪心

1055. 形成字符串的最短路径

对于任何字符串，我们可以通过删除其中一些字符（也可能不删除）来构造该字符串的 子序列 。(例如，“ace” 是 “abcde” 的子序列，而 “aec” 不是)。

给定源字符串 source 和目标字符串 target，返回 源字符串 source 中能通过串联形成目标字符串 target 的 子序列 的最小数量 。如果无法通过串联源字符串中的子序列来构造目标字符串，则返回 -1。

示例 1：

输入：source = "abc", target = "abcbc"
输出：2
解释：目标字符串 "abcbc" 可以由 "abc" 和 "bc" 形成，它们都是源字符串 "abc" 的子序列。

示例 2：

输入：source = "abc", target = "acdbc"
输出：-1
解释：由于目标字符串中包含字符 "d"，所以无法由源字符串的子序列构建目标字符串。

示例 3：

输入：source = "xyz", target = "xzyxz"
输出：3
解释：目标字符串可以按如下方式构建： "xz" + "y" + "xz"。

提示：

1 <= source.length, target.length <= 1000
source 和 target 仅包含英文小写字母。


class Solution {
public:
    int subLen(string source, string target)
    {
        int j=0;
        for(int i=0;i<source.length() && j<target.length();i++){
            if(source[i]==target[j])j++;
        }
        return j;
    }
    int shortestWay(string source, string target) {
        int ans=0;
        while(target.length())
        {
            int len=subLen(source,target);
            if(len==0)return -1;
            ans++;
            target=target.substr(len,target.length()-len);
        }
        return ans;
    }
};

1056. 易混淆数

给定一个数字 N，当它满足以下条件的时候返回 true：

原数字旋转 180° 以后可以得到新的数字。

如 0, 1, 6, 8, 9 旋转 180° 以后，得到了新的数字 0, 1, 9, 8, 6 。

2, 3, 4, 5, 7 旋转 180° 后，得到的不是数字。

易混淆数 (confusing number) 在旋转180°以后，可以得到和原来不同的数，且新数字的每一位都是有效的。

示例 1：

输入：6
输出：true
解释：
把 6 旋转 180° 以后得到 9，9 是有效数字且 9!=6 。
示例 2：

输入：89
输出：true
解释:
把 89 旋转 180° 以后得到 68，86 是有效数字且 86!=89 。
示例 3：

输入：11
输出：false
解释：
把 11 旋转 180° 以后得到 11，11 是有效数字但是值保持不变，所以 11 不是易混淆数字。
示例 4：

输入：25
输出：false
解释：
把 25 旋转 180° 以后得到的不是数字。

提示：

0 <= N <= 10^9
可以忽略掉旋转后得到的前导零，例如，如果我们旋转后得到 0008 那么该数字就是 8 。


class Solution {
public:
	int change(int i) {
		if (i == 6 || i == 9)return 15 - i;
		return i;
	}
	bool confusingNumber(int n) {
		char* str = NULL;
		int len = IntToStr(n, 10, str);
		for (int i = 0; i < len; i++)if (str[i] >= '2' && str[i] <= '7' && str[i] != '6')return false;
		for (int i = 0, j = len - 1; i <= j; i++, j--)if (change(str[i] - '0') != str[j] - '0')return true;
		return false;
	}
};

1060. 有序数组中的缺失元素

1062. 最长重复子串

给定字符串 S，找出最长重复子串的长度。如果不存在重复子串就返回 0。

示例 1：

输入："abcd"
输出：0
解释：没有重复子串。
示例 2：

输入："abbaba"
输出：2
解释：最长的重复子串为 "ab" 和 "ba"，每个出现 2 次。
示例 3：

输入："aabcaabdaab"
输出：3
解释：最长的重复子串为 "aab"，出现 3 次。
示例 4：

输入："aaaaa"
输出：4
解释：最长的重复子串为 "aaaa"，出现 2 次。

提示：

字符串 S 仅包含从 'a' 到 'z' 的小写英文字母。
1 <= S.length <= 1500


class Solution {
public:
	int longestRepeatingSubstring(string s) {
		int ans = 0;
		for (int d = 1; d < s.length(); d++) {
			int a = 0;
			for (int i = s.length() - 1; i - d >= 0; i--) {
				if (s[i] == s[i - d])a++;
				else a = 0;
				ans = max(ans, a);
			}
		}
		return ans;
	}
};

1063. 有效子数组的数目

待更新

1064. 不动点

给定已经按升序排列、由不同整数组成的数组 arr，返回满足 arr[i] == i 的最小索引 i。如果不存在这样的 i，返回 -1。

示例 1：

输入：arr = [-10,-5,0,3,7]
输出：3
解释：对于给定的数组，arr[0] = -10，arr[1] = -5，arr[2] = 0，arr[3] = 3，因此输出为 3 。
示例 2：

输入：arr = [0,2,5,8,17]
输出：0
解释：arr[0] = 0，因此输出为 0 。
示例 3：

输入：arr = [-10,-5,3,4,7,9]
输出：-1
解释：不存在这样的 i 满足 arr[i] = i，因此输出为 -1 。

提示：

1 <= arr.length < 104
-109 <= arr[i] <= 109

进阶：时间复杂度为 O(n) 的解决方案很直观也很简单。你可以设计更优的解决方案吗？


class Solution:public Bsearch<int> {
public:
	int fixedPoint(vector<int>& arr) {
		for (int i = 0; i < arr.size(); i++)arr[i] -= i;
		this->arr = arr;
		auto x= find(0,arr.size()-1);
		return x >= arr.size() || arr[x]!=0 ? -1 :x;
	}
private:
	virtual bool isOk(int x) const //若isOk(x)且!isOk(y)则必有y<x
	{
		return arr[x] >= 0;
	}
	vector<int> arr;
};

1065. 字符串的索引对

1085. 最小元素各数位之和

1086. 前五科的均分

给你一个不同学生的分数列表 items，其中 items[i] = [IDi, scorei] 表示 IDi 的学生的一科分数，你需要计算每个学生 最高的五科 成绩的 平均分。

返回答案 result 以数对数组形式给出，其中 result[j] = [IDj, topFiveAveragej] 表示 IDj 的学生和他 最高的五科 成绩的 平均分。result 需要按 IDj 递增的 顺序排列 。

学生 最高的五科 成绩的 平均分 的计算方法是将最高的五科分数相加，然后用 整数除法 除以 5 。

示例 1：

输入：items = [[1,91],[1,92],[2,93],[2,97],[1,60],[2,77],[1,65],[1,87],[1,100],[2,100],[2,76]]
输出：[[1,87],[2,88]]
解释：
ID = 1 的学生分数为 91、92、60、65、87 和 100 。前五科的平均分 (100 + 92 + 91 + 87 + 65) / 5 = 87
ID = 2 的学生分数为 93、97、77、100 和 76 。前五科的平均分 (100 + 97 + 93 + 77 + 76) / 5 = 88.6，但是由于使用整数除法，结果转换为 88

示例 2：

输入：items = [[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100],[1,100],[7,100]]
输出：[[1,100],[7,100]]

提示：

1 <= items.length <= 1000
items[i].length == 2
1 <= IDi <= 1000
0 <= scorei <= 100
对于每个 IDi，至少存在五个分数


class Solution {
public:
    vector<vector<int>> highFive(vector<vector<int>>& items) {
        map<int, multiset<int>>m;
        for (auto v : items)m[v[0]].insert(-v[1]);
        vector<vector<int>>ans;
        for (auto& mi : m) {
            int flag = 5, s = 0;
            for (auto x : mi.second) {
                s -= x;
                if (--flag == 0)break;
            }
            ans.push_back(vector<int>{mi.first, s/5});
        }
        return ans;
    }
};

1090. 受标签影响的最大值

题目：

我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。

我们从这些项中选出一个子集 S，这样一来：

|S| <= num_wanted
对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。
返回子集 S 的最大可能的和。

示例 1：

输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1
输出：9
解释：选出的子集是第一项，第三项和第五项。
示例 2：

输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2
输出：12
解释：选出的子集是第一项，第二项和第三项。
示例 3：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1
输出：16
解释：选出的子集是第一项和第四项。
示例 4：

输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2
输出：24
解释：选出的子集是第一项，第二项和第四项。

提示：

1 <= values.length == labels.length <= 20000
0 <= values[i], labels[i] <= 20000
1 <= num_wanted, use_limit <= values.length

代码：


 
struct node
{
    int va,lab;
};
 
class cmp
{
public:
    bool operator()(node a,node b)
    {
        if(a.lab==b.lab)return a.va<b.va;
        return a.lab<b.lab;
    }
};
 
class Solution {
public:
    int largestValsFromLabels(vector<int>& values, vector<int>& labels, int num_wanted, int use_limit) {
        priority_queue<node,vector<node>,cmp>pq;
        node tmp;
        for(int i=0;i<values.size();i++)        
        {            
            tmp.va=values[i],tmp.lab=labels[i];
            pq.push(tmp);
        }
        int tmplab=-1,k=0;
        vector<int>v;
        while(pq.size())
        {
            tmp=pq.top();
            pq.pop();
            if(tmplab==tmp.lab)k++;
            else k=1,tmplab=tmp.lab;
            if(k<=use_limit)v.insert(v.end(),tmp.va);
        }
        sort(v.begin(),v.end(),greater<int>());
        int ans=0;
        for(int i=0;i<num_wanted && i<v.size();i++)
        {
            ans+=v[i];
        }
        return ans;
    }
};

1093. 大样本统计

1094. 拼车

假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车只能向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：

必须接送的乘客数量；
乘客的上车地点；
以及乘客的下车地点。
这些给出的地点位置是从你的初始出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false
示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true
示例 3：

输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true
示例 4：

输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true

提示：

你可以假设乘客会自觉遵守 “先下后上” 的良好素质
trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000

思路：拆分成上车操作和下车操作，然后所有操作排个序再遍历一遍即可。


struct Node
{
	int t;
	int n;
};
 
bool cmp(Node a, Node b)
{
	if (a.t == b.t)return a.n < b.n;
	return a.t < b.t;
}
 
class Solution {
public:
	bool carPooling(vector<vector<int>>& trips, int capacity) {
		vector<Node> vnodes;
		for (auto& tr : trips) {
			vnodes.push_back({ tr[1],tr[0] });
			vnodes.push_back({ tr[2],-tr[0] });
		}
		sort(vnodes.begin(), vnodes.end(), cmp);
		int s = 0;
		for (auto& vi : vnodes) {
			s += vi.n;
			if (s > capacity)return false;
		}
		return true;
	}
};

1099. 小于 K 的两数之和

给你一个整数数组 nums 和整数 k ，返回最大和 sum ，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < k 。如果没有满足此等式的 i,j 存在，则返回 -1 。

示例 1：

输入：nums = [34,23,1,24,75,33,54,8], k = 60
输出：58
解释：
34 和 24 相加得到 58，58 小于 60，满足题意。
示例 2：

输入：nums = [10,20,30], k = 15
输出：-1
解释：
我们无法找到和小于 15 的两个元素。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 1000
1 <= k <= 2000


class Solution {
public:
	int twoSumLessThanK(vector<int>& nums, int k) {
		sort(nums.begin(), nums.end());
		int ans = INT_MIN;
		for (int i = 0,j = nums.size()-1; i < j;) {
			if (nums[i] + nums[j] >= k)j--;
			else ans = max(ans, nums[i++] + nums[j]);
		}
		return ans == INT_MIN ? -1 : ans;
	}
};

1100. 长度为 K 的无重复字符子串

给你一个字符串 S，找出所有长度为 K 且不含重复字符的子串，请你返回全部满足要求的子串的数目。

示例 1：

输入：S = "havefunonleetcode", K = 5
输出：6
解释：
这里有 6 个满足题意的子串，分别是：'havef','avefu','vefun','efuno','etcod','tcode'。

示例 2：

输入：S = "home", K = 5
输出：0
解释：
注意：K 可能会大于 S 的长度。在这种情况下，就无法找到任何长度为 K 的子串。

提示：

1 <= S.length <= 10^4
S 中的所有字符均为小写英文字母
1 <= K <= 10^4


class Solution {
public:
    int numKLenSubstrNoRepeats(string s, int k) {
        map<char,int>m;
        int num=0;
        int ans=0;
        for(int i=0;i<s.length();i++){
            auto c=s[i];
            if(m[c]==1)num--;
            m[c]++;
            if(m[c]==1)num++;
            if(i>=k){
                c=s[i-k];
                if(m[c]==1)num--;
                m[c]--;
                if(m[c]==1)num++;
            }
            if(num==k)ans++;
            cout<<num<<endl;
        }
        return ans;
    }
};

1102. 得分最高的路径

1103. 分糖果 II

排排坐，分糖果。

我们买了一些糖果 candies，打算把它们分给排好队的 n = num_people 个小朋友。

给第一个小朋友 1 颗糖果，第二个小朋友 2 颗，依此类推，直到给最后一个小朋友 n 颗糖果。

然后，我们再回到队伍的起点，给第一个小朋友 n + 1 颗糖果，第二个小朋友 n + 2 颗，依此类推，直到给最后一个小朋友 2 * n 颗糖果。

重复上述过程（每次都比上一次多给出一颗糖果，当到达队伍终点后再次从队伍起点开始），直到我们分完所有的糖果。注意，就算我们手中的剩下糖果数不够（不比前一次发出的糖果多），这些糖果也会全部发给当前的小朋友。

返回一个长度为 num_people、元素之和为 candies 的数组，以表示糖果的最终分发情况（即 ans[i] 表示第 i 个小朋友分到的糖果数）。

示例 1：

输入：candies = 7, num_people = 4
输出：[1,2,3,1]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0,0]。
第三次，ans[2] += 3，数组变为 [1,2,3,0]。
第四次，ans[3] += 1（因为此时只剩下 1 颗糖果），最终数组变为 [1,2,3,1]。

示例 2：

输入：candies = 10, num_people = 3
输出：[5,2,3]
解释：
第一次，ans[0] += 1，数组变为 [1,0,0]。
第二次，ans[1] += 2，数组变为 [1,2,0]。
第三次，ans[2] += 3，数组变为 [1,2,3]。
第四次，ans[0] += 4，最终数组变为 [5,2,3]。

提示：

1 <= candies <= 10^9
1 <= num_people <= 1000


class Solution {
public:
	vector<int> distributeCandies(int candies, int num_people) {
		vector<int>v(num_people, 0);
		for (int i = 0;; i++) {
			v[i%v.size()] += min(i + 1, candies);
			candies -= i + 1;
			if (candies <= 0)break;
		}
		return v;
	}
};

1110. 删点成林

1118. 一月有多少天

指定年份 year 和月份 month，返回该月天数。

示例 1：

输入：year = 1992, month = 7
输出：31
示例 2：

输入：year = 2000, month = 2
输出：29
示例 3：

输入：year = 1900, month = 2
输出：28

提示：

1583 <= year <= 2100
1 <= month <= 12


class Solution {
public:
	int numberOfDays(int year, int m) {
		if (m == 2) {
			if (year % 4)return 28;
			if (year % 100)return 29;
			if (year % 400)return 28;
			return 29;
		}
		if (m == 4 || m == 6 || m == 9 || m == 11)return 30;
		return 31;
	}
};

1119. 删去字符串中的元音

1120. 子树的最大平均值

二叉树

1121. 将数组分成几个递增序列

给你一个非递减的正整数数组 nums 和整数 K，判断该数组是否可以被分成一个或几个长度至少为 K 的不相交的递增子序列。

示例 1：

输入：nums = [1,2,2,3,3,4,4], K = 3
输出：true
解释：
该数组可以分成两个子序列 [1,2,3,4] 和 [2,3,4]，每个子序列的长度都至少是 3。
示例 2：

输入：nums = [5,6,6,7,8], K = 3
输出：false
解释：
没有办法根据条件来划分数组。

提示：

1 <= nums.length <= 10^5
1 <= K <= nums.length
1 <= nums[i] <= 10^5


class Solution {
public:
	bool canDivideIntoSubsequences(vector<int>& nums, int k) {
		int m = 0;
		map<int, int>mn;
		for (int i = 0; i < nums.size(); i++)mn[nums[i]]++, m = max(m, mn[nums[i]]);
		return m * k <= nums.size();
	}
};

1123. 最深叶节点的最近公共祖先

二叉树

1124. 表现良好的最长时间段

单调栈

1133. 最大唯一数

1134. 阿姆斯特朗数

给你一个整数 n ，让你来判定他是否是阿姆斯特朗数，是则返回 true，不是则返回 false。

假设存在一个 k 位数 n ，其每一位上的数字的 k 次幂的总和也是 n ，那么这个数是阿姆斯特朗数。

示例 1：

输入：n = 153
输出：true
示例：
153 是一个 3 位数，且 153 = 13 + 53 + 33。
示例 2：

输入：n = 123
输出：false
解释：123 是一个 3 位数，且 123 != 13 + 23 + 33 = 36。

提示：

1 <= n <= 108


class Solution {
public:
	bool isArmstrong(int n) {
		int m = n;
		int len = NumInRadix(n, 10);
		int s = 0;
		while (n)s += int(pow(n % 10, len) + 0.5), n /= 10;
		cout << s;
		return s == m;
	}
};

1135. 最低成本联通所有城市

最小生成树

1137. 第 N 个泰波那契数

泰波那契序列 Tn 定义如下：

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

示例 1：

输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

示例 2：

输入：n = 25
输出：1389537

提示：

0 <= n <= 37
答案保证是一个 32 位整数，即 answer <= 2^31 - 1。


class Solution {
public:
	int tribonacci(int n) {
		int ans[40] = { 0,1,1 };
		for (int i = 3; i <= n; i++)ans[i] = ans[i - 1] + ans[i - 2] + ans[i - 3];
		return ans[n];
	}
};

1138. 字母板上的路径

题目：

我们从一块字母板上的位置 (0, 0) 出发，该坐标对应的字符为 board[0][0]。

在本题里，字母板为board = ["abcde", "fghij", "klmno", "pqrst", "uvwxy", "z"]，如下所示。

我们可以按下面的指令规则行动：

如果方格存在，'U' 意味着将我们的位置上移一行；
如果方格存在，'D' 意味着将我们的位置下移一行；
如果方格存在，'L' 意味着将我们的位置左移一列；
如果方格存在，'R' 意味着将我们的位置右移一列；
'!' 会把在我们当前位置 (r, c) 的字符 board[r][c] 添加到答案中。
（注意，字母板上只存在有字母的位置。）

返回指令序列，用最小的行动次数让答案和目标 target 相同。你可以返回任何达成目标的路径。

示例 1：

输入：target = "leet"
输出："DDR!UURRR!!DDD!"
示例 2：

输入：target = "code"
输出："RR!DDRR!UUL!R!"

提示：

1 <= target.length <= 100
target 仅含有小写英文字母。

思路：

每个格子到每个格子的最短路径可以直接表示出来，然后全部拼接起来即可。

如果是5*5的二维表格，上下左右四个while循环任意顺序都行。

本题多了一个z，为了方便快速表示最短路径，只需要控制一下四个循环的先后顺序即可。

代码：


class Solution {
public:
    string alphabetBoardPath(int a,int b)
    {
        string ans="";
        int dx=b/5-a/5,dy=b%5-a%5;
        while(dy<0)dy++,ans+='L';
        while(dx>0)dx--,ans+='D';
        while(dx<0)dx++,ans+='U';
        while(dy>0)dy--,ans+='R';
        return ans+'!';
    }
    string alphabetBoardPath(string target) {
        char a='a';
        string ans="";
        for(int i=0;i<target.length();i++)
        {
            ans+=alphabetBoardPath(a-'a',target[i]-'a'),a=target[i];
        }
        return ans;
    }
};

1140. 石子游戏 II

公开游戏

1143. 最长公共子序列

1146. 快照数组

二分法

1150. 检查一个数是否在数组中占绝大多数

1151. 最少交换次数来组合所有的 1

1153. 字符串转化

给出两个长度相同的字符串 str1 和 str2。请你帮忙判断字符串 str1 能不能在零次或多次转化后变成字符串 str2。

每一次转化时，你可以将 str1 中出现的所有相同字母变成其他任何小写英文字母。

只有在字符串 str1 能够通过上述方式顺利转化为字符串 str2 时才能返回 true 。

示例 1：

输入：str1 = "aabcc", str2 = "ccdee"
输出：true
解释：将 'c' 变成 'e'，然后把 'b' 变成 'd'，接着再把 'a' 变成 'c'。注意，转化的顺序也很重要。

示例 2：

输入：str1 = "leetcode", str2 = "codeleet"
输出：false
解释：我们没有办法能够把 str1 转化为 str2。

提示：

1 <= str1.length == str2.length <= 104
str1 和 str2 中都只会出现小写英文字母


class Solution {
public:
    bool canConvert(string str1, string str2) {
        if(str1.length()!=str2.length())return false;
        if(str1==str2)return true;
        map<char,char>m;
        map<char,int>m2;
        for(int i=0;i<str1.length();i++){
            if(m[str1[i]]==m['?'])m[str1[i]]=str2[i];
            else if(m[str1[i]]!=str2[i])return false;
            m2[str2[i]]++;
        }
        for(char c='a';c<='z';c++){
            if(m2[c]==0)return true;
        }
        return false;
    }
};

1154. 一年中的第几天

历法

1155. 掷骰子等于目标和的方法数

高维DP

1161. 最大层内元素和

二叉树

1162. 地图分析

1168. 水资源分配优化

最小生成树

1171. 从链表中删去总和值为零的连续节点

题目：

给你一个链表的头节点 head，请你编写代码，反复删去链表中由总和值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。
示例 2：

输入：head = [1,2,3,-3,4]
输出：[1,2,4]
示例 3：

输入：head = [1,2,3,-3,-2]
输出：[1]

提示：

给你的链表中可能有 1 到 1000 个节点。
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

思路：

存前缀和，搜索相同的前缀和，对应的一段就是和为0的一段。

代码：


class Solution {
public:
	ListNode* removeZeroSumSublists(ListNode* head) {
		int s[1005] = { 0 }, k = 0; //s是链表前缀和，k是链表长度
		ListNode*p = head, *list[1005];
		while (p)
		{
			list[++k] = p, s[k] = p->val + s[k - 1], p = p->next;
		}
		for (int i = 0; i < k; i++)
		{
			for (int j = k; j > i; j--)
			{
				if (s[i] != s[j])continue;
				if (i == 0)head = list[j]->next;
				else list[i]->next = list[j]->next;
				i = j;
			}
		}
		return head;
	}
};

1175. 质数排列

全排列

1177. 构建回文串检测

异或

1180. 统计只含单一字母的子串

1181. 前后拼接

给你一个「短语」列表 phrases，请你帮忙按规则生成拼接后的「新短语」列表。

「短语」（phrase）是仅由小写英文字母和空格组成的字符串。「短语」的开头和结尾都不会出现空格，「短语」中的空格不会连续出现。

「前后拼接」（Before and After puzzles）是合并两个「短语」形成「新短语」的方法。我们规定拼接时，第一个短语的最后一个单词 和 第二个短语的第一个单词 必须相同。

返回每两个「短语」 phrases[i] 和 phrases[j]（i != j）进行「前后拼接」得到的「新短语」。

注意，两个「短语」拼接时的顺序也很重要，我们需要同时考虑这两个「短语」。另外，同一个「短语」可以多次参与拼接，但「新短语」不能再参与拼接。

请你按字典序排列并返回「新短语」列表，列表中的字符串应该是 不重复的 。

示例 1：

输入：phrases = ["writing code","code rocks"]
输出：["writing code rocks"]

示例 2：

输入：phrases = ["mission statement",
                "a quick bite to eat",
                "a chip off the old block",
                "chocolate bar",
                "mission impossible",
                "a man on a mission",
                "block party",
                "eat my words",
                "bar of soap"]
输出：["a chip off the old block party",
      "a man on a mission impossible",
      "a man on a mission statement",
      "a quick bite to eat my words",
      "chocolate bar of soap"]

示例 3：

输入：phrases = ["a","b","a"]
输出：["a"]

提示：

1 <= phrases.length <= 100
1 <= phrases[i].length <= 100


class Solution {
public:
    vector<string> beforeAndAfterPuzzles(vector<string>& phrases) {
        map<string,vector<int>>sfirst;
        vector<vector<string>>v(phrases.size());
        for(int i=0;i<phrases.size();i++){
            v[i]=StringSplit(phrases[i],' ');
            sfirst[v[i][0]].push_back(i);
        }
        map<string,int>m;
        vector<string> ans;
        for(int i=0;i<phrases.size();i++){
            vector<int>ids=sfirst[*v[i].rbegin()];
            string s1=phrases[i].substr(0, phrases[i].length()-(*v[i].rbegin()).length());
            for(auto id:ids){
                if(id==i)continue;
                m[s1+phrases[id]]++;
            }
        }
        for(auto p:m)ans.push_back(p.first);
        return ans;
    }
};

1183. 矩阵中 1 的最大数量

现在有一个尺寸为 width * height 的矩阵 M，矩阵中的每个单元格的值不是 0 就是 1。

而且矩阵 M 中每个大小为 sideLength * sideLength 的 正方形 子阵中，1 的数量不得超过 maxOnes。

请你设计一个算法，计算矩阵中最多可以有多少个 1。

示例 1：

输入：width = 3, height = 3, sideLength = 2, maxOnes = 1
输出：4
解释：
题目要求：在一个 3*3 的矩阵中，每一个 2*2 的子阵中的 1 的数目不超过 1 个。
最好的解决方案中，矩阵 M 里最多可以有 4 个 1，如下所示：
[1,0,1]
[0,0,0]
[1,0,1]

示例 2：

输入：width = 3, height = 3, sideLength = 2, maxOnes = 2
输出：6
解释：
[1,0,1]
[1,0,1]
[1,0,1]

提示：

1 <= width, height <= 100
1 <= sideLength <= width, height
0 <= maxOnes <= sideLength * sideLength


class Solution {
public:
    int maximumNumberOfOnes(int width, int height, int sideLength, int maxOnes) {
        if(width<height)width^=height^=width^=height;
        int k1=width/sideLength,k2=height/sideLength;
        vector<int>v;
        for(int i=0;i<(width%sideLength)*(height%sideLength);i++)
            v.push_back((k1+1)*(k2+1));
        for(int i=0;i<(sideLength-width%sideLength)*(height%sideLength);i++)
            v.push_back(k1*(k2+1));
        for(int i=0;i<(width%sideLength)*(sideLength-height%sideLength);i++)
            v.push_back((k1+1)*k2);
        for(int i=0;i<(sideLength-width%sideLength)*(sideLength-height%sideLength);i++)
            v.push_back(k1*k2);
        int ans=0;
        for(int i=0;i<maxOnes;i++)ans+=v[i];
        return ans;
    }
};

1185. 一周中的第几天

历法

1186. 删除一次得到子数组最大和

1192. 查找集群内的关键连接

图的连通分量

1196. 最多可以买到的苹果数量

1197. 进击的骑士

1198. 找出所有行中最小公共元素

双指针

1201. 丑数 III

欧几里得

1207. 独一无二的出现次数

给你一个整数数组 arr，请你帮忙统计数组中每个数的出现次数。

如果每个数的出现次数都是独一无二的，就返回 true；否则返回 false。

示例 1：

输入：arr = [1,2,2,1,1,3]
输出：true
解释：在该数组中，1 出现了 3 次，2 出现了 2 次，3 只出现了 1 次。没有两个数的出现次数相同。
示例 2：

输入：arr = [1,2]
输出：false
示例 3：

输入：arr = [-3,0,1,-3,1,1,1,-3,10,0]
输出：true

提示：

1 <= arr.length <= 1000
-1000 <= arr[i] <= 1000


class Solution {
public:
	bool uniqueOccurrences(vector<int>& arr) {
		map<int, int>m;
		for (auto& vi : arr)m[vi]++;
		map<int, int>m2;
		for (auto& mi : m) {
			if (m2[mi.second])return false;
			m2[mi.second] = 1;
		}
		return true;
	}
};

1213. 三个有序数组的交集

1214. 查找两棵二叉搜索树之和

二叉搜索树

1215. 步进数

数位DP

1218. 最长定差子序列

1222. 可以攻击国王的皇后

题目：

在一个 8x8 的棋盘上，放置着若干「黑皇后」和一个「白国王」。

「黑皇后」在棋盘上的位置分布用整数坐标数组 queens 表示，「白国王」的坐标用数组 king 表示。

「黑皇后」的行棋规定是：横、直、斜都可以走，步数不受限制，但是，不能越子行棋。

请你返回可以直接攻击到「白国王」的所有「黑皇后」的坐标（任意顺序）。

示例 1：

输入：queens = [[0,1],[1,0],[4,0],[0,4],[3,3],[2,4]], king = [0,0]
输出：[[0,1],[1,0],[3,3]]
解释：
[0,1] 的皇后可以攻击到国王，因为他们在同一行上。
[1,0] 的皇后可以攻击到国王，因为他们在同一列上。
[3,3] 的皇后可以攻击到国王，因为他们在同一条对角线上。
[0,4] 的皇后无法攻击到国王，因为她被位于 [0,1] 的皇后挡住了。
[4,0] 的皇后无法攻击到国王，因为她被位于 [1,0] 的皇后挡住了。
[2,4] 的皇后无法攻击到国王，因为她和国王不在同一行/列/对角线上。
示例 2：

输入：queens = [[0,0],[1,1],[2,2],[3,4],[3,5],[4,4],[4,5]], king = [3,3]
输出：[[2,2],[3,4],[4,4]]
示例 3：

输入：queens = [[5,6],[7,7],[2,1],[0,7],[1,6],[5,1],[3,7],[0,3],[4,0],[1,2],[6,3],[5,0],[0,4],[2,2],[1,1],[6,4],[5,4],[0,0],[2,6],[4,5],[5,2],[1,4],[7,5],[2,3],[0,5],[4,2],[1,0],[2,7],[0,1],[4,6],[6,1],[0,6],[4,3],[1,7]], king = [3,4]
输出：[[2,3],[1,4],[1,6],[3,7],[4,3],[5,4],[4,5]]

提示：

1 <= queens.length <= 63
queens[0].length == 2
0 <= queens[i][j] < 8
king.length == 2
0 <= king[0], king[1] < 8
一个棋盘格上最多只能放置一枚棋子。

代码：


int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 }; //flat技术
int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };//（dx,dy）是8个方向向量
 
class Solution {
public:
    int board[8][8];
    vector<vector<int>> queensAttacktheKing(vector<vector<int>>& queens, vector<int>& king) {
        memset(board,0,sizeof(board));
        for(int i=0;i<queens.size();i++)board[queens[i][0]][queens[i][1]]=1;
        vector<vector<int>>ans;
        for(int i=0;i<8;i++)
        {
            int x=king[0],y=king[1];
            while(x>=0 && x<8 && y>=0 && y<8)
            {
                if(board[x][y])
                {
                    vector<int>tmp;
                    tmp.insert(tmp.end(),x);
                    tmp.insert(tmp.end(),y);
                    ans.insert(ans.end(),tmp);
                    break;
                }
                x+=dx[i],y+=dy[i];
            }
        }
        return ans;
    }
};

1223. 掷骰子模拟（DP的空间压缩，解空间平移）

高维DP

1227. 飞机座位分配概率

题目：

有 n 位乘客即将登机，飞机正好有 n 个座位。第一位乘客的票丢了，他随便选了一个座位坐下。

剩下的乘客将会：

如果他们自己的座位还空着，就坐到自己的座位上，

当他们自己的座位被占用时，随机选择其他座位
第 n 位乘客坐在自己的座位上的概率是多少？

示例 1：

输入：n = 1
输出：1.00000
解释：第一个人只会坐在自己的位置上。
示例 2：

输入: n = 2
输出: 0.50000
解释：在第一个人选好座位坐下后，第二个人坐在自己的座位上的概率是 0.5。

提示：

1 <= n <= 10^5

编程之美中的金刚坐飞机问题。

代码：


class Solution {
public:
	double nthPersonGetsNthSeat(int n) {
		if (n == 1)return 1;
		return 0.5;
	}
};

1228. 等差数列中缺失的数字

1230. 抛掷硬币

有一些不规则的硬币。在这些硬币中，prob[i] 表示第 i 枚硬币正面朝上的概率。

请对每一枚硬币抛掷一次，然后返回正面朝上的硬币数等于 target 的概率。

示例 1：

输入：prob = [0.4], target = 1
输出：0.40000

示例 2：

输入：prob = [0.5,0.5,0.5,0.5,0.5], target = 0
输出：0.03125

提示：

1 <= prob.length <= 1000
0 <= prob[i] <= 1
0 <= target <= prob.length
如果答案与标准答案的误差在 10^-5 内，则被视为正确答案。


class Solution {
public:
	double probabilityOfHeads(vector<double>& prob, int target) {
		auto ans = vector<double>{ 1 };
		for (auto p : prob) {
			auto ans2 = ans;
			Fcheng(ans, p);
			ans.insert(ans.begin(), 0);
			Fcheng(ans2, 1-p);
			ans = VecAdd(ans, ans2);
		}
		return ans[target];
	}
};

1235. 规划兼职工作

1243. 数组变换

首先，给你一个初始数组 arr。然后，每天你都要根据前一天的数组生成一个新的数组。

第 i 天所生成的数组，是由你对第 i-1 天的数组进行如下操作所得的：

假如一个元素小于它的左右邻居，那么该元素自增 1。
假如一个元素大于它的左右邻居，那么该元素自减 1。
首、尾元素永不改变。
过些时日，你会发现数组将会不再发生变化，请返回最终所得到的数组。

示例 1：

输入：[6,2,3,4]
输出：[6,3,3,4]
解释：
第一天，数组从 [6,2,3,4] 变为 [6,3,3,4]。
无法再对该数组进行更多操作。
示例 2：

输入：[1,6,3,4,3,5]
输出：[1,4,4,4,4,5]
解释：
第一天，数组从 [1,6,3,4,3,5] 变为 [1,5,4,3,4,5]。
第二天，数组从 [1,5,4,3,4,5] 变为 [1,4,4,4,4,5]。
无法再对该数组进行更多操作。

提示：

1 <= arr.length <= 100
1 <= arr[i] <= 100


class Solution {
public:
	vector<int> transformArray(vector<int>& arr) {
		bool flag = true;
		while (flag) {
			flag = false;
			vector<int> v = arr;
			for (int i = 1; i < arr.size() - 1; i++) {
				if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])v[i]--, flag = true;
				if (arr[i] < arr[i - 1] && arr[i] < arr[i + 1])v[i]++, flag = true;
			}
			arr = v;
		}
		return arr;
	}
};

1245. 树的直径

1248. 统计「优美子数组」

给你一个整数数组 nums 和一个整数 k。

如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length


class Solution {
public:
    int numberOfSubarrays(vector<int>& nums, int k) {
        vector<int>ji;
        ji.push_back(-1);
        for(int i=0;i<nums.size();i++)if(nums[i]%2)ji.push_back(i);
        ji.push_back(nums.size());
        int ans=0;
        for(int i=1;i+k<ji.size();i++)
        {
            ans+=(ji[i]-ji[i-1])*(ji[i+k]-ji[i+k-1]);
        }
        return ans;
    }
};

1250. 检查「好数组」

裴蜀定理

1254. 统计封闭岛屿的数目

1256. 加密数字

给你一个非负整数 num ，返回它的「加密字符串」。

加密的过程是把一个整数用某个未知函数进行转化，你需要从下表推测出该转化函数：

示例 1：

输入：num = 23
输出："1000"

示例 2：

输入：num = 107
输出："101100"

提示：

0 <= num <= 10^9


class Solution {
public:
	string encode(int num) {
		if (num == 0)return "";
		int m = 1, k = 0;
		while (m * 2 <= num + 1)m *= 2, k++;
		char* str;
		int len = IntToStr(num - m + 1, 2, str);
		string ans;
		for (int i = 0; i < k - len; i++)ans += '0';
		for (int i = 0; i < len; i++)ans += str[i];
		return ans;
	}
};

1259. 不相交的握手

1261. 在受污染的二叉树中查找元素

1262. 可被三整除的最大和

给你一个整数数组 nums，请你找出并返回能被三整除的元素最大和。

示例 1：

输入：nums = [3,6,5,1,8]
输出：18
解释：选出数字 3, 6, 1 和 8，它们的和是 18（可被 3 整除的最大和）。
示例 2：

输入：nums = [4]
输出：0
解释：4 不能被 3 整除，所以无法选出数字，返回 0。
示例 3：

输入：nums = [1,2,3,4,4]
输出：12
解释：选出数字 1, 3, 4 以及 4，它们的和是 12（可被 3 整除的最大和）。

提示：

1 <= nums.length <= 4 * 10^4
1 <= nums[i] <= 10^4


class Solution {
public:
	int maxSumDivThree(vector<int>& nums) {
		vector<int>v1, v2;
		int s = 0;
		for (auto x : nums) {
			s += x;
			if (x % 3 == 1)v1.push_back(x);
			if (x % 3 == 2)v2.push_back(x);
		}
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
		int ans = 0;
		int num = s % 3;
		if (v1.size() >= num) {
			ans = s;
			for (int i = 0; i < num; i++)ans -= v1[i];
		}
		num = s*2 % 3;
		if (v2.size() >= num) {
			for (int i = 0; i < num; i++)s -= v2[i];
			ans = max(ans, s);
		}
		return ans;
	}
};

1267. 统计参与通信的服务器

题目：

这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。

如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

示例 1：

输入：grid = [[1,0],[0,1]]
输出：0
解释：没有一台服务器能与其他服务器进行通信。
示例 2：

输入：grid = [[1,0],[1,1]]
输出：3
解释：所有这些服务器都至少可以与一台别的服务器进行通信。
示例 3：

输入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
输出：4
解释：第一行的两台服务器互相通信，第三列的两台服务器互相通信，但右下角的服务器无法与其他服务器通信。

提示：

m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

代码：


class Solution {
public:
	int countServers(vector<vector<int>>& grid) {
		if (grid.empty() || grid[0].empty())return 0;
		int m = grid.size();
		int n = grid[0].size();
		int ans1[300] = { 0 };
		int ans2[300] = { 0 };
		for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)
		{
			ans1[i] += grid[i][j], ans2[j] += grid[i][j];
		}
		int ans = 0;
		for (int i = 0; i < m; i++)for (int j = 0; j < n; j++)
		{
			ans += (grid[i][j] && (ans1[i]>1 || ans2[j] > 1));
		}
		return ans;
	}
};

1271. 十六进制魔术数字

你有一个十进制数字，请按照此规则将它变成「十六进制魔术数字」：首先将它变成字母大写的十六进制字符串，然后将所有的数字 0 变成字母 O ，将数字 1 变成字母 I 。

如果一个数字在转换后只包含 {"A", "B", "C", "D", "E", "F", "I", "O"} ，那么我们就认为这个转换是有效的。

给你一个字符串 num ，它表示一个十进制数 N，如果它的十六进制魔术数字转换是有效的，请返回转换后的结果，否则返回 "ERROR" 。

示例 1：

输入：num = "257"
输出："IOI"
解释：257 的十六进制表示是 101 。

示例 2：

输入：num = "3"
输出："ERROR"

提示：

1 <= N <= 10^12
给定字符串不会有前导 0 。
结果中的所有字母都应该是大写字母。


class Solution {
public:
	string toHexspeak(string num) {
		long long n = StrToInt(num.data(), 10);
		char*str;
		int len = IntToStr(n, 16, str);
		string ans;
		for (int i = 0; i < len; i++)
			if (str[i] >= '2' && str[i] <= '9')return "ERROR";
			else ans += str[i];
		return ans;
	}
};

1272. 删除区间

实数集合可以表示为若干不相交区间的并集，其中每个区间的形式为 [a, b)（左闭右开），表示满足 a <= x < b 的所有实数 x 的集合。如果某个区间 [a, b) 中包含实数 x ，则称实数 x 在集合中。

给你一个 有序的 不相交区间列表 intervals 。intervals 表示一个实数集合，其中每一项 intervals[i] = [ai, bi] 都表示一个区间 [ai, bi) 。再给你一个要删除的区间 toBeRemoved 。

返回 一组实数，该实数表示intervals 中删除了 toBeRemoved 的部分 。换句话说，返回实数集合，并满足集合中的每个实数 x 都在 intervals 中，但不在 toBeRemoved 中。你的答案应该是一个如上所述的 有序的 不相连的间隔列表。

示例 1：

输入：intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
输出：[[0,1],[6,7]]

示例 2：

输入：intervals = [[0,5]], toBeRemoved = [2,3]
输出：[[0,2],[3,5]]

示例 3：

输入：intervals = [[-5,-4],[-3,-2],[1,2],[3,5],[8,9]], toBeRemoved = [-1,4]
输出：[[-5,-4],[-3,-2],[4,5],[8,9]]

提示：

1 <= intervals.length <= 104
-109 <= ai < bi <= 109


class Solution {
public:
    vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& toBeRemoved) {
        CloseInterval<1> c;
        for(auto v:intervals)c.push(CloseIval<1>{v[0],v[1]});
        c.del(CloseIval<1> {toBeRemoved[0],toBeRemoved[1]});
        vector<vector<int>>ans;
        for(auto v:c.allCi)ans.push_back({v.low,v.high});
        return ans;
    }
};

1281. 整数的各位积和之差

给你一个整数 n，请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。

示例 1：

输入：n = 234
输出：15 
解释：
各位数之积 = 2 * 3 * 4 = 24 
各位数之和 = 2 + 3 + 4 = 9 
结果 = 24 - 9 = 15

示例 2：

输入：n = 4421
输出：21
解释： 
各位数之积 = 4 * 4 * 2 * 1 = 32 
各位数之和 = 4 + 4 + 2 + 1 = 11 
结果 = 32 - 11 = 21

提示：

1 <= n <= 10^5


class Solution {
public:
    int subtractProductAndSum(int n) {
        int a=1,b=0;
        while(n)a*=n%10,b+=n%10,n/=10;
        return a-b;
    }
};

1304. 和为零的 N 个不同整数

给你一个整数 n，请你返回任意一个由 n 个 各不相同 的整数组成的数组，并且这 n 个数相加和为 0 。

示例 1：

输入：n = 5
输出：[-7,-1,1,3,4]
解释：这些数组也是正确的 [-5,-1,1,2,3]，[-3,-1,2,-2,4]。

示例 2：

输入：n = 3
输出：[-1,0,1]

示例 3：

输入：n = 1
输出：[0]

提示：

1 <= n <= 1000


class Solution {
public:
	vector<int> sumZero(int n) {
		vector<int>ans;
		if (n & 1)ans.push_back(0);
		n /= 2;
		for (int i = 1; i <= n; i++)ans.push_back(i), ans.push_back(-i);
		return ans;
	}
};

1306. 跳跃游戏 III

图DP

1313. 解压缩编码列表

给你一个以行程长度编码压缩的整数列表 nums 。

考虑每对相邻的两个元素 [freq, val] = [nums[2*i], nums[2*i+1]] （其中 i >= 0 ），每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。

请你返回解压后的列表。

示例：

输入：nums = [1,2,3,4]
输出：[2,4,4,4]
解释：第一对 [1,2] 代表着 2 的出现频次为 1，所以生成数组 [2]。
第二对 [3,4] 代表着 4 的出现频次为 3，所以生成数组 [4,4,4]。
最后将它们串联到一起 [2] + [4,4,4] = [2,4,4,4]。
示例 2：

输入：nums = [1,1,2,3]
输出：[1,3,3]

提示：

2 <= nums.length <= 100
nums.length % 2 == 0
1 <= nums[i] <= 100


class Solution {
public:
    vector<int> decompressRLElist(vector<int> &nums)
    {
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            if (i % 2) continue;
            int freq = nums[i], val = nums[i + 1];
            while (freq--) ans.push_back(val);
        }
        return ans;
    }
};

1314. 矩阵区域和

高维DP

1315. 祖父节点值为偶数的节点和

给你一棵二叉树，请你返回满足以下条件的所有节点的值之和：

该节点的祖父节点的值为偶数。（一个节点的祖父节点是指该节点的父节点的父节点。）
如果不存在祖父节点值为偶数的节点，那么返回 0 。

示例：

输入：root = [6,7,8,2,7,1,3,9,null,1,4,null,null,null,5]
输出：18
解释：图中红色节点的祖父节点的值为偶数，蓝色节点为这些红色节点的祖父节点。

提示：

树中节点的数目在 1 到 10^4 之间。
每个节点的值在 1 到 100 之间。


int ans;
class Solution {
public:
    void sumEvenGrandparent(TreeNode* root,int fafa,int fa,int deep) {
            if(!root)return;
            if(deep>=3 && fafa%2==0)ans+=root->val;
            sumEvenGrandparent(root->left,fa,root->val,deep+1);
            sumEvenGrandparent(root->right,fa,root->val,deep+1);         
    }
    int sumEvenGrandparent(TreeNode* root) {
        ans=0;
        sumEvenGrandparent(root,0,0,1);
        return ans;
    }
};

1316. 不同的循环子字符串

给你一个字符串 text ，请你返回满足下述条件的不同非空子字符串的数目：

可以写成某个字符串与其自身相连接的形式（即，可以写为 a + a，其中 a 是某个字符串）。
例如，abcabc 就是 abc 和它自身连接形成的。

示例 1：

输入：text = "abcabcabc"
输出：3
解释：3 个子字符串分别为 "abcabc"，"bcabca" 和 "cabcab" 。
示例 2：

输入：text = "leetcodeleetcode"
输出：2
解释：2 个子字符串为 "ee" 和 "leetcodeleetcode" 。

提示：

1 <= text.length <= 2000
text 只包含小写英文字母。


class Solution {
public:
    int distinctEchoSubstrings(string text) {
        unordered_set<string>s;
        for(int len=1;len*2<=text.length();len++)
        {
            int tmpans=0;
            for(int i=text.length()-1-len,j=text.length()-1;i>=0;i--,j--)
            {
                tmpans=((text[i]==text[j]) ? (tmpans+1) : 0);
                if(tmpans>=len)s.insert(text.substr(i,j-i));
            }
        }
        return s.size();
    }
};

这是O（n^3）的算法，但是数据比较弱，所以可以过。

用字符串哈希算法，可以实现O（n^2）的算法


long long h[2005][2005];
void getHash(string text)
{
    for(int i=0;i<text.length();i++)
    {
        long long k=0;
        for(int j=i;j<text.length();j++)
        {
            k=(k*1234567 +int(text[j])+1234)%12345678901;
            h[i][j]=k;
        }
    }
}
class Solution {
public:
    int distinctEchoSubstrings(string text) {
        getHash(text);
        unordered_set<long long>s;
        for(int len=1;len*2<=text.length();len++)
        {
            int tmpans=0;
            for(int i=text.length()-1-len,j=text.length()-1;i>=0;i--,j--)
            {
                tmpans=((text[i]==text[j]) ? (tmpans+1) : 0);
                if(tmpans>=len)s.insert(h[i][j]);
            }
        }
        return s.size();
    }
};

1319. 连通网络的操作次数

1329. 将矩阵按对角线排序

矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。

给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。

示例 1：

输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]

示例 2：

输入：mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
输出：[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]

提示：

m == mat.length
n == mat[i].length
1 <= m, n <= 100
1 <= mat[i][j] <= 100


class Solution {
public:
	vector<vector<int>> diagonalSort(vector<vector<int>>& mat) {
		for (int i = 0; i < mat.size(); i++)fresh(mat, i, 0);
		for (int i = 1; i < mat[0].size(); i++)fresh(mat, 0, i);
		return mat;
	}
	void fresh(vector<vector<int>>& mat, int i, int j) {
		int len = min(mat.size() - i, mat[0].size() - j);
		vector<int>v;
		for (int k = 0; k < len; k++) {
			v.push_back(mat[i + k][j + k]);
		}
		sort(v.begin(), v.end());
		for (int k = 0; k < len; k++) {
			mat[i + k][j + k] = v[k];
		}
	}
};

1330. 翻转子数组得到最大的数组值

给你一个整数数组 nums 。「数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。

你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作一次。

请你找到可行的最大数组值。

示例 1：

输入：nums = [2,3,1,5,4]
输出：10
解释：通过翻转子数组 [3,1,5] ，数组变成 [2,5,1,3,4] ，数组值为 10 。
示例 2：

输入：nums = [2,4,9,24,2,1,10]
输出：68

提示：

1 <= nums.length <= 3*10^4
-10^5 <= nums[i] <= 10^5

思路：

假设4个数分别是a<=b<=c<=d，枚举|arr[i]-arr[i+1]|=|b-a|、|c-a|、|d-a|、|b-c|、|d-c|、|b-d|这6种情况，方向有4种是不超过0的，还有2种情况可以总结成：

arr[i]和arr[i+1]要么是4个数里面最小的2个，要么是最大的2个，此时f一定等于2c-2b

所以只需要求所有相邻2个数里面较大值的最小值，所有相邻2个数里面较小值的最大值。

初版代码：


class Solution {
public:
	int maxValueAfterReverse(vector<int>& nums) {
		vector<int>dif = nums;
		int len = nums.size();
		for (int i = len - 1; i; i--)dif[i] -= dif[i - 1];
		int ans = 0;
		for (int i = 1; i < len - 1; i++)ans = max(ans, abs(nums[0] - nums[i + 1]) - abs(dif[i + 1]));
		for (int i = 1; i < len - 1; i++)ans = max(ans, abs(nums[len - 1] - nums[i - 1]) - abs(dif[i]));
		int mina = 0, maxa = 0;
		for (int i = 2; i < len - 1; i++)
		{
			if (max(nums[mina], nums[mina + 1]) > max(nums[i-1], nums[i-2])) {
				mina = i - 2;
			}
			if (min(nums[maxa], nums[maxa + 1]) < min(nums[i - 1], nums[i - 2])) {
				maxa = i - 2;
			}
			vector<int>v = { mina,maxa};
			for (auto vi : v) {
				//vi vi+1 i i+1
				ans = max(ans, abs(nums[vi] - nums[i]) + abs(nums[vi + 1] - nums[i + 1]) - abs(dif[vi + 1]) - abs(dif[i + 1]));
			}
		}
		for (auto di : dif)ans += abs(di);
		return ans - abs(dif[0]);
	}
};

美化之后：


class Solution {
public:
	int maxValueAfterReverse(vector<int>& nums) {
		int len = nums.size();
		vector<int>dif = nums;
		for (int i = len - 1; i; i--)dif[i] -= dif[i - 1];
		int mina = 0, maxa = 0, ans = 0;
		for (int i = 1; i < len - 1; i++)
		{
			if (max(nums[mina], nums[mina + 1]) > max(nums[i], nums[i+1]))mina = i;
			if (min(nums[maxa], nums[maxa + 1]) < min(nums[i], nums[i+1]))maxa = i;
			ans = max(ans, abs(nums[0] - nums[i + 1]) - abs(dif[i + 1]));
			ans = max(ans, abs(nums[len - 1] - nums[i - 1]) - abs(dif[i]));
		}
		ans = max(ans,(min(nums[maxa], nums[maxa + 1]) - max(nums[mina], nums[mina + 1]))*2);
		for (auto di : dif)ans += abs(di);
		return ans - abs(dif[0]);
	}
};

1331. 数组序号转换

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。

序号代表了一个元素有多大。序号编号的规则如下：

序号从 1 开始编号。
一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
每个数字的序号都应该尽可能地小。

示例 1：

输入：arr = [40,10,20,30]
输出：[4,1,2,3]
解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。

示例 2：

输入：arr = [100,100,100]
输出：[1,1,1]
解释：所有元素有相同的序号。

示例 3：

输入：arr = [37,12,28,9,100,56,80,5,12]
输出：[5,3,4,2,8,6,7,1,3]

提示：

0 <= arr.length <= 105
-109 <= arr[i] <= 109


class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        if(arr.empty())return arr;
        auto ids= SortId(arr);
        auto v=arr;
        int x=1,oldid=ids[0];
        for(auto id:ids){
            if(arr[id]==arr[oldid])v[id]=x;
            else v[id]=++x;
            oldid=id;
        }
        return v;
    }
};

1335. 工作计划的最低难度

1340. 跳跃游戏 V

1345. 跳跃游戏 IV

1356. 根据数字二进制下 1 的数目排序

二进制

1358. 包含所有三种字符的子字符串数目

给你一个字符串 s ，它只包含三种字符 a, b 和 c 。

请你返回 a，b 和 c 都至少出现过一次的子字符串数目。

示例 1：

输入：s = "abcabc"
输出：10
解释：包含 a，b 和 c 各至少一次的子字符串为 "abc", "abca", "abcab", "abcabc", "bca", "bcab", "bcabc", "cab", "cabc" 和 "abc" (相同字符串算多次)。
示例 2：

输入：s = "aaacb"
输出：3
解释：包含 a，b 和 c 各至少一次的子字符串为 "aaacb", "aacb" 和 "acb" 。
示例 3：

输入：s = "abc"
输出：1

提示：

3 <= s.length <= 5 x 10^4
s 只包含字符 a，b 和 c 。


class Solution {
public:
    int numberOfSubstrings(string s) {
        int n[3]={-1,-1,-1};
        for(int i=0;i<s.length();i++)
        {
            for(int j=0;j<3;j++)if(s[i]-'a'==j)n[j]=i;
            if(n[0]>-1 && n[1]>-1 && n[2]>-1)break;
        }
        int ans=0;
        for(unsigned int i=max(n[0],max(n[1],n[2]));i<s.length();i++)
        {
            for(int j=0;j<3;j++)if(s[i]-'a'==j)n[j]=i;
            ans+=min(n[0],min(n[1],n[2]))+1;
        }
        return ans;
    }
};

1359. 有效的快递序列数目

组合

1367. 二叉树中的链表

rust

1375. 二进制字符串前缀一致的次数

二进制

1377. T 秒后青蛙的位置

拓扑排序

1379. 找出克隆二叉树中的相同节点