力扣.1471数组的k个最强值,力扣.1471数组的k个最强值力扣1576.替换所有的问号力扣1419.数青蛙​编辑力扣300.最长递增子序列

目录

力扣.1471数组的k个最强值

力扣1576.替换所有的问号

力扣1419.数青蛙​编辑

力扣300.最长递增子序列

---

力扣.1471数组的k个最强值

class Solution {public static int[] getStrongest(int[] arr,int k) {if(k==arr.length){return arr;}int []ret=new int[k];int n=arr.length;//归并排序，我只是想练一下，你直接Arrays.sort()即可merge(arr,0,n-1);//数组已经有序int mid=arr[(n-1)/2];int jj=0;int i=0;int j=n-1;while(i<j&&k>0){//看题中的条件while((k>0&&i<j)&&(Math.abs(arr[i]-mid)>Math.abs(arr[j]-mid)||(Math.abs(arr[i]-mid)==Math.abs(arr[j]-mid)&&arr[i]>arr[j]))){k--;ret[jj++]=arr[i++];}//注意此时涉及到一个情况，假如k还剩一个，然后一个7还有一个7两个都是中位数，事例3.这个情况，就随便让那个一个相等即可。我们选择让后面的相同，因为一般后面的更大一点while((k>0&&i<j)&&(Math.abs(arr[i]-mid)<Math.abs(arr[j]-mid)||(Math.abs(arr[i]-mid)==Math.abs(arr[j]-mid)&&arr[i]<=arr[j]))){//找到一个数字，再进行插入k--;ret[jj++]=arr[j--];}}return ret;}
public static void merge(int[]arr,int left,int right){if(left>=right)return ;int mid=(left+right)/2;merge(arr,left,mid);merge(arr,mid+1,right);//数组两个有序之后，合并两个有序数组int cur1=left;int cur2=mid+1;int []tmp=new int[right-left+1];int k=0;while(cur1<=mid&&cur2<=right){if(arr[cur1]<=arr[cur2])tmp[k++]=arr[cur1++];else tmp[k++]=arr[cur2++];}while(cur1<=mid) tmp[k++]=arr[cur1++];while(cur2<=right) tmp[k++]=arr[cur2++];k=0;for(int i=left;i<=right;i++){arr[i]=tmp[k++];}}
}

模拟算法流程->转化成代码

力扣1576.替换所有的问号

没什么操作，挺简单的想法

但是要补充一些知识:

单引号:表示的是字符的含义

双引号:表示的是字符串的含义

此时这里需要用到的是单引号

String.valueOf()

转化成字符串。

 public String modifyString(String s) {char[]a=s.toCharArray();for(int i=0;i<a.length;i++){if(a[i]=='?'){for(char a1='a';a1<='z';a1++){if((i==0||a1!=a[i-1])&&(i==a.length-1||a1!=a[i+1])){a[i]=a1;break;}}}}return String.valueOf(a);}

力扣1419.数青蛙

用下标模拟哈希表进行下标映射，基本操作，剩下慢慢打表即可。

class Solution {public static int minNumberOfFrogs(String croakOfFrogs) {int count=0;int []a=new int[26];for(int i=0;i<croakOfFrogs.length();i++){int tmp=croakOfFrogs.charAt(i)-'a';if(tmp==2){if(a[10]!=0){a[10]--;a[2]++;}else{a[2]++;}}else if(tmp==17){if(a[2]!=0){a[2]--;a[17]++;}else{return -1;}}else if(tmp==14){if(a[17]!=0){a[17]--;a[14]++;}else{return -1;}}else if(tmp==0){if(a[14]!=0){a[14]--;a[0]++;}else{return -1;}}else if(tmp==10){if(a[0]!=0){a[0]--;a[10]++;}else{return -1;}}}if(a[10]==0){return -1;}if(a[2]!=0){return -1;}return a[10];}
}

力扣300.最长递增子序列

1.状态表示

dp[i]:以i位置元素为结尾的所有子序列中，最长递增子序列的长度

状态转移方程

dp[i]=max(dp[j]+1)(j<i&nums[j]<nums[i])

我们仅关心你的最后一个元素是谁

2.贪心优化

仅存你的最后一个元素

存什么:所有长度为x的递增子序列中，最后一个元素的最小值

存哪里:所有大于等于nums[i]的最小值的位置

利用二分可以进行优化，快速定位插入位置

来个x