[Leetcode] Optimal Account Balancing, Solution

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for $10. Then later Chris gave Alice $5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y $z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as [[0, 1, 10], [2, 0, 5]].

Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.

Note:

1. A transaction will be given as a tuple (x, y, z). Note that x ? y and z > 0.
2. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.

Example 1:

Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 $10.
Person #2 gave person #0 $5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 $5 each.

Example 2:

Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 $10.
Person #1 gave person #0 $1.
Person #1 gave person #2 $5.
Person #2 gave person #0 $5.

Therefore, person #1 only need to give person #0 $4, and all debt is settled.

[Thoughts]
很有意思的一道题。首先，对图进行处理，算清楚每个人的负债， 有两个前提：
1. 最后的负债一定可以清零
2. 题目不要求保留原有付款关系。

所以，对图做个dfs即可。

[Code]

1:    int minTransfers(vector<vector<int>>& trans) {  
2:      unordered_map<int, long> bal; // balance on each person  
3:      for(auto t: trans) {  
4:        bal[t[0]] -= t[2];  
5:        bal[t[1]] += t[2];  
6:      }  
7:        
8:      vector<long> debt;  
9:      for(auto b: bal) {  
10:        // only track the person who has debt    
11:        if(b.second) debt.push_back(b.second);  
12:      }  
13:      return dfs(0, 0, debt);  
14:    }  
15:    
16:    // get the min number of transactions starting from s  
17:    int dfs(int s, int cnt, vector<long>& debt) {   
18:         while (s < debt.size() && !debt[s]) ++s; // skip all zero debt  
19:        
20:         int res = INT_MAX;  
21:         for (long i = s+1, prev = 0; i < debt.size(); ++i) {  
22:        // skip same value or same sign debt  
23:        if (debt[i] != prev && debt[i]*debt[s] < 0){   
24:             debt[i] += debt[s];  
25:          res = min(res, dfs(s+1,cnt+1, debt));  
26:          debt[i]-=debt[s];  
27:          prev = debt[i];  
28:        }  
29:      }  
30:         return res < INT_MAX? res : cnt;  
31:    }  

[LeetCode] Jump Game II 解题报告

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

» Solve this problem

[解题思路]
二指针问题，最大覆盖区间。
从左往右扫描，维护一个覆盖区间，每扫过一个元素，就重新计算覆盖区间的边界。比如，开始时区间[start, end], 遍历A数组的过程中，不断计算A[i]+i最大值（即从i坐标开始最大的覆盖坐标），并设置这个最大覆盖坐标为新的end边界。而新的start边界则为原end+1。不断循环，直到end> n.


[Code]

1:    int jump(int A[], int n) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function  
4:      int start = 0;  
5:      int end = 0;  
6:      int count =0;  
7:      if(n == 1) return 0;  
8:      while(end < n)  
9:      {  
10:        int max = 0;  
11:        count++;  
12:        for(int i =start; i<= end ; i++ )  
13:        {   
14:          if(A[i]+i >= n-1)  
15:          {            
16:            return count;  
17:          }  
18:          if(A[i]+ i > max)  
19:            max = A[i]+i;  
20:        }  
21:        start = end+1;  
22:        end = max;        
23:      }  
24:    }  

[注意]
Line7，当n=1的时候，需要特殊处理一下。