暖树

在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 record，返回其中存在的「交易逆序对」总数。 示例 1： **输入：**record = [9, 7, 5, 4, 6] **输出：**8 **解释：**交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。 提示： 0 <= record.length <= 50000 求逆序对的个数，就是求冒泡排序中交换的次数 同理在归并排序中我们也可以得到本应交换的次数 例如[1,3,5]和[2,4,6]合并mid=2，i=1,j=0时已经合并1下一个要放入2 如果是冒泡排序需要2分别与5，3交换 i=2,j=1时已经合并1，2，3下一个要放入4 如果是冒泡排序需要4与5交换，可以看到交换次数就是左数组剩下的数字个数，也即交换mid-i+1次 12345678910111213141516171819202122232425262728293031323334353 ...

进程同步 进程互斥 一个进程访问某临界资源时，另一个想访问该临界资源的进程必须等待 进程互斥软件实现 单标志法 违反 空闲让进 双标志先检查法 违反 忙则等待 双标志后检查法 违 反空闲让进 和 有限等待 Peterson算法 未遵循 让权等待 进程互斥硬件实现 中断屏蔽法 进程开始访问临界区到结束为止都不允许被中断，就不会发生进程切换 TestAndSet指令 TSL把上锁并检查用硬件方式变成了原子操作 优点：实现简单，适用于多处理机环境 缺点：不满足让权等待，暂时无法进入临界区的进程会占用cpu循环执行TSL Swap指令 也是原子操作，与TSL基本一样都是把lock记录在old中然后lock变为true 信号量机制 整型信号量 记录型信号量 信号量实现进程同步 生产者-消费者 同步是不同进程间同步，互斥是对临界资源的互斥 读者-写者 读-写互斥，写-写互斥，但是读-读不互斥 上述方法如果在读者读期间不断有读者进入会导致写进程饿死 下面可以让写进程进入后，先阻塞读进程的排队但不影响已经开始读的进程，只要在写进程之前进入的读者读完就可以开始写 哲 ...

某套连招动作记作仅由小写字母组成的序列 arr，其中 arr[i] 第 i 个招式的名字。请返回第一个只出现一次的招式名称，如不存在请返回空格。 示例 1： **输入：**arr = “abbccdeff” 输出：‘a’ 示例 2： **输入：**arr = “ccdd” 输出：’ ’ 限制： 0 <= arr.length <= 50000 用哈希表存字符出现次数，也可以外加keys数组，最后遍历时可以少遍历重复元素 1234567891011121314class Solution {public: char dismantlingAction(string arr) { unordered_map<char, int> flag; for (char c : arr) { flag[c]++; } for (char i : arr) { if (flag[i] == 1) ...

给你一个整数 n ，请你找出并返回第 n 个 丑数 。 **说明：**丑数是只包含质因数 2、3 或 5 的正整数；1 是丑数。 示例 1： 输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。 提示： 1 <= n <= 1690 首先可以知道，后面的丑数都是由前面的丑数乘以2或3或5得到的，但是我们不知道先出现的是哪个数乘以哪个值 可以考虑维护一个最小堆，同时使用哈希表避免重复，这样相当于我们是先求值再排序，直到能确定位置的丑数的个数达到n个。 123456789101112131415161718192021222324class Solution {public: int nthUglyNumber(int n) { priority_queue<long, vector<long>, greater<long>> q; q.push(1); unordered_map<long, b ...

某套连招动作记作序列 arr，其中 arr[i] 为第 i 个招式的名字。请返回 arr 中最多可以出连续不重复的多少个招式。 示例 1： **输入：**arr = “dbascDdad” **输出：**6 **解释：**因为连续且最长的招式序列是 “dbascD” 或 “bascDd”，所以其长度为 6。 示例 2： **输入：**arr = “KKK” **输出：**1 **解释：**因为无重复字符的最长子串是 “K”，所以其长度为 1。 示例 3： **输入：**arr = “pwwkew” **输出：**3 **解释：**因为连续且最长的招式序列是 “wke”，所以其长度为 3。 请注意区分 子串 与 子序列 的概念：你的答案必须是 连续招式 的长度，也就是 子串。而 “pwke” 是一个非连续的 子序列，不是 子串。 提示： 0 <= arr.length <= 40000 arr 由英文字母、数字、符号和空格组成。 可以通过滑动窗口来计算以当前字符结尾的最长不重复子串 使用哈希表来保存当前字符最后一次出现的下标 关键是更新左边界时要取 max(l, flag[c ...

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为： 只能从架子的左上角开始拿珠宝 每次可以移动到右侧或下侧的相邻位置 到达珠宝架子的右下角时，停止拿取 注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。 示例 1： **输入：**frame = [[1,3,1],[1,5,1],[4,2,1]] **输出：**12 **解释：**路径 1→3→5→2→1 可以拿到最高价值的珠宝 提示： 0 < frame.length <= 200 0 < frame[0].length <= 200 动态规划 dp[i][j] = max( dp[i-1][j]+frame[i][j], dp[i][j-1]+frame[i][j] ) 后续不会用到dp[i-1][j]和dp[i][j-1]，所以可以直接在原数组上操作 12345678910111213141516171819202122class Solution {public: int jewel ...