数据结构与算法学习笔记(训练营三)-经典面试四

给你一个字符串类型的数组arr,譬如:
String[] arr = { "b\st", "d\", "a\d\e", "a\b\c" }; 
把这些路径中蕴含的目录结构给打印出来,子目录直接列在父目录下面,并比父目录向右进两格,就像这样:
a
  b
    c
  d
    e
b
  cst
d
同一级的需要按字母顺序排列不能乱。

  • 利用前缀树,让后深度优先遍历
/**
 * 给你一个字符串类型的数组arr,譬如:
 * String[] arr = { "b\st", "d\", "a\d\e", "a\b\c" };
 * 把这些路径中蕴含的目录结构给打印出来,子目录直接列在父目录下面,并比父目录向右进两格,就像这样:
 * a
 * b
 * c
 * d
 * e
 * b
 * cst
 * d
 * 同一级的需要按字母顺序排列不能乱。
 */
public class PrintDir {
    public static void printDir(String[] strs) {
        if (strs == null || strs.length == 0) {
            return;
        }
        // 生成前缀树
        TreeNode prefixTree = getPrefixTree(strs);
        // 打印前缀树
        printPrefixTree(prefixTree, 0);
    }

    // 生成一棵前缀树,返回前缀树的根节点
    private static TreeNode getPrefixTree(String[] strs) {
        // 生成一个根节点
        TreeNode root = new TreeNode("");
        // 遍历每个单词,每个单词都在以'\'为分隔,挂在前缀树上
        for (String word : strs) {
            // 当前节点
            TreeNode cur = root;
            // 以'\'分隔每个单词
            String[] dirs = word.split("\\\\");
            // 挂在前缀树上
            for (String dir : dirs) {
                // 如果当前节点下面没有条路那么久建出来挂在当前节点下面,否则就复用当前节点
                // 下面的路
                if (!cur.nexts.containsKey(dir)) {
                    // 没有新建
                    cur.nexts.put(dir, new TreeNode(dir));
                }
                cur = cur.nexts.get(dir);
            }
            // 一条路径挂完了
            cur.end = true;
        }
        return root;
    }

    private static void printPrefixTree(TreeNode root, int level) {
        // 遍历前缀树打印
        TreeNode cur = root;
        // 如果当前是第0层直接打印
        if (level == 0) {
            System.out.println(cur.path);
        } else {
            System.out.println(blank(level) + cur.path);
        }
        // 深度遍历后续节点
        for (Map.Entry entry : cur.nexts.entrySet()) {
            printPrefixTree((TreeNode) entry.getValue(), level + 1);
        }

    }

    // 加空格数
    private static String blank(int level) {
        String blank = "";
        for (int i = 0; i < level; i++) {
            blank += "  ";
        }
        return blank;
    }

    public static void main(String[] args) {
        String[] strs = new String[]{ "b\\st", "d\\", "a\\d\\e", "a\\b\\c" };
        printDir(strs);
    }
}

  • 已知一棵二叉树中没有重复节点,并且给定了这棵树的中序遍历数组和先序遍历 数组,返回后序遍历数组。
    比如给定:
    int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
    int[] in = { 4, 2, 5, 1, 6, 3, 7 }; 返回:
    {4,5,2,6,7,3,1}
  • 题解:我们知道先序遍历的第一个节点,是后序遍历的最后一个基点,那么我们可以,每次从先序遍历中拿出第一个节点,填到后续遍历的最后一个位置上,然后用先序遍历中的第一个节点,在中粗遍历中找到他的位置,把中序遍历分成了左右两棵子树,在重复上面的过程即可。
/**
 * 已知一棵二叉树中没有重复节点,并且给定了这棵树的中序遍历数组和先序遍历 数组,返回后序遍历数组。
 * 比如给定:
 * int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
 * int[] in = { 4, 2, 5, 1, 6, 3, 7 }; 返回:
 * {4,5,2,6,7,3,1}
 */
public class Post {

    public static int[] post(int[] pre,int[] in){
        if(pre == null || in == null || pre.length != in.length){
            return null;
        }
        // 预处理
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < in.length; i++) {
            map.put(in[i],i);
        }
        int[] post = new int[pre.length];
        process(pre,0,pre.length-1,in,0,in.length-1,post,0,post.length-1,map);
        return post;
    }

    // pre先序数组L1,R1分别表示先序中的子树的部分,同理in post有相同的含义
    private static void process(int[] pre, int L1, int R1,
                                int[] in, int L2, int R2,
                                int[] post, int L3, int R3,
                                HashMap<Integer,Integer> map){

        if(L1 > R1){
            return;
        }
        if(L1 == R1){
            post[L3] = pre[L1];
            return;
        }
        // 先序数组第一元素填到后续,数组最后一个元素上
        post[R3] = pre[L1];
        // 找到中续遍历中的位置
        int index = map.get(pre[L1]);
//        for(int i = L2;i <= R2;i++){
//            if(in[i] == pre[L1]){
//                index = i;
//                break;
//            }
//        }

        // 左右部分长度
        int len = index - L2;
        process(pre,L1+1,L1+len,in,L2,index-1,post,L3,L3+len-1,map);
        process(pre,L1+len+1,R1,in,index+1,R2,post,L3+len,R3-1,map);
    }

    public static void main(String[] args) {
        int[] pre = { 1, 2, 4, 5, 3, 6, 7 };
        int[] in = { 4, 2, 5, 1, 6, 3, 7 };
        int[] post = post(pre, in);

        for (int i :post){
            System.out.print(i+" ");
        }
    }
}

  • 最长递增子序列问题的O(N*logN)的解法。
/**
 * 最长递增子序列问题的O(N*logN)的解法,严格递增
 */
public class MaxIncreasingSubSeq {
    // O(N^2)解法
    public static int maxIncreasingSubSeq(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int n = arr.length;
        int[] temp = new int[n];
        // 以第一个元素结尾的最长递增子序列一定是自己1
        temp[0] = 1;
        // 预处理数组的有效区域
        int r = 0;
        int res = 0;
        for (int i = 1; i < n; i++) {
            int max = 0;
            for (int j = r; j >=0; j--) {
                if(arr[i] > arr[j]){
                    max = Math.max(max,temp[j]);
                }
            }
            temp[i] = max+1;
            r++;
            res = Math.max(res,temp[i]);
        }

        return res;
    }

    // O(logn),
    // 定义dp数组记录每个位置结尾时,最大递增子序列
    // 辅助数组temp,第一个位置时dp[0] = 1,temp[0] = arr[0],后面依次遍历,每遍历到一个数
    // ends[i]的最左边的位置,把它更新成arr[i],i位置结尾的最大递增子序列就是
    // 此时0到此时找到的ends位置之间的元素个数,如果没有,扩充有效区ends,如此重复。
    // ends[i] 长度为i+1的最长递增子序列的最小结尾。

    public static int maxIncreasingSubSeq2(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int n = arr.length;
        int[] dp = new int[n];
        int[] ends = new int[n];
        dp[0] = 1;
        ends[0] = arr[0];
        // ends数组有效区
        int right = 0;
        int l = 0;
        int r = right;
        int mid = 0;
        // 遍历数组,每遍历到一个数时,在ends中通过二分找到大于等于这个数的最左的位置更新,
        // 起点到此时位置的元素个数之差就是i位置的最大递增子序列
        int max = 0;
        for (int i = 1; i < n; i++) {
            l = 0;
            r = right;
            // 二分找大于等于当前数最左边的值
            while (l <= r){
                mid = l + ((r - l) >> 1);

                if(ends[mid] >= arr[i]){
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            // 如果没有找到l会来打right+1的位子,更新right
            // 找到了right 不变
            right = Math.max(right,l);
            ends[l] = arr[i];
            dp[i] = l + 1;
            max = Math.max(max,dp[i]);

        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{2,1,4,3,5,8,7,9};
        int[] arr2 = new int[]{2,1,4,3,5,8,7,9};
        System.out.println(maxIncreasingSubSeq(arr));
        System.out.println(maxIncreasingSubSeq2(arr2));
        //System.out.println(5+((9-5)>>1));
    }

}


  • 每个信封都有长和宽两个维度的数据,A信封如果想套在B信封里面,A信封必须在长和宽上都小于B信封才行。如果给你一批信封,返回最大的嵌套层数。
    题解,利用最长递增子序列求解。
    按照长从小到大排序,长一样按照宽从大到小排序。然后把排好序的信封的第二维数据拎出来,求他的最大递增子序列就是解。假设现在排好序中的i位置的宽是V ,那么以V结尾的最长递增子序列其实就是宽也比V小长也比位置长小的信封。
/**
 * 每个信封都有长和宽两个维度的数据,A信封
 * 如果想套在B信封里面,A信封必须在长和宽上都小于B信封才行。
 * 如果给你一批信封,返回最大的嵌套层数
 */
public class Envelope {
    public static int envelope(EnvelopeNode[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }

        Arrays.sort(arr,new MyComparator());
        int[] dArr = new int[arr.length];
        int index = 0;
        for (EnvelopeNode item : arr){
            dArr[index++] = item.d;
        }
        int i = maxIncreasingSubSeq2(dArr);
        return i;

    }

    public static int maxIncreasingSubSeq2(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        int n = arr.length;
        int[] dp = new int[n];
        int[] ends = new int[n];
        dp[0] = 1;
        ends[0] = arr[0];
        // ends数组有效区
        int right = 0;
        int l = 0;
        int r = right;
        int mid = 0;
        // 遍历数组,每遍历到一个数时,在ends中通过二分找到大于等于这个数的最左的位置更新,
        // 起点到此时位置的元素个数之差就是i位置的最大递增子序列
        int max = 0;
        for (int i = 1; i < n; i++) {
            l = 0;
            r = right;
            // 二分找大于等于当前数最左边的值
            while (l <= r){
                mid = l + ((r - l) >> 1);

                if(ends[mid] >= arr[i]){
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            // 如果没有找到l会来打right+1的位子,更新right
            // 找到了right 不变
            right = Math.max(right,l);
            ends[l] = arr[i];
            dp[i] = l + 1;
            max = Math.max(max,dp[i]);

        }
        return max;
    }


    static class MyComparator implements Comparator<EnvelopeNode> {

        @Override
        public int compare(EnvelopeNode o1, EnvelopeNode o2) {
            return o1.l != o2.l ? o1.l - o2.l : o2.d - o1.d;
        }
    }

    public static void main(String[] args) {
        EnvelopeNode[] arr = new EnvelopeNode[]{
                new EnvelopeNode(3,2),
                new EnvelopeNode(4,3),
                new EnvelopeNode(5,6),
                new EnvelopeNode(7,2),
                new EnvelopeNode(6,3),
                new EnvelopeNode(8,7),
                new EnvelopeNode(3,2)
        };
        System.out.println(envelope(arr));
    }
}

  • 给定一个数组arr,返回子数组的最大累加和。
/**
 * 给定一个数组arr,返回子数组的最大累加和。
 */
public class MaxArraySum {
    public static int maxArraySum(int[] arr){
        if(arr == null || arr.length == 0){
            return 0;
        }
        // 定义变量cur如果当前累加和大于0那么就一直累加,累加过程中记录最大值,
        // 当cur小于0时,把cur重置为0
        int max = arr[0];
        int cur = arr[0];
        for (int i = 1; i < arr.length; i++) {
            cur = cur < 0 ? 0 : cur;
            cur += arr[i];
            max = Math.max(max,cur);
        }

        return max;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1,2,-3,4,2,-2,1,1,5,-9};
        System.out.println(maxArraySum(arr));
    }
}
  • 给定一个整型矩阵,返回子矩阵的最大累计和。
    流程:假设是一个n*m的矩阵,算00,01,02,......,0n-1,11,12,13...1n-1,.....n-1~n-1各自的累加和,求最大值,每一次求和时,可以吧多行压缩成一行让后转化为求一个数组的最大累加和问题。各个数组求最大值。
/**
 * 给定一个整型矩阵,返回子矩阵的最大累计和。
 */
public class MatrixMaxSum {

    public static int matrixMaxSum(int[][] matirx){
        if(matirx == null || matirx[0].length == 0){
            return 0;
        }
        int row = matirx.length;
        int col = matirx[0].length;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < row; i++) {
            int[] temp = new int[col];
            for (int j = i; j < row; j++) {
                int h = 0;
                for (int k = 0; k < col; k++) {
                    temp[k] += matirx[j][k];
                    h += temp[k];
                    max = Math.max(max,h);
                    h = h < 0 ? 0:h;
                }
            }
        }
        return max;
    }


    public static void main(String[] args) {
        int[][] matrix = new int[][]{ { -90, 48, 78 }, { 64, -40, 64 }, { -81, -7, 66 } };
        System.out.println(matrixMaxSum(matrix));
    }
}

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 212,884评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,755评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 158,369评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,799评论 1 285
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,910评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,096评论 1 291
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,159评论 3 411
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,917评论 0 268
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,360评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,673评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,814评论 1 341
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,509评论 4 334
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,156评论 3 317
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,882评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,123评论 1 267
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,641评论 2 362
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,728评论 2 351

推荐阅读更多精彩内容