This page looks best with JavaScript enabled

[学习笔记] 算法与数据结构

 ·  ☕ 4 min read

我是个从未接受过计算机专业教育的野生程序员, 数据结构这块先是看了浙江大学的数据结构公开课和《数据结构与算法》黑皮书, 看完之后感觉自己好像都懂了,其实并没理解。所以定个计划:完成 leetcodeDaily Challenge。我的习题答案在这:eval-exec/Algorithm ,才疏学浅,请多批评。

专项练习

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] (左右闭区间)。
拿到这道题之后, 我的第一反应就是定义一个 nn1 -> 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 的左边是 01 的右边是 2, 这时候我们就不用检查 0 + 1 + 2 一组满足要求的组合了。
于是就 加一个剪枝判断,及时退出 循环!

以下是我的解法(不同于官方给的答案)

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

时间、空间复杂度分析

因为 n 一直从 1N 递增,
递增到这样的情况时就不能递增了:
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
19
20
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
35
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
24
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 来保持遍历历史

Share on

EXEC
WRITTEN BY
EXEC
Evil EXEC