##这是我的第一篇博客:😄


字符串

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队列

  • Queue的实现类有LinkedList和PriorityQueue,第一个最常用;

  • 压入元素:add(), offer()

  • 弹出元素:remove(), poll()

  • 获取头元素:element(), peek()

​ 区别:容量为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) {
// double res=1.0;
// int tmp = n;
// if(n<0){
// tmp = -n;
// }
// for(int i=1; i<=tmp; i++){
// res *= x;
// }
// if(n>0){
// return res;
// }
// else{
// return (double)1/res;
// }
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;
}
//指数除以2
power = power >> 1;
//底数乘2
base = base*base;
}
return res;
}
}

验证二叉搜索树的后序遍历序列(反向构建BST)

比较巧妙的是,用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];
}
}

LCR 164. 破解闯关密码

快速排序+自定义比较器,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;
}