LeetCode每周五题_2024/01/01~2024/01/05

1599. 经营摩天轮的最大利润 [2024/01/01]

题目

• 1599. 经营摩天轮的最大利润

你正在经营一座摩天轮，该摩天轮共有 4 个座舱 ，每个座舱 最多可以容纳 4 位游客 。你可以 逆时针 轮转座舱，但每次轮转都需要支付一定的运行成本 runningCost 。摩天轮每次轮转都恰好转动 1 / 4 周。
给你一个长度为 n 的数组 customers ， customers[i] 是在第 i 次轮转（下标从 0 开始）之前到达的新游客的数量。这也意味着你必须在新游客到来前轮转 i 次。每位游客在登上离地面最近的座舱前都会支付登舱成本 boardingCost ，一旦该座舱再次抵达地面，他们就会离开座舱结束游玩。
你可以随时停下摩天轮，即便是 在服务所有游客之前 。如果你决定停止运营摩天轮，为了保证所有游客安全着陆，将免费进行所有后续轮转 。注意，如果有超过 4 位游客在等摩天轮，那么只有 4 位游客可以登上摩天轮，其余的需要等待 下一次轮转 。
返回最大化利润所需执行的 最小轮转次数 。 如果不存在利润为正的方案，则返回 -1 。

题解

/**
 * @param {number[]} customers
 * @param {number} boardingCost
 * @param {number} runningCost
 * @return {number}
 */
var minOperationsMaxProfit = function (customers, boardingCost, runningCost) {
  let remainder = 0; //等待人数
  let profit = 0; //盈利
  let orders = 0; //轮次
  let maxProfit = 0; //最大盈利
  let maxIndex = 0; //最大盈利轮次
  let profitOnce = 4 * boardingCost - runningCost; //一轮4个人盈利
  // 轮次游客
  for (let i = 0; i < customers.length; i++) { 
    const customer = customers[i];
    // 运行一轮后剩余人数 
    const remainderPeople = remainder + customer - 4;
    if (remainderPeople > 0) {
      remainder = remainderPeople;
      const num = profit + profitOnce;
      maxProfit = Math.max(maxProfit, profit, num);
      if (maxProfit >= profit && num > profit) {
        maxIndex = orders + 1;
      }
      profit = num;
    } else {
      remainder = 0;
      const num = profit + (4 + remainderPeople) * boardingCost - runningCost;
      maxProfit = Math.max(maxProfit, profit, num);
      if (maxProfit >= profit && num > profit) {
        maxIndex = orders + 1;
      }
      profit = num;
    }
    orders++;
  }
  // 只需要让剩余人做完摩天轮
  while (remainder > 0) {
    if (remainder > 4) {
      const num = profit + profitOnce;
      maxProfit = Math.max(maxProfit, profit, num);
      profit = num;
      if (maxProfit >= profit) {
        maxIndex = orders + 1;
      }
    } else {
      const num = profit + remainder * boardingCost - runningCost;
      maxProfit = Math.max(maxProfit, profit, num);
      if (maxProfit > profit && profit > num) {
        maxIndex = orders;
      } else if (maxProfit > profit) {
        maxIndex = orders + 1;
      }
      profit = num;
    }
    remainder = remainder - 4;
    orders++;
  }
  return profit > 0 ? (maxIndex ? maxIndex : orders) : -1;
};

466. 统计重复个数 [2024/01/02]

题目

• 466. 统计重复个数

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。
例如，str == [“abc”, 3] ==“abcabcabc” 。
如果可以从 s2 中删除某些字符使其变为 s1，则称字符串 s1 可以从字符串 s2 获得。
例如，根据定义，s1 = “abc” 可以从 s2 = “abdbec” 获得，仅需要删除加粗且用斜体标识的字符。
现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。
请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。

题解

/**
 * @param {string} s1
 * @param {number} n1
 * @param {string} s2
 * @param {number} n2
 * @return {number}
 */
var getMaxRepetitions = function (s1, n1, s2, n2) {
  let indexMap = new Map();
  let countS1 = 0,
    countS2 = 0;
  let s2p = 0;
  while (countS1 < n1) {
    let prev = indexMap.get(s2p);
    if (!prev) {
      indexMap.set(s2p, [countS1, countS2]);
    } else {
      // 循环节 下一个s1 对应的 s2p 索引有相同时

      // 循环节循环的次数 向下取整
      let t = ((n1 - prev[0]) / (countS1 - prev[0])) | 0;
      countS2 = prev[1] + t * (countS2 - prev[1]);
      countS1 = prev[0] + t * (countS1 - prev[0]);
      // 清楚之前的循环记录
      indexMap.clear();
      // 整除
      if (countS1 === n1) break;
    }
    // 循环s1
    for (let i = 0; i < s1.length; i++) {
      if (s1[i] === s2[s2p]) {
        s2p++;
        if (s2p === s2.length) {
          s2p = 0;
          countS2++;
        }
      }
    }
    countS1++;
  }
  return (countS2 / n2) | 0;
};

2487. 从链表中移除节点 [2024/01/03]

• 2487. 从链表中移除节点

题目

给你一个链表的头节点 head 。
移除每个右侧有一个更大数值的节点。
返回修改后链表的头节点 head 。

题解

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

 
/**
 * @desc 反转链表
 * @param {ListNode} head
 */
var reverseList = function(head) {
    let prev = null;
    let curr = head;
    while(curr){
        let nextCurr = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nextCurr;
    }
    return prev;
};


/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeNodes = function(head) {
    head = reverseList(head);
    let maxVal = 0;
    let newList = new ListNode(0);
    let newHead = newList;
    let curr = head;

    while(curr){
        if(curr.val>=maxVal){
            newHead.next = curr;
            newHead =  newHead.next;
            maxVal = curr.val;
        }
        curr=curr.next;
    }
    newHead.next =null;
    return reverseList(newList.next)
}