栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

B站左程云算法视频中级班08

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

B站左程云算法视频中级班08

题目1:路灯问题

//s中只有'.'和'x'两种字符
//路灯影响三个位置
//至少需要多少灯,可以把.都点亮
public static int minLight(String s){
    char[] str = s.toCHarArray();
    int index = 0;

    int light = 0;
    //当你来到i位置,一定保证之前的灯,彻底不会影响i位置
    int i = 0;
    while(index < str.length){
        if (str[index] == 'X'){
            index++;
        }else{//str[index] == "."
            light++;
            if(index + 1 == str.length){
                break;
            }else{//如果下面有位置
                if(str[index+1] == 'X'){
                    index = index + 2;
                }else{//下个位置是点
                    index = index + 3
                }
            }
        }
    }
    return light;
    
}

题目2:已知一棵二叉树中没有重复节点,给定前序遍历和中序遍历数组,得出后序遍历数组

递归: int[ ] pre int[ ] in 生成 int[] pos

写一个函数,利用pre[prei.....prej]结合in[ini .....inj]生成pos[posi.....posj]

pre: a b d  e  c   中左右

in : d  b  e  a  c   左中右

pos:      d  b  e      c    a   左右中

public static void set(int[] pre, int[] in, int[] pos, int prei, int prej, int ini, int inj, int posi, int posj, HashMap inMap){
    if(prei > prej){
        return;
    } 
    if(prei == prej){ //只剩下一个数了,直接填
        pos[posi] = pre[prei];
        return;
    }
    pos[posj] = pre[prei];
    int find = inMap.get(pre[prej]);
    
    set(pre, in, pos, prei + 1, prei + find - ini, ini, find - 1, posi, posi + find - ini - 1);
    set(pre, in, pos, prei + find - ini + 1, prej, find + 1, inj, posi + find - ini, posj - 1);
}
//优化
public static int[] getPostArray(int[] pre, int[] in){
    if (pre == null){
        return null;
    }
    int N = pre.length;
    int[] pos = new int[N];
    HashMap inMap = new HashMap<>();
    for(int i = 0; i < in.length; i++){
        inMap.put(in[i], i);
    }
    set(pre, in, pos, 0, N - 1, 0, N - 1, 0, N-1, inMap);
    return pos;
}

优化:中序遍历数组改成建一张HashMap

题目3:把数字转化成汉字

小范围到大范围

先搞定 1~19,然后处理1~99,接着1~999

中文:先搞定1~99,1~999.......  然后再处理一些特殊情况

题目4:求完全二叉树的节点的个数

1.先看深度

2.右树最左节点到了最后一层,则左树是满二叉树,右树是完全二叉树,递归

   右树最左节点没到最后一层,右树是满二叉树,递归左树

//请保证head为头的树是完全二叉树
public static int nodeNum(Node head){
    if (head == null){
        return 0;
    }
    return bs(head, 1, mostLeftLevel(head, 1));
}

//node在第level层, h是总的深度, (h永远不变,全局变量)
//以node为头的完全二叉树,节点个数是多少

public static int bs(Node node, int Level, int h){
    if (Level == h){
        return 1;
    }
    if(mostLeftLevel(node.right, Level + 1) == h){
        return (1 << (h - Level)) + bs(node.right, Level + 1, h);
    }else{
        return (1 << (h - Level - 1)) + bs(node.left, Level + 1, h);
    }
}

//如果node在第level层
//求以node为头的子树, 最大深度是多少
//node为头的子树,一定是完全二叉树
public static int mostLeftLevel(Node node, int level){
    while(node != null){
        level++;
        node = node.left;
    } 
    return level - 1;
}

题目5:最长递增子序列问题

经典方法:遍历+动态规划

dp最大的就是结果

优化方法:用ends数组,初始化为都是无效区,ends[i]是所有长度为i+1的递增子序列中,最小结尾的值

在ends的有效区里二分的找大于nums[i] 数最左的位置,然后更新

使得长度短的递增子序列结尾小于长度大的递增子序列结尾,使得有效区必有序

构造单调性

public static int lengthOfLIS1(int[] nums) {
        if(nums.length==1)return 1;
        int n=nums.length;
        int[] dp=new int[n];
        int[] ends=new int[n];
        Arrays.fill(ends,Integer.MIN_VALUE);
        dp[0]=1;
        ends[0]=nums[0];
        int index=0;
        int res=Integer.MIN_VALUE;
        for (int i = 1; i < dp.length; i++) {
            int left=0;
            int right=index+1;
            int mid=left+((right-left)>>1);
            while(left!=right){
                if(nums[i]<=ends[mid]){
                    right=mid;
                }else {
                    left=mid+1;
                }
                mid=left+((right-left)>>1);
            }
            if(nums[i]>ends[mid]){
                ends[++index]=nums[i];
                dp[i]=index+1;
                res=Math.max(res,dp[i]);
                continue;
            }

            ends[mid]=nums[i];
            dp[i]=mid+1;
            res=Math.max(res,dp[i]);
            if(ends[i]==-22) System.out.println(Arrays.toString(ends));
        }
        System.out.println(Arrays.toString(dp));

        return res;
    }

题目6:表示区间内能否被整除

1034 % 3 等价于 1 + 0 + 3 + 4 %3

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970588.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号