587. 安装栅栏 / 剑指 Offer II 014. 字符串中的变位词

587. 安装栅栏【困难题】【每日一题】

思路：

直接看题解，理解了半天~ 写在注释里了，但愿我下次看见还记得今天怎么理解的…

代码：

class Solution {
    
    public int[][] outerTrees(int[][] trees) {
    
        int n = trees.length;
        if (n < 4){
    //树小于4时，所有的树都在边界，必须被围住，于是直接返回trees
            return trees;
        }
        //对trees先按 x 坐标排序，x坐标相等时按 y 坐标排序 (均为升序)
        Arrays.sort(trees,(a,b)->(a[0] == b[0] ? a[1]-b[1] : a[0]-b[0]));
        int tp = 0;//tp表示栈顶元素下标
        int[] stk = new int[n+10];//通过stk数组实现栈功能，stk中存入的是tree在trees中的下标
        boolean[] vis = new boolean[n+10];//vis数组用于标记当前这个位置的树是否需要处在边界，即是否需要使用
        stk[++tp] = 0;//向栈中压入第一个tree，tp现在为1
        //trees数组排好序之后，第一个tree必然要处在边界，因此从第2个tree开始遍历
        //画第一部分凸包,即下半部分（以trees左右端点连线为界）
        for (int i = 1; i < n; i++) {
    //按顺序遍历所有的tree
            int[] c = trees[i];//用c表示当前树坐标
            while (tp >= 2){
    //当栈里有超过两个元素时，才需要判断当前树是否在边界
                //取出栈顶树坐标 b，以及栈顶的上一个树坐标 a
                int[] a = trees[stk[tp-1]], b = trees[stk[tp]];
                //判断向量ac是否在ab左边
                if (getArea(a,b,c) < 0){
    
                    //ac在ab右边，那么说明c更符合边界条件，需要废弃b节点
                    //于是将此时栈顶节点 b 废弃，即在vis中对应 b 的下标位置置为false，同时栈顶下标自减1，表示移除栈顶下标
                    vis[stk[tp--]] = false;
                }else {
    
                    //ac在ab左边，那么退出while循环处理将当前树压入栈即可
                    break;
                }
            }
            stk[++tp] = i;//向栈中压入当前树的下标
            vis[i] = true;//标记当前树已被选为边界
        }
        int size = tp;//记录第一部分凸包已经有几个树
        //画第二部分凸包,即凸包的上半部分
        for (int i = n-1; i >= 0 ; i--) {
    
            if (vis[i]){
    //如果当前树已被使用，则直接去判断下一棵树
                continue;
            }
            int[] c = trees[i];//取出当前遍历到的树
            while (tp > size){
    //当栈中元素个数大于第一部分凸包个数时
                //取出栈顶元素 b 和 栈顶元素的上一个元素 a
                int[] a = trees[stk[tp-1]],b = trees[stk[tp]];
                //判断向量ac是否在向量ab左边
                if (getArea(a,b,c) < 0){
    
                    //如果ac在ab右边，那么将栈顶上一个元素 废弃
                    vis[stk[tp--]] = false;
                }else {
    
                    //如果ac在ab左边，那么退出while循环，将当前树压入栈
                    break;
                }
            }
            stk[++tp] = i;//将当前树的下标i压入栈
            vis[i] = true;//将当前树标记为已使用状态
        }
        int[][] ans = new int[tp-1][2];
        for (int i = 1; i < tp; i++) {
    
            ans[i-1] = trees[stk[i]];//将栈中元素对应的trees中树存入ans数字返回
        }
        return ans;
    }
    public int[] subtraction(int[] a,int[] b){
    //二维向量相减
        return new int[]{
    a[0]-b[0],a[1]-b[1]};
    }
    public double cross(int[] a,int[] b){
    //二维向量叉乘
        return a[0]*b[1]-a[1]*b[0];//结果大于0表示向量b在向量a左侧，结果小于0表示向量b在向量a右侧
    }
    public double getArea(int[] a,int[] b,int[] c){
    //计算向量ab转为向量ac的过程中
        //结果大于0表示向量ac在向量ab左侧，结果小于0表示向量ac在向量ab右侧
        return cross(subtraction(b,a),subtraction(c,a));
    }
}

---

剑指 Offer II 014. 字符串中的变位词【中等题】

思路：

统计s1中各个字符出现的次数，用一个长度与s1相等的滑动窗口框住s2，统计窗口内的各个字符出现次数，如果s1中字符出现次数与s2滑动窗口内字符出现次数相同，那么表示s2包含s1的某个变位词。
窗口滑动时，将窗口左侧字符次数减1，将窗口右侧字符次数加1即可实现窗口内字符次数统计的更新，而不用重新统计整个窗口的字符出现次数。

代码；

class Solution {
    
    public boolean checkInclusion(String s1, String s2) {
    
        int n1 = s1.length(),n2 = s2.length();
        if (n1 > n2){
    
            return false;
        }
        int[] cnt1 = new int[26],cnt2 = new int[26];
        char[] chars1 = s1.toCharArray(),chars2 = s2.toCharArray();
        for (char c : chars1) {
    //统计字符串s1中每个字符的个数
            cnt1[c-'a']++;
        }
        for (int i = 0; i < n1; i++) {
    //统计字符串s2前n1个字符中每个字符的个数
            cnt2[chars2[i]-'a']++;
        }
        if (Arrays.equals(cnt1,cnt2)){
    
            return true;
        }
        for (int i = 1; i < n2-n1+1; i++) {
    
            cnt2[chars2[i-1]-'a']--;//将当前窗口左端字符个数减1
            cnt2[chars2[i+n1-1]-'a']++;//将当前窗口右端字符个数加1
            if (Arrays.equals(cnt1,cnt2)){
    
                return true;
            }
        }
        return false;
    }
}