【题解】—— LeetCode一周小结1

class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        int ans = -1; // 初始化答案为-1，表示没有找到最大利润的方案
        int max = 0, t = 0; // 初始化最大利润为0，当前总利润为0
        int wait = 0, i = 0; // 初始化等待人数为0，轮转次数为0
        // 当等待人数大于0或者还有客户需要服务时，继续循环
        while (wait > 0 || i < customers.length) { 
            // 如果还有游客，将等待人数加入等待游客的人数
            wait += i < customers.length ? customers[i] : 0; 
            int up = Math.min(4, wait); // 计算可以上车的人数，最多为4人
            wait -= up; // 更新等待人数
            i++; // 轮转次数
            t += up * boardingCost - runningCost; // 更新当前总利润
            if (t > max) { // 如果当前总利润大于最大利润
                max = t; // 更新最大利润
                ans = i; // 更新答案为当前的轮转次数
            }
        }
        return ans; // 返回答案
    }
}

class Solution {
    public int minOperationsMaxProfit(int[] customers, int boardingCost, int runningCost) {
        // 如果每次摩天轮的载客量乘以4小于等于运行成本，则无法盈利，返回-1
        if (boardingCost * 4 <= runningCost) return -1;
        
        int customer = 0, time = 0, income = 0, bestRes = 0, bestTime = -1;
        
        for (int i = 0; i < customers.length; ) {
            // 计算当前轮次前是否有新的游客加入，如果之前存在游客，尽量凑 4 人
            for (; i < customers.length && i <= time; i++) {
                customer += customers[i]; // 累加游客人数
                income += (customer >> 2 << 2) * boardingCost; // 计算收入
                time += customer >> 2; // 更新轮转次数
                customer &= 3; // 更新剩余游客人数
            }
            // 上轮循环跳出证明当前出现无游客凑够 4 人的情况，所以先核算之前满载 4 人的最优情况下利润是否创新高
            if (bestRes < income - runningCost * time) {
                bestRes = income - runningCost * time; // 更新最佳利润
                bestTime = time; // 更新轮转次数
            }
            // 到这里证明游客少于 4 人，且必须转动，那么就直接计算并判断
            income += boardingCost * customer; // 计算收入
            customer = 0; // 更新剩余游客人数
            time++; // 更新轮转次数
            if (bestRes < income - runningCost * time) {
                bestRes = income - runningCost * time; // 更新最佳利润
                bestTime = time; // 更新轮转次数
            }
        }
        return bestTime; // 返回轮转次数
    }
}

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        if (n1 == 0) {
            return 0;
        }
        int s1cnt = 0, index = 0, s2cnt = 0;
        // recall 是我们用来找循环节的变量，它是一个哈希映射
        // 我们如何找循环节？假设我们遍历了 s1cnt 个 s1，此时匹配到了第 s2cnt 个 s2 中的第 index 个字符
        // 如果我们之前遍历了 s1cnt' 个 s1 时，匹配到的是第 s2cnt' 个 s2 中同样的第 index 个字符，那么就有循环节了
        // 我们用 (s1cnt', s2cnt', index) 和 (s1cnt, s2cnt, index) 表示两次包含相同 index 的匹配结果
        // 那么哈希映射中的键就是 index，值就是 (s1cnt', s2cnt') 这个二元组
        // 循环节就是；
        //    - 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
        //    - 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
        // 那么还会剩下 (n1 - s1cnt') % (s1cnt - s1cnt') 个 s1, 我们对这些与 s2 进行暴力匹配
        // 注意 s2 要从第 index 个字符开始匹配
        Map<Integer, int[]> recall = new HashMap<Integer, int[]>();
        int[] preLoop = new int[2];
        int[] inLoop = new int[2];
        while (true) {
            // 我们多遍历一个 s1，看看能不能找到循环节
            ++s1cnt;
            for (int i = 0; i < s1.length(); ++i) {
                char ch = s1.charAt(i);
                if (ch == s2.charAt(index)) {
                    index += 1;
                    if (index == s2.length()) {
                        ++s2cnt;
                        index = 0;
                    }
                }
            }
            // 还没有找到循环节，所有的 s1 就用完了
            if (s1cnt == n1) {
                return s2cnt / n2;
            }
            // 出现了之前的 index，表示找到了循环节
            if (recall.containsKey(index)) {
                int[] value = recall.get(index);
                int s1cntPrime = value[0];
                int s2cntPrime = value[1];
                // 前 s1cnt' 个 s1 包含了 s2cnt' 个 s2
                preLoop = new int[]{s1cntPrime, s2cntPrime};
                // 以后的每 (s1cnt - s1cnt') 个 s1 包含了 (s2cnt - s2cnt') 个 s2
                inLoop = new int[]{s1cnt - s1cntPrime, s2cnt - s2cntPrime};
                break;
            } else {
                recall.put(index, new int[]{s1cnt, s2cnt});
            }
        }
        // ans 存储的是 S1 包含的 s2 的数量，考虑的之前的 preLoop 和 inLoop
        int ans = preLoop[1] + (n1 - preLoop[0]) / inLoop[0] * inLoop[1];
        // S1 的末尾还剩下一些 s1，我们暴力进行匹配
        int rest = (n1 - preLoop[0]) % inLoop[0];
        for (int i = 0; i < rest; ++i) {
            for (int j = 0; j < s1.length(); ++j) {
                char ch = s1.charAt(j);
                if (ch == s2.charAt(index)) {
                    ++index;
                    if (index == s2.length()) {
                        ++ans;
                        index = 0;
                    }
                }
            }
        }
        // S1 包含 ans 个 s2，那么就包含 ans / n2 个 S2
        return ans / n2;
    }
}

class Solution {
    public int getMaxRepetitions(String s1, int n1, String s2, int n2) {
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] DP = new int[len2][0]; // 0 记录s2匹配的个数 1 记录下一个s2匹配的位置
        for (int i = 0; i < len2; i++) {
            int j = i; // 记录下一个s2匹配的位置
            int cnt = 0; // 记录s2匹配的个数: 一个s1中可能含有多个s2串
            for (int k = 0; k < len1; k++) { // 遍历s1字符串进行匹配
                if (s1.charAt(k) == s2.charAt(j)) { // 匹配相同的字符串
                    j++; // 指向下一个位置
                    if (j == len2) { // s2匹配完一段
                        j = 0; // 重置索引
                        cnt++; // 匹配个数加1
                    }
                }
            }
            // 循环结束，j的位置始终对标在s1中的位置
            DP[i] = new int[]{cnt, j}; // 匹配完一次 则将结果添加到数组中
        }
        int ans = 0; // 定义结果变量
        for (int j = 0; n1 > 0; n1--) { // 遍历n1，记录每个循环中s2下标出现的数量
            ans += DP[j][0]; // 累加匹配数
            j = DP[j][1]; // 获取下一个位置
        }
        return ans / n2; // 将n2个s2作为一个整体数量，砍掉n2个就是结果
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNodes(ListNode head) {
        if (head == null) {
            return null;
        }
        head.next = removeNodes(head.next);
        if (head.next != null && head.val < head.next.val) {
            return head.next;
        } else {
            return head;
        }
    }
}

class Solution {
    public int maximumRows(int[][] matrix, int numSelect) {
        // 获取矩阵的行数m和列数n
        int m = matrix.length, n = matrix[0].length;
        // 定义一个长度为m的一维数组rows，用于存储每一行的二进制表示
        int[] rows = new int[m];
        // 遍历矩阵的每一行
        for (int i = 0; i < m; ++i) {
            // 遍历矩阵的每一列
            for (int j = 0; j < n; ++j) {
                // 如果当前位置的元素值为1，则将该位置对应的二进制位设置为1
                if (matrix[i][j] == 1) {
                    rows[i] |= 1 << j;
                }
            }
        }
        // 初始化答案ans为0
        int ans = 0;
        // 遍历所有可能的二进制掩码（从1到2^n-1）
        for (int mask = 1; mask < 1 << n; ++mask) {
            // 如果当前掩码中1的个数不等于numSelect，则跳过当前循环
            if (Integer.bitCount(mask) != numSelect) {
                continue;
            }
            // 初始化计数器t为0
            int t = 0;
            // 遍历每一行的二进制表示
            for (int x : rows) {
                // 如果当前行的二进制表示与当前掩码进行按位与运算后的结果等于当前行的二进制表示，则计数器t加1
                if ((x & mask) == x) {
                    ++t;
                }
            }
            // 更新答案ans为ans和t中的较大值
            ans = Math.max(ans, t);
        }
        // 返回答案ans
        return ans;
    }
}

class Solution {
    public int[] canSeePersonsCount(int[] heights) { 
        int n = heights.length; 
        int[] ans = new int[n]; 
        Deque<Integer> stk = new ArrayDeque<>(); // 双端队列stk，用于存储高度信息
        for (int i = n - 1; i >= 0; --i) { // 倒序遍历数组
            while (!stk.isEmpty() && stk.peek() < heights[i]) { // 如果栈不为空且栈顶元素小于当前元素
                stk.pop(); // 弹出栈顶元素
                ++ans[i]; 
            }
            if (!stk.isEmpty()) { 
                ++ans[i];
            }
            stk.push(heights[i]); // 将当前元素压入栈中
        }
        return ans; 
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 插入最大公约数节点的方法
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode node = head; // 初始化当前节点为头节点
        while (node.next != null) { // 遍历链表，直到最后一个节点
            node.next = new ListNode(gcd(node.val, node.next.val), node.next); // 将当前节点的下一个节点替换为最大公约数节点
            node = node.next.next; // 移动到新插入的最大公约数节点的下一个节点
        }
        return head; // 返回修改后的链表头节点
    }
    // 计算两个整数的最大公约数的方法
    public int gcd(int a, int b) {
        while (b != 0) { // 当b不为0时，继续循环
            int tmp = a % b; // 计算a除以b的余数
            a = b; // 将b的值赋给a
            b = tmp; // 将余数赋给b
        }
        return a; // 返回最大公约数
    }
}

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] memo = new int[26];
        
        // 遍历magazine字符串中的每个字符，将其转换为小写字母后在memo数组中对应的位置加1
        for (char ch : magazine.toCharArray()) memo[ch - 'a']++;
        
        // 遍历ransomNote字符串中的每个字符，将其转换为小写字母后在memo数组中对应的位置减1
        for (char ch : ransomNote.toCharArray()) if (--memo[ch - 'a'] < 0) return false;
        
        // 如果减1后的值小于0，说明ransomNote中的某个字符在magazine中不存在，返回false
        // 如果ransomNote中的所有字符都在magazine中存在，返回true
        return true;
    }
}