dis数组中有三种可能的值，-1表示未出现过，由于如果出现那么必定出现两次，因此第一次出现做记录，第二次出现计算差值。
class Solution {
public boolean checkDistances(String s, int[] distance) {
int[]dis=new int[26];
int len=s.length();
Arrays.fill(dis,-1);
for(int i=0;i<len;i++){
char c=s.charAt(i);
if(dis[c-'a']==-1) dis[c-'a']=i;
else dis[c-'a']=i-dis[c-'a']-1;
}
for(int i=0;i<26;i++){
if(dis[i]==-1) continue;
if(dis[i]!=-1&&dis[i]!=distance[i]) return false;
}
return true;
}
}
当时只想着动态规划能做，但是始终不知道如何表示恰好走几步以及走的位置，还有当走出去又走回来怎么办，看朋友的题解才想到，开辟二维数组表示，每轮都暴力枚举所有的空间状态就可以了，某个位置的方法数目只和其左右两边有关。因此用二维动态规划，dp[i][j]代表最多走i步到下标j的方法数目。因为会往左右两边都走，因此出发点设置在中间。为了计算最终状态dp[k][1005+endPos-startPos]，每轮的j都需要从开始的位置枚举到最多走i步，其状态只和左右两边状态有关。
class Solution {
public int numberOfWays(int startPos, int endPos, int k) {
int[][]dp=new int[k+1][2010];
dp[0][1005]=1;
int mod=(int)1e9+7;
for(int i=1;i<=k;i++){
for(int j=0;j<=i;j++){
dp[i][1005+j]=(dp[i-1][1005+j-1]+dp[i-1][1005+j+1])%mod;
dp[i][1005-j]=(dp[i-1][1005-j-1]+dp[i-1][1005-j+1])%mod;
}
}
return dp[k][1005+endPos-startPos];
}
}
动态规划可以做，同样记忆化搜索也可以做，递归函数中返回到某个位置x还剩余left步的情况下，能够有的方案数，将(x,left)进行记忆化。Python题解如下：
class Solution:
def numberOfWays(self, startPos: int, endPos: int, k: int) -> int:
MOD=10**9+7
@cache
# 返回到某个位置x还剩余left步的情况下，能够有的方案数
def dfs(x:int, left:int) -> int:
# 当没法到达终点的时候，包括left=0但是还没到终点
if abs(x-endPos)>left: return 0
# 在排除了上面的情况后，剩下的left=0一定是到达终点的
if(left==0): return 1
return (dfs(x-1,left-1)+dfs(x+1,left-1))%MOD
return dfs(startPos,k)
用Java的HashMap实现记忆化搜索，在数据范围合适的情况下，对原来需要存储两个维度的信息能够转换为一个维度的信息，这题就需要存储当前位置信息和剩余步数信息
class Solution {
int mod=(int)1e9+7;
int endPos;
HashMap<Integer,Integer> map;
public int numberOfWays(int startPos, int _endPos, int k) {
endPos=_endPos;
map=new HashMap<>();
return (int)dfs(startPos,k);
}
public long dfs(int x,int left){
if(Math.abs(x-endPos)>left) return 0;
if(left==0) return 1;
//二维信息转一维
//由于0<=left<=1000，因此可以让当前位置乘以一个大于1000的数再加上它
int key=x*1005+left;
if(map.containsKey(key)) return map.get(key);
int ans= (int)(dfs(x-1,left-1)+dfs(x+1,left-1))%mod;
map.put(key,ans);
return ans;
}
}
滑动窗口+位运算。用一个数字窗口window维护整型32位上出现的数字，每次移动right只需要判断当前数字与窗口中的&以后，是否为0，如果为0则代表所有数字都散落在窗口的不同位置，如果不为0则需要收缩左边界。可以保证的是，如果当前的数字与窗口&只为0才加入，那么窗口中所有的数字互相&都是0.
class Solution {
public int longestNiceSubarray(int[] nums) {
int res=0;
int len=nums.length;
int window=0;
int left=0;
int right=0;
while(right<len){
int temp=window & nums[right];
while(temp!=0){
window ^= nums[left];
temp = window & nums[right];
left++;
}
window |= nums[right];
res=Math.max(res,right-left+1);
right++;
}
return res;
}
}
双堆模拟。“当会议室处于未占用状态时，将会优先提供给原开始时间更早的会议。”从这句话就可以知道，会议的安排只和会议的开始时间顺序相关，因此可以按照开始时间对会议升序处理。用一个小顶堆维护空闲会议室编号，这是为了每次能够取用最小编号的空闲会议室；用另一个小顶堆维护（已占用会议室的结束时间，已占用编号），在遍历所有会议的时候，每次将遍历的meetings[0]前结束的会议弹出，放入空闲会议室。接下来在判断当前会议加入哪个会议室的时候，如果有空会议室，则占用；没有可用的会议室，则等待，编程上反映就是弹出已占有会议室中结束时间最早的会议室（但仍然比当前meetings[0]要大），占用它并更新已占用会议室的结束时间的差值（相当于当前会议室延后了我等待的时间），将其加入占用会议室堆。
时间复杂度：O(MlogM+MlogN+N)。分别为会议排序时间，遍历会议调整堆中会议室，最后选出答案。
class Solution {
public int mostBooked(int n, int[][] meetings) {
Arrays.sort(meetings,(a,b)->a[0]-b[0]);
int[]ans=new int[n];
PriorityQueue<Integer> pqidle=new PriorityQueue<>();
//存放（会议室结束时间，编号），优先选择结束时间最早的会议室，当结束时间相同，优先弹出编号小的
PriorityQueue<Pair<Long,Integer>> pqusing=new PriorityQueue<Pair<Long,Integer>>((a,b)->Objects.equals(a.getKey(),b.getKey())?Integer.compare(a.getValue(),b.getValue()):Long.compare(a.getKey(),b.getKey()));
for(int i=0;i<n;i++) pqidle.offer(i);
int len=meetings.length;
for(int i=0;i<len;i++){
long start=meetings[i][0];
long end=meetings[i][1];
//将start以前结束的会议室放出
while(!pqusing.isEmpty()&&start>=pqusing.peek().getKey()){
Pair<Long,Integer> top=pqusing.poll();
pqidle.offer(top.getValue());
}
int id;
//如果没有空闲会议室
if(pqidle.size()==0){
//等待top.getKey()-start的时间空出来并占用
Pair<Long,Integer>top=pqusing.poll();
end+=top.getKey()-start;
id=top.getValue();
pqusing.offer(new Pair<Long,Integer>(end,id));
}else{
int idletop=pqidle.poll();
id=idletop;
pqusing.offer(new Pair<Long,Integer>(end,idletop));
}
ans[id]+=1;
}
int res=0;
for(int i=0;i<ans.length;i++){
if(ans[i]>ans[res]) res=i;
}
return res;
}
}