发表更新LeetCode / 算法26 分钟读完 (大约3825个字)

LeetCode-27

[Medium] 29. 两数相除

分析

  • 只能用加减法，最朴素的方法是循环相减/加，直到小于0/大于0，计算加/减的次数
  • 这样算法是o(n)，考虑到i+=i或者i<<=1相当于i*=2,i>>=1相当于i/=2
  • 只考虑divisor, divident都大于0的情况，先找到整数p，使得 $divisor2^p <= divident$，$divident-=divisor2^p, ratio+=2^p$若divident为0，则商为ratio，否则重复上面的过程，直到divident为0。
  • 考虑divisor, divident到可能正，可能负，而负数的范围大于正数，直接将所有整数变成负数，并记录符号
  • 注意取相反数的时候要用位运算~x+1

代码

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
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(dividend < divisor && dividend > 0) return 0;
        if(dividend > divisor && dividend < 0) return 0;
        if((dividend == INT_MIN) && (divisor == -1)) return INT_MAX;
        if((dividend == INT_MIN) && (divisor == 1)) return INT_MIN;
        if(dividend == divisor) return 1;
        if(dividend < 0 && divisor > 0 && dividend == ~divisor+1) return -1;
        if(dividend > 0 && divisor < 0 && ~dividend+1 == divisor) return -1;
        bool sign = false;
        if(dividend < 0) {
            sign = !sign;
        } else {
            dividend = ~dividend+1;
        }
        if(divisor < 0) {
            sign = !sign;
        } else {
            divisor = ~divisor+1;
        }
        int res = 0;
        int i = -1;
        while(dividend < divisor && divisor >= (INT_MIN >> 1)) {
            divisor += divisor;
            i+=i;
        }
        while(true) {
            while(dividend > divisor) {
                if(i == -1) {
                    return sign ? (res) : (~res+1);
                }
                divisor >>= 1;
                i>>=1;
            }
            dividend -= divisor;
            res+=i;
        }
    }
};

275. H 指数 II

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int l = 0, r = n-1;
        int res = 0;
        while(l < r) {
            int mid = (r - l) / 2 + l;
            if(n - mid <= citations[mid]) {
                res = max(res, n-mid);
                r=mid-1;
            } else {
                res = max(res, citations[mid]);
                l = mid+1;
            }
        }
        return max(res, min(citations[l], n-l));
    }
};

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int n = citations.size();
        int l = 0, r = n-1;
        int res = 0;
        while(l <= r) {
            int mid = (r - l) / 2 + l;
            if(n - mid <= citations[mid]) {
                r=mid - 1;
            } else {
                l = mid+1;
            }
        }
        return n-l;
    }
};

274. H 指数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int hIndex(vector<int>& citations) {
        int arr[1001] = {0};
        int max_cite = 0;
        int min_cite = INT_MAX;
        for(int n : citations) {
            arr[n]++;
            max_cite = max(max_cite, n);
            min_cite = min(min_cite, n);
        }
        int sum = 0, res = 0;
        for(int i = max_cite; i >= min_cite; i--) {
            sum += arr[i];
            res = max(res, min(sum, i));
        }
        return res;
    }
};

2558. 从数量最多的堆取走礼物

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    long long pickGifts(vector<int>& gifts, int k) {
        priority_queue<int> gift_heap;
        for(int n : gifts) {
            gift_heap.push(n);
        }
        long long res = 0;
        while(k--) {
            gift_heap.push(sqrt(gift_heap.top()));
            gift_heap.pop();
        }
        while(!gift_heap.empty()) {
            res += gift_heap.top();
            gift_heap.pop();
        }
        return res;
    }
};

1465. 切割后面积最大的蛋糕

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {
        int h_len = horizontalCuts.size();
        int v_len = verticalCuts.size();
        sort(verticalCuts.begin(), verticalCuts.end());
        sort(horizontalCuts.begin(), horizontalCuts.end());
        int max_h = max(h - horizontalCuts.back(), horizontalCuts.front());
        int max_v = max(w - verticalCuts.back(), verticalCuts.front());
        for(int i = 1; i < h_len; i++) {
            max_h = max(max_h, horizontalCuts[i] - horizontalCuts[i-1]);
        }
        for(int i = 1; i < v_len; i++) {
            max_v = max(max_v, verticalCuts[i] - verticalCuts[i-1]);
        }
        return ((long long)(max_h)%1000000007 * (max_v)%1000000007) % 1000000007;
    }
};

2520. 统计能整除数字的位数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int countDigits(int num) {
        int n = num;
        int ret = 0;
        while(n) {
            if(num % (n % 10) == 0) {
                ret++;
            }
            n /= 10;
        }
        return ret;
    }
};

2698. 求一个整数的惩罚数

思路

  • 首先要计算出所有满足sum(split(i*i)) == i的元素
  • 发现很少，直接放到数组里去查表
  • 对于一个数i，希望它拆分后和等于target
    • 先分成a，b两份，判断是否等于，等于return true，不等于就把a分开（递归）

代码

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:
    int punishmentNumber(int n) {
        int res = 0;
        // for(int i = 1; i <= 1000; i++) {
        //     int n = i*i;
        //     if(search(i*i, i)) {
        //         cout << i << ", ";
        //     }
        // }
        int punish_arr[] = {1, 9, 10, 36, 45, 55, 82, 91, 99, 100, 235, 297, 369, 370, 379, 414, 657, 675, 703, 756, 792, 909, 918, 945, 964, 990, 991, 999, 1000};
        int len = sizeof(punish_arr)/sizeof(int);
        for(int i = 0; i < len; i++) {
            if(n >= punish_arr[i]) res += punish_arr[i]*punish_arr[i];
        }
        return res;
    }
    bool search(int i, int target) {
        int n = i;
        int base = 1;
        int r = 0;
        while(n) {
            r += base*(n%10);
            if(r+n/10 == target) {
                return true;
            } else {
                if(search(n/10, target - r)){
                    return true;
                }
            }
            n /= 10;
            base *= 10;
        }
        return false;
    }
};

1155. 掷骰子等于目标和的方法数

思路

  • 先暴力递归，然后发现可以总结出dp公式，然后把递归改成dp尝试，成功了

代码

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
class Solution {
public:
    vector<vector<int>> dp;
    int numRollsToTarget(int n, int k, int target) {
        dp = vector<vector<int>>(30+1, vector<int>(1000+1, 0));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int t = 1; t <= target; t++)
                for(int K = 1;K <= k; K++)
                    if(t >= K)
                        dp[i][t] = (dp[i][t] + dp[i-1][t-K]) % 1000000007;
        }
        return dp[n][target];
    }
    int search(int n, int k, int target) {
        if(target == 0 && n == 0) {
            return 1;
        } else if(n == 0) return 0;
        int res = 0;
        for(int i = 1; i <= k; i++) {
            if(target >= i) {
                res += numRollsToTarget(n-1, k, target-i);
            }
        }
        return res;
    }
};

优化

观察代码可知，dp[i][t]就是dp[i-1][t-1]+…dp[i-1][t-k]，可以用前缀和优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<vector<int>> dp;
    int numRollsToTarget(int n, int k, int target) {
        dp = vector<vector<int>>(30+1, vector<int>(1000+1,0));
        dp[0][0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int t = 1; t <= target; t++) {
                dp[i][t] = (dp[i][t-1] + dp[i-1][t-1]) % 1000000007;
            }
            for(int t = target; t >= k; t--) {
                dp[i][t] = (dp[i][t] - dp[i][t-k] + 1000000007) % 1000000007;
            }
        }
        return dp[n][target];
    }
};

1402. 做菜顺序

  • 一眼dp，鉴定为，纯纯的简单题
  • 一遍就做对啦哈哈哈
    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 maxSatisfaction(vector<int>& satisfaction) {
            int n = satisfaction.size();
            vector<int> dp(n+1, 0);
            vector<int> sums(n+1, 0);
            sums[0] = accumulate(satisfaction.begin(), satisfaction.end(), 0);
            sort(satisfaction.begin(), satisfaction.end(), less<int>());
            for(int i = 0; i < n; i++) {
                dp[0] += (i+1) * satisfaction[i];
            }
            for(int i = 1; i <= n; i++) {
                if(dp[i-1] < dp[i-1] - sums[i-1]) {
                    dp[i] = dp[i-1] - sums[i-1];
                    sums[i] = sums[i-1] - satisfaction[i-1];
                } else {
                    dp[i] = dp[i-1];
                    sums[i] = sums[i-1];
                }
            }
            return dp[n];
        }
    };

优化

dp数组和sum数组可以优化掉

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int maxSatisfaction(vector<int>& satisfaction) {
        int n = satisfaction.size();
        int dp = 0;
        int sums = 0;
        sort(satisfaction.begin(), satisfaction.end());
        for(int i = 0; i < n; i++) {
            dp += (i+1) * satisfaction[i];
            sums += satisfaction[i];
        }
        for(int i = 1; i <= n; i++) {
            if(dp < dp - sums) {
                dp = dp - sums;
                sums = sums - satisfaction[i-1];
            }
        }
        return dp;
    }
};

2678. 老人的数目

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int countSeniors(vector<string>& details) {
        int res = 0;
        for(const string &laodeng : details) {
            if((laodeng[11] == '6' && laodeng[12] > '0') || (laodeng[11] > '6' && laodeng[12] >= '0')) res++;
        }
        return res;
    }
};

2316. 统计无向图中无法互相到达点对数

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<vector<int>> g;
    vector<bool> visited;
    long long countPairs(int n, vector<vector<int>>& edges) {
        g = move(vector<vector<int>>(n, vector<int>()));
        visited = move(vector<bool>(n, false));
        for(const vector<int>& edge : edges) {
            g[edge[0]].push_back(edge[1]);
            g[edge[1]].push_back(edge[0]);
        }
        long long res = 0;
        for(int i = 0; i < n; i++) {
            if(!visited[i]) {
                long long node_num = count_nodes(i);
                res += (n - node_num) * node_num;
            }
        }
        return res >>  1;
    }
    int count_nodes(int root) {
        visited[root] = true;
        int res = 1;
        for(int child : g[root]) {
            if(!visited[child])
                res += count_nodes(child);
        }
        return res;
    }
};

并查集

  • 这里一直写不出来，发现并查集无法把所有相连的点归到一个集合中，因为在遍历的时候没有用union操作
    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:
        vector<int> s;
        int find(int x) {
            return x == s[x] ? x : (s[x] = find(s[x]));
        }
        long long countPairs(int n, vector<vector<int>>& edges) {
            s = move(vector<int>(n, 0));
            vector<int> cnt = move(vector<int>(n, 0));
            iota(s.begin(), s.end(), 0);
            size_t elen = edges.size();
            for(int j = 0; j < elen; j++) {
                s[find(edges[j][1])] =  find(edges[j][0]);
            }
            for(int i = 0; i < n; i++) {
                cnt[find(i)]++;
            }
            long long res = 0;
            for(int i = 0; i < n; i++) {
                res += (n - (long long)cnt[i])*cnt[i];
            }
            return res >> 1;
        }
    };

继续优化

  • 换个公式减少一次循环
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    class Solution {
    public:
        vector<int> s;
        int find(int x) {
            return x == s[x] ? x : (s[x] = find(s[x]));
        }
        long long countPairs(int n, vector<vector<int>>& edges) {
            s = move(vector<int>(n, 0));
            vector<int> cnt = move(vector<int>(n, 0));
            iota(s.begin(), s.end(), 0);
            size_t elen = edges.size();
            for(int j = 0; j < elen; j++) {
                s[find(edges[j][1])] =  find(edges[j][0]);
            }
            long long res = 0;
            for(int i = 0; i < n; i++) {
                res += cnt[find(i)]++;
            }
            return (long long)n*(n-1)/2 - res;
        }
    };

2525. 根据规则将箱子分类

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    string categorizeBox(int length, int width, int height, int mass) {
        bool bulky = length >= 10000 || height >= 10000 || width >= 10000 || (long long)length*width*height >= 1000000000;
        bool heavy = mass >= 100;
        if(bulky &&  heavy) return "Both";
        else if(!bulky && !heavy) return "Neither";
        else if(bulky && !heavy) return "Bulky";
        else return "Heavy";
    }
};

117. 填充每个节点的下一个右侧节点指针 II

思路

  • 首先想到的就是层次遍历，非常简单
  • 对于进阶使用O(1)空间的算法，一直没想到利用已有的next指针
    • 树每层最左侧节点找parent，把同层都连起来就好
      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
      43
      44
      45
      46
      47
      48
      49
      50
      51
      class Solution {
      public:
          Node* levelConnect(Node* root) {
              queue<Node *> q;
              if(root) q.push(root);
              while(!q.empty()) {
                  Node *node = nullptr;
                  int n = q.size();
                  while(n--) {
                      if(node) node->next = q.front();
                      node = q.front();
                      if(node->left) q.push(node->left);
                      if(node->right) q.push(node->right);
                      q.pop();
                  }
              }
              return root;
          }
          Node* connect(Node* root) {
              // return levelConnect(root);
              if(root) recursiveConnect(root, new Node(0, root, nullptr, nullptr), true);
              return root;
          }
          void recursiveConnect(Node* root, Node *parent, bool isLeft) {
              Node *move = root;
              while(move && !move->next) {
                  Node *to = nullptr;
                  if(isLeft && parent->right) {
                      to = parent->right;
                      isLeft = false;
                  } else {
                      Node *pMove = parent->next;
                      while(pMove && !pMove->left && !pMove->right) pMove = pMove->next;
                      if(pMove) {
                          if(pMove->left) {
                              isLeft = true;
                              to = pMove->left;
                          } else if(pMove->right) {
                              isLeft = false;
                              to = pMove->right;
                          }
                          parent = pMove;
                      }
                  }
                  move->next = to;
                  move = to;
              }
              if(root->right) recursiveConnect(root->right, root, false);
              if(root->left) recursiveConnect(root->left, root, true);
          }
      };

整理下代码

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
43
44
45
46
47
class Solution {
public:
    Node* levelConnect(Node* root) {
        queue<Node *> q;
        if(root) q.push(root);
        while(!q.empty()) {
            Node *node = nullptr;
            int n = q.size();
            while(n--) {
                if(node) node->next = q.front();
                node = q.front();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
                q.pop();
            }
        }
        return root;
    }
    Node* connect(Node* root) {
        // return levelConnect(root);
        if(root) recursiveConnect(root, new Node(0, root, nullptr, nullptr));
        return root;
    }
    void recursiveConnect(Node* root, Node *parent) {
        Node *move = root;
        while(move && !move->next) {
            Node *to = nullptr;
            if(move != parent->left || !parent->right) {
                parent = parent->next;
            }
            Node *pMove = parent;
            while(pMove && !pMove->left && !pMove->right) pMove = pMove->next;
            to = pMove 
                ? (pMove->left == move 
                ? pMove->right 
                : pMove->left 
                ? pMove->left 
                : pMove->right)
                : nullptr; // 你就猜吧，一猜一个不吱声
            parent = pMove;
            move->next = to;
            move = to;
        }
        if(root->right) recursiveConnect(root->right, root);
        if(root->left) recursiveConnect(root->left, root);
    }
};

2127. 参加会议的最多员工数

并查集

  • 一个重要结论，图中一定有环（n个节点，大于n-1条边）
  • 如果环的大小大于2，则只能将环上的节点上桌，支链上的点无法上桌
  • 如果环的大小不大于2，则环上节点的最长支链也可以跟着上桌
  • 多个环长为2的子图（不论是否有支链），都可以全部上桌

故，统计所有环长大于2的最大环长，为maxRing
统计所有环长不大于2的环长之和，以及环上各节点的最大之链长度之和，为maxNumber
返回max(maxRing, maxNumber)

步骤

  • 并查集将节点分类

  • degree统计每个节点的入度

  • dSetSize统计每个集合的大小

  • 按照是否存在入度为0的点，将子图划分两类

    • 存在，则图含有支链，计算环的长度(findMaxRing)
      • 大于2，统计最大环长（maxRing）
      • 不大于2，从任意度为0的节点开始遍历，将环上节点的visited变成非0，并标记该子图为is2，累加maxNumber（环长为2，都可以上桌）
    • 不存在，则图不含有支链，计算环的长度(findMaxRing)
      • 大于2，统计最大环长（maxRing）
      • 不大于2，累加如maxNumber（环长为2，都可以上桌）

  • 对所有入度为0，且所在子图是is2的节点，计算该点到环上点的距离为支链长度，记录最大支链长度

  • 所有最大支链长度累加maxNumber

  • 返回max(maxNumber, maxRing)

    时间 1848 ms 击败 5.2%
    内存 98.4 MB 击败 35.8%

    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
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    class Solution {
    public:
        int maxRing = 0;
        vector<int> visited;
        vector<int> addtional_len;
        vector<int> dSet;
        vector<bool> dSetVisited;
        vector<int> dSetSize;
        vector<bool> isRing;
        vector<bool> is2;
        vector<int> degree;
        int find(int i) {
            return i == dSet[i] ? i : (dSet[i] = find(dSet[i])); 
        }
        int maximumInvitations(vector<int>& favorite) {
            int n = favorite.size();
            visited = move(vector<int>(n, 0));
            dSetVisited = move(vector<bool>(n, false));
            isRing = move(vector<bool>(n, true));
            is2 = move(vector<bool>(n, false));
            addtional_len = move(vector<int>(n, 0));
            degree = move(vector<int>(n, 0));
            dSet = move(vector<int>(n, 0));
            iota(dSet.begin(), dSet.end(), 0);
            dSetSize = move(vector<int>(n, 0));
            for(int i = 0; i < n; i++) {
                degree[favorite[i]]++;
                dSet[find(i)] = find(favorite[i]);
            }
            for(int i = 0; i < n; i++) {
                dSetSize[find(i)]++;
                if(degree[i] == 0) isRing[dSet[i]] = false;
            }
            int maxNumber = 0;
            for(int i = 0; i < n; i++) {
                int len = 1;
                int ringNode = -1;
                if(isRing[dSet[i]]) {
                    if(!dSetVisited[dSet[i]]) {
                        dSetVisited[dSet[i]] = true;
                        int ring = dSetSize[dSet[i]]++;
                        if(ring > 2) {
                            maxRing = max(maxRing, ring);
                        } else {
                            maxNumber += ring;
                        }
                    }
                } else {
                    if(!dSetVisited[dSet[i]] && degree[i] == 0) {
                        dSetVisited[dSet[i]] = true;
                        int ring = findMaxRing(favorite, i, len, ringNode);
                        if(ring > 2) {
                            maxRing = max(maxRing, ring);
                        } else {
                            // addtional_len[ringNode] = max(len - ring, addtional_len[ringNode]);
                            int move = i;
                            while(move != ringNode) {
                                visited[move] = false;
                                move = favorite[move];
                            }
                            is2[dSet[i]] = true;
                            maxNumber += ring;
                        }
                    }
                }
            }
            for(int i = 0; i < n; i++) {
                if(is2[dSet[i]] && degree[i] == 0) {
                    int move = i;
                    int len = 0;
                    while(!visited[move]) {
                        len++;
                        move = favorite[move];
                    }
                    addtional_len[move] = max(addtional_len[move], len);
                }
            }
            for(int i = 0; i < n; i++) {
                // cout << i << ", " << addtional_len[i] << endl;
                if(addtional_len[i] > 0) {
                    maxNumber += addtional_len[i];
                }
            }
            return max(maxNumber, maxRing);
        }

        int findMaxRing(const vector<int>& favorite, int node, int &len, int &ringNode) {
            visited[node] = len;
            int child = favorite[node];
            if(visited[child]) {
                ringNode = child;
                return len - visited[child] + 1;
            }
            len++;
            return findMaxRing(favorite, child, len, ringNode);
        }
    };

  • 优化

上面的代码在遇到有公共部分的支链，（会分叉的支链时），会导致重叠部分反复被访问

使用arcFav统计被喜欢图，根据被喜欢图从环上开始寻找最大支链，可以避免，速度也得到了极大的优化

时间 284ms 击败 12.78% 使用 C++ 的用户
内存 166.84MB 击败 25.57% 使用 C++ 的用户

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
class Solution {
public:
    int maxRing = 0;
    vector<int> visited;
    vector<int> addtional_len;
    vector<vector<int>> arcFav;
    vector<int> dSet;
    vector<bool> dSetVisited;
    vector<int> dSetSize;
    vector<bool> isRing;
    vector<int> degree;
    int find(int i) {
        return i == dSet[i] ? i : (dSet[i] = find(dSet[i])); 
    }
    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        visited = move(vector<int>(n, 0));
        arcFav = move(vector<vector<int>>(n, vector<int>()));
        dSetVisited = move(vector<bool>(n, false));
        isRing = move(vector<bool>(n, true));
        addtional_len = move(vector<int>(n, 0));
        degree = move(vector<int>(n, 0));
        dSet = move(vector<int>(n, 0));
        iota(dSet.begin(), dSet.end(), 0);
        dSetSize = move(vector<int>(n, 0));
        for(int i = 0; i < n; i++) {
            degree[favorite[i]]++;
            dSet[find(i)] = find(favorite[i]);
            arcFav[favorite[i]].push_back(i);
        }
        for(int i = 0; i < n; i++) {
            dSetSize[find(i)]++;
            if(degree[i] == 0) isRing[dSet[i]] = false;
        }
        int maxNumber = 0;
        for(int i = 0; i < n; i++) {
            int len = 1;
            int ringNode = -1;
            if(isRing[dSet[i]]) {
                if(!dSetVisited[dSet[i]]) {
                    dSetVisited[dSet[i]] = true;
                    int ring = dSetSize[dSet[i]]++;
                    if(ring > 2) {
                        maxRing = max(maxRing, ring);
                    } else {
                        maxNumber += ring;
                    }
                }
            } else {
                if(!dSetVisited[dSet[i]] && degree[i] == 0) {
                    dSetVisited[dSet[i]] = true;
                    int ring = findMaxRing(favorite, i, len, ringNode);
                    if(ring > 2) {
                        maxRing = max(maxRing, ring);
                    } else {
                        int move = i;
                        while(move != ringNode) {
                            visited[move] = 0;
                            move = favorite[move];
                        }
                        addtional_len[ringNode] = searchArcFav(ringNode);
                        move = favorite[ringNode];
                        while(move != ringNode) {
                            addtional_len[move] = searchArcFav(move);
                            move = favorite[move];
                        }
                        maxNumber += ring;
                    }
                }
            }
        }
        for(int i = 0; i < n; i++) {
            if(addtional_len[i] > 0) {
                maxNumber += addtional_len[i];
            }
        }
        return max(maxNumber, maxRing);
    }
    int searchArcFav(int move) {
        visited[move] = 1;
        int ret = 0;
        for(int child : arcFav[move]) {
            if(!visited[child]) {
                ret = max(searchArcFav(child)+1, ret);
            }
        }
        return ret;
    }
    int findMaxRing(const vector<int>& favorite, int node, int &len, int &ringNode) {
        visited[node] = len;
        int child = favorite[node];
        if(visited[child]) {
            ringNode = child;
            return len - visited[child] + 1;
        }
        len++;
        return findMaxRing(favorite, child, len, ringNode);
    }
};

并查集+拓扑排序

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
public:
    int maxRing = 0;
    vector<int> visited;
    vector<int> addtional_len;
    vector<vector<int>> arcFav;
    vector<int> dSet;
    vector<int> degree;
    int find(int i) {
        return i == dSet[i] ? i : (dSet[i] = find(dSet[i])); 
    }
    int maximumInvitations(vector<int>& favorite) {
        int n = favorite.size();
        visited = move(vector<int>(n, 0));
        arcFav = move(vector<vector<int>>(n, vector<int>()));
        addtional_len = move(vector<int>(n, 0));
        degree = move(vector<int>(n, 0));
        dSet = move(vector<int>(n, 0));
        iota(dSet.begin(), dSet.end(), 0);
        vector<int> ringNodes;
        unordered_map<int, int> ringSize;
        for(int i = 0; i < n; i++) {
            degree[favorite[i]]++;
            dSet[find(i)] = find(favorite[i]);
            arcFav[favorite[i]].push_back(i);
        }
        queue<int> topologyQueue;
        for(int i = 0; i < n; i++) {
            if(degree[i] == 0) {
                topologyQueue.push(i);
            }
        }
        while(!topologyQueue.empty()) {
            int front = topologyQueue.front();
            topologyQueue.pop();
            if((--degree[favorite[front]]) == 0) {
                topologyQueue.push(favorite[front]);
            }
        }
        unordered_set<int> ring2set;
        for(int i = 0; i < n; i++) {
            if(degree[i] > 0) {
                ringNodes.push_back(i);
                ringSize[find(i)]++;
            }
        }
        for(int i = 0; i < n; i++) {
            if(ringSize[find(i)] <= 2) {
                ring2set.insert(find(i));
            }
        }
        int maxNumber = 0;
        for(int ringNode : ringNodes) {
            int ring = ringSize[dSet[ringNode]];
            if(ring > 2) {
                maxRing = max(maxRing, ring);
            } else {
                addtional_len[ringNode] = searchArcFav(ringNode);
            }
        }
        for(int i = 0; i < n; i++) {
            if(addtional_len[i] > 0) {
                maxNumber += addtional_len[i]; // add ring number
            }
        }
        return max(maxNumber + (ring2set.size() << 1), (size_t)maxRing);
    }
    int searchArcFav(int move) {
        visited[move] = 1; // 判断， not in ring
        int ret = 0;
        for(int child : arcFav[move]) {
            if(!visited[child] && degree[child] == 0) {
                ret = max(searchArcFav(child)+1, ret);
            }
        }
        return ret;
    }
};

更慢了，原因是不能在拓扑排序的同时计算最大支链长度

优化掉并查集

  • 在拓扑排序中寻找最长支链，为每个节点定义f(x)
  • $ f(x) = max_{i=0}^j(f(aFav(x)_i) + 1) $
  • 每个节点初始为0，拓扑排序时，每次i将j的degree被减小，其值为max(f(i)+1, f(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
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    class Solution {
    public:
        int maxRing = 0;
        vector<bool> visited;
        vector<int> degree;
        vector<int> f;
        int maximumInvitations(vector<int>& favorite) {
            int n = favorite.size();
            visited = move(vector<bool>(n, false));
            degree = move(vector<int>(n, 0));
            f = move(vector<int>(n, 0));
            vector<int> ringNodes;
            unordered_map<int, int> ringSize;
            for(int i = 0; i < n; i++) {
                degree[favorite[i]]++;
            }
            queue<int> topologyQueue;
            for(int i = 0; i < n; i++) {
                if(degree[i] == 0) {
                    topologyQueue.push(i);
                }
            }
            while(!topologyQueue.empty()) {
                int front = topologyQueue.front();
                topologyQueue.pop();
                f[favorite[front]] = max(f[favorite[front]], f[front] + 1);
                visited[front] = true;
                if((--degree[favorite[front]]) == 0) {
                    topologyQueue.push(favorite[front]);
                }
            }
            int maxNumber = 0;
            for(int i = 0; i < n; i++) {
                if(!visited[i])
                    if(favorite[favorite[i]] == i) {
                        maxNumber += f[i] + 1;
                    } else {
                        int ring = 1;
                        int move = favorite[i];
                        while(!visited[move] && move != i) {
                            visited[move] = true;
                            move = favorite[move];
                            ring++;
                        }
                        maxRing = max(maxRing, ring);
                    }
            }
            return max(maxNumber, maxRing);
        }
    };

LeetCode-27

https://jingtianer.github.io/home/2023/10/28/LeetCode/LeetCode-刷题总结27/

作者

Meow Meow Liu

发布于

2023-10-28

更新于

2025-04-15

许可协议

#

评论

×