【数算】复习2

柔情只为你懂 2022-09-11 07:11 124阅读 0赞

# 2021年9月14日 #

### 会议室问题： ###

> 贪心算法是几乎没有规律的一种算法，面试场合比较少见（无区分度）  
> 与之相反，dp问题比较常见，因为dp涉及到优化的问题，将复杂的重复计算问题优化为单次计算的。

https://www.acwing.com/problem/content/description/2759/  
一些项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲。给你每一个项目开始的时间和结束的时间 。你来安排宣讲的日程，要求会议室进行的宣讲的场次最多。 返回最多的宣讲场次。

public int solution(Project projects[], int currentTime) {
        
        //sort by the end time
        Arrays.sort(projects, new BestArrayComparator());
        int res = 0;
        for (int i = 0; i < projects.length; i++) {
        
            if (currentTime <= projects[i].begin) {
        
                res++;
                currentTime = projects[i].end;
            }
        }
        return res;
    }
    // 会议的定义，开始时间和结束时间
    class Project {
        
        int begin;
        int end;
    }
    // 比较器
    class BestArrayComparator implements Comparator<Project> {
        
        public int compare(Project o1, Project o2) {
        
            return o1.end - o2.end;
        }
    }

### 502. IPO ###

优先队列的思想,来回倒

https://leetcode-cn.com/problems/ipo/

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]

class Solution {
        
        // 串行执行 k 个任务
        // 初始资金 w
        // ==》题目类似于一种解锁的机制，一开始的资金比较少，但是随着越赚越多，慢慢能打高级怪
        //     维护一个costHeap小根堆、一个profitHeap大根堆
        public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        
            PriorityQueue<Project> costHeap = new PriorityQueue<>(new costHeapCompare());
            PriorityQueue<Project> profitHeap = new PriorityQueue<>(new profitHeapCompare());
            // 1. 填充小根堆,待接任务costHeap
            for (int i = 0; i < capital.length; i++) {
        
                costHeap.add(new Project(capital[i], profits[i]));
            }
            // 2. 排好可接任务的最高收益表(因为步数有限,只能挑选最优的来做)
            for (int i = 0; i < k; i++) {
        
                while (!costHeap.isEmpty() && w >= costHeap.peek().cost) {
        
                    profitHeap.add(costHeap.poll());
                }
                // 2.1 没有任务可以做了,直接返回
                if (profitHeap.isEmpty()) return w;
                // 2.2 还有任务可以做,那么加上去收益进入下一个循环
                w += profitHeap.poll().profit;
            }
            return w;
        }
    
        class Project {
        
            int cost;
            int profit;
    
            Project(int cost, int profit) {
        
                this.cost = cost;
                this.profit = profit;
            }
        }
    
        class costHeapCompare implements Comparator<Project> {
        
            public int compare(Project o1, Project o2) {
        
                return o1.cost - o2.cost;
            }
        }
    
        class profitHeapCompare implements Comparator<Project> {
        
            public int compare(Project o1, Project o2) {
        
                return o2.profit - o1.profit;
            }
        }
    }

### 分金条\_haffman编码问题: ###

参考:  
https://blog.csdn.net/zhou\_209/article/details/79436325

### 575. 分糖果 ###

https://leetcode-cn.com/problems/distribute-candies/  
![在这里插入图片描述][54f7db57a93a4518a36262523f93b640.png]

class Solution {
        
        public int distributeCandies(int[] candyType) {
        
            int[] count = new int[200001];
    
            for(int i =0; i<candyType.length; i++) {
        
                count[candyType[i]+100000]++;
            }
            int allType = 0;
            for(int i =0; i<count.length; i++) {
        
                if(count[i]!=0) allType++;
            }
            // 1. 如果种类太多,那么妹妹势必最多只能分到一半(超过一半都是不一样的糖果)
            // 2. 如果种类比较少,保证妹妹能分到所有不同的种类,而弟弟只能分到一种糖果
            return  allType > candyType.length>>1 ? candyType.length>>1 : allType;
        }
    }

### 剑指 Offer II 048. 序列化与反序列化二叉树 ###

这题没啥需要注意的，主要就是if(str.equals("\#")) 这里又犯错了，其他逻辑都走得很顺。

public class Codec {
        
    
        // Encodes a tree to a single string.
        public String serialize(TreeNode root) {
        
            String res = "";
            if (root == null) {
        
                return "#_";
            }
            res = root.val+"_";
            res += serialize(root.left);
            res += serialize(root.right);
            return res;
        }
    
        // Decodes your encoded data to tree.
        public TreeNode deserialize(String data) {
        
            String[] strArr = data.split("_");
            Queue<String> que = new LinkedList<>();
            for (int i =0; i<strArr.length; i++) {
        
                que.add(strArr[i]);
            }
            return getNode(que);
        }
    
        public TreeNode getNode(Queue<String> que) {
        
            String str = que.poll();
            if(str.equals("#")) return null;
            TreeNode cur = new TreeNode(Integer.valueOf(str));
            cur.left = getNode(que);
            cur.right = getNode(que);
            return cur;
        }
    }

### 剑指 Offer II 105. 岛屿的最大面积 ###

https://leetcode-cn.com/problems/ZL6zAn/

![在这里插入图片描述][38127bc911f04c7097c04cd219b8710c.png]

class Solution {
        
        public int maxAreaOfIsland(int[][] grid) {
        
        	//有可能不存在岛，这种情况返回0
            int res = 0;
            for (int i = 0; i<grid.length; i++) {
        
                for(int j =0; j<grid[0].length; j++) {
        
                    if(grid[i][j] == 1) {
        
                        res = Math.max(infect(grid, i, j), res);
                    }
                }
            }
            return res;
        }
    
        public int infect(int[][] grid, int i, int j) {
        
            // 1、排除越界问题
            if(i<0||i>=grid.length || j<0||j>=grid[0].length) return 0;
            // 2、排除无效节点
            if(grid[i][j] != 1) return 0;
            // 3、合格节点进行染色，然后继续对后面的节点进行染色
            grid[i][j] = 2;
            return 
                infect(grid, i, j-1) + 
                infect(grid, i+1, j) + 
                infect(grid, i, j+1) + 
                infect(grid, i-1, j) + 1;
        }
    }

### 并查集 ###

public class UnionFindSet {
        
    
        private Map<Node, Node> fatherMap;
        private Map<Node, Integer> nodesNumMap;
    
        /*
        * 定义并查集的结构：
        * 1、fatherMap存折每个元素的父亲
        * 2、nodesNumMap是每个元素自己的单独集合
        * */
        public UnionFindSet(List<Node> nodes) {
        
            fatherMap = new HashMap();
            nodesNumMap = new HashMap();
            for (Node node : nodes) {
        
                fatherMap.put(node, node);
                nodesNumMap.put(node, 1);
            }
        }
    
        /*
         * 合并节点
         * */
        public void union(Node a, Node b) {
        
            if (a == null || b == null) {
        
                return;
            }
            Node rootOfA = getRoot(a);
            Node rootOfB = getRoot(b);
            if (rootOfA != rootOfB) {
        
                int numOfA = nodesNumMap.get(rootOfA);
                int numOfB = nodesNumMap.get(rootOfB);
                if (numOfA >= numOfB) {
        
                    fatherMap.put(rootOfB, rootOfA);
                    nodesNumMap.put(rootOfA, numOfA + numOfB);
                } else {
        
                    fatherMap.put(rootOfA, rootOfB);
                    nodesNumMap.put(rootOfB, numOfA + numOfB);
                }
            }
        }
    
        /**
         * 拿到元素a，b的root节点，进行判断两个是否同一并查集
         */
        public boolean isSameSet(Node a, Node b) {
        
            if (a == null || b == null) return false;
            return getRoot(a) == getRoot(b);
        }
    
        /**
         * 不断遍历找root节点
         * 如果路径过长的话，直接将自己拉到父亲节点之下
         */
        public Node getRoot(Node node) {
        
            if (node == null) {
        
                return null;
            }
            Node father = fatherMap.get(node);
            if (father != node) {
        
                father = fatherMap.get(father);
            }
            fatherMap.put(node, father);
            return father;
        }
    
        public static class Node {
        
            //whatever you like to store   int , char , String ..etc
        }
    
        public static void main(String[] args) {
        
            Node a = new Node();
            Node b = new Node();
            Node c = new Node();
            Node d = new Node();
            Node e = new Node();
            Node f = new Node();
            Node[] nodes = {
        a, b, c, d, e, f};
    
            UnionFindSet unionFindSet = new UnionFindSet(Arrays.asList(nodes));
            unionFindSet.union(a, b);
            unionFindSet.union(c, d);
            unionFindSet.union(b, e);
            unionFindSet.union(a, c);
            System.out.println(unionFindSet.isSameSet(d, e));
        }
    }

## **回溯算法：** ##

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAd2lsbG9ybg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/587fa5c89f1c46f2b6cfa3a8c9c4fe97.png
[54f7db57a93a4518a36262523f93b640.png]: /images/20220828/92cd8a3063374f78a1dd4dd21f2a7257.png
[38127bc911f04c7097c04cd219b8710c.png]: /images/20220828/be7dccdce89442699d49a6987385f3a1.png