LeetCode - 801 Minimum Swaps To Make Sequences Increasing


https://leetcode.com/articles/minimum-swaps-to-make-sequences-increasing/
We have two integer sequences A and B of the same non-zero length.
We are allowed to swap elements A[i] and B[i].  Note that both elements are in the same index position in their respective sequences.
At the end of some number of swaps, A and B are both strictly increasing.  (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)
Given A and B, return the minimum number of swaps to make both sequences strictly increasing.  It is guaranteed that the given input always makes it possible.
Example:
Input: A = [1,3,5,4], B = [1,2,3,7]
Output: 1
Explanation: 
Swap A[3] and B[3].  Then the sequences are:
A = [1, 3, 5, 7] and B = [1, 2, 3, 4]
which are both strictly increasing.
Note:
  • A, B are arrays with the same length, and that length will be in the range [1, 1000].
  • A[i], B[i] are integer values in the range [0, 2000].



The cost of making both sequences increasing up to the first i columns can be expressed in terms of the cost of making both sequences increasing up to the first i-1 columns. This is because the only thing that matters to the ith column is whether the previous column was swapped or not. This makes dynamic programming an ideal choice.
Let's remember n1 (natural1), the cost of making the first i-1 columns increasing and not swapping the i-1th column; and s1 (swapped1), the cost of making the first i-1 columns increasing and swapping the i-1th column.
Now we want candidates n2 (and s2), the costs of making the first i columns increasing if we do not swap (or swap, respectively) the ith column.
Algorithm
For convenience, say a1 = A[i-1], b1 = B[i-1] and a2 = A[i], b2 = B[i].
Now, if a1 < a2 and b1 < b2, then it is allowed to have both of these columns natural (unswapped), or both of these columns swapped. This possibility leads to n2 = min(n2, n1) and s2 = min(s2, s1 + 1).
Another, (not exclusive) possibility is that a1 < b2 and b1 < a2. This means that it is allowed to have exactly one of these columns swapped. This possibility leads to n2 = min(n2, s1) or s2 = min(s2, n1 + 1).
Note that it is important to use two if statements separately, because both of the above possibilities might be possible.
At the end, the optimal solution must leave the last column either natural or swapped, so we take the minimum number of swaps between the two possibilities.
    public int minSwap(int[] A, int[] B) {
        // n: natural, s: swapped
        int n1 = 0, s1 = 1;
        for (int i = 1; i < A.length; ++i) {
            int n2 = Integer.MAX_VALUE, s2 = Integer.MAX_VALUE;
            if (A[i-1] < A[i] && B[i-1] < B[i]) {
                n2 = Math.min(n2, n1);
                s2 = Math.min(s2, s1 + 1);
            }
            if (A[i-1] < B[i] && B[i-1] < A[i]) {
                n2 = Math.min(n2, s1);
                s2 = Math.min(s2, n1 + 1);
            }
            n1 = n2;
            s1 = s2;
        }
        return Math.min(n1, s1);
    }


  int minSwap(vector<int>& A, vector<int>& B) {
    const int n = A.size();
        
    vector<int> keep(n, INT_MAX);
    vector<int> swap(n, INT_MAX);
    
    keep[0] = 0;
    swap[0] = 1;
    
    for (int i = 1; i < n; ++i) {
      if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
        // Good case, no swapping needed.
        keep[i] = keep[i - 1];
    
        // Swapped A[i - 1] / B[i - 1], swap A[i], B[i] as well
        swap[i] = swap[i - 1] + 1;
      }      
      
      if (B[i] > A[i - 1] && A[i] > B[i - 1]) {
        // A[i - 1] / B[i - 1] weren't swapped.
        swap[i] = min(swap[i], keep[i - 1] + 1);
      
        // Swapped A[i - 1] / B[i - 1], no swap needed for A[i] / B[i]      
        keep[i] = min(keep[i], swap[i - 1]);
      }      
    }
      
    return min(keep.back(), swap.back());
  }

https://blog.xiadong.info/2018/03/18/LeetCode-801-Minimum-Swaps-To-Make-Sequences-Increasing/
使用DP,如果array长度为n,那么使用2行n列的二维DP。dp[0][i]保存i位置没有交换的步数,dp[1][i]保存i位置交换了的最小步数。与i-1位置的情况组合之后有四种情况。但是实际上只有两种:
  1. i-1位置没有交换的情况下i位置不需要交换;i-1i位置都进行了交换。这两种情况都是ABi元素分别大于i-1元素。
  2. 如果AB中有一个不满足递增,那么就要交换,分为i-1交换和i交换两种。
    int minSwap(vector<int>& A, vector<int>& B) {
        int len = A.size();
        vector<vector<int>> dp(2, vector<int>(len, INT_MAX));
        dp[0][0] = 0;
        dp[1][0] = 1;
        for (int i = 1; i < len; i++) {
            if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
                dp[0][i] = min(dp[0][i], dp[0][i - 1]);
                dp[1][i] = min(dp[1][i], dp[1][i - 1]) + 1;
            }

            if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
                dp[0][i] = min(dp[0][i], dp[1][i - 1]);
                dp[1][i] = min(dp[1][i], dp[0][i - 1]) + 1;
            }
        }
        return min(dp[0][len - 1], dp[1][len - 1]);
    }
https://blog.csdn.net/zjucor/article/details/79599287
  1.     def minSwap(self, A, B):  
  2.         """ 
  3.         :type A: List[int] 
  4.         :type B: List[int] 
  5.         :rtype: int 
  6.         """  
  7.         dp = [[999999,999999for _ in range(len(A))]  
  8.         dp[0][0]=0  
  9.         dp[0][1]=1  
  10.         for i in range(1, len(A)):  
  11.             if dp[i-1][0]!=999999 and A[i]>A[i-1and B[i]>B[i-1]:  
  12.                 dp[i][0] = min(dp[i-1][0], dp[i][0])  
  13.             if dp[i-1][1]!=999999 and A[i]>B[i-1and B[i]>A[i-1]:  
  14.                 dp[i][0] = min(dp[i-1][1], dp[i][0])  
  15.                   
  16.             if dp[i-1][0]!=999999 and A[i]>B[i-1and B[i]>A[i-1]:  
  17.                 dp[i][1] = min(dp[i-1][0]+1, dp[i][1])  
  18.             if dp[i-1][1]!=999999 and A[i]>A[i-1and B[i]>B[i-1]:  
  19.                 dp[i][1] = min(dp[i-1][1]+1, dp[i][1])  
  20.                   
  21.         return min(dp[-1]) 
http://bookshadow.com/weblog/2018/03/18/leetcode-minimum-swaps-to-make-sequences-increasing/
swap和keep分别记录A[i]与B[i]交换或者不交换时的最小代价
分三种情况讨论:
A[i]与B[i]必须交换
A[i]与B[i]可以交换也可以保持原状
A[i]与B[i]必须保持原状
def minSwap(self, A, B): """ :type A: List[int] :type B: List[int] :rtype: int """ swap, keep = 1, 0 for i in range(1, len(A)): if A[i] <= A[i - 1] or B[i] <= B[i - 1]: # swap nswap = keep + 1 nkeep = swap elif A[i] > B[i - 1] and B[i] > A[i - 1]: # swap or keep nkeep = min(keep, swap) nswap = nkeep + 1 else: # keep nkeep = keep nswap = swap + 1 swap, keep = nswap, nkeep return min(swap, keep)

2. DFS, Brute Force
http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-801-minimum-swaps-to-make-sequences-increasing/
  int minSwap(vector<int>& A, vector<int>& B) {
    int ans = INT_MAX;
    dfs(A, B, 0, 0, ans);
    return ans;
  }
private:
  void dfs(vector<int>& A, vector<int>& B, int i, int c, int& ans) {
    if (c >= ans) return;
    
    if (i == A.size()) {
      ans = min(ans, c);
      return;
    }
    
    if (i == 0 || A[i] > A[i - 1] && B[i] > B[i - 1])
      dfs(A, B, i + 1, c, ans);
    
    if (i == 0 || A[i] > B[i - 1] && B[i] > A[i - 1]) {
      swap(A[i], B[i]);
      dfs(A, B, i + 1, c + 1, ans);
      swap(A[i], B[i]);
    }
  }

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