##这是我的第一篇博客:😄
字符串
1 2 3 4 5 6 7
|
char[] ch = str.toCharArray();
ch = Arrays.copyOfRange(ch,1,ch.length);
|
整形的最大最小值
1 2
| Integer.MAX_VALUE Integer.MIN_VALUE
|
LinkedList
LinkedList stack1;
LinkedList实现了Deque接口,所以Stack能做的事LinkedList都能做,其本身结构是个双向链表,扩容消耗少
模拟实现栈,使用ArrayList的效率大于使用LinkedList 利用单调递减队列实现滑动窗口最大值: 类似于min栈中的最小值,有意思的是:初始化的状态是i=1-k,j=0
Queue队列
区别:容量为0的时候,element()会抛出异常,peek()返回null
StringBuffer
与String类型不同,支持字符串的修改
LCR 134. Pow(x, n)快速幂
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| class Solution { public double myPow(double x, int n) {
long b = n; if(n<0){ b=-b; x=1/x; } double res = cal(x, b); return res;
} public double cal(double base, long power){ double res=1.0; while(power > 0){ if((power & 1) == 1){ res*=base; } power = power >> 1; base = base*base; } return res; } }
|
比较巧妙的是,用end访问后序遍历数组,然后依次判断
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
| public class VerifyTreeOrder {
int end; int[] tmp; public boolean verifyTreeOrder(int[] postorder) { end = postorder.length-1; tmp = postorder.clone(); build(Integer.MIN_VALUE, Integer.MAX_VALUE); return end<0; }
public void build(int min,int max){ if(end<0)return; int rootVal = tmp[end]; if(rootVal >= max || rootVal <= min){ return; } end--; build(rootVal,max); build(min,rootVal); } }
|
LCR 170. 交易逆序对的总数
利用归并排序获得逆序对,重点在于merge的部分以及最后将temp数组中排好序的数据覆盖nums原数组中,而使用回溯算法超出内存限制
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
| int nums[]; int result=0; public int reversePairs(int[] record){ nums = record.clone(); mergeSort(0,nums.length-1); return result; }
public void mergeSort(int left, int right){ if(left >= right)return; int mid = (left+right)/2; mergeSort(left,mid); mergeSort(mid+1,right); merge(left,mid,right); }
public void merge(int left,int mid,int right){ int[] temp = new int[right-left+1]; int t=0; int i; int j; for(i=left,j=mid+1;i<=mid&&j<=right;){ if(nums[i]<=nums[j]){ temp[t++]=nums[i++]; }else{ result+=(mid-i+1); temp[t++]=nums[j++]; } } if(i<=mid){ for(int k=i;k<=mid; k++){ temp[t++]=nums[k]; } } if(j<=right){ for(int k=j;k<=right; k++){ temp[t++]=nums[k]; } } for(int k=0; k<temp.length; k++){ nums[k+left] = temp[k]; } }
|
快速排序+自定义比较器,pivot的 值变成了String[left],因此每次都要和temp进行比较
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
| String[] str; public String crackPassword(int[] password) { StringBuilder res = new StringBuilder(); str = new String[password.length]; for(int i=0; i<password.length; i++){ str[i]= String.valueOf(password[i]); } quickSort(0,str.length-1); for(String s:str){ res.append(s); } return res.toString();
} public void quickSort(int left, int right){ if(left < right){ int pivot = partition(left,right); quickSort(left,pivot-1); quickSort(pivot+1,right); } }
public int partition(int left, int right){ String temp = str[left]; while(left < right){ while(left < right && (str[right]+temp).compareTo(temp+str[right])>=0)right--; str[left] = str[right]; while(left < right && (str[left]+temp).compareTo(temp+str[left])<=0)left++; str[right] = str[left]; } str[left] = temp; return left; }
|