2022-0819

这个好难啊

之前做264的时候，我是直接用bfs+优先队列做的

但这一题里n很大，质因数也很大，所以bfs要么超时要么内存溢出，这是我写的超时bfs：

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        Queue<Long> queue = new PriorityQueue<>();
        queue.offer(1L);
        Set<Long> vis = new HashSet<>();
        int index = 0;
        while(!queue.isEmpty()) {
            long num = queue.poll();
            index++;
            if (index == n) {
                return (int)num;
            }
            for (int prim : primes) {
                long newNum = prim * num;
                if (vis.contains(newNum)) {
                    continue;
                }
                vis.add(newNum);
                queue.offer(newNum);
            }
        }
        return -1;
    }
}

这题我是只能看了答案才知道怎么做，甚至看答案还研究了半天，好累。

前置题目： 264. 丑数 II - 力扣（LeetCode），里面的质因数只有[2,3,5]，以这个为例

相当于对于1~x个丑数而言，想要求第x+1个丑数

首先知道下面这个概念：

当第8个丑数被2乘了之后，下一个可以尝试被2乘的且尽可能小的，一定是第9个丑数，不可能跳级到第10个丑数，即乘2的动作，应当按顺序发生在之前已经算出来的丑数上。
3和5都同理
且每个丑数（注意是丑数而不是非丑数）都可以被2、3、5乘一次

那我就维护2、3、5的三个指针，每次从各指针位置丑数 * （2或3或5）选出最小值，然后更新指针即可。

class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        long[] dp = new long[n+1];
        dp[1] = 1;
        int[] pIndex = new int[primes.length];
        Arrays.fill(pIndex, 1);
        for (int i = 2;i<=n;i++) {
            long min = Integer.MAX_VALUE;
            List<Integer> selectPis = new ArrayList<>();
            // 找到最小值以及符合的指针
            for (int pi = 0;pi< primes.length;pi++) {
                if (dp[pIndex[pi]] * primes[pi] < min) {
                    min = dp[pIndex[pi]] * primes[pi];
                    selectPis.clear();
                    selectPis.add(pi);
                } else if (dp[pIndex[pi]] * primes[pi] == min) {
                    selectPis.add(pi);
                }
            }
            dp[i] = min;
            // 也可以先得到最小值，再逐个排除
            for (int selectPi : selectPis) {
                pIndex[selectPi]++;
            }
        }
        return (int)dp[n];
    }
}

面试题 02.04. 分割链表 - 力扣（LeetCode）

设置2个头节点，按x的值区分处理即可

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode h1 = new ListNode(0);
        ListNode h2 = new ListNode(0);
        ListNode node1 = h1,node2 = h2;
        ListNode node = head;
        while(node != null) {
            ListNode nextNode = node.next;
            if (node.val < x) {
                node1.next = node;
                node1 = node1.next;
            } else {
                node2.next = node;
                node2 = node2.next;
            }
            node = nextNode;
        }
        node1.next = h2.next;
        node2.next = null;
        return h1.next;
    }
}

面试题 08.09. 括号 - 力扣（LeetCode）

直接dfs即可，不会有重复，无需记忆化

class Solution {
    public List<String> generateParenthesis(int n) {
        dfs(0, n, n, new StringBuilder());
        return results;
    }

    List<String> results = new ArrayList<>();
    void dfs(int leftInStackCount, int leftRealCount, int rightRealCount, StringBuilder sb) {
        if (rightRealCount == 0) {
            results.add(sb.toString());
            return;
        }
        if (leftInStackCount > 0) {
            sb.append(")");
            dfs(leftInStackCount-1, leftRealCount, rightRealCount - 1, sb);
            sb.deleteCharAt(sb.length()-1);
        }
        if (leftRealCount > 0) {
            sb.append("(");
            dfs(leftInStackCount+1, leftRealCount-1, rightRealCount, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}