2024/06/04记录
学习记录 10:13 --12:02 14:22 -- 15:34 15:55 -- 17:10 算法小计 386. 字典序排数 - 力扣（LeetCode） https://leetcode.cn/problems/lexicographical-numbers/description/?envType=study-plan-v2&envId=2024-spring-sprint-100 440. 字典序的第K小数…
学习记录
10:13 –12:02
14:22 – 15:34
15:55 – 17:10
算法小计
// 递归解法，对于这类型不好思考遍历顺序的题目，都可以尝试使用递归
// 时间复杂度：本质上在搜索一棵节点数量为 n 的多阶树（形态类似于字典树），复杂度为 O(n)
// 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)
class Solution {
List<Integer> ans = new ArrayList<>();
public List<Integer> lexicalOrder(int n) {
for (int i = 1; i <= 9; i++) dfs(i, n);
return ans;
}
public void dfs(int cur, int limit) {
if (cur > limit) return;
ans.add(cur);
for (int i = 0; i <= 9; i++) dfs(cur * 10 + i, limit);
}
}class Solution {
public List<Integer> lexicalOrder(int n) {
List<Integer> ans = new ArrayList<>();
// i 用来表示操作次数，加入ans的元素个数是确定的
for (int i = 0, j = 1; i < n; i++) {
// j 代表当前处理的元素
ans.add(j);
// 在满足条件的情况下，优先在j的后面添加0
if (j * 10 <= n) {
j *= 10;
} else {
// 考虑将上一步的操作回退，如果当前处理的数即将进位或者大于n 考虑将上一步的操作回退
// 进行加一操作
while (j % 10 == 9 || j + 1 > n) j /= 10;
j++;
}
}
return ans;
}
}字典序排列也就是对十叉树进行先序遍历
以下两者解法的区别仅仅在于getCnt()方法上
class Solution {
public int findKthNumber(int n, int k) {
int ans = 1;
while (k > 1) {
int cnt = getCnt(ans, n);
// 说明所有以x为前缀的数组均可跳过，此时让x自增，k减去cnt。含义为从下一个[数值比x大]的前缀中找目标值
if (cnt < k) {
k -= cnt;
ans ++;
// 说明目标值前缀必然为x，此时，我们需要在以x为前缀的前提下找目标值.
// 此时让 x 乘 10，k 减 1，含义为从下一个[字典序比x大]的前缀中寻找目标值
// 当 k == 1时候，当前前缀x即是答案（含义为以x为前缀的所有数中，最小的数，也就是x本身）
} else {
k--;
ans *= 10;
}
}
return ans;
}
/**
在范围[1, limit]内，以x为前缀的数值数量等于下面所有情况的数量之和
位数为 n 的数：仅有 x 本身，共1个
位数为 n + 1 < m 的数，有 x0 到 x9，共10个
位数为 n + 2 < m 的数，有 x00 到 x99，共100个
...
位数为m的数，要根据limit长度与x等同的前缀u 和 x 的大小关系。进一步分情况讨论
u < x：此时所有位数为m的数均大于limiy，合法个数为0
u == x，此时所有位数为m的数中部分满足limit限制的合法个数为 limit - x * 10^k + 1 只有[x0...0, limit] 合法
u > x：此时所有位数为m的数均小于limit，合法个数为 10 ^ k
*/
public int getCnt(int x, int limit) {
String a = String.valueOf(x), b = String.valueOf(limit);
int n = a.length(), m = b.length(), k = m - n;
int ans = 0, u = Integer.parseInt(b.substring(0, n));
for (int i = 0; i < k; i++) ans += Math.pow(10, i);
if (u > x) ans += Math.pow(10, k);
else if (u == x) ans += limit - x * Math.pow(10, k) + 1;
return ans;
}
}class Solution {
public int findKthNumber(int n, int k) {
int cur=1;//第一字典序小的(就是1)
int prefix=1;// 前缀从1开始
while(cur<k) {
int tmp=getCnt(n,prefix); //当前prefix峰的值
if(tmp+cur>k) {// 找到了
prefix*=10; //往下层遍历
cur++;//一直遍历到第K个推出循环
}else {
prefix++;//去下个峰头(前缀)遍历
cur+=tmp;//跨过了一个峰(前缀)
}
}//退出循环时 cur==k 正好找到
return prefix;
}
private int getCnt(int n, int prefix) {
//不断向下层遍历可能一个乘10就溢出了, 所以用long
long cur=prefix;
long next=cur+1;//下一个前缀峰头
int count=0;
while(cur<=n) {
count+=Math.min(n+1,next)-cur;//下一峰头减去此峰头
// 如果说刚刚prefix是1，next是2，那么现在分别变成10和20
// 1为前缀的子节点增加10个，十叉树增加一层, 变成了两层
// 如果说现在prefix是10，next是20，那么现在分别变成100和200，
// 1为前缀的子节点增加100个，十叉树又增加了一层，变成了三层
cur*=10;
next*=10; //往下层走
}
return count;
}
}class Solution {
public int[][] reconstructQueue(int[][] people) {
// 按照身高重建队列，其中身高people[i][0]表示身高，people[i][1]表示前面有people[i][1]个人的身高大于等于
// 可以知道，令u = people[i][0] v = people[i][1]，当 u 相同的时候。v按照升序
// 这样，从前往后处理排序的数组的时候，可以知道前面的所有数组一定是大于待处理的数的，这个时候就可以按照 v直接插入对应的位置
Arrays.sort(people, (a, b) -> {
if (a[0] == b[0]) return a[1] - b[1];
return b[0] - a[0];
});
List<int[]> ans = new ArrayList<>();
for (int i = 0; i < people.length; i++) {
ans.add(people[i][1], people[i]);
}
return ans.toArray(new int[people.length][2]);
}
}LCR 170. 交易逆序对的总数 - 力扣（LeetCode）
比较经典的逆序对问题，注意一点，在计算逆序对的时候，哪边需要用到下标计算，哪边在相等的时候就先处理
class Solution {
public int reversePairs(int[] record) {
if (record == null || record.length < 1) return 0;
return reversePairsProcess(record, 0, record.length - 1);
}
public int reversePairsProcess(int[] nums, int L, int R) {
if (L >= R) return 0;
int M = L + (R - L) / 2;
return reversePairsProcess(nums, L, M) +
reversePairsProcess(nums, M + 1, R) +
mergeTwo(nums, L, M, R);
}
public int mergeTwo(int[] nums, int L, int M, int R) {
int p1 = L, p2 = M + 1;
int[] help = new int[R - L + 1];
int reversePairs = 0;
int index = 0;
while (p1 <= M && p2 <= R) {
reversePairs += nums[p1] > nums[p2] ? (M - p1 + 1) : 0;
help[index++] = nums[p1] > nums[p2] ? nums[p2++] : nums[p1++];
}
while (p1 <= M) {
help[index++] = nums[p1++];
}
while (p2 <= R) {
help[index++] = nums[p2++];
}
for (int i = 0; i < help.length; i++) {
nums[L + i] = help[i];
}
return reversePairs;
}
}315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）
这道题是之前上一道逆序对的扩展
没太明白，为什么这道题采用上一道题的正序排列，在求取对应下标的逆序对的时候会失败。
class Solution {
List<Integer> ans = new ArrayList<>();
int[] index;
int[] count;
public List<Integer> countSmaller(int[] nums) {
int len = nums.length;
index = new int[len];
count = new int[len];
for (int i = 0; i < nums.length; i++) {
index[i] = i;
}
process(nums, 0, nums.length - 1);
for (int i = 0; i < len; i++) {
ans.add(count[i]);
}
return ans;
}
public void process(int[] nums, int L, int R) {
if (L >= R) return;
int M = L + (R - L) / 2;
process(nums, L, M);
process(nums, M + 1, R);
mergeTwo(nums, L, M, R);
}
public void mergeTwo(int[] nums, int L, int M, int R) {
int p1 = L, p2 = M + 1;
int[] tmp = new int[R - L + 1];
int[] tmpIndex = new int[R - L + 1];
int idx = 0;
while (p1 <= M && p2 <= R) {
if (nums[p1] > nums[p2]) {
count[index[p1]] += R - p2 + 1;
tmpIndex[idx] = index[p1];
tmp[idx++] = nums[p1++];
} else {
tmpIndex[idx] = index[p2];
tmp[idx++] = nums[p2++];
}
}
while (p1 <= M) {
tmpIndex[idx] = index[p1];
tmp[idx++] = nums[p1++];
}
while (p2 <= R) {
tmpIndex[idx] = index[p2];
tmp[idx++] = nums[p2++];
}
for (int i = 0; i < tmp.length; i++) {
nums[L + i] = tmp[i];
index[L + i] = tmpIndex[i];
}
}
}