第一题：两个相同字符之间的最长子字符串
给你一个字符串
s
，请你返回 两个相同字符之间的最长子字符串的长度 ，计算长度时不含这两个字符。如果不存在这样的子字符串，返回
-1
。
子字符串 是字符串中的一个连续字符序列。
示例 1：
输入：s = "aa"
输出：0
解释：最优的子字符串是两个 'a' 之间的空子字符串。
示例 2：
输入：s = "abca"
输出：2
解释：最优的子字符串是 "bc" 。
示例 3：
输入：s = "cbzxy"
输出：-1
解释：s 中不存在出现出现两次的字符，所以返回 -1 。
示例 4：
输入：s = "cabbac"
输出：4
解释：最优的子字符串是 "abba" ，其他的非最优解包括 "bb" 和 "" 。
提示：
-
1 <= s.length <= 300
-
s
难度：简单
class Solution {
public int maxLengthBetweenEqualCharacters(String s) {
int i,j,k,res=0;
int[] dp=new int[27];
for(i=0;i<s.length();i++){
k=s.charAt(i)-'a'+1;
if(dp[k]==0)
dp[k]=i+1;
else
res=Math.max(res,i+1-dp[k]);
}
return res-1;
}
}
第二题：执行操作后字典序最小的字符串
给你一个字符串 s 以及两个整数 a 和 b 。其中，字符串 s 的长度为偶数，且仅由数字 0 到 9 组成。
你可以在 s 上按任意顺序多次执行下面两个操作之一：
累加：将 a 加到 s 中所有下标为奇数的元素上（下标从 0 开始）。数字一旦超过 9 就会变成 0，如此循环往复。例如，s = "3456" 且 a = 5，则执行此操作后 s 变成 "3951"。
轮转：将 s 向右轮转 b 位。例如，s = "3456" 且 b = 1，则执行此操作后 s 变成 "6345"。
请你返回在 s 上执行上述操作任意次后可以得到的 字典序最小 的字符串。
如果两个字符串长度相同，那么字符串 a 字典序比字符串 b 小可以这样定义：在 a 和 b 出现不同的第一个位置上，字符串 a 中的字符出现在字母表中的时间早于 b 中的对应字符。例如，"0158” 字典序比 "0190" 小，因为不同的第一个位置是在第三个字符，显然 '5' 出现在 '9' 之前。
示例 1：
输入：s = "5525", a = 9, b = 2
输出："2050"
解释：执行操作如下：
初态："5525"
轮转："2555"
累加："2454"
累加："2353"
轮转："5323"
累加："5222"
累加："5121"
轮转："2151"
累加："2050"
无法获得字典序小于 "2050" 的字符串。
示例 2：
输入：s = "74", a = 5, b = 1
输出："24"
解释：执行操作如下：
初态："74"
轮转："47"
累加："42"
轮转："24"
无法获得字典序小于 "24" 的字符串。
示例 3：
输入：s = "0011", a = 4, b = 2
输出："0011"
解释：无法获得字典序小于 "0011" 的字符串。
示例 4：
输入：s = "43987654", a = 7, b = 3
输出："00553311"
提示：
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lexicographically-smallest-string-after-applying-operations
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
难度：中等
思路：set+dfs；只有两种操作轮转和累加；
class Solution {
Set<String> set=new HashSet<>();
String res;
public void dfs(String s,int a,int b){
//if(set.contains(t)) return ;
String t1="";
t1=s.substring(s.length()-b,s.length())+s.substring(0,s.length()-b);
if(set.contains(t1)==false){
set.add(t1);
if(res.compareTo(t1)>0) res=t1;
dfs(t1,a,b);
}
String t="";
for(int i=0;i<s.length();i++){
if(i%2==0)
t=t+s.charAt(i);
else {
String t2=""+s.charAt(i);
int k=Integer.valueOf(t2)+a;
k=k%10;
t=t+String.valueOf(k);
}
}
if(set.contains(t)==false){
//res=Math.min(res,t);
set.add(t);
if(res.compareTo(t)>0) res=t;
dfs(t,a,b);
}
}
public String findLexSmallestString(String s, int a, int b) {
res=s;
set.add(s);
dfs(s,a,b);
return res;
}
}
第三题： 无矛盾的最佳球队
假设你是球队的经理。对于即将到来的锦标赛，你想组合一支总体得分最高的球队。球队的得分是球队中所有球员的分数 总和 。
然而，球队中的矛盾会限制球员的发挥，所以必须选出一支 没有矛盾 的球队。如果一名年龄较小球员的分数 严格大于 一名年龄较大的球员，则存在矛盾。同龄球员之间不会发生矛盾。
给你两个列表
scores
和
ages
，其中每组
scores[i]
和
ages[i]
表示第
i
名球员的分数和年龄。请你返回 所有可能的无矛盾球队中得分最高那支的分数 。
示例 1：
输入：scores = [1,3,5,10,15], ages = [1,2,3,4,5]
输出：34
解释：你可以选中所有球员。
示例 2：
输入：scores = [4,5,6,5], ages = [2,1,2,1]
输出：16
解释：最佳的选择是后 3 名球员。注意，你可以选中多个同龄球员。
示例 3：
输入：scores = [1,2,3,5], ages = [8,9,10,1]
输出：6
解释：最佳的选择是前 3 名球员。
提示：
-
1 <= scores.length, ages.length <= 1000
-
scores.length == ages.length
-
1 <= scores[i] <= 106
-
1 <= ages[i] <= 1000
难度：中等
思路：先排序+枚举。用f[i]记录：以选取队员i结尾时的最大分数。
class Solution {
public int bestTeamScore(int[] scores, int[] ages) {
int[][] dp=new int[ages.length][2];
int[] f=new int[ages.length];
int i,j,k,res=0;
for(i=0;i<ages.length;i++){
dp[i][0]=ages[i];
dp[i][1]=scores[i];
}
Arrays.sort(dp, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[0]==o2[0]) return o1[1]-o2[1];
return o1[0]-o2[0];}});
for(i=0;i<ages.length;i++){
f[i]=dp[i][1];
}
res=f[0];
//System.out.print(f[0]+" ");
for(i=1;i<ages.length;i++){
k=f[i];
for(j=i-1;j>=0;j--){
if(dp[i][0]==dp[j][0]){
k=Math.max(k,f[i]+f[j]);
}else if(dp[i][0]!=dp[j][0]&&dp[i][1]>=dp[j][1]){
k=Math.max(k,f[i]+f[j]);
}
}
f[i]=k;
res=Math.max(f[i],res);
}
return res;
}
}
第四题：带阈值的图连通性
有
n
座城市，编号从
1
到
n
。编号为
x
和
y
的两座城市直接连通的前提是：
x
和
y
的公因数中，至少有一个 严格大于 某个阈值
threshold
。更正式地说，如果存在整数
z
，且满足以下所有条件，则编号
x
和
y
的城市之间有一条道路：
-
x % z == 0
-
y % z == 0
-
z > threshold
给你两个整数
n
和
threshold
，以及一个待查询数组，请你判断每个查询
queries[i] = [ai, bi]
指向的城市
ai
和
bi
是否连通（即，它们之间是否存在一条路径）。
返回数组
answer
，其中
answer.length == queries.length
。如果第
i
个查询中指向的城市
ai
和
bi
连通，则
answer[i]
为
true
；如果不连通，则
answer[i]
为
false
。
示例 1：
输入：n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]
输出：[false,false,true]
解释：每个数的因数如下：
1: 1
2: 1, 2
3: 1, 3
4: 1, 2, 4
5: 1, 5
6: 1, 2, 3, 6
所有大于阈值的的因数已经加粗标识，只有城市 3 和 6 共享公约数 3 ，因此结果是：
[1,4] 1 与 4 不连通
[2,5] 2 与 5 不连通
[3,6] 3 与 6 连通，存在路径 3--6
示例 2：
输入：n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]
输出：[true,true,true,true,true]
解释：每个数的因数与上一个例子相同。但是，由于阈值为 0 ，所有的因数都大于阈值。因为所有的数字共享公因数 1 ，所以所有的城市都互相连通。
示例 3：
输入：n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]
输出：[false,false,false,false,false]
解释：只有城市 2 和 4 共享的公约数 2 严格大于阈值 1 ，所以只有这两座城市是连通的。
注意，同一对节点 [x, y] 可以有多个查询，并且查询 [x，y] 等同于查询 [y，x] 。
提示：
-
2 <= n <= 104
-
0 <= threshold <= n
-
1 <= queries.length <= 105
-
queries[i].length == 2
-
1 <= ai, bi <= cities
-
ai != bi
难度：困难
思路：并查集，两个城市直接相连，说明两个城市有共因子大于
threshold
，根据这一点，建连通图。
class Solution {
public int find(int x,int[] f){
while(x!=f[x]){
f[x]=f[f[x]]; //路径压缩优化
x=f[x];
}
return x;
}
public List<Boolean> areConnected(int n, int threshold, int[][] queries) {
//并查集
List<Boolean> res=new ArrayList<>();
int[] f=new int[n+1];
int i,j,k;
for(i=1;i<=n;i++){
f[i]=i;
}
for(i=threshold+1;i<=n/2;i++){
int y=find(i,f);
for(j=i*2;j<=n;j=j+i){//为啥会直接跳过j=i；因为i==j时本身就是连通的；
if(j%i==0){
int x=find(j,f);
//if(x==y) continue;
f[x]=y;
}
}
}
for(i=0;i<queries.length;i++){
int x,y;
x=find(queries[i][0],f);
y=find(queries[i][1],f);
if(x==y)
res.add(true);
else res.add(false);
}
return res;
}
}