6369. 左右元素和的差值
给你一个下标从 0 开始的整数数组 nums ，请你找出一个下标从 0 开始的整数数组 answer ，其中：
answer.length == nums.length
answer[i] = |leftSum[i] - rightSum[i]|
其中：
leftSum[i] 是数组 nums 中下标 i 左侧元素之和。如果不存在对应的元素，leftSum[i] = 0 。
rightSum[i] 是数组 nums 中下标 i 右侧元素之和。如果不存在对应的元素，rightSum[i] = 0 。
返回数组 answer 。
示例 1：
输入：nums = [10,4,8,3]
输出：[15,1,11,22]
解释：数组 leftSum 为 [0,10,14,22] 且数组 rightSum 为 [15,11,3,0] 。
数组 answer 为 [|0 - 15|,|10 - 11|,|14 - 3|,|22 - 0|] = [15,1,11,22] 。
示例 2：
输入：nums = [1]
输出：[0]
解释：数组 leftSum 为 [0] 且数组 rightSum 为 [0] 。
数组 answer 为 [|0 - 0|] = [0] 。
提示：
1 <= nums.length <= 1000
1 <= nums[i] <= 10^5解答：分别统计左右两边的前缀和
class Solution {
public int[] leftRigthDifference(int[] nums) {
int n=nums.length;
int[] left=new int[n];
int[] right=new int[n];
for(int i=1;i<n;i++){
left[i]+=left[i-1]+nums[i-1];
}
for (int i = n-2; i >=0 ; i--) {
right[i]+=right[i+1]+nums[i+1];
}
int[] res=new int[n];
for (int i = 0; i < n; i++) {
res[i]=Math.abs(left[i]-right[i]);
}
return res;
}
}6368. 找出字符串的可整除数组
给你一个下标从 0 开始的字符串 word ，长度为 n ，由从 0 到 9 的数字组成。另给你一个正整数 m 。
word 的 可整除数组 div 是一个长度为 n 的整数数组，并满足：
如果 word[0,...,i] 所表示的 数值 能被 m 整除，div[i] = 1
否则，div[i] = 0
返回 word 的可整除数组。
示例 1：
输入：word = "998244353", m = 3
输出：[1,1,0,0,0,1,1,0,0]
解释：仅有 4 个前缀可以被 3 整除："9"、"99"、"998244" 和 "9982443" 。
示例 2：
输入：word = "1010", m = 10
输出：[0,1,0,1]
解释：仅有 2 个前缀可以被 10 整除："10" 和 "1010" 。
提示：
1 <= n <= 10^5
word.length == n
word 由数字 0 到 9 组成
1 <= m <= 10^9解答：每次都对m取模
class Solution {
public int[] divisibilityArray(String word, int m) {
int n=word.length();
int[] res=new int[n];
long sum=0;
for(int i=0;i<n;i++){
int num=word.charAt(i)-'0';
sum=num+sum*10;
//能整除，直接置sum为0
if(sum%m==0){
res[i]++;
sum=0;
}
//不能整除，直接对m取模运算
else{
sum=sum%m;
}
}
return res;
}
}6367. 求出最多标记下标
给你一个下标从 0 开始的整数数组 nums 。
一开始，所有下标都没有被标记。你可以执行以下操作任意次：
选择两个 互不相同且未标记 的下标 i 和 j ，满足 2 * nums[i] <= nums[j] ，标记下标 i 和 j 。
请你执行上述操作任意次，返回 nums 中最多可以标记的下标数目。
示例 1：
输入：nums = [3,5,2,4]
输出：2
解释：第一次操作中，选择 i = 2 和 j = 1 ，操作可以执行的原因是 2 * nums[2] <= nums[1] ，标记下标 2 和 1 。
没有其他更多可执行的操作，所以答案为 2 。
示例 2：
输入：nums = [9,2,5,4]
输出：4
解释：第一次操作中，选择 i = 3 和 j = 0 ，操作可以执行的原因是 2 * nums[3] <= nums[0] ，标记下标 3 和 0 。
第二次操作中，选择 i = 1 和 j = 2 ，操作可以执行的原因是 2 * nums[1] <= nums[2] ，标记下标 1 和 2 。
没有其他更多可执行的操作，所以答案为 4 。
示例 3：
输入：nums = [7,6,8]
输出：0
解释：没有任何可以执行的操作，所以答案为 0 。
提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9解答：贪心，直接排序取中心下标，然后双指针遍历数据统计
class Solution {
public int maxNumOfMarkedIndices(int[] nums) {
int n=nums.length;
Arrays.sort(nums);
int res=0;
int index=(n-1)/2,r=n-1;
Set<Integer> set=new HashSet<>();
while(index>=0&&r>=0){
while(set.contains(r)){
r--;
}
if(nums[index]*2<=nums[r]){
set.add(index);
r--;
index--;
res+=2;
}
else if(nums[index]*2>nums[r]){
index--;
}
}
return res;
}
}6366. 在网格图中访问一个格子的最少时间
给你一个 m x n 的矩阵 grid ，每个元素都为 非负 整数，其中 grid[row][col] 表示可以访问格子 (row, col) 的 最早 时间。也就是说当你访问格子 (row, col) 时，最少已经经过的时间为 grid[row][col] 。
你从 最左上角 出发，出发时刻为 0 ，你必须一直移动到上下左右相邻四个格子中的 任意 一个格子（即不能停留在格子上）。每次移动都需要花费 1 单位时间。
请你返回 最早 到达右下角格子的时间，如果你无法到达右下角的格子，请你返回 -1 。
示例 1：
输入：grid = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
输出：7
解释：一条可行的路径为：
- 时刻 t = 0 ，我们在格子 (0,0) 。
- 时刻 t = 1 ，我们移动到格子 (0,1) ，可以移动的原因是 grid[0][1] <= 1 。
- 时刻 t = 2 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 2 。
- 时刻 t = 3 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 3 。
- 时刻 t = 4 ，我们移动到格子 (1,1) ，可以移动的原因是 grid[1][1] <= 4 。
- 时刻 t = 5 ，我们移动到格子 (1,2) ，可以移动的原因是 grid[1][2] <= 5 。
- 时刻 t = 6 ，我们移动到格子 (1,3) ，可以移动的原因是 grid[1][3] <= 6 。
- 时刻 t = 7 ，我们移动到格子 (2,3) ，可以移动的原因是 grid[2][3] <= 7 。
最终到达时刻为 7 。这是最早可以到达的时间。
示例 2：
输入：grid = [[0,2,4],[3,2,1],[1,0,4]]
输出：-1
解释：没法从左上角按题目规定走到右下角。
提示：
m == grid.length
n == grid[i].length
2 <= m, n <= 1000
4 <= m * n <= 10^5
0 <= grid[i][j] <= 10^5
grid[0][0] == 0解答：BFS+优先队列+最短路，因为能来回走所有到达一个位置的时间应该与该坐标同奇偶
class Solution {
int m,n;
int[] dx={0,1,0,-1};
int[] dy={1,0,-1,0};
public int minimumTime(int[][] grid) {
m=grid.length;n=grid[0].length;
//刚开始两个位置都无法到达直接返回-1
if(grid[0][1]>1&&grid[1][0]>1)return -1;
Queue<int[]> q=new PriorityQueue<>((a,b)->a[2]-b[2]);
int[][] d=new int[m][n];
for(int[] a:d)Arrays.fill(a,Integer.MAX_VALUE);
q.offer(new int[]{0,0,0});
int res=Integer.MAX_VALUE;
while(true){
int[] tmp=q.poll();
int i=tmp[0],j=tmp[1],c=tmp[2];
if(tmp[0]==m-1&&tmp[1]==n-1)return c;
//枚举上下左右四个方向
for(int k=0;k<4;k++){
int x=i+dx[k],y=j+dy[k];
if(x<0||x>=m||y<0||y>=n)continue;
int curd=Math.max(c+1,grid[x][y]);
curd+=(curd-x-y)%2;//curd和x+y同奇偶
if(curd<d[x][y]){
d[x][y]=curd;//更新最短路
q.offer(new int[]{x,y,curd});
}
}
}
}
}
