算法杂记 2023/04/02

算法杂记 2023/04/02

• 算法杂记 2023/04/02
  • 网易笔试第二题
  • 输入：
  • 输出：
  • 例子：
  • 6329. Make K-Subarray Sums Equal

网易笔试第二题

给定一棵中序遍历的二叉树，如果当前树为空则表示为X，如果不为空则表示为(left_tree)cur_value(right_tree)，其中left_tree和right_tree分别表示按此规则序列化之后的左右子树字符串。找出重复子树的数量，相同子树只计算一次。

输入：

字符编码的二叉树

输出：

重复子树的个数

例子：

输入：
((X)2(X))1(((X)4(X))3((X)2(X)))
输出：
1

解释：只有相同节点2

这题如果不考虑反序列化的操作，实际上就是力扣的一道原题 LC625，寻找重复的子树，我们对子树进行序列化后用哈希表存储就行了。

考虑如何进行反序列化操作。流程，设当前索引是 index：

• 如果碰到 X ，说明是 NULL 节点，直接 return
• 碰到 ( 说明存在左子树，进入下一层递归，最后返回得到的左子树和新索引。
• 从当前索引开始，直到第一次碰到 ( ，该区间表示节点值 int(s[index->end])
• 碰到 ( 说明存在右子树，进入下一层递归，最后返回得到的右子树和新索引。

最后代码：

def deserialize(s):
    def helper(index):
        # print("index", index)
        if s[index] == 'X':
            return None, index + 1

        if s[index] == '(':
            left, index = helper(index + 1)
        else:
            left = None
            index = index + 1
        index += 1
        
        i = index
        while s[i] != '(':
            i += 1
        num = int(s[index:i])
        index = i
        

        if s[index] == '(':
            right, index = helper(index + 1)
        else:
            right = None
            index = index + 1
        # print("finish index", index)
        return TreeNode(num, left, right), index + 1

    root, _ = helper(0)
    return root

6329. Make K-Subarray Sums Equal

You are given a 0-indexed integer array arr and an integer k. The array arr is circular. In other words, the first element of the array is the next element of the last element, and the last element of the array is the previous element of the first element.

You can do the following operation any number of times:

• Pick any element from arr and increase or decrease it by 1.

Return the minimum number of operations such that the sum of each subarray of length k is equal.

A subarray is a contiguous part of the array.

Example 1:

Input: arr = [1,4,1,3], k = 2
Output: 1
Explanation: we can do one operation on index 1 to make its value equal to 3.
The array after the operation is [1,3,1,3]
- Subarray starts at index 0 is [1, 3], and its sum is 4 
- Subarray starts at index 1 is [3, 1], and its sum is 4 
- Subarray starts at index 2 is [1, 3], and its sum is 4 
- Subarray starts at index 3 is [3, 1], and its sum is 4 

Example 2:

Input: arr = [2,5,5,7], k = 3
Output: 5
Explanation: we can do three operations on index 0 to make its value equal to 5 and two operations on index 3 to make its value equal to 5.
The array after the operations is [5,5,5,5]
- Subarray starts at index 0 is [5, 5, 5], and its sum is 15
- Subarray starts at index 1 is [5, 5, 5], and its sum is 15
- Subarray starts at index 2 is [5, 5, 5], and its sum is 15
- Subarray starts at index 3 is [5, 5, 5], and its sum is 15 

Constraints:

• 1 <= k <= arr.length <= 105
• 1 <= arr[i] <= 109

不使用裴蜀定理，arr[i...i+k-1] = arr[i+1...i+k] 实际上等价于 arr[i] = arr[i+k] 我们可以相对于循环查找。

class Solution {
public:
    long long makeSubKSumEqual(vector<int>& arr, int k) {
        int n = arr.size();
        long long ans = 0;
        vector<int> vis(n, 0);
        for (int i = 0; i < n; ++ i){
            if (vis[i]) continue;
            vector<int> cur;
            for (int j = i; !vis[j]; j = (j + k) % n){
                vis[j] = 1;
                cur.push_back(arr[j]);
            }
            int m = cur.size();
            sort(cur.begin(), cur.end());
            for (auto x: cur) ans += abs(x  - cur[m / 2]);
        }
        return ans;
    }
};

否则，我们得使用裴蜀定理，定理是：ax + by = gcd(a, b) ，我们可以进行如下推导：

这样，我们就直接转化成在一维数组上进行一遍遍历得到结果（感觉在时间复杂度方面没区别）。

class Solution {
public:
    int gcd(int x, int y){
        if (y == 0) return x;
        return gcd(y, x % y);
    }

    long long makeSubKSumEqual(vector<int>& arr, int k) {
        int n = arr.size();
        int d = gcd(n, k);
        long long ans = 0;
        for (int i = 0; i < d; ++ i){
            vector<int> cur;
            for (int j = i; j < n; j += d) cur.push_back(arr[j]);
            sort(cur.begin(), cur.end());
            int _m = cur.size();
            for (auto x: cur) ans += abs(x - cur[_m / 2]);
        }
        return ans;
    }
};