This page looks best with JavaScript enabled

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

 ·  ☕ 9 min read

数据结构这块先是看了浙江大学的数据结构公开课和《数据结构与算法》黑皮书, 看完之后感觉自己好像都懂了，其实并没理解。所以定两个计划：

  • 完成课后作业代码
  • 完成leetcode 的 Daily Challenge

我的习题答案在这：eval-exec/Algorithm
才疏学浅，请多批评。

2121. Intervals Between Identical Elements

You are given a 0-indexed array of n integers arr.

The interval between two elements in arr is defined as the absolute difference between their indices. More formally, the interval between arr[i] and arr[j] is |i - j|.

Return an array intervals of length n where intervals[i] is the sum of intervals between arr[i] and each element in arr with the same value as arr[i].

Note: |x| is the absolute value of x.

 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

class Solution {
public:
  vector<long long> getDistances(vector<int> &arr) {
    unordered_map<int, vector<int>> mm;
    for (int i = 0; i < arr.size(); i++) {
      mm[arr[i]].push_back(i);
    }
    vector<long long> rets(arr.size());
    for (auto m : mm) {
      vector<long long> leftsum(m.second.size());
      int count = 1;
      for (int i = 1; i < m.second.size(); i++) {
        int delta = m.second[i] - m.second[i - 1];
        leftsum[i] = leftsum[i - 1] + count * delta;
        count++;
      }
      rets[m.second.back()] = leftsum.back();

      vector<long long> rightsum(m.second.size());
      count = 1;
      for (int i = m.second.size() - 2; i >= 0; i--) {
        int delta = m.second[i + 1] - m.second[i];
        rightsum[i] = rightsum[i + 1] + count * delta;
        count++;
        rets[m.second[i]] = leftsum[i] + rightsum[i];
      }
    }
    return rets;
  }
};

Best Time to Buy and Sell Stock III

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete at most two transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

先初始化一维动态规划的备忘录: dp;
我的思路是先从 prices 从左到右遍历。先找到在i 时间处，最多交易一次的最大收益。
再从右到左遍历 prices，找到在i时间处, 最多交易一次的最大收益。
其中：在第二次遍历的时候，根据 dp[i-1]和 dp[i]去更新 “最多交易两次” 的最大总收益。

代码代码如下：

 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

class Solution {
 public:
  int maxProfit(vector<int> &prices) {
	vector<int> dp(prices.size(), 0);
	if (prices.size() <= 1)return 0;
	{
	  int low = prices[0];
	  dp[0] = 0;
	  for (int i = 1; i < prices.size(); i++) {
		dp[i] = prices[i] - low > dp[i - 1] ? prices[i] - low : dp[i - 1];
		low = prices[i] < low ? prices[i] : low;
	  }
	}
	int maxProfit = dp.back();
	{
	  dp[prices.size() - 1] = 0;
	  int high = prices[prices.size() - 1];
	  for (int i = prices.size() - 2; i >= 1; i--) {
		dp[i] = high - prices[i] > dp[i + 1] ? high - prices[i] : dp[i + 1];
		high = prices[i] > high ? prices[i] : high;
		maxProfit = max(maxProfit, dp[i - 1] + dp[i]);
	  }
	}
	return maxProfit;
  }
};

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<vector<long>> dp(m, vector<long>(n));
	for (int move = 1; move <= maxMove; move++) {
	  vector<vector<long>> tmp(m, vector<long>(n));
	  for (int mi = 0; mi < m; mi++) {
		for (int ni = 0; ni < n; ni++) {
		  for (auto dir : dirs) {
			auto now = vector<int>{mi, ni};
			now[0] += dir[0];
			now[1] += dir[1];
			bool valid = true;
			if (now[0] < 0 || now[0] >= m || now[1] < 0 || now[1] >= n) valid = false;
			if (valid) {
			  tmp[mi][ni] += dp[now[0]][now[1]];
			} else {
			  tmp[mi][ni] += 1;
			}
			tmp[mi][ni] %= mod;
		  }
		}
	  }
	  dp = tmp;
	}
	return dp[startRow][startColumn] % mod;
  }
 private:
  const long mod = 1e9+7;
  vector<vector<int>> 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]].

我的解法： 运行速度打败了 93% 的人
时间复杂度：O(N), N 为 解压后的数组长度
时间复杂度：小于等于 O(N)， 因为内部维护了返回值： rets, rets 的最大长度一定小于等于 N

 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:
  vector<vector<int>> findRLEArray(vector<vector<int>>& encoded1, vector<vector<int>>& encoded2) {
	int ei1=0,ei2 = 0;
	int ni1= 0,ni2= 0;
	vector<vector<int>> rets;
	while (1){
	  if (ei1 == encoded1.size()) break;
	  int pd = encoded1[ei1][0]*encoded2[ei2][0];
	  if (rets.empty()){
		rets.push_back({pd,1});
		ni1++;
		ni2++;
	  }else{
		int ec = min(encoded1[ei1][1]-ni1,encoded2[ei2][1]-ni2);
		if (pd == rets.back()[0]){
		  rets.back()[1]+=ec;
		}else{
		  rets.push_back({pd,ec});
		}
		ni1+=ec;
		ni2+=ec;
	  }
	  if (ni1 == encoded1[ei1][1]){
		ei1++;
		ni1=0;
	  }
	  if (ni2 == encoded2[ei2][1]){
		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<vector<int>> nodes) {
        base.resize(n, -1);
        for (const auto &node:nodes) {
            int rx = find_root(node[0]);
            int ry = find_root(node[1]);
            if (rx == ry) {
                return true;
            }
            base[rx] = ry;
        }
        return false;
    }
  private:
    vector<int> base;
    int find_root(int node) {
        if (base[node] == -1) {
            return node;
        }
        return find_root(base[node]);
    }
};

int main() {
    Solution solution;
    vector<vector<int>> 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 等于连续的正数的累加和，那么我们只需要用俩数表示这个范围：[n1,n2] （左右闭区间）。
拿到这道题之后， 我的第一反应就是定义一个 n （n 从 1 -> N）检查：

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

而且，我们检查一个闭区间的连续的数的累加和等不等于N，只要直到这串数字的中位数和这串数字的个数：n就行了：

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

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

仔细想了想， n 不用从 1 递增到N， 因为考虑有这种情况：
假设 N = 5，
如果 n = 1： 5 / 1 = 5 ok
如果 n = 2： 5 / 2 = 2 2 + (2 + 1) == 5 ;ok
如果 n = 3: 5 / 3 = 1 1 的左边是 0， 1 的右边是 2， 这时候我们就不用检查 0 + 1 + 2 一组满足要求的组合了。
于是就 加一个剪枝判断，及时退出 循环！

以下是我的解法（不同于官方给的答案）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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;
    }
};

时间、空间复杂度分析

因为 n 一直从 1 到 N 递增,
递增到这样的情况时就不能递增了：
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
要是 n 还递增，就超过题目要求的 positive integer 的限制了！

即： (N /(2*n)) = n ，所以空间复杂度是 sqrt(N*2)

  • 时间复杂度：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 组成的一串的 1 全部合并到一起呢？并且要用最小的操作次数？这串数的 0 或 1 的总数我可以算出来(假设为 ones_len)，那么这个问题就可以转化为:给定一个大小为 ones_len 的窗口，得把这个窗口放在哪个位置，才能让窗口内的 0 的数量最小？

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

class Solution {
  public:
    int minSwaps(vector<int> &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;
    }
};

时间/空间复杂度分析： O(N), O(1)

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.

思路:
这题一看就知道用栈就 ok

 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

class Solution {
  public:
    string removeDuplicates(string s, int k) {
        stack<pair<char, int>> 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

class Solution {
  public:
    int countNicePairs(vector<int> &nums) {
        unordered_map<int, int> 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;
    }
};

时间复杂度：O(N):只在 for 循环中遍历了一遍 nums
空间复杂度：O(N) , 我使用了额外的 unordered_map 来保持遍历历史

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 = [[2],[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).

应该从最底部向上走：用dp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
  public:
    int minimumTotal(vector<vector<int>> &triangle) {
        int height = triangle.size();
        vector<int> dp(triangle[height - 1]);
        for (int h = height - 2; h >= 0; h--) {
            vector<int> tmp(dp);
            for (int i = 0; i <= h; i++) {
                dp[i] = triangle[h][i] + min(tmp[i], tmp[i + 1]);
            }
        }
        return dp[0];
    }
};

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<int> &arr) {
        int last = arr[1] - arr[0];
        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<int> &a, const vector<int> &b) const {
            if (a[1] > b[1]) return true;
            if (a[1] == b[1]) return a[2] > b[2];
            return false;
        }
    };
    vector<int> getOrder(vector<vector<int>> &tasks) {

        for (int i = 0; i < tasks.size(); i++) {
            tasks[i].push_back(i);
        }

        sort(tasks.begin(), tasks.end(), [](const vector<int> &v1, const vector<int> &v2) -> bool {
            return v1[0] < v2[0];
        });

        priority_queue<vector<int>, vector<vector<int>>, my_comparator> pq;
        vector<int> rets;
        long now = 0;
        int ti = 0;

        while (rets.size() < tasks.size()) {
            if (pq.empty() && ti < tasks.size()) {
                if (tasks[ti][0] > now) now = tasks[ti][0];
            }
            while (ti < tasks.size() && tasks[ti][0] <= now) {
                pq.push(tasks[ti]);
                ti++;
            }
            if (!pq.empty()) {
                auto top = pq.top();
                pq.pop();
                now += top[1];
                rets.push_back(top[2]);
            }
        }
        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.

思路：
要找出一个分区内连续的 01 串，那就以最中心的01为中心，向左右展开搜索，如果左翼和右翼满足条件，则 count++，否则 搜索下一个。

 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
EXEC
WRITTEN BY
EXEC
Eval EXEC