目錄
力扣.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
