蓝鸟 2020 OA (附整理的所有题目+解法)

[noun]

我运气比较好，出现的4个全是easy…真是枉费我辛苦准备了2天……

一共四个题目

1. Balanced Sales Array
2. Sub Palindrome
3. Coloring the Blocks
4. Unique Twitter User Id Set

下面是我整理的约20道OA的题，我感觉题库基本就这些了~在LC上有讨论的，我会贴原链接/原题，没有的我就大概写个解题思路。

1. Twitter new office design
貌似是道数学题… https://leetcode.com/discuss/int … r-New-Office-Design
2. Efficient Job Processing
经典的0/1背包问题，用DP解: https://leetcode.com/discuss/int … -Processing-Service
3. Game Event
https://leetcode.com/discuss/int … 2019-or-Game-Events
4. Unique Twitter User Id Set
https://leetcode.com/discuss/int … Twitter-User-Id-Set
5. Partitioning Array
主要是判断1. len(numbers)%k !=0; 2. 是否有元素的个数> len(numbers)//k: https://leetcode.com/discuss/int … -Partitioning-array
6. Autoscale Policy
https://leetcode.com/discuss/int … or-Autoscale-Policy
7. Authentication Token
https://leetcode.com/discuss/int … thentication-Tokens
8. K difference
LC伍叁贰
9. Buying show tickets
(这是唯一一个我们找到原题的…不好意思…)
10. Weird Faculty
https://leetcode.com/discuss/int … 19-or-Weird-Faculty
11. Final discounted price
LC齐三久 变种
12. Reaching Points
LC岐拔灵 原
13. twitter social network
LC吴思琪 原
14.Activate fountain
算是greedy里比较经典的区间覆盖问题，可以转化成interval以后sort: https://leetcode.com/discuss/int … r-Activate-Fountain
15. Coloring the blocks
LC而物流 原
16. Parking Dilemma
这个题LC讨论里的图非常不清楚，不过好像不难，用sliding window就好: https://leetcode.com/discuss/int … -or-Parkin‍‌‌‌‌‌‌‍‌‍‌‌‍‌‍‌‌‌‍‍g-Dilemma
17. Get set on
LC似时 变种 不需要求全部可能，所以可以用set
18. Sub Palindrome
LC刘思琪 变种 需要找到unique substring，额外加一个set()检查一下就好
19.Restocking the Warehouse
这个不难…遍历一下就好
20.Balanced Sales Array
这个也不难，也是遍历就好
21. university career fair
https://leetcode.com/discuss/int … versity-Career-Fair
22. Anagram Difference
Hacker上的题: https://www.hackerrank.com/challenges/anagram/problem

[匿名1377]

public static int balancedSum(List<Integer> sales) {
    // Write your code here     
		int sum =0;
        for(int i=0;i<list.size();i++){
            sum += list.get(i);
        }
        int curr =list.get(0);
        for(int i=1;i<list.size();i++){
            if(curr == sum - curr - list.get(i)){
                return i;
            }
            curr += list.get(i);
        }
        return -1;
    }

[匿名1377]

public static List<Integer> getMinimumDifference(List<String> a, List<String> b) {
    // Write your code here
        List<Integer> result = new ArrayList<>();
        for(int i=0;i<a.size();i++){
            result.add(countDifference(a.get(i),b.get(i)));
        }
    
        return result;
    }
    public static int countDifference(String s1 , String s2){
        if(s1.length()!=s2.length()){
            return -1;
        }
    int count = 0; 
  
        // store the count of character 
        int char_count[] = new int[26]; 
  
        // iterate though the first String and update  
        // count 
        for (int i = 0; i < s1.length(); i++)  
            char_count[s1.charAt(i) - 'a']++;         
  
        // iterate through the second string 
        // update char_count. 
        // if character is not found in char_count 
        // then increase count 
        for (int i = 0; i < s2.length(); i++)  
            if (char_count[s2.charAt(i) - 'a']-- <= 0) 
                count++; 
          
        return count; 
    }

[匿名1377]

---

static boolean isSubsetSum(Integer set[], 
                            int n, int sum) 
    { 
        // Base Cases 
        if (sum == 0) 
            return true; 
        if (n == 0 && sum != 0) 
            return false; 
         
        if (set[n-1] > sum) 
            return isSubsetSum(set, n-1, sum); 
        return isSubsetSum(set, n-1, sum) ||  
            isSubsetSum(set, n-1, sum-set[n-1]); 
    } 
    public static boolean isPossible(List<Integer> calCounts, int requiredCals) {
        Integer[] array = new Integer[calCounts.size()];
        calCounts.toArray(array); 
        return isSubsetSum(array, calCounts.size(), requiredCals);
    }