剑指offer

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

---

字符串

//字符串向字符数组的转化

char[] ch = str.toCharArray();

//拷贝一部分字符数组

ch = Arrays.copyOfRange(ch,1,ch.length);

整形的最大最小值

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)快速幂

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访问后序遍历数组，然后依次判断

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原数组中，而使用回溯算法超出内存限制

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进行比较

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;
}