## [课后作业] 算法与数据结构

• 完成课后作业
• 完成leetcodeDaily Challenge

## Out Of Boundary Paths

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent four cells in the grid (possibly out of the grid crossing the grid boundary). You can apply at most maxMove moves to the ball. Given the five integers m, n, maxMove, startRow, startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 109 + 7.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37   class Solution { public: int findPaths(int m, int n, int maxMove, int startRow, int startColumn) { vector> dp(m, vector(n)); for (int move = 1; move <= maxMove; move++) { vector> tmp(m, vector(n)); for (int mi = 0; mi < m; mi++) { for (int ni = 0; ni < n; ni++) { for (auto dir : dirs) { auto now = vector{mi, ni}; now += dir; now += dir; bool valid = true; if (now < 0 || now >= m || now < 0 || now >= n) valid = false; if (valid) { tmp[mi][ni] += dp[now][now]; } else { tmp[mi][ni] += 1; } tmp[mi][ni] %= mod; } } } dp = tmp; } return dp[startRow][startColumn] % mod; } private: const long mod = 1e9+7; vector> dirs = { {1, 0}, {-1, 0}, {0, 1}, {0, -1}, }; }; 

## Product of Two Run-Length Encoded Arrays

Run-length encoding is a compression algorithm that allows for an integer array nums with many segments of consecutive repeated numbers to be represented by a (generally smaller) 2D array encoded. Each encoded[i] = [vali, freqi] describes the ith segment of repeated numbers in nums where vali is the value that is repeated freqi times.

Input: encoded1 = [[1,3],[2,1],[3,2]], encoded2 = [[2,3],[3,3]]
Output: [[2,3],[6,1],[9,2]]
Explanation: encoded1 expands to [1,1,1,2,3,3] and encoded2 expands to [2,2,2,3,3,3].
prodNums = [2,2,2,6,9,9], which is compressed into the run-length encoded array [[2,3],[6,1],[9,2]].

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36  class Solution { public: vector> findRLEArray(vector>& encoded1, vector>& encoded2) { int ei1=0,ei2 = 0; int ni1= 0,ni2= 0; vector> rets; while (1){ if (ei1 == encoded1.size()) break; int pd = encoded1[ei1]*encoded2[ei2]; if (rets.empty()){ rets.push_back({pd,1}); ni1++; ni2++; }else{ int ec = min(encoded1[ei1]-ni1,encoded2[ei2]-ni2); if (pd == rets.back()){ rets.back()+=ec; }else{ rets.push_back({pd,ec}); } ni1+=ec; ni2+=ec; } if (ni1 == encoded1[ei1]){ ei1++; ni1=0; } if (ni2 == encoded2[ei2]){ ei2++; ni2=0; } } return rets; } }; 

## Union Find

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31  class Solution { public: bool detect_cycle(int n, vector> nodes) { base.resize(n, -1); for (const auto &node:nodes) { int rx = find_root(node); int ry = find_root(node); if (rx == ry) { return true; } base[rx] = ry; } return false; } private: vector base; int find_root(int node) { if (base[node] == -1) { return node; } return find_root(base[node]); } }; int main() { Solution solution; vector> nodes = {{0, 1},{1, 2},{1, 3},{3, 4},{2, 5}, // {5,4}, }; cout << solution.detect_cycle(6, nodes) << endl; } 

## 专项练习

### 图

https://leetcode.com/discuss/general-discussion/655708/Graph-For-Beginners-Problems-or-Pattern-or-Sample-Solutions

# leetcode 习题

## Consecutive Numbers Sum

Given a positive integer N, how many ways can we write it as a sum of consecutive positive integers?

Example 1:

Input: 5
Output: 2
Explanation: 5 = 5 = 2 + 3


Example 2:

Input: 9
Output: 3
Explanation: 9 = 9 = 4 + 5 = 2 + 3 + 4


Example 3:

Input: 15
Output: 4
Explanation: 15 = 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5


Note: 1 <= N <= 10 ^ 9.

• N能不能用1个连续的正数表示？
• N能不能用2个连续的正数表示？
• N能不能用3个连续的正数表示？
• N能不能用4个连续的正数表示？
• N能不能用5个连续的正数表示？
• N能不能用N个连续的正数表示？

if n is even{
sum = (num + num + 1 ) * n/2

}else { // n is odd
sum = num * n
}


  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  class Solution { public: int consecutiveNumbersSum(int N) { int count = 1, n = 2; while (n < N) { // let n from 1 to N int x = N / n; if (n % 2 == 0) { // if n is an even number if (x < n / 2) break; if (N == (x + (x + 1)) * n / 2) count++; } else { // else n is an odd number if (x < n / 2 + 1) break; if (N == x * n) count++; } n++; } return count; } }; 

### 时间、空间复杂度分析

1, 2, 3, 4, 5, ... n-2, n-1, n, n+1, n+2, n+3, ... 2n-2, 2n-1, 2n, ... , N-3, N-2, N-1, N

• 时间复杂度：O(sqrt(N*2)
• 空间复杂度：O(1)

## Minimum Swaps to Group All 1’s Together

Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.
example 1

Input: data = [1,0,1,0,1]
Output: 1
Explanation:
There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.


example 2

Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation:
One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].


0,1,0,1,1,1,[1,0,0,0，0,1,0,1],0,0,0,1
|               |
[      窗口      ]


  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20  class Solution { public: int minSwaps(vector &data) { int len = data.size(); int win = count_if(data.begin(), data.end(), [](const int &n) -> bool { return n == 1; }); int zeros = 0; for (int i = 0; i < win; i++) { if (data[i] == 0)zeros++; } int ret = zeros; for (int i = win; i < len; i++) { if (data[i] == 0) zeros++; if (data[i - win] == 0) zeros--; ret = min(ret, zeros); } return ret; } }; 

## Remove All Adjacent Duplicates in String II

Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together.
We repeatedly make k duplicate removals on s until we no longer can.
Return the final string after all such duplicate removals have been made.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35  class Solution { public: string removeDuplicates(string s, int k) { stack> st; for (char c : s) { if (st.empty()) { st.push(make_pair(c, 1)); } else { auto top = st.top(); if (top.first == c) { top.second++; st.pop(); if (top.second != k) { st.push(top); } } else { st.push(make_pair(c, 1)); } } } string ret; while (!st.empty()) { auto top = st.top(); st.pop(); int n = 0; while (n < top.second) { n++; ret.insert(ret.begin(), top.first); } } return ret; } }; 

## Count Nice Pairs In An Array

You are given an array nums that consists of non-negative integers. Let us define rev(x) as the reverse of the non-negative integer x. For example, rev(123) = 321, and rev(120) = 21. A pair of indices (i, j) is nice if it satisfies all of the following conditions:

0 <= i < j < nums.length
nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])
Return the number of nice pairs of indices. Since that number can be too large, return it modulo 109 + 7.

Example 1:

Input: nums = [42,11,1,97]
Output: 2
Explanation: The two pairs are:
- (0,3) : 42 + rev(97) = 42 + 79 = 121, 97 + rev(42) = 97 + 24 = 121.
- (1,2) : 11 + rev(1) = 11 + 1 = 12, 1 + rev(11) = 1 + 11 = 12.



nums[i] + rev(nums[j]) == nums[j] + rev(nums[i])

nums[i] - rev(nums[i]) == nums[j] - rev(nums[j])

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24  class Solution { public: int countNicePairs(vector &nums) { unordered_map memo; long count = 0; const int mod = 1e9+7; int v = 0; for (int n : nums) { v = n - rev(n); count += memo[v]++; } return count % mod; } private: int rev(int n) { int ret = 0; while (n > 0) { ret = ret * 10 + n % 10; n /= 10; } return ret; } }; 

## Triangle

Given a triangle array, return the minimum path sum from top to bottom.

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Example 1:

Input: triangle = [,[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: The triangle looks like:
2
3 4
6 5 7
4 1 8 3
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).


  1 2 3 4 5 6 7 8 9 10 11 12 13 14  class Solution { public: int minimumTotal(vector> &triangle) { int height = triangle.size(); vector dp(triangle[height - 1]); for (int h = height - 2; h >= 0; h--) { vector tmp(dp); for (int i = 0; i <= h; i++) { dp[i] = triangle[h][i] + min(tmp[i], tmp[i + 1]); } } return dp; } }; 

## Missing Number In Arithmetic Progression

In some array arr, the values were in arithmetic progression: the values arr[i+1] - arr[i] are all equal for every 0 <= i < arr.length - 1.
Then, a value from arr was removed that was not the first or last value in the array.
Return the removed value.

Input: arr = [5,7,11,13]
Output: 9
Explanation: The previous array was [5,7,9,11,13].

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  class Solution { public: int missingNumber(vector &arr) { int last = arr - arr; for (int i = 2; i < arr.size(); i++) { int now = arr[i] - arr[i - 1]; if (now == last) { last = now; continue; } if (last == now * 2) { return arr[i - 1] - now; } else { return arr[i - 1] + last; } } return arr.back(); } }; 

## Single Process CPU

You are given n​​​​​​ tasks labeled from 0 to n - 1 represented by a 2D integer array tasks, where tasks[i] = [enqueueTimei, processingTimei] means that the i​​​​​​th​​​​ task will be available to process at enqueueTimei and will take processingTimei to finish processing.
You have a single-threaded CPU that can process at most one task at a time and will act in the following way:

If the CPU is idle and there are no available tasks to process, the CPU remains idle.
If the CPU is idle and there are available tasks, the CPU will choose the one with the shortest processing time. If multiple tasks have the same shortest processing time, it will choose the task with the smallest index.
Once a task is started, the CPU will process the entire task without stopping.
The CPU can finish a task then start a new one instantly.
Return the order in which the CPU will process the tasks.


Example 1:

Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows:
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42  class Solution { public: struct my_comparator { bool operator()(const vector &a, const vector &b) const { if (a > b) return true; if (a == b) return a > b; return false; } }; vector getOrder(vector> &tasks) { for (int i = 0; i < tasks.size(); i++) { tasks[i].push_back(i); } sort(tasks.begin(), tasks.end(), [](const vector &v1, const vector &v2) -> bool { return v1 < v2; }); priority_queue, vector>, my_comparator> pq; vector rets; long now = 0; int ti = 0; while (rets.size() < tasks.size()) { if (pq.empty() && ti < tasks.size()) { if (tasks[ti] > now) now = tasks[ti]; } while (ti < tasks.size() && tasks[ti] <= now) { pq.push(tasks[ti]); ti++; } if (!pq.empty()) { auto top = pq.top(); pq.pop(); now += top; rets.push_back(top); } } return rets; } }; 

## Count Binary Substrings

Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".

Notice that some of these substrings repeat and are counted the number of times they occur.

Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together.


  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22  class Solution { public: int countBinarySubstrings(string s) { int count = 0; for (int i = 0; i + 1 < s.size(); i++) { if (s[i] == s[i + 1]) continue; // i-1,i,i+,i+2 count++; int left = i - 1, right = i + 2; while (left >= 0 && right < s.size()) { if (s[left] == s[left + 1] && s[right] == s[right - 1]) { count++; left--; right++; } else { break; } } } return count; } }; 
Share on WRITTEN BY
EXEC
Evil EXEC