classSolution{publicbooleanisValid(char[]s,char[]p,intsi,intpi){return si <s.length&&(s[si]== p[pi]|| p[pi]=='.');}publicbooleanisMatch(char[]s,char[]p,intsi,intpi){if(pi ==p.length)return si ==s.length;// 必须同时全部对上 // 1. 当前pi+1位置为*if(pi +1<p.length&& p[pi +1]=='*'){returnisMatch(s, p, si, pi +2)||(isValid(s, p, si, pi)&&isMatch(s, p, si +1, pi));}elsereturnisValid(s, p, si, pi)&&isMatch(s, p, si +1, pi +1);}publicbooleanisMatch(Strings,Stringp){for(int i =0; i <s.length(); i++){if(s.charAt(i)>'z'||s.charAt(i)<'a')returnfalse;}for(int i =0; i <p.length(); i++){if(i ==0&&p.charAt(i)=='*')returnfalse;if(i >0&&p.charAt(i)==p.charAt(i -1)&&p.charAt(i)=='*')// 出现"**"无法识别returnfalse;if(!(p.charAt(i)<='z'&&p.charAt(i)>='a'||(p.charAt(i)=='.'||p.charAt(i)=='*')))returnfalse;}returnthis.isMatch(s.toCharArray(),p.toCharArray(),0,0);}}
public int process(int[] arr,int k){
int left = 0,right = 0;
int length = arr.length;
int max = 0;
while (left < length){
while (right < length && arr[right] - arr[left] <= k){
right++;
}
max = Math.max(max,right - (left++));
}
return max;
}
public int process(char[] chrs) {
int left = 0, right = chrs.length-1;
int count = 0;
while (left < right){
if(chrs[left] == 'B'){
if(chrs[right] == 'G'){
swap(chrs,left++,right--);
count++;
}else{
right--;
}
}else{
if(chrs[right] == 'B'){
left++;
right--;
}else{
left++;
}
}
}
return count;
}
// 暴力递归
public int process(int[] nums, int i, int rest) {
if (i == nums.length) return rest == 0 ? 1 : 0;
// + or - 的可能性方法
return process(nums, i + 1, rest - nums[i]) + process(nums, i + 1, rest + nums[i]);
}
public int process(int[] nums, int target) {
return this.process(nums, 0, target);
}
// 记忆化搜索
public int process1(int[] nums, HashMap<Integer,HashMap<Integer, Integer>> map, int i, int rest) {
if(map.containsKey(i) && map.get(i).containsKey(rest)){
return map.get(i).get(rest);
}
int ans = 0;
if (i == nums.length) ans = rest == 0 ? 1 : 0;
else
ans = process1(nums, map, i + 1, rest - nums[i]) + process1(nums, map, i + 1, rest + nums[i]);
if(!map.containsKey(i)){
map.put(i,new HashMap<>());
}
map.get(i).put(rest,ans);
// + or - 的可能性方法
return map.get(i).get(rest);
}
public int process1(int[] nums, int target) {
return this.process1(nums, new HashMap<>(), 0, target);
}
public int subset(int[] nums,int target){
int[] dp = new int[target+1];
dp[0] = 1;
for(int num:nums){
for(int t = target;t>=num;t--){
dp[t] += dp[t-num];
}
}
return dp[target];
}
public int process2(int[] nums,int target){
int sum = 0;
for(int num:nums)
sum += num;
return sum < target || ((target & 1) ^ (sum & 1)) != 0?0:subset(nums,(target+sum)/2);
}
public static void main(String[] args) {
Problem03 solution = new Problem03();
int[] nums = {1, 3};
System.out.println(solution.process1(nums, 3));;
}
public int maxMoney(int[][] income){
if(income == null || income.length < 2 || (income.length & 1) != 0){
return 0;
}
int N = income.length; // 司机数量一定是偶数，所以才能平分
int M = N >> 1; // M = N / 2 要去A区域的人，剩下的人就是去B区域了
return process(income,0,M);
}
// index . ....所有的司机。往A和B区域分配!
// A区域还有rest个名额!
// 返回把index.. .司机，分配完，并且最终A和B区域同样多的情况下，index...往后的这些司机，整体收入最大是多少!
public int process(int[][] income,int index,int rest) { // 暴力递归
if(index == income.length){
return 0;
}
// 还剩下的司机
if(income.length - index == rest){ // 正好剩下的数量，和需要的数量一样，就全部给出去
return income[index][0] + process(income,index+1,rest-1);
}
// 当前司机可以去A，也可以去B
int p1 = income[index][0] + process(income,index+1, rest-1); // A
int p2 = income[index][1] + process(income,index+1, rest); // B
return Math.max(p1,p2);
}
public int process2(int[][] income,int[][] dp,int index,int rest) {
if(dp[index][rest] != -1) return dp[index][rest];
if(index == income.length){
dp[index][rest] = 0;
}
else if(income.length - index == rest){
dp[index][rest] = income[index][0] + process(income,index+1,rest-1);
}else{
// 当前司机可以去A，也可以去B
int p1 = income[index][0] + process(income,index+1, rest-1); // A
int p2 = income[index][1] + process(income,index+1, rest); // B
dp[index][rest] = Math.max(p1,p2);
}
return dp[index][rest];
}
int all = 0;//修改的值
long settAllTime;//修改的时间
long time;//当前时间
map =>(key,value,time)
如果当前key值修改时间time小于settAllTime，就可以知道当前key已经被setAll了，直接返回all即可。
public int process(String str) { // 动态规划
if(str == null || str.equals(""))
return 0;
char[] chrs = str.toCharArray();
int[] map = new int[256];
for(int i=0;i<256;i++){
map[i] = -1;
}
int len = 0;
int pre = -1;
int cur = 0;
for(int i=0;i < chrs.length;i++){
pre = Math.max(pre,map[chrs[i]]); // 获取字符上一次的出现位置，没出现过就返回-1(这里会保留最近的重复字符的位置)
cur = i - pre;// 当前位置i-上一次该字符出现的位置
len = Math.max(len,cur);
map[chrs[i]] = i;
}
return len;
}
public int process2(String str) {
if(str == null || str.equals(""))
return 0;
char[] chrs = str.toCharArray();
int[] map = new int[256];
for(int i=0;i<256;i++){
map[i] = -1;
}
int pre = 1;
int ans = 1;
map[chrs[0]] = 0;
for(int i=1;i <= chrs.length;i++){
pre = Math.min(i - map[chrs[i]], pre+1);
ans = Math.max(ans,pre);
map[chrs[i]] = i;
}
return ans;
}
public int process(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int max = Integer.MIN_VALUE;
int cur = 0;
for (int num : nums) {
cur += num;
max = Math.max(cur, max);
cur = Math.max(cur, 0); //
}
return max;
}
[1,3,3,2,1,4,2,2,5,2,1] <- arr
[1,2,1,1,2,1,1,2,1,1,1] <- left
[1,1,3,2,1,2,1,1,3,2,1] <- right
[1,2,3,2,2,2,1,2,3,2,1] <- 当前最高的坡度 => max(left[i],right[i])
[2,2,3,3,2,2,1,0,1,2,4,4,3,3] <- arr
[1,1,2,2,1,1,1,1,2,3,4,4,1,1] <- left
[1,1,4,4,3,3,2,1,1,1,2,2,1,1] <- right
当前最高的坡度 => max(left[i],right[i])
static class Info{
String str;
int ans;
public Info(int ans,String str){
this.ans = ans;
this.str = str;
}
}
public int sameNumber2(Node node){
return this.process(node).ans;
}
public Info process(Node node){
if(node == null) return new Info(0,String.valueOf("#_".hashCode()));
Info left = process(node.left);
Info right = process(node.right);
int ans = (left.str.equals(right.str)?1:0) + left.ans + right.ans;
String str = String.valueOf("_"+node.value+"_").hashCode() + left.str + right.str;
return new Info(ans,str);
}
public class Problem14 {
static class Info{
int value;
int index;
public Info(int value, int index) {
this.value = value;
this.index = index;
}
}
public Info process(char[] chrs, LinkedList<String> queue, int i){
int num = 0;
Info info = null;
boolean isNeg = false;
if(i < chrs.length && chrs[i] == '-'){ // 当前是负数
isNeg = true;
i++;
}
while (i < chrs.length && chrs[i] != ')'){
if(chrs[i] <= '9' && chrs[i] >= '0'){
num = num*10 + chrs[i++] - '0';
}else if(chrs[i] != '('){
if(isNeg){
num = -num;
isNeg = false;
}
addNum(queue,num);
queue.addLast(String.valueOf(chrs[i++]));
num = 0;
}else{
info = process(chrs,queue,i+1);// 遇到左括号
i = info.index+1;
num = info.value;
}
}
if(isNeg){
num = -num;
}
addNum(queue,num);
return new Info(getSum(queue),i);
}
public void addNum(LinkedList<String> queue,int num){
if(!queue.isEmpty()){
String top = queue.pollLast();
if(top.equals("+") || top.equals("-"))
queue.addLast(top);
else{
Integer cur = Integer.parseInt(queue.pollLast());
num = top.equals("*")?cur*num:cur/num;
}
}
queue.addLast(String.valueOf(num));
}
public int getSum(LinkedList<String> queue){
int result = 0;
boolean add = true;
String cur = null;
while (!queue.isEmpty()){
cur = queue.pollFirst();
if(cur.equals("+"))
add = true;
else if(cur.equals("-"))
add = false;
else
result += add?Integer.parseInt(cur):-Integer.parseInt(cur);
}
return result;
}
public int process(String str){
return this.process(str.toCharArray(),new LinkedList<>(),0).value;
}
public static void main(String[] args) {
Problem14 solution = new Problem14();
String str = "3+4*(-2)-5";
System.out.println(solution.process(str));;
}
}
public int process(int[] h){
int max = 0;
int left = 0;
int right = h.length-1;
while (left < right){
max = Math.max(max, Math.min(h[left],h[right])*(right-left));
if (h[left] > h[right]) {
right--;
} else {
left++;
}
}
return max;
}
public void remove(String s, List<String> ans, int checkIndex, int deleteIndex, char[] par){
for(int count=0,i=checkIndex;i<s.length();i++){
if(s.charAt(i) == par[0]){ // '(' => 反转后->')'
count++;
}
if(s.charAt(i) == par[1]){ // ')
count--;
}
// i check计数<0的第一个位置
if(count < 0){
for(int j=deleteIndex;j<=i;j++){
if(s.charAt(j) == par[1] && (j == deleteIndex || s.charAt(j-1) != par[1])){
remove(
s.substring(0,j)+s.substring(j+1,s.length()),
ans, i, j, par
);
}
}
return;
}
}
String reversed = new StringBuffer(s).reverse().toString();
if(par[0] == '('){ // 避免重复调用
remove(reversed,ans,0,0,new char[]{')','('});
}else{
ans.add(reversed);
}
}
arr => 3 2 1 2 3 0 4 6 2 7
i => 0 1 2 3 4 5 6 7 8 9
dp => 1 1 1 2 3
end => 1 2 3
i = 0的时候，end[0] = 3
i = 1的时候，发现2 < 3，end就更新end[0] = 2
i = 2的时候，发现1 < 2，end就更新end[0] = 1
i = 3的时候，发现2 > 1，end就更新end[1] = 2，这时候end就扩张，依次类推
...
i = 5的时候，arr[5]=0，寻找end中大于等于的数的位置，就end[0]=1，然后修改
end[0]=0。
public int jump(int[] arr){
if(arr == null || arr.length == 0) return 0;
int step = 0;
int cur = 0;
int next = 0;
for(int i=0;i<arr.length;i++){
if(cur < i){
step++;
cur = next;
}
next = Math.max(next,i+arr[i]);
}
return step;
}
static class Info{
public int t;
public int f;
public Info(int t,int f){
this.t = t;
this.f = f;
}
}
// L...R上，一定有奇数个字符
// L位置以及R位置上的字符，非0即1，不能是逻辑字符
// 返回str[L...R]这一段，为true的方法数，和false的方法数
public Info process(char[] chrs,int left,int right){
int t = 0;
int f = 0;
if(left == right){
t = chrs[left] == '1'?1:0;
f = chrs[left] == '0'?1:0;
return new Info(t,f);
}else{
for(int i=left+1;i<right;i+=2){ // 当前是逻辑符号
Info leftInfo = process(chrs,left,i-1);
Info rightInfo = process(chrs,i+1,right);
int a = leftInfo.t;
int b = leftInfo.f;
int c = rightInfo.t;
int d = rightInfo.f;
switch (chrs[i]){
case '&':{
t += a * c;
f += b * c + b * d + a * d;
break;
}
case '|':{
t += a * c + a * d + b * c;
f += b * d;
break;
}
case '^':{ // 不同为1，相同为0
t += a * d + b * c;
f += a * c + b * d;
break;
}
}
}
}
return new Info(t,f);
}
// ans表示尝试的累加和
public double f(int N,int ans,int a,int b){
if(ans >= a && ans < b) return 1.0;
else if(ans >= b) return 0.0;
double p = 0.0;
for(int i=1;i<=N;i++){
p += f(N,ans+i,a,b);
}
return p / N;
}
public int process(int[] arr){
if(arr == null || arr.length == 0) return -1;
int size = arr.length;
int sum = 0;
for(int num:arr)
sum += num;
if(sum % size != 0) return -1;
int avg = sum / size;
int leftSum = 0;//当前i位置的左边和
int leftRest = 0;// 当前左边的剩余
int rightRest = 0;//当前i位置的右边和-(size-i-1)*avg
int ans = 0;
for(int i=0;i<arr.length;i++){
leftRest = leftSum - i * avg;
rightRest = (sum - leftRest - arr[i]) - (size - i - 1) * avg;
if(leftRest < 0 &&rightRest < 0){
ans = Math.max(ans,Math.abs(leftRest) + Math.abs(rightRest));
}else{
ans = Math.max(ans,Math.max(Math.abs(leftRest),Math.abs(rightRest)));
}
leftSum += arr[i];
}
return ans;
}
public class Problem28 {
static class LinkNode<K,V>{
K key;
V value;
LinkNode<K,V> pre; // 前驱节点
LinkNode<K,V> next; // 后继节点
public LinkNode(K key,V value){
this.key = key;
this.value = value;
this.pre = null;
this.next = null;
}
}
static class LinkList<K,V>{
LinkNode<K,V> head; // 头结点
LinkNode<K,V> tail; // 尾节点
public LinkList(){
head = null;
tail = null;
}
public void add(LinkNode<K,V> node){
if(head == null){
head = node;
tail = node;
}else{
node.pre = tail;
tail.next = node;
tail = node;
}
}
public void removeNode(LinkNode<K,V> node){
if(tail == node) return;
if(head == node){
head = head.next;
head.pre = null;
}else{
node.pre.next = node.next;
node.next.pre = node.pre;
}
node.next = null;
add(node);
}
// 链表达到了最大容量，就需要删除头结点
public LinkNode<K,V> removeHead() {
if(head == null) return null;
LinkNode<K,V> node = head;
if(head == tail){
head = null;
tail = null;
}else{
head = head.next;
head.pre = null;
node.next = null;
}
return node;
}
}
static class LRUCache<K,V>{
private final HashMap<K,LinkNode<K,V>> cache = new HashMap<>();
private final LinkList<K,V> linkList = new LinkList<>();
private final int capacity; // 最大容量
public LRUCache(int capacity){
this.capacity = capacity;
}
public void put(K key,V value){
if(cache.containsKey(key)){ // 存在就更新
LinkNode<K,V> node = cache.get(key);
node.value = value;
linkList.removeNode(cache.get(key));
}else{
if(cache.size() == capacity){
LinkNode<K,V> head = linkList.removeHead();
cache.remove(head.key);
}
LinkNode<K,V> node = new LinkNode<>(key,value);
cache.put(key,node);
linkList.add(node);
}
}
public V get(K key){
if(!cache.containsKey(key)) return null;
linkList.removeNode(cache.get(key));
return cache.get(key).value;
}
}
public static void main(String[] args) {
LRUCache<Integer,Integer> cache = new LRUCache<Integer,Integer>(3);
cache.put(1,2);
cache.put(2,3);
cache.put(3,4);
cache.put(4,5);
System.out.println(cache.get(2));
}
}
public int process(int[] nums){
int left = 0;
int right = nums.length-1;
int leftMaxHigh = nums[left];
int rightMaxHigh = nums[right];
int ans = 0;
while (left <= right){
if(leftMaxHigh <= rightMaxHigh){
ans += Math.max(0,leftMaxHigh - nums[left++]);
leftMaxHigh = Math.max(leftMaxHigh,nums[left]);
}else{
ans += Math.max(0,rightMaxHigh - nums[right--]);
rightMaxHigh = Math.max(rightMaxHigh,nums[right]);
}
}
System.out.println(ans);
return ans;
}
// 在arr[L...R]上一定要整出P份，合并最小代价，返回
// persum前缀累加和数组，用来快速求i...j的累加和
public static int process(int[] arr,int L,int R,int K,int P,int[] preSum){
// 在L...R上无法弄出P份
if(((R-L+1)%P) == (R-L+1)) return -1;
if(L == R){
return P==1?0:-1;
}
if(P == 1){
int result = process(arr,L,R,K,K,preSum);
if(result == -1) return -1;
else return result + preSum[R+1] - preSum[L];
}
// P > 1
int ans = Integer.MAX_VALUE;
for(int i=L;i<R;i++){
// L...i (1份) 和 i+1...R(P-1份)
int left = process(arr,L,i,K,1,preSum);
if(left == -1) continue;
int right = process(arr,i+1,R,K,P-1,preSum);
if(right == -1) continue;
int all = left + right;
ans = Math.min(ans, all);
}
return ans;
}
public static int process(int[] arr,int K){
int[] perSum = new int[arr.length+1];
if((arr.length-1) %(K-1) > 0) return -1;
for(int i=0;i<arr.length;i++) {
perSum[i + 1] = arr[i] + perSum[i];
}
return process(arr,0,arr.length-1,K,1,perSum);
}
public double myPow(double x, int n) {
if( n == 0) return 1;
boolean isNeg = n < 0;
int pow = Math.abs(n == Integer.MIN_VALUE?n+1:n);
double result = 1;
double t = x;
while (pow != 0){
if((pow & 1) != 0){
result *= t;
}
pow = pow >> 1;
t = t * t;
}
if(n == Integer.MIN_VALUE)
result *= x;
return n < 0?1D/result:result;
}
public int mySqrt(int x) {
if(x == 0) return x;
else if(x < 3) return 1;
long left = 1;
long right = x;
long mid = x;
long ans = 1;
while (left <= right){
mid = (right - left) / 2 + left;
if(mid*mid<=x){
left = mid + 1;
ans = mid;
}else{
right = mid - 1;
}
}
return (int)ans;
}
public static int maxProduct(int[] nums) {
int minResult = 1;
int maxResult = 1;
int result = Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++){
// 当前数 * dp[i-1]的结果（最大的数/最小的数）
int curMinResult = Math.min(nums[i],Math.min(maxResult*nums[i],minResult*nums[i]));
int curMaxResult = Math.max(nums[i],Math.max(maxResult*nums[i],minResult*nums[i]));
minResult = curMinResult;
maxResult = curMaxResult;
result = Math.max(result,maxResult);
}
return result;
}
public static int trailingZeroes(int n) {
int ans = 0;
int i = 1;
while (i*5 <= n) {
int j = i*5;
while (j != 0 && j % 5 == 0) {
ans++;
j /= 5;
}
i++;
}
return ans;
}
public static int trailingZeroes(int n) {
int ans = 0;
while (n != 0) {
n /= 5;
ans += n;
}
return ans;
}
public static int reverseBits(int n) {
n = (n >>> 16) | (n << 16);
n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
return n;
}
public static int countPrimes(int n) {
if(n < 3) return 0;
int ans = n/2;//所有偶数不需要，然后判断剩下的奇数
boolean[] flag = new boolean[n+1];
for(int i=3;i*i<=n;i+=2) {
if (flag[i])
continue;
for (int j = i; i*j <= n; j += 2) {
if (!flag[i*j]) {
flag[i*j] = true;
--ans;
}
}
}
return ans;
}
public int rob(int[] nums,int i,int[] dp,boolean head) {
// 当前i已经超过了nums长度，就说明无法偷取了
if(i >= nums.length || ( i >= nums.length - 1 && head && nums.length > 1)) return 0;
if(dp[i] != -1) return dp[i];
int ans = 0; // 当前偷取i号房屋的价值
// 当前i被偷取了，那么只能偷取i+2以后的房屋的价值
for(int j=i;j<nums.length;j++){
ans = Math.max(rob(nums,j+2,dp,head)+nums[i],ans);
}
dp[i] = ans;
return ans;
}
// 不能偷相邻房屋，第一个房屋与最后一个房屋是相邻的。
// 那就是需要判断以第一个数开头的，不能选择最后一个数
public int rob(int[] nums) {
int[] dp = new int[nums.length];
int ans = 0;
for(int i=0;i<3;i++){
Arrays.fill(dp,-1);
ans = i==0?Math.max(this.rob(nums, i,dp,true),ans):Math.max(this.rob(nums, i,dp,false),ans);
}
return ans;
}
# The knows API is already defined for you.
# return a bool, whether a knows b
# def knows(a: int, b: int) -> bool:
class Solution:
def findCelebrity(self, n: int) -> int:
#找到可能的名人，并用cur记录
cur=0
for i in range(1,n):
#若cur认识某人,则cur一定不是名人,因为名人不认识任何人
#若当前cur为名人，则cur将不会变动，因为cur不认识任何人
if knows(cur,i):
cur=i
#验证cur是否为名人
#验证cur是否为名人
for i in range(n):
if i==cur:
continue
#存在一个人不认识cur,则cur不是名人
if not knows(i,cur):
return -1
#cur认识某个人，则cur不是名人
if knows(cur,i):
return -1
return cur
// 判断是否为完全平方数
public boolean isPerfectSquare(int x) {
int y = (int) Math.sqrt(x);
return y * y == x;
}
public int numSquares(int n) {
if(isPerfectSquare(n)) return 1;
while (n % 4 == 0) n /= 4;
if(n % 8 == 7) return 4;
for(int i = 0;i*i<=n;i++) {
if(isPerfectSquare(n - i * i)) return 2;
}
return 3;
}
// 统计周围有几个1
public int neighbors(int[][] board, int i, int j) {
return f(board, i - 1, j - 1)
+ f(board, i - 1, j)
+ f(board, i - 1, j + 1)
+ f(board, i, j - 1)
+ f(board, i, j + 1)
+ f(board, i + 1, j - 1)
+ f(board, i + 1, j)
+ f(board, i + 1, j + 1);
}
public int f(int[][] board, int i, int j) {
return (i >= 0 && i < board.length && j < board[0].length && j >= 0 && (board[i][j] & 1) == 1) ? 1 : 0;
}
public void gameOfLife(int[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
int neighbors = this.neighbors(board, i, j);
if (neighbors == 3 || (board[i][j] == 1 && neighbors == 2)) {
board[i][j] |= 2;
}
}
}
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board[0].length; j++) {
board[i][j] >>= 1;
}
}
}
// 当前数组中，那一行比较合适
public int f(int[] arr){
int i = 0,j = arr.length-1;
int left = 0,right = 0;
int ans = 0;
while (i!=j){
if(arr[i]+left < arr[j]+right){
ans += arr[i] + left;
left += arr[i++];
}else{
ans += arr[j] + right;
left += arr[j--];
}
}
return ans;
}
public int minTotalDistance(int[][] matrix){
int[] rowOne = new int[matrix.length];
int[] colOne = new int[matrix[0].length];
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
if(matrix[i][j] == 1){
rowOne[i]++;
colOne[j]++;
}
}
}
return f(rowOne) + f(colOne);
}
public int process(int[] arr,int i,int rest,int x,int y){
if(rest <= 0) return 0;
// sum > 0 没搞定
if(i >= arr.length) return Integer.MAX_VALUE;
// 当前第i个位置不处理，交给下一个位置进行处理
int p1 = process(arr,i+1,rest,x,y);
// 当前第i个位置，进行处理，尝试使用x代价，将当前第i个数变成0
int p2 = process(arr,i+1,rest-arr[i],x,y);
if(p2 != Integer.MAX_VALUE) p2 += x; // 避免溢出，反而变成最小的
// 当前第i个位置，进行处理，尝试使用y代价，将当前第i个数变成相反数
int p3 = process(arr,i+1,rest-(arr[i]<<1),x,y) + y;
if(p3 != Integer.MAX_VALUE) p3 += x;
return Math.min(p1,Math.min(p2,p3));
}
public int process(int[] arr,int x,int y){
int sum = 0;
for (int num:arr)
sum += num;
return this.process(arr,0,sum,x,y);
}
public int subarraysWithKDistinct(int[] nums, int k) {
if (nums.length < 0 || nums.length > 2 * 1000 || k < 0 || k > nums.length) return 0;
// 统计词频
HashMap<Integer, Integer> lessCache = new HashMap<>(); // 记录k种字符
HashMap<Integer,Integer> equalCache = new HashMap<>(); // 记录后k-1种字符
// 当前有数为Y..X..i
int leftLess = 0; // k种字符的左边界，即第1种字符的开头位置
int leftEqual = 0;// k种字符的左边界，即第2种字符的开头位置
int right = 0;
int ans = 0;
while (right < nums.length){
// 记录词频
lessCache.put(nums[right],lessCache.getOrDefault(nums[right],0)+1);
equalCache.put(nums[right],equalCache.getOrDefault(nums[right],0)+1);
while (lessCache.size() == k){ // 主要是为了，能够让leftLess来到第2种字符的开始位置
lessCache.put(nums[leftLess],lessCache.get(nums[leftLess])-1);
if(lessCache.get(nums[leftLess]) == 0) lessCache.remove(nums[leftLess]);
leftLess++;
}
while (equalCache.size() > k){ // 主要是为了，能够让leftEqual来到第2种字符的开始位置，因为当前是k+1种字符，需要删除第1种
equalCache.put(nums[leftEqual],equalCache.get(nums[leftEqual])-1);
if(equalCache.get(nums[leftEqual]) == 0) equalCache.remove(nums[leftEqual]);
leftEqual++;
}
ans += leftLess - leftEqual; // 统计当前满足了k种字符全部数量，第2中字符开始位置leftLess以及第1种字符开始位置leftEqual
right++;
}
return ans;
}
public int process(int[] arr,int k,int x) {
Arrays.sort(arr);
int size = 0;
int[] needs = new int[arr.length];
int splits = 1; // 记录当前有多少堆
for (int i = 1; i < arr.length; i++) {
if(arr[i] - arr[i-1] > x){
needs[size++] = arr[i] - arr[i-1]; // 记录不符合的差值
splits++;
}
}
if(splits == 1 || x == 0 || k == 0) return splits;
Arrays.sort(needs,0,size); // 将堆之间的差值进行排序，优先选取差值小的
for(int i = 0;i<size;i++){
int need = (needs[i] - 1) / x; // 需要几块魔法积木
if(k >= need){
splits--;
k -= need;
}else{
break;
}
}
return splits;
}
houses = {1,13,26,100,500} i=0
heaters = {-4,-3,2,9,11,17,27} j=0
i = 0,j = 0，当前供暖器距离房屋有5个距离,j++
i = 0,j = 1，当前供暖器距离房屋有4个距离,j++
i = 0,j = 2，当前供暖器距离房屋有1个距离,j++
i = 0,j = 3，当前供暖器距离房屋有8个距离,i++,j--，发现没有j=2的时候好
i = 1,j = 2，当前供暖器距离房屋有11个距离,j++
i = 1,j = 3，当前供暖器距离房屋有4个距离,j++
i = 1,j = 4，当前供暖器距离房屋有2个距离,j++
i = 1,j = 5，当前供暖器距离房屋有4个距离,i++,j--
public int findRadius(int[] houses, int[] heaters) {
int i = 0,j = 0;
int maxDistance = Integer.MIN_VALUE;
Arrays.sort(houses);
Arrays.sort(heaters);
while (i < houses.length && j < heaters.length){
// 选取最佳的j
while (j + 1 < heaters.length && Math.abs(houses[i]-heaters[j]) >= Math.abs(houses[i]-heaters[j+1])){
j++;
}
// 当前第j个供暖器与第i个房屋的距离
int distance = Math.abs(houses[i]-heaters[j]);
maxDistance = Math.max(maxDistance,distance);
i++;
}
return maxDistance;
}
public int process(int[] arr,int k){
Arrays.sort(arr);
int n = arr.length;
int left = 0;
int right = arr[n - 1] - arr[0];
int mid = 0;
int rightest = -1;
while (left <= right){
mid = (left + right) / 2;
// <= mid的个数是不是小于k个
if(valid(arr,mid,k)){
rightest = mid;
left = mid + 1;
}else{
right = mid - 1;
}
}
return rightest + 1;
}
public boolean valid(int[] arr,int limit,int k){
int left = 0, right = 1;
int count = 0;
while (left < arr.length){
while (right < arr.length && arr[right] - arr[left] <= limit){
right++;
}
count += right - left - 1;
right = Math.max(right,++left);
}
return count < k;
}
class Solution {
public:
string findShortestWay(vector<vector<int>>& maze, vector<int>& ball, vector<int>& hole) {
int m = maze.size(), n = maze[0].size();
vector<vector<int>> dists(m, vector<int>(n, INT_MAX));
vector<vector<int>> dirs{{0,-1},{-1,0},{0,1},{1,0}};
vector<char> way{'l','u','r','d'};
queue<pair<int, int>> q;
unordered_map<int, string> u;
dists[ball[0]][ball[1]] = 0;
q.push({ball[0], ball[1]});
while (!q.empty()) {
auto t = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int x = t.first, y = t.second, dist = dists[x][y];
string path = u[x * n + y];
while (x >= 0 && x < m && y >= 0 && y < n && maze[x][y] == 0 && (x != hole[0] || y != hole[1])) {
x += dirs[i][0]; y += dirs[i][1]; ++dist;
}// while
if (x != hole[0] || y != hole[1]) {
x -= dirs[i][0]; y -= dirs[i][1]; --dist;
}
path.push_back(way[i]);
if (dists[x][y] > dist) {
dists[x][y] = dist;
u[x * n + y] = path;
if (x != hole[0] || y != hole[1]) q.push({x, y});
} else if (dists[x][y] == dist && u[x * n + y].compare(path) > 0) {
u[x * n + y] = path;
if (x != hole[0] || y != hole[1]) q.push({x, y});
}
}
}
string res = u[hole[0] * n + hole[1]];
return res.empty() ? "impossible" : res;
}
};
classSolution{
public: vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
voidcleanRoom(Robot& robot){
unordered_set<string> visited;
helper(robot, 0, 0, 0, visited);
}
voidhelper(Robot& robot, int x, int y, int dir, unordered_set<string>& visited){
robot.clean();
visited.insert(to_string(x) + "-"+ to_string(y));
for(int i = 0; i < 4; ++i) { // 4个方向
int cur = (i + dir) % 4, newX = x + dirs[cur][0], newY = y + dirs[cur][1];
if(!visited.count(to_string(newX) + "-"+ to_string(newY)) && robot.move()) {
helper(robot, newX, newY, cur, visited);
}
robot.turnRight();
}
// 保持不动，回到原来上一个位置
robot.turnRight(); // 跳转方向，回去
robot.turnRight();
robot.move();
robot.turnLeft(); // 保持原来状态
robot.turnLeft();
}
};
public int minEatingSpeed(int[] piles, int h) {
if (piles.length < 1 || piles.length > 10000) return 0;
if (!(piles.length <= h && h <= Math.pow(10, 9))) return 0;
int left = 1, right = Integer.MIN_VALUE;
for (int i = 0; i < piles.length; i++) {
right = Math.max(right, piles[i]);
}
int minH = right;
while (left < right) {
int mid = (left + right) / 2;
int ans = 0;
for (int i = 0; i < piles.length; i++) {
ans += (int) ((mid + piles[i] - 1) / mid);
}
if (ans <= h) {
minH = Math.min(minH, mid);
right = mid;
} else {
left = mid + 1;
}
}
return minH;
}
public int maxUncrossedLines(int[] nums1, int[] nums2, int i, int j, int[][] dp) {
if (i >= nums1.length || j >= nums2.length) return 0;
if (dp[i][j] != -1) return dp[i][j];
int ans = 0;
// 如果当前i和j相等
if (nums1[i] == nums2[j]) {
ans = maxUncrossedLines(nums1, nums2, i + 1, j + 1, dp) + 1;
} else {
int p1 = maxUncrossedLines(nums1, nums2, i + 1, j, dp);
int p2 = maxUncrossedLines(nums1, nums2, i, j + 1, dp);
ans = Math.max(p1, p2);
}
dp[i][j] = ans;
return ans;
}
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length][nums2.length];
for (int i = 0; i < nums1.length; i++)
Arrays.fill(dp[i], -1);
return this.maxUncrossedLines(nums1, nums2, 0, 0, dp);
}
public int maxUncrossedLines2(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length+1][nums2.length+1];
// 经过发现当前dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j])+nums1[i] == nums2[i]
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j])
dp[i+1][j+1] = dp[i][j] + 1;
else
dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
}
}
return dp[nums1.length][nums2.length];
}
public int[] avoidFlood(int[] rains) {
if (!(0<=rains.length && rains.length <= Math.pow(10,5))) return new int[]{};
int[] ans = new int[rains.length];
Arrays.fill(ans,1);
HashMap<Integer, Integer> record = new HashMap<>(); // 记录当前第rains[i]号湖，目前第i天有能够被填满几次
TreeSet<Integer> zero = new TreeSet<>();// 当前第i天，第rains[i]号湖，之前有几次可以抽干湖的机会
for (int i = 0; i < rains.length; i++) {
if (rains[i] == 0) { // 记录第i天拥有抽水能力
zero.add(i);
continue;
}
// 如果当前第rains[i]湖存在，需要抽干，不然就凉了
if (record.containsKey(rains[i])) {
int preRain = record.get(rains[i]); // 上一次的第rains[i]湖，第preRain天的时候是雨天
Integer cur = zero.higher(preRain);
if (cur == null) return new int[]{}; // 没找到有晴天
ans[cur] = rains[i]; // 记录抽干的几号湖
zero.remove(cur); // 移除第cur天-晴天
}
record.put(rains[i], i);// 记录第rains[i]号湖，在第i天下过雨
ans[i] = -1;
}
return ans;
}
public String process(int[] arr){
Arrays.sort(arr);
int sum = 0;
int index = -1;
StringBuilder s = new StringBuilder();
for(int i = arr.length-1;i >= 0;i--) {
sum += arr[i];
if(arr[i] % 3 == 1)
index = i;
s.append(arr[i]);
}
index = arr.length - index - 1;
int mod = sum % 3;
if(mod == 0) return s.toString();
int count = 0;
for(int i = 0 ;i < arr.length;i++){
if(arr[i] % 3 == mod){
s = new StringBuilder(s.substring(0, index) + s.substring(index + 1, s.length()));
break;
}
if(index == -1 && mod == 1 && count < 2 && arr[i] % 3 == 2){
s = new StringBuilder(s.substring(0, i) + s.substring(i + 1, s.length()));
count++;
}
if(count == 2) break;
}
return s.toString();
}
