2024/06/04记录

学习记录

10:13 –12:02

14:22 – 15:34

15:55 – 17:10

算法小计

386. 字典序排数 - 力扣（LeetCode）

// 递归解法，对于这类型不好思考遍历顺序的题目，都可以尝试使用递归
// 时间复杂度：本质上在搜索一棵节点数量为 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;
    }
}

440. 字典序的第K小数字 - 力扣（LeetCode）

字典序排列也就是对十叉树进行先序遍历

以下两者解法的区别仅仅在于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;
	}
}

406. 根据身高重建队列 - 力扣（LeetCode）

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];
        }
    }

}

素养提升