

0321-0330

321. Create Maximum Number $\star\star\star$

322. Coin Change $\star\star$

• 标准DP的方法，无法bottom-top迭代
• 完全背包问题，trick的点在于
• 从0...V迭代而不是coins[i-1]...V，因为在面对物品coins[i-1]时，即使背包大小放不下它，也要同步更新0...coins[i-1]-1的状态，不应该还是初始值了(-1or之后的amount+1)
• 初始值不要用-1，会导致代码很啰嗦，使用amount+1即，最糟糕的情况下，假设有1大小的物品，最多也就放amount次，amount+1一定时最大的了

func coinChange(coins []int, amount int) int {
    // return func1(coins, amount);
    // return func2(coins, amount);
    // return completeKnapsack4(coins, amount);
    // return completeKnapsack5(coins, amount);
    return completeKnapsack6(coins, amount);
}

// 1. Basic, Time Limit Exceeded
func func1(coins []int, amount int) int {
    if amount == 0 {
        return 0;
    }

    ret := -1;

    for _, coin := range coins {
        if coin == amount {
            return 1;
        }
        if coin < amount {
            tmp := func1(coins, amount - coin);
            if tmp != -1 {
                if ret == -1 {
                    ret = 1 + tmp;
                } else if ret > tmp + 1 {
                    ret = tmp + 1;
                }
            }
        }
    }

    return ret;
}

// 2. Top-down memo, Time Limit Exceeded
func func2(coins []int, amount int) int {
    memo := make(map[int]int);
    return helper2(coins, amount, memo);
}
func helper2(coins []int, amount int, memo map[int]int) int {
    if amount == 0 {
        return 0;
    }

    if val, ok := memo[amount]; ok {
        return val;
    }

    ret := -1;
    for _, coin := range coins {
        if coin == amount {
            ret = 1;
            break;
        }
        if coin < amount {
            tmp := helper2(coins, amount - coin, memo);
            if tmp != -1 {
                if ret == -1 {
                    ret = 1 + tmp;
                } else if ret > tmp + 1 {
                    ret = tmp + 1;
                }
            }
        }
    }
    memo[amount] = ret;

    return memo[amount];
}

// 3. Bottom-up??

// 4. Complete knapsack, 2D array, -1 as failed condition => complex checking
func completeKnapsack4(coins []int, amount int) int {
    if amount == 0 {
        return 0;
    }

    N := len(coins);
    V := amount;

    pack := make([][]int, N+1);
    for i := 0; i < N+1; i++ {
        pack[i] = make([]int, V+1);
        for j := 0; j < V+1; j++ {
            pack[i][j] = -1;
        }
    }
    for i := 0; i < N+1; i++ {
        pack[i][0] = 0;
    }

    for i := 1; i <= N; i++ { 
        for v := 0; v <= V; v++ {
            if pack[i-1][v] != -1 {
                pack[i][v] = pack[i-1][v];
            }
            if v >= coins[i-1] && pack[i][v-coins[i-1]] != -1 {
                if pack[i][v] == -1 {
                    pack[i][v] = pack[i][v-coins[i-1]] + 1;
                } else {
                    pack[i][v] = min(pack[i][v], pack[i][v-coins[i-1]] + 1);
                }
            }
        }
    }

    ret := -1;
    for i := 1; i <= N; i++ {
        if pack[i][V] != -1 {
            if ret == -1 {
                ret = pack[i][V];
            } else {
                ret = min(ret, pack[i][V]);
            }
        }
    }

    return ret;
}

// 5. Complete knapsack, 2D array, amount + 1 as failed condition => simple checking
// !!!Key Point, set ret = amount + 1,
// because max number of operations is put 1 into package with amount time
func completeKnapsack5(coins []int, amount int) int {
    if amount == 0 {
        return 0;
    }

    N := len(coins);
    V := amount;

    pack := make([][]int, N+1);
    for i := 0; i < N+1; i++ {
        pack[i] = make([]int, V+1);
        for j := 0; j < V+1; j++ {
            pack[i][j] = amount + 1;
        }
    }
    for i := 0; i < N+1; i++ {
        pack[i][0] = 0;
    }

    for i := 1; i <= N; i++ { 
        for v := 0; v <= V; v++ {
            pack[i][v] = pack[i-1][v];
            if v >= coins[i-1] {
                pack[i][v] = min(pack[i][v], pack[i][v-coins[i-1]] + 1);
            }
        }
    }

    ret := amount + 1;
    for i := 1; i <= N; i++ {
        ret = min(ret, pack[i][V]);
    }
    if ret == amount + 1 {
        return -1;
    }

    return ret;
}

// 6. Complete knapsack, 1D array
func completeKnapsack6(coins []int, amount int) int {
    if amount == 0 {
        return 0;
    }

    N := len(coins);
    V := amount;

    pack := make([]int, V+1);
    for i := 1; i < V+1; i++ {
        pack[i] = amount + 1;
    }

    for i := 1; i <= N; i++ { 
        for v := 0; v <= V; v++ {
            if v >= coins[i-1] {
                pack[v] = min(pack[v], pack[v-coins[i-1]] + 1);
            }
        }
    }

    if pack[V] == amount + 1 {
        return -1;
    }

    return pack[V];
}

func min(a int, b int) int {
    if a < b {
        return a;
    }
    return b;
}

323. Number of Connected Components in an Undirected Graph $\star\star$

324. Wiggle Sort II $\star\star$

325. Maximum Size Subarray Sum Equals k $\star\star$

326. Power of Three $\star$

327. Count of Range Sum $\star\star\star$

328. Odd Even Linked List $\star\star$

class Solution {
 public:
  ListNode* oddEvenList(ListNode* head) {
    if (!head) return NULL;

    ListNode dummyOdd(0);
    ListNode dummyEven(0);
    ListNode* prevOdd = &dummyOdd;
    ListNode* prevEven = &dummyEven;
    int index = 0;

    while (head) {
      auto next = head->next;
      head->next = NULL;
      if (index++ & 1) {
        prevEven->next = head;
        prevEven = head;
      } else {
        prevOdd->next = head;
        prevOdd = head;
      }
      head = next;
    }
    prevOdd->next = dummyEven.next;

    return dummyOdd.next;
  }
};

329. Longest Increasing Path in a Matrix $\star\star\star$

330. Patching Array $\star\star\star$