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

卖大米 2020-11-22 518


上岸算法

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

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

No.1 检查两个字符串数组是否相等

★ 解题思路

String.join!!!

代码展示


class Solution { 
   public boolean arrayStringsAreEqual(String[] word1, String[] word2) { 
       return String.join("", word1).equals(String.join("", word2)); 
   } 
}

No.2 具有给定数值的最小字符串

解题思路

贪心, 每次用的字符越小越好.

代码展示


class Solution { 
   public String getSmallestString(int n, int k) { 
       StringBuilder sb = new StringBuilder(); 
       for (int i = 0; i < n; i++) { 
           int c = 1; 
           while ((n - i - 1) * 26 + c < k) c++; 
           k -= c; 
           sb.append((char) (c - 1 + 'a')); 
       } 
       return sb.toString(); 
   } 
}

No.3 生成平衡数组的方案数

★解题思路

前缀和稍作改动: 只包含原奇数下标的前缀和以及偶数下标的前缀和.

使用这两个前缀和就可以快速计算出删除一个数字后的新奇偶下标的元素和.

代码展示


class Solution { 
   public int waysToMakeFair(int[] nums) { 
       // oddSum[i] 表示 i 位置之后的所有原奇数下标元素的和 
       // oddSum[0] == oddSum[1], oddSum[2] == oddSum[3]... 
       int[] oddSum = new int[nums.length + 1];  // + 1 避免越界 
       int[] eveSum = new int[nums.length + 1]; 
       int n = nums.length; 
       oddSum[n - 1] = (n - 1) % 2 == 1 ? nums[n - 1] : 0; 
       eveSum[n - 1] = (n - 1) % 2 == 0 ? nums[n - 1] : 0; 
       for (int i = n - 2; i >= 0; i--) { 
           oddSum[i] = oddSum[i + 1] + (i % 2 == 1 ? nums[i] : 0); 
           eveSum[i] = eveSum[i + 1] + (i % 2 == 0 ? nums[i] : 0); 
       } 

       int res = 0; 
       for (int i = 0; i < n; i++) { 
           int odd = oddSum[0] - oddSum[i] + eveSum[i + 1]; 
           int eve = eveSum[0] - eveSum[i] + oddSum[i + 1]; 
           res += odd == eve ? 1 : 0; 
       } 
       return res; 
   } 
}

No.4 完成所有任务的最少初始能量

★解题思路

实际上我们并不需要关心真正的顺序, 只需要关心 “差值” 和最大的启动值就可以了.

tot 表示实际消耗的总能量和.

minDiff 表示启动值和实际耗费的差中的最小值.

maxStart 表示所有任务中, 起始能量最高的.

最终答案是 tot + minDiffmaxStart

代码展示


class Solution { 
   public int minimumEffort(int[][] tasks) { 
       int tot = 0, minDiff = 10000, maxStart = 0; 
       for (int[] task : tasks) { 
           tot += task[0]; 
           maxStart = Math.max(maxStart, task[1]); 
           minDiff = Math.min(minDiff, task[1] - task[0]); 
       } 
       return Math.max(maxStart, tot + minDiff); 
   } 
}

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

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

最新回复 (0)
返回