859. 亲密字符串
给你两个字符串 s 和 goal ，只要我们可以通过交换 s 中的两个字母得到与 goal 相等的结果，就返回 true ；否则返回 false 。
交换字母的定义是：取两个下标 i 和 j （下标从 0 开始）且满足 i != j ，接着交换 s[i] 和 s[j] 处的字符。
例如，在 "abcd" 中交换下标 0 和下标 2 的元素可以生成 "cbad" 。
示例 1：
输入：s = "ab", goal = "ba"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 相等。
示例 2：
输入：s = "ab", goal = "ab"
输出：false
解释：你只能交换 s[0] = 'a' 和 s[1] = 'b' 生成 "ba"，此时 s 和 goal 不相等。
示例 3：
输入：s = "aa", goal = "aa"
输出：true
解释：你可以交换 s[0] = 'a' 和 s[1] = 'a' 生成 "aa"，此时 s 和 goal 相等。
提示：
1 <= s.length, goal.length <= 2 * 10^4
s 和 goal 由小写英文字母组成解答：分类讨论
class Solution {
public boolean buddyStrings(String s, String goal) {
if(s.length()!=goal.length())return false;
int[] res=new int[26];
int[] res1=new int[26];
//统计不一样的位置
int a=0;
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
char c1=goal.charAt(i);
if(c!=c1)a++;
res[c-'a']++;
res1[c1-'a']++;
}
//看有没有字母出现了两次以上
int b=0;
boolean flag=true;
for(int i=0;i<26;i++){
b=Math.max(b,res[i]);
if(res[i]!=res1[i])flag=false;
}
if(!flag)return false;
//如果都相等并且有字母出现过两次
if(a==0&&b>=2)return true;
if(a==2)return true;
return false;
}
}1419. 数青蛙
给你一个字符串 croakOfFrogs，它表示不同青蛙发出的蛙鸣声（字符串 "croak" ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以 croakOfFrogs 中会混合多个 “croak” 。
请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。
要想发出蛙鸣 "croak"，青蛙必须 依序 输出 ‘c’, ’r’, ’o’, ’a’, ’k’ 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 croakOfFrogs 不是由若干有效的 "croak" 字符混合而成，请返回 -1 。
示例 1：
输入：croakOfFrogs = "croakcroak"
输出：1
解释：一只青蛙 “呱呱” 两次
示例 2：
输入：croakOfFrogs = "crcoakroak"
输出：2
解释：最少需要两只青蛙，“呱呱” 声用黑体标注
第一只青蛙 "crcoakroak"
第二只青蛙 "crcoakroak"
示例 3：
输入：croakOfFrogs = "croakcrook"
输出：-1
解释：给出的字符串不是 "croak" 的有效组合。
提示：
1 <= croakOfFrogs.length <= 105
字符串中的字符只有 'c', 'r', 'o', 'a' 或者 'k'解答：暴力枚举，每次判断是否合法
class Solution {
public int minNumberOfFrogs(String croakOfFrogs) {
int[] h=new int[26];
int res=0;
int cc=0,r=0,o=0,a=0,k=0;
for(char c:croakOfFrogs.toCharArray()){
if(c=='c'){
cc++;
res=Math.max(res,cc-k);
}
else if(c=='r'){
if(cc>r)r++;
else return -1;
}
else if(c=='o'){
if(r>o)o++;
else return -1;
}
else if(c=='a'){
if(o>a)a++;
else return -1;
}
else{
if(a>k)k++;
else return -1;
}
}
//都要相等才能返回res
if(cc==r&&r==o&&o==a&&a==k)return res;
return -1;
}
}剑指 Offer II 087. 复原 IP
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
示例 1：
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000"
输出：["0.0.0.0"]
示例 3：
输入：s = "1111"
输出：["1.1.1.1"]
示例 4：
输入：s = "010010"
输出：["0.10.0.10","0.100.1.0"]
示例 5：
输入：s = "10203040"
输出：["10.20.30.40","102.0.30.40","10.203.0.40"]
提示：
0 <= s.length <= 3000
s 仅由数字组成解答：直接回溯，判断每次的结果是否合法，合法就加到答案里
class Solution {
List<String> res=new ArrayList<>();
public List<String> restoreIpAddresses(String s) {
if(s.length()>12)return res;
backing(s,0,0);
return res;
}
private void backing(String s,int pointNum,int start){
if(pointNum==3){
if(isVaild(s,start,s.length()-1)){
res.add(s);
return;
}
}
for(int i=start;i<s.length();i++){
//判断区间[start,i]是否合法
if(isVaild(s,start,i)){
s=s.substring(0,i+1)+"."+s.substring(i+1);
pointNum++;
backing(s,pointNum,i+2);
pointNum--;
s=s.substring(0,i+1)+s.substring(i+2);//回溯,删除'.';
}
else break;
}
}
//判断ip地址是否合法
private boolean isVaild(String s,int start,int end){
if(start>end)return false;
//首位为0，不合法
if(start!=end&&s.charAt(start)=='0')return false;
int num=0;
for(int i=start;i<=end;i++){
if(s.charAt(i)<'0'&&s.charAt(i)>'9')return false;
num=s.charAt(i)-'0'+10*num;
if(num<0||num>255)return false;
}
return true;
}
}630. 课程表 III
这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。
你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。
返回你最多可以修读的课程数目。
示例 1：
输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。
示例 2：
输入：courses = [[1,2]]
输出：1
示例 3：
输入：courses = [[3,2],[4,3]]
输出：0
提示:
1 <= courses.length <= 10^4
1 <= durationi, lastDayi <= 10^4解答：贪心+排序+大顶堆
class Solution {
public int scheduleCourse(int[][] courses) {
Arrays.sort(courses,(a,b)->a[1]-b[1]);
//大顶堆
PriorityQueue<Integer> pq=new PriorityQueue<>((a,b)->(b-a));
int res=0;
for(int[] c:courses){
int d=c[0],e=c[1];
res+=d;
pq.offer(d);
//当前不满足要求时，直接返回最大的那个时间段
if(res>e)res-=pq.poll();
}
return pq.size();
}
}
