有效的快递序列数目
有效的快递序列数目
一对一对添加,每次添加都是上一个问题的子问题,通过递推的方式,滚动数组
class Solution {
public int countOrders(int n){
int MOD=1000000007;
if(n==1){
return 1;
}
long res=1;
for(int i=2;i<=n;i++){
res=1L*(i%MOD*(2*i-1)%MOD)*res%MOD;
}
return (int)(res%MOD);
}
}
z字形输出
class Solution {
public String convert(String s, int numRows) {
String res="";
if(numRows==1){
return s;
}
for(int i=0;i<numRows;i++){
if(i==0||i==numRows-1){
for(int j=i;j<s.length();j+=2*numRows-2){
res+=s.charAt(j);
}
}else{
for(int j=i,k=2*numRows-2-i;j<s.length()||k<s.length();j+=2*numRows-2,k+=2*numRows-2){
if(j<s.length()){
res+=s.charAt(j);
}
if(k<s.length()){
res+=s.charAt(k);
}
}
}
}
return res;
}
}
使数组唯一的最小增量
使数组唯一的最小增量
将某一个重复元素a变为目标值 b 需要操作 b-a次
可以拆分成两个先后操作:先将重复元素减为0 -a 对重复元素计数
再将重复元素加到target +b
class Solution {
public int minIncrementForUnique(int[] nums) {
//方式一,将重复元素进行计数
int[] cnt=new int[200000];
for(int num:nums){
cnt[num]++;
}
int res=0;
int taken=0;
for(int i=0;i<200000;i++){
if(cnt[i]>=2){
taken+=(cnt[i]-1);
res-=((cnt[i]-1)*i);
} else if (taken > 0 && cnt[i] == 0) {
taken--;
res+=i;
}
}
return res;
}
}
方式二
class Solution {
public int minIncrementForUnique(int[] nums) {
Arrays.sort(nums);
int res=0;int taken=0;
for(int i=1;i<nums.length;i++){
if(nums[i]==nums[i-1]){
taken++;
res-=nums[i];
}else{
int cnt=Math.min(taken,nums[i]-1-(nums[i-1]+1)+1);
//将所有的元素
res+=cnt*(cnt+1)/2+cnt*(nums[i-1]);
taken-=(cnt);
}
}
//如果最后taken>0
if(taken>0){
res+=taken*(taken+1)/2+nums[nums.length-1]*taken;
}
return res;
}
}
全局倒置与局部倒置
全局倒置与局部倒置
检测是否存在非局部倒置
class Solution {
public boolean isIdealPermutation(int[] nums) {
int n=nums.length;
int minv=Integer.MAX_VALUE;
for(int i=n-1;i>=2;i--){
minv=Math.min(minv,nums[i]);
if(nums[i-2]>minv){
return false;
}
}
return true;
}
}
放置盒子
放置盒子
cur=1+(1+2)+(1+2+3)+(1+2+3+4)+....+(1+2+3+....+j) 对应的结果为1+2+3+…+j
如果对应的结果大于cur>n ,对应的放置方式
class Solution {
public int minimumBoxes(int n){
//通过滚动变量进行计数
int cur=0;int i=0;int j=0;
while(cur<n){
j++;
i+=j;
cur+=i;
}
if(cur==n){
return i;
}
//对应的cur>n
cur-=i;
i-=j;
j=0;
while(cur<n){
j++;
cur+=j;
}
return i+j;
}
}
绝对值表达式的最大值
绝对值表达式的最大值
最后结果一定是大于等于0
对于任意两个点之间的曼哈顿距离,一定是这8种情况中的最大值,其他的结果可能不存在,但是也绝对不可能最为最后结果出现
class Solution {
int[][] dir=new int[][]{{1,1,1},{1,1,-1},{1,-1,1},{-1,1,1},{-1,-1,-1},{-1,-1,1},{-1,1,-1},{1,-1,-1}};
public int maxAbsValExpr(int[] arr1, int[] arr2) {
int[] maxv=new int[8];
Arrays.fill(maxv,Integer.MIN_VALUE);
int[] minv=new int[8];
int n=arr1.length;
for(int k=0;k<8;k++){
for(int i=0;i<n;i++){
maxv[k]=Math.max(maxv[k],arr1[i]*dir[k][0]+arr2[i]*dir[k][1]+i*dir[k][2]);
}
}
int res=0;
for(int k=0;k<8;k++){
for(int i=0;i<n;i++){
res=Math.max(res,maxv[k]-(arr1[i]*dir[k][0]+arr2[i]*dir[k][1]+i*dir[k][2]));
}
}
return res;
}
}
方式二:对应的八种情况,其中存在两两互为相反数的情况,所以实际上只有四对
class Solution {
int[][] dir=new int[][]{{1,1,1},{1,1,-1},{1,-1,1},{-1,1,1}};
public int maxAbsValExpr(int[] arr1, int[] arr2) {
int[] maxv=new int[4];
Arrays.fill(maxv,Integer.MIN_VALUE);
int[] minv=new int[4];
int n=arr1.length;
for(int k=0;k<4;k++){
for(int i=0;i<n;i++){
maxv[k]=Math.max(maxv[k],arr1[i]*dir[k][0]+arr2[i]*dir[k][1]+i*dir[k][2]);
}
}
int res=0;
for(int k=0;k<4;k++){
for(int i=0;i<n;i++){
res=Math.max(res,maxv[k]-(arr1[i]*dir[k][0]+arr2[i]*dir[k][1]+i*dir[k][2]));
res=Math.max(res,(arr1[i]*dir[k][0]+arr2[i]*dir[k][1]+i*dir[k][2])-maxv[k]);
}
}
return res;
}
}
翻转子数组得到最大的数组和
原问题可以转为曼哈顿距离,通过暴力开绝对值方式只需在对应的所有情况取最大值
class Solution {
public int maxValueAfterReverse(int[] nums) {
//计算未翻转的情况
int res=0;
int n=nums.length;
for(int i=0;i<n-1;i++){
res+=Math.abs(nums[i]-nums[i+1]);
}
//最大变化值
int maxv=0;
for(int i=0;i<n;i++){
if(i!=n-1){
maxv=Math.max(maxv,Math.abs(nums[0]-nums[i+1])-Math.abs(nums[i]-nums[i+1]));
}
if(i!=0){
maxv=Math.max(maxv,Math.abs(nums[n-1]-nums[i-1])-Math.abs(nums[i]-nums[i-1]));
}
}
int[] dx={1,1,-1,-1};
int[] dy={1,-1,1,-1};
for(int k=0;k<4;k++){
PriorityQueue<Integer> top=new PriorityQueue<Integer>((a,b)->b-a);
PriorityQueue<Integer> low=new PriorityQueue<Integer>((a,b)->a-b);
for(int j=0;j+1<n;j++){
int a=dx[k]*nums[j];
int b=dy[k]*nums[j+1];
int cur=Math.abs(nums[j]-nums[j+1]);
top.offer(a+b-cur);
low.offer(a+b+cur);
}
int first=top.peek();
int second=low.peek();
maxv=Math.max(maxv,first-second);
}
return res+maxv;
}
}
子数组按位或操作
子数组按位或操作
子数组按位或可以的到的最多不同数
class Solution {
public static int subarrayBitwiseORs(int[] arr) {
//维护以arr[i]结尾的所有或结果
int res=0;
Set<Integer> set=new HashSet<Integer>();
Set<Integer> ans=new HashSet<>();
for(int i=0;i<arr.length;i++){
Set<Integer> set1=new HashSet<>();
for (Integer v : set) {
set1.add(arr[i]|v);
}
set1.add(arr[i]);
ans.addAll(set1);
set=set1;
}
return ans.size();
}
}
方式二:通过剪枝方式,对于之前元素最多32个
public int subarrayBitwiseORs(int[] arr) {
Set<Integer> set=new HashSet<>();
for(int i=0;i<arr.length;i++){
set.add(arr[i]);
for(int j=0;j<i;j++){
if((arr[i]&arr[j])==arr[i]){//表示当前arr[i]已经包含在arr[j]和之前所有的数中
break;//前面的所有元素都是之前与arr[j]进行异或得到的
}
arr[j]|=arr[i];
set.add(arr[j]);
}
}
return set.size();
}
好子数组最大分数
好子数组最大分数
包含nums[k]区间的最小值小于等于nums[k],每次向左或向右扩展一个位置,只需要保证最小值尽量大,
每次都选择左右更大的方向扩展
class Solution {
public int maximumScore(int[] nums, int k) {
int n=nums.length;
int ans=nums[k];
int left=k;int right=k;
int minv=nums[k];
while(left-1>=0||right+1<n){
if(right+1>=n||(left-1>=0&&nums[left-1]>nums[right+1])){
left--;
minv=Math.min(minv,nums[left]);
}else{
right++;
minv=Math.min(minv,nums[right]);
}
ans=Math.max(ans,(right-left+1)*minv);
}
return ans;
}
}
数组的最小偏移量
数组最小偏移量
现将所有的奇数变成偶数,维护最小值
然后单向将最大偶数/2缩小最大值,维护最小值,计算最小偏移量
直到最大数不是偶数,说明最大值不能缩小
对于最小奇数是否能变大,最小奇数一定是之前最大偶数变来的,所以之前计算过,所以最小奇数不能变大
class Solution {
public int minimumDeviation(int[] nums){
PriorityQueue<Integer> queue=new PriorityQueue<Integer>((a,b)->b-a);
//将所有的数都变成偶数,维护最小值
int minv=Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
if(nums[i]%2!=0){
nums[i]*=2;
}
queue.offer(nums[i]);
minv=Math.min(minv,nums[i]);
}
int res=queue.peek()-minv;
while(queue.peek()%2==0){
int num=queue.poll()/2;
queue.offer(num);
minv=Math.min(minv,num);
res=Math.min(res,queue.peek()-minv);
}
return res;
}
}
有序队列
有序队列
对于前k个字符,每次取一个字符添加到末尾,可以得到的最小字典序字符串
当k==1,相当于环形数组,从最小字典序字符断开
当k>=2,可以交换任意相邻字符,相当于冒泡排序
public String orderlyQueue(String s, int k) {
if(k==1){
String ans=s;
for(int i=0;i<s.length();i++){
String t=s.substring(i)+s.substring(0,i);
if(t.compareTo(ans)<0){
ans=t;
}
}
return ans;
}else{
char[] chs=s.toCharArray();
Arrays.sort(chs);
return new String(chs);
}
}
所有子序列宽度之和
所有子序列宽度之和
数组的顺序不会对最后结果造成影响
class Solution {
public int sumSubseqWidths(int[] nums) {
int MOD=1000000007;
int n=nums.length;
Arrays.sort(nums);
//预处理所有幂次
long[] pow2=new long[n];
pow2[0]=1;
for(int i=1;i<n;i++){
pow2[i]=pow2[i-1]*2%MOD;
}
long ans=0;
for(int i=0;i<n;i++){
ans=(ans+(pow2[i]-pow2[n-1-i])*nums[i])%MOD;
}
return (int)ans;
}
}
数组中元素的最小非零乘积
数组中元素的最小非零乘积
要想使乘积最小,应该使一部分尽可能小,一部分尽可能大,对于交换1,2,3,4,5,6....,2^p-2,2^p-1;存在1+2^p-2=2+2^p-3=3+2^p-4=....=2^p-1
但是要非负积,所以最小值至少为1 最后(2^p-2)有(2^p-1)/2对 剩下一个2^p-1
class Solution {
long MOD=(long)1000000007;
public int minNonZeroProduct(int p) {
return (int)(((1L<<p)-1)%MOD*pow((1L<<p)-2,(1L<<(p-1))-1)%MOD);
}
//快速幂
public long pow(long x,long n){
x%=MOD;
long res=1L;
while(n>0){
if((n&1)!=0){
res=(res*x)%MOD;
}
x=(x*x)%MOD;
n>>=1;
}
return res;
}
}
//快速幂
public int pow(int x,int n){
int res=1;
while(n>0){
if((n&1)!=0){
res*=x;
}
x=x*x;
n>>=1;
}
return res;
}
统计字典序元音字符串的数目
构造长度为n的字符串,要求对应的字符字典序不递减,通过给定字符构造指定长度的字符串
public int countVowelStrings(int n) {
return (n+4)*(n+3)*(n+2)*(n+1)/24;
}
交换字符使得字符串相同
class Solution {
public int minimumSwap(String s1, String s2) {
//统计对应的位i字符类型,所有的字符类型 xy xx yx yy
int cnt1=0;int cnt2=0;
for(int i=0;i<s1.length();i++){
if(s1.charAt(i)=='x'&&s2.charAt(i)=='y'){
cnt1++;
}
if(s1.charAt(i)=='y'&&s2.charAt(i)=='x'){
cnt2++;
}
}
//如果对应的字符类型不为偶数
if((cnt1+cnt2)%2!=0){
return -1;
}
return cnt1/2+cnt2/2+2*(cnt1%2);
}
}
行相等的最少多米诺旋转
class Solution {
public int minDominoRotations(int[] tops, int[] bottoms) {
//最终结果之只能是tops[0] bottom[0]中的一个
int res=check(tops,bottoms,tops[0]);
if(res!=-1){
return res;
}else{
return check(tops,bottoms,bottoms[0]);
}
}
public int check(int[] a,int[] b,int target){
int res_a=0;int res_b=0;
for(int i=0;i<a.length;i++){
if(a[i]!=target&&b[i]!=target){
return -1;
}else if(a[i]!=target){
res_a++;
}else if(b[i]!=target){
res_b++;
}
}
return Math.min(res_a,res_b);
}
}
Cpu调度平均等待时间
平均等待时间
通过start表示上一个任务结束时间,初始时上一个任务结束时间即第一个任务开始时间,任务到达时间
class Solution {
public double averageWaitingTime(int[][] customers) {
//cpu调度,先来先服务
int n=customers.length;
//上一个任务的开始时间
int start=customers[0][0];//start表示上一个任务的结束时间
long res=0;
for(int[] customer:customers){
start=Math.max(start,customer[0])+customer[1];
res+=start-customer[0];
}
return 1.0*res/n;
}
}
通过一次遍历判断回文串
class Solution {
public boolean checkPalindromeFormation(String a,String b){
return check(a,b)||check(b,a);
}
public boolean check(String a,String b){
int start=0;int end=a.length()-1;
while(start<end){
if(a.charAt(start)==b.charAt(end)){
start++;end--;
}else{
break;
}
}
if(start>=end){
return true;
}
while(start<end){
if(a.charAt(start)==a.charAt(end)){
start++;end--;
}else{
break;
}
}
if(start>=end){
return true;
}
while(start<end){
if (b.charAt(start) == b.charAt(end)) {
start++;end--;
}else{
break;
}
}
if(start>=end){
return true;
}
return false;
}
}
和可以被k整除的子数组
class Solution {
public int subarraysDivByK(int[] nums, int k) {
//通过hashMap进行计数
Map<Integer,Integer> cnt=new HashMap<Integer,Integer>();
//对于整除,当前前缀及符合条件
cnt.put(0,1);
int sum=0;int ans=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
int remain=(sum%k+k)%k;
int count=cnt.getOrDefault(remain,0);
ans+=count;
cnt.put(remain,count+1);
}
return ans;
}
}
使数组和能被p整除
通过hashMap记录前缀%p出现的次数,相对于两数之和通过map存储对应的为%p 对应的最后要保证为正数,所以需要(subMod%p-target%p+p)%p
使数组和能被p整除
class Solution {
public static int minSubarray(int[] nums,int p){
int n=nums.length;
long sum=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
}
if(sum<p){
return -1;
}
long target=sum%p;
if(target==0){
return 0;
}
//通过前缀和+hashMap进行优化判断是否存在和为target子数组
long[] prefix=new long[n+1];
for(int i=0;i<n;i++){
prefix[i+1]=prefix[i]+nums[i];
}
Map<Long,Integer> cnt=new HashMap<Long,Integer>();
int res=n;
long subMod=0;
for(int i=0;i<=n;i++){
subMod=prefix[i]%p;
long t=(subMod-target+p)%p;
if(cnt.containsKey(t)){
res=Math.min(res,i-cnt.get(t));
}
cnt.put(subMod,i);
}
if(res==n){
return -1;
}
return res;
}
}
k和数对的最大数目
k和数对的最大数目
通过hashMap进行优化,类似于两数之和
class Solution {
public int maxOperations(int[] nums, int k) {
Map<Integer,Integer> cnt=new HashMap<Integer,Integer>();
int res=0;
for(int i=0;i<nums.length;i++){
if(cnt.containsKey(k-nums[i])){
res++;
//将对应的计数减一
cnt.put(k-nums[i],cnt.get(k-nums[i])-1);
//如果对应的计数为0,直接删除
if(cnt.get(k-nums[i])==0){
cnt.remove(k-nums[i]);
}
}else{
//将对应的当前数加入集合
cnt.put(nums[i],cnt.getOrDefault(nums[i],0)+1);
}
}
return res;
}
}
数的平方等于两数的乘积的方法数
数的平方等于两数的乘积的方法数
如果对应的乘积超过int范围,可以将对应的乘法转为对应的除法
同理,可以将对应的加法转为对应的减法
class Solution {
public int numTriplets(int[] nums1,int[] nums2){
Map<Integer,Integer> cnt1=new HashMap<>();
Map<Integer,Integer> cnt2=new HashMap<>();
for(int i=0;i<nums1.length;i++){
cnt1.put(nums1[i],cnt1.getOrDefault(nums1[i],0)+1);
}
for(int i=0;i<nums2.length;i++){
cnt2.put(nums2[i],cnt2.getOrDefault(nums2[i],0)+1);
}
return getRes(cnt1,cnt2)+getRes(cnt2,cnt1);
}
public int getRes(Map<Integer,Integer> cnt1,Map<Integer,Integer> cnt2){
int res=0;
Set<Integer> set1=cnt1.keySet();
Set<Integer> set2=cnt2.keySet();
for(int num:set1){
int count1=cnt1.get(num);
long square=(long)num*num;//所有数据平方对应的可以通过long进行接收
//对于
for(int num1:set2){
if(square%num1==0){
int num2=(int)(square/num1);
if(num1==num2){
int count2=cnt2.get(num2);
res+=count1*count2*(count2-1)/2;
}else if(num1<num2&&cnt2.containsKey(num2)){
int count2=cnt2.get(num1);
int count3=cnt2.get(num2);
res+=count1*count2*count3;
}
}
}
}
return res;
}
}
数组中重复出现的数据
对于当前数据,反复进行交换,最后将所有的数据放到应该放的位置
位置i数nums[i]应该放的位置对应的元素nums[nums[i]-1]如果不是该数,进行交换
最后遍历每一个位置i 判断对应的元素nums[i]-1是否应该放在当前位置i
class Solution {
public List<Integer> findDuplicates(int[] nums) {
for(int i=0;i<nums.length;i++){
while(nums[i]!=nums[nums[i]-1]){
swap(nums,i,nums[i]-1);
}
}
List<Integer> res=new ArrayList<Integer>();
for(int i=0;i<nums.length;i++){
if(nums[i]-1!=i){
res.add(nums[i]);
}
}
return res;
}
public void swap(int[] nums,int i,int j){
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
自定义排序规则
自定义排序规则
如果对应的长度相等,排序字典序,如果对应的长度不相等,比较长度
class Solution {
public String kthLargestNumber(String[] nums, int k) {
Arrays.sort(nums,(a, b)->a.length()==b.length()? a.compareTo(b):a.length()-b.length());
return nums[nums.length-k];
}
}
翻转列得到的最大等行数
翻转列得到的最大等行数
所有的相等行都可以通过若干次翻转变为全0或者是全1的行
如果两行是互补的,其中一行通过反转变成全行相等之后,与之互补的行也会同时变为全行相等
class Solution {
public int maxEqualRowsAfterFlips(int[][] matrix) {
//将每一行相同行与相反行通过hashMap进行个数统计
Map<String,Integer> cnt=new HashMap<String,Integer>();
int res=0;
for(int i=0;i<matrix.length;i++){
String a="";String b="";
for(int j=0;j<matrix[0].length;j++){
a+=String.valueOf(matrix[i][j]);
b+=String.valueOf(1^matrix[i][j]);
}
cnt.put(a,cnt.getOrDefault(a,0)+1);
cnt.put(b,cnt.getOrDefault(b,0)+1);
res=Math.max(res,Math.max(cnt.get(a),cnt.get(b)));
}
return res;
}
}
交换一次的先前排列
交换一次的先前排列
对于一个序列,如果需要交换两个元素得到字典序,小于原序列的最大序列,只需要从后往前进行找第一个小于a[i]的最大元素进行一次交换即可
如果需要大于原序列最小的序列,只需要从后往前大于a[i]的最小元素进行交换
class Solution {
public int[] prevPermOpt1(int[] arr) {
//从右往左找,第一个逆序对,将小于arr[i]最大的元素进行交换
int n=arr.length;
for(int i=n-2;i>=0;i--){
int maxv=Integer.MIN_VALUE;
int index=i;
boolean flag=false;
for(int j=i+1;j<n;j++){
if(arr[i]>arr[j]){
flag=true;
if(arr[j]>maxv){
index=j;
maxv=arr[j];
}
}
}
if(flag){
//交换,直接返回
swap(arr,index,i);
break;
}
}
return arr;
}
public void swap(int[] nums,int i,int j){
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
从字母重建数字
环绕字符串中唯一的子字符串
环绕字符串中的唯一的子字符串
将问题转化为对应的统计p字符串对应的每一个字符结尾的最长长度
class Solution {
public int findSubstringInWraproundString(String p) {
//连续子串数量等于一改字符结尾的最长长度===对应的字串个数
int n=p.length();
int count=0;
int[] cnt=new int[26];
for(int i=0;i<n;i++){
if(i>0&&(p.charAt(i)-p.charAt(i-1)-1)%26==0){
count++;
}else{
count=1;
}
//将对应的长度
cnt[p.charAt(i)-'a']=Math.max(cnt[p.charAt(i)-'a'],count);
}
//将所有的字符结尾长度累加
int res=0;
for(int i=0;i<cnt.length;i++){
res+=cnt[i];
}
return res;
}
}
最大方阵和
class Solution {
public long maxMatrixSum(int[][] matrix) {
//如果有奇数个负数,则最终会有一个负数,直接选择最小的元素
//如果有偶数个负数,最终所有的元素会成为正数
int n=matrix.length;int m=matrix[0].length;
long sum=0;int cnt=0;int minv=Integer.MAX_VALUE;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(matrix[i][j]<0){
cnt++;
}
minv=Math.min(minv,Math.abs(matrix[i][j]));
sum+=Math.abs(matrix[i][j]);
}
}
if(cnt%2==0){
return sum;
}else{
return sum-=2*minv;
}
}
}
矩阵中最大的三个菱形和
矩阵中最大的三个菱形和
二维前缀和,对于斜对角线维护前缀和
class Solution {
public int[] getBiggestThree(int[][] grid) {
//通过存储写对角线前缀和
int n=grid.length;int m=grid[0].length;
int[][] sum1=new int[n+10][m+10];
int[][] sum2=new int[n+10][m+10];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
sum1[i][j]=sum1[i-1][j-1]+grid[i-1][j-1];
sum2[i][j]=sum2[i-1][j+1]+grid[i-1][j-1];
}
}
Set<Integer> set=new TreeSet<Integer>((a,b)->b-a);
//对于所有的节点通过枚举菱形中心与边长
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
set.add(grid[i-1][j-1]);
for(int k=1;i-k>=1&i+k<=n&&j-k>=1&&j+k<=m;k++){
int a=sum2[i][j-k]-sum2[i-k][j];
int b=sum2[i+k][j]-sum2[i][j+k];
int c=sum1[i+k][j]-sum1[i][j-k];
int d=sum1[i][j+k]-sum1[i-k][j];
int re=a+b+c+d-grid[i+k-1][j-1]+grid[i-k-1][j-1];
set.add(re);
}
}
}
int[] res=new int[set.size()];
int index=0;
Iterator it=set.iterator();
while(it.hasNext()){
res[index++]=(int)it.next();
}
return Arrays.copyOf(res,Math.min(3,index));
}
}