【Everyday】(1)拿手套问题 - Everyday - SegmentFault


【Everyday】(1)拿手套问题 - Everyday - SegmentFault
在地下室里放着n种颜色的手套,手套分左右手,但是每种颜色的左右手手套个数不一定相同。A先生现在要出门,所以他要去地下室选手套。但是昏暗的灯光让他无法分辨手套的颜色,只能分辨出左右手。所以他会多拿一些手套,然后选出一双颜色相同的左右手手套。现在的问题是,他至少要拿多少只手套(左手加右手),才能保证一定能选出一双颜色相同的手套。
给定颜色种数n(1≤n≤13),同时给定两个长度为n的数组left,right,分别代表每种颜色左右手手套的数量。数据保证左右的手套总数均不超过26,且一定存在至少一种合法方案。
测试样例
4,[0,7,1,6],[1,5,0,6]
返回10(解释:可以左手手套取2只,右手手套取8只)

解决这个问题的时候,根据测试样例的提示找到了思路,(1)从一只手中取出一种颜色,然后在另一种手中取出所有颜色,那么这个时候,就可以保证一定会出现满足条件的情况,大致思路理清了,然后考虑具体算法实现,(2)找出一种颜色,在给定的数组中找出一种颜色,从中选取一个不就可以了,但是这个时候要考虑的问题是,在另外一只手中,你索取的颜色,可能并没有对应,考虑到最坏情况,当我们在一只手中,取一个颜色手套的时候,我们要将另一只手中对应颜色为0的所有颜色取尽,然后在多取一个,才可以保证去取出一个可以和另一只手对应。(3)接下来是如何在另一只手中将所有可能的颜色都取出来呢?这个问题首先考虑到的是将所有的全部拿一遍就好了呀,但是这样并不是最优的,考虑如果右手是4,4,3,我们其实是只需要取9个就可以了,就可以将所有的颜色取一遍,规律是在所有的数目进行排序后,对于最小的数字,我们只需要取1个就好了,因此我们可以在对其进行一个最小值标记,最后判断最小值是否为大于1,大于1的话,就要减去其超出1的部分。还有对于这个最小值的选取,是不可以选取对应数组的值为0的,如果有该值被选取了,实际上是可以的,因为我们要确保的是找出所有的颜色种类,这对我们的选取是没有任何影响的。(4)到这里还没有完,由于看测试用例,所以自己的思路潜移默化中受了测试用例的影响,所以也是跟着进去了,只考虑从左手拿一种颜色,而忘记了考虑可以先从右手拿出一种颜色的问题。因此导致结果迟迟不对。
    public static int findOneColorCost(int[] array1,int[] array2){
        int cost = 0;
        for(int i=0; i<array1.length; i++)
            if(array2[i]==0)
                cost += array1[i];
        return ++cost;
    }

    public static int getAllColorCost(int[] array1,int[] array2){
        int min = -1;
        int cost = 0;
        for(int j=0; j<array1.length; j++){
            if(min==-1&&array2[j]!=0)
                min = array2[j];
            else if(min!=-1&&array2[j]<min&&array2[j]!=0)
                min = array2[j];
            cost += array2[j];
        }
        if(min>1)
             cost = cost - min + 1;
        return cost;
    }

    public static void main(String[] args){
        int [] left = {1,2,0,1,3,1};
        int [] right= {0,0,0,2,0,1};
        System.out.println(findMinimum(6,left,right));
    }
}

优化发散

不均等配对问题,择其1,另一配对中选择所有从而达成能够组成一对。测试用例引导带来一个误区,考虑问题要全面。
Read full article from 【Everyday】(1)拿手套问题 - Everyday - SegmentFault

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts