leetCode/周赛308.html

<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>周赛308</title>
  </head>
  <body>
    <script>
      /**
       * 周赛308
       * 6160. 和有限的最长子序列 https://leetcode.cn/problems/longest-subsequence-with-limited-sum/
       * 6161. 从字符串中移除星号 https://leetcode.cn/problems/removing-stars-from-a-string/
       * 6162. 收集垃圾的最少总时间 https://leetcode.cn/problems/minimum-amount-of-time-to-collect-garbage/
       * 6163. 给定条件下构造矩阵 https://leetcode.cn/problems/build-a-matrix-with-conditions/
       */

      // --- example-1 ---

      // 贪心 取小的 能取多少个就多少个
      var answerQueries = function (nums = [], queries = []) {
        nums.sort((a, b) => a - b);
        const result = [];
        for (let i = 0; i < queries.length; i++) {
          const target = queries[i];
          let cur = 0;
          let j = 0;
          while ((cur += nums[j]) <= target && j < nums.length) {
            // cur += nums[j];
            j += 1;
          }
          result[i] = j;
        }
        return result;
      };

      var nums = [4, 5, 2, 1],
        queries = [3, 10, 21];
      var result = [2, 3, 4];

      var nums = [2, 3, 4, 5],
        queries = [1];
      var result = [0];

      console.log('nums = ', nums);
      console.log('queries = ', queries);
      console.log('result = ', result);
      console.log('answerQueries = ', answerQueries(nums, queries));
      console.log('');

      // --- example-1 ---

      // --- example-2 ---

      // 栈
      var removeStars = function (s) {
        let stack = [];
        for (let c of s) {
          if (c === '*') {
            stack.pop();
          } else {
            stack.push(c);
          }
        }
        return stack.join('');
      };

      var s = 'leet**cod*e',
        result = 'lecoe';

      console.log('s = ', s);
      console.log('result = ', result);
      console.log('removeStars ', removeStars(s));
      console.log('');

      // --- example-2 ---

      // --- example-3 ---

      // 直接计算每种垃圾的花费
      var garbageCollection = function (garbage = [], travel = []) {
        function cost(char) {
          let spend = 0;
          let distSpend = 0;
          for (let i = 0; i < garbage.length; i++) {
            const sp = garbage[i].split('').filter((x) => x === char).length;
            distSpend += travel[i - 1] || 0;
            if (sp) {
              spend = spend + sp + distSpend;
              distSpend = 0;
            }
          }
          return spend;
        }
        console.log('M = ', cost('M'));
        return cost('M') + cost('P') + cost('G');
      };

      var garbage = ['G', 'P', 'GP', 'GG'],
        travel = [2, 4, 3];
      var result = 21;

      // var garbage = ['MMM', 'PGM', 'GP'],
      //   travel = [3, 10];
      // var result = 37;

      console.log('garbage = ', garbage);
      console.log('travel = ', travel);
      console.log('result = ', result);
      console.log('garbageCollection = ', garbageCollection(garbage, travel));
      console.log('');

      // --- example-3 ---

      // --- example-4 ---

      // 之前没刷过这样的拓扑排序的题，想想很多方式都不对

      function topoSort(k, edges) {
        // 有向图
        let g = Array.from({ length: k }, () => new Array());
        // 节点的使用次数
        let inDeg = new Array(k).fill(0);
        for (let e of edges) {
          let x = e[0] - 1;
          let y = e[1] - 1;
          g[x].push(y);
          inDeg[y] += 1;
        }
        const order = [];
        let q = [];
        for (let i = 0; i < k; ++i) {
          if (inDeg[i] == 0) q.push(i);
        }

        while (q.length) {
          let x = q.pop();
          order.push(x);
          for (let y of g[x]) {
            if (--inDeg[y] === 0) q.push(y);
          }
        }
        return order;
      }

      var buildMatrix = function (k, rowConditions, colConditions) {
        const row = topoSort(k, rowConditions);
        const col = topoSort(k, colConditions);

        if (row.length < k || col.length < k) return [];
        var pos = [];
        for (var i = 0; i < k; ++i) {
          pos[col[i]] = i;
        }
        var ans = Array.from({ length: k }, () => Array.from({ length: k }, () => 0));
        for (var i = 0; i < k; ++i) {
          ans[i][pos[row[i]]] = row[i] + 1;
        }
        return ans;
      };

      var k = 3,
        rowConditions = [
          [1, 2],
          [3, 2]
        ],
        colConditions = [
          [2, 1],
          [3, 2]
        ];
      var result = [
        [3, 0, 0],
        [0, 0, 1],
        [0, 2, 0]
      ];

      var k = 3,
        rowConditions = [
          [1, 2],
          [2, 3],
          [3, 1],
          [2, 3]
        ],
        colConditions = [[2, 1]];
      var result = [];

      console.log('nums = ', nums);
      console.log('queries = ', queries);
      console.log('result = ', result);
      console.log('buildMatrix = ', buildMatrix(k, rowConditions, colConditions));

      // --- example-4 ---
    </script>
  </body>
</html>