上岸 I LeetCode Weekly Contest 208解题报告 算法 刷题解法

卖大米 2020-9-27 486


上岸算法

死磕100%上岸率的精品小班课

关注我们,第一时间获得大厂面试真题讲解

No.1 文件夹操作日志搜集齐

★ 解题思路

注意使用 equals 比较字符串, 而不是 ==

代码展示


class Solution { 
   public int minOperations(String[] logs) { 
       int res = 0; 
       for (String log : logs) { 
           if (log.equals("../") && res > 0) 
               res--; 
           if (!log.equals("./") && !log.equals("../")) 
               res++; 
       } 
       return res; 
   } 
} 

No.2

经营摩天轮的最大利润

解题思路

模拟摩天轮的运营过程即可, 在最大利润时停下来.

代码展示


class Solution { 
   public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) { 
       int[] queue = new int[4]; // 四个仓 
       int head = 0;             // 表示当前在底部的仓是哪个 
       int waiting = 0; 
       int profit = 0, maxProfit = 0; 
       int res = -1; 
       for (int i = 0; i < customers.length || waiting > 0; i++) { 
           if (i < customers.length) 
               waiting += customers[i]; 
           int onboard = Math.min(waiting, 4); 
           waiting -= onboard; 
           queue[head] = onboard; 
           head = (head + 1) % 4;    // 每一轮转动之后 head + 1 
           profit += onboard * boardingCost; 
           profit -= runningCost; 
           if (profit > maxProfit) { // 维护最大利益, 被更新时才更新 res 
               maxProfit = profit; 
               res = i + 1; 
           } 
       } 
       return res; 
   } 
}

No.3 皇位继承顺序

★解题思路

维护一棵树, 再使用 Set 来记录死亡信息, 获取继承顺序时对树进行前序遍历即可.

代码展示


class ThroneInheritance { 

   static class Node { 
       String name; 
       List<Node> children; 

       public Node(String kingName) { 
           this.name = kingName; 
           this.children = new ArrayList<Node>(); 

       } 

       public void add(Node child) { 
           this.children.add(child); 

       } 
   } 

   Map<String, Node> map = new HashMap<String, Node>(); 
   Set<String> deadSet = new HashSet<>(); 
   Node king; 

   public ThroneInheritance(String kingName) { 
       this.king = new Node(kingName); 
       this.map.put(kingName, this.king); 
   } 

   public void birth(String parentName, String childName) { 
       Node kid = new Node(childName); 
       this.map.put(childName, kid); 
       this.map.get(parentName).add(kid); 
   } 

   public void death(String name) { 
       deadSet.add(name); 
   } 

   public List<String> getInheritanceOrder() { 
       List<String> res = new LinkedList<>(); 
       dfs(this.king, res); 
       return res; 
   } 

   void dfs(Node root, List<String> res) { 
       if (root == null) return; 
       if (!deadSet.contains(root.name)) { 
           res.add(root.name); 
       } 
       for (Node kid : root.children) { 
           dfs(kid, res); 
       } 
   } 
}

No.4 最多可达成的换楼请求数目

★ 解题思路

回溯法.

代码展示


class Solution { 
   public int maximumRequests(int n, int[][] requests) { 
       int[] status = new int[n]; 
       return dfs(requests, status, 0, 0); 
   } 

   public int dfs(int[][] requests, int[] status, int depth, int num) { 
       if (depth == requests.length) { 
           for (int i : status) { 
               if (i != 0) { 
                   return 0; 
               } 
           } 
           return num; 
       } 
       int res = 0; 
       status[requests[depth][0]]--; 
       status[requests[depth][1]]++; 
       res = Math.max(res, dfs(requests, status, depth + 1, num + 1)); 
       status[requests[depth][0]]++; 
       status[requests[depth][1]]--; 
       res = Math.max(res, dfs(requests, status, depth + 1, num)); 
       return res; 
   } 
}

杭州上岸算法网络科技有限公司

上岸算法网络科技有限公司是一家致力于用高质量,高互动性小班课程来帮助学生更好的在就业市场中定位以及求职的公司。我们以顶级的课程质量,高互动性的教学方式以及独特的小班教学模式来帮助学生更快的跨过求职的鸿沟,用最高效,经济,合理的方式帮助更多学生快速找到梦寐以求的工作。

最新回复 (0)
返回