网站一直百度上搜不到是怎么回事,音乐网站建设教程,1空间做2个网站,附近装修公司1.报数 实现一个十进制数字报数程序#xff0c;请按照数字从小到大的顺序返回一个整数数列#xff0c;该数列从数字 1 开始#xff0c;到最大的正整数 cnt 位数字结束。
示例 1:
输入#xff1a;cnt 2
输出#xff1a;[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,1…1.报数 实现一个十进制数字报数程序请按照数字从小到大的顺序返回一个整数数列该数列从数字 1 开始到最大的正整数 cnt 位数字结束。
示例 1:
输入cnt 2
输出[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99]
1.1不考虑大数越界 题目要求打印 “从 1 至 cnt 的数字” 最大的 cnt 位数记为 end 和位数 cnt 的关系 例如最大的 1 位数是 9 最大的 2 位数是 99 最大的 3 位数是 999 。则可推出公式为10的cnt次方减去1。因此只需定义区间 [1,10 cnt−1] 和步长 1 通过 for 循环生成结果列表 res 并返回即可。
class Solution {public int[] countNumbers(int cnt) {
//查询数组最大值。int end (int)Math.pow(10, cnt) - 1;
//创建对应长度数组。int[] res new int[end];
//依次存储。for(int i 0; i end; i)res[i] i 1;return res;}
}
1.2大数打印 实际上本题的主要考点是大数越界情况下的打印。需要解决以下三个问题
1. 表示大数的变量类型 无论是 short / int / long ... 任意变量类型数字的取值范围都是有限的。因此大数的表示应用字符串 String 类型。
2. 生成数字的字符串集 使用 int 类型时每轮可通过 1 生成下个数字而此方法无法应用至 String 类型。并且 String 类型的数字的进位操作效率较低例如 9999 至 10000 需要从个位到千位循环判断进位 4 次。 观察可知生成的列表实际上是 cnt 位 0 - 9 的 全排列 因此可避开进位操作通过递归生成数字的 String 列表。
3. 递归生成全排列 基于分治算法的思想先固定高位向低位递归当个位已被固定时添加数字的字符串。例如当 cnt2 时数字范围 1−99 固定十位为 0 - 9 按顺序依次开启递归固定个位 0 - 9 终止递归并添加数字字符串。 复杂度分析时间复杂度 O(10的cnt次方) 递归的生成的排列的数量为 10的cnt次方。空间复杂度 O(10的cnt次方) 。结果列表 res 的长度为 10 cnt−1 各数字字符串的长度区间为 1,2,...,cnt 因此占用 O(10 cnt) 大小的额外空间。 辅助函数 dfs(x, len) 的作用是生成长度为len的数字正在确定第 x 位。当 x0 时表示左边第一位不能为0这样可以避免出现 0 开头的字符串。
代码实现
class Solution {ListInteger res; // 用于存储结果StringBuilder cur; // 当前生成的数字char[] NUM {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // 允许使用的数字// 生成长度为 len 的数字正在确定第 x 位从左往右void dfs(int x, int len) {if (x len) { // 递归终止条件所有位数已经确定res.add(Integer.parseInt(cur.toString())); // 将当前数字加入结果集转换为整数return;}int start (x 0) ? 1 : 0; // 如果是第一位数字不能为 0for (int i start; i 10; i) {cur.append(NUM[i]); // 确定当前位的数字dfs(x 1, len); // 继续确定下一位cur.deleteCharAt(cur.length() - 1); // 回溯删除本位数字}}public int[] countNumbers(int cnt) {res new ArrayList(); // 初始化结果集cur new StringBuilder(); // 初始化当前数字生成器for (int i 1; i cnt; i) { // 数字长度从 1 到 cntdfs(0, i); // 生成长度为 i 的所有数字}// 将结果转换为数组int[] resultArray new int[res.size()];for (int i 0; i res.size(); i) {resultArray[i] res.get(i);}return resultArray; // 返回结果数组}
}
1.3总结 本题主要考察大数越界即用string来表示数组且用递归生成全排列来生成数组。
2.训练计划I
2.1双线指针 教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练趣味性需要将所有奇数编号训练项目调整至偶数编号训练项目之前。请将调整后的训练项目编号以 数组 形式返回。
示例 1
输入actions [1,2,3,4,5]
输出[1,3,5,2,4]
解释为正确答案之一
提示
0 actions.length 500000 actions[i] 10000 考虑定义双指针 i , j 分列数组左右两端循环执行 指针 i 从左向右寻找偶数 指针 j 从右向左寻找奇数 将 偶数 actions[i] 和 奇数 actions[j] 交换。 可始终保证 指针 i 左边都是奇数指针 j 右边都是偶数 。 时间复杂度 O(N) N 为数组 actions 长度双指针 i, j 共同遍历整个数组。空间复杂度 O(1) 双指针 i, j 使用常数大小的额外空间。
代码实现
class Solution {public int[] trainingPlan(int[] actions) {
//定义两个指针分别指向首尾两端。int i 0, j actions.length - 1, tmp;
//确保指针顺序while(i j) {
//确保指针指向需调换元素上。while(i j (actions[i] 1) 1) i;while(i j (actions[j] 1) 0) j--;
//若指到同一位置互换无影响。tmp actions[i];actions[i] actions[j];actions[j] tmp;}return actions;}
}2.2 总结 题主要考察双向指针的灵活运用其中要注意判断条件的选取。
3.库存管理II 仓库管理员以数组 stock 形式记录商品库存表。stock[i] 表示商品 id可能存在重复。请返回库存表中数量大于 stock.length / 2 的商品 id。
示例 1:
输入: stock [6, 1, 3, 1, 1, 1]
输出: 1
限制
1 stock.length 50000给定数组为非空数组且存在结果数字 3.1哈希表统计法 遍历数组 stock 用 HashMap 统计各数字的数量即可找出 众数 。此方法时间和空间复杂度均为 O(N) 。
代码实现
class Solution {public int inventoryManagement(int[] stock) {// 创建一个 HashMap 来存储元素和它们的出现次数MapInteger, Integer map new HashMap();// 计算数组长度的一半用于判断某元素是否出现超过一半int n stock.length / 2;// 遍历数组中的每一个元素for (int num : stock) {// 统计每个元素的出现次数如果元素不在 map 中则默认次数为 0map.put(num, map.getOrDefault(num, 0) 1);// 如果某个元素的次数超过数组长度的一半返回该元素if (map.get(num) n)return num;}// 如果没有找到符合条件的元素返回 0return 0;}
}3.2数组排序法 将数组 stock 排序数组中点的元素 一定为众数。时间复杂度: O(NlogN)因为排序的时间复杂度是 O(NlogN)。空间复杂度: O(1)对于原地排序或者 O(N)取决于排序算法实现。
class Solution {public int inventoryManagement(int[] stock) {// 首先对数组进行排序Arrays.sort(stock);// 返回数组中间的元素众数一定在中间位置return stock[stock.length / 2];}
}
3.3摩尔投票法 核心理念为 票数正负抵消 。此方法时间和空间复杂度分别为 O(N) 和 O(1) 为本题的最佳解法。
摩尔投票法 设输入数组 stock 的众数为 x 数组长度为 n 。
推论一 若记 众数 的票数为 1 非众数 的票数为 −1 则一定有所有数字的 票数和 0 。
推论二 若数组的前 a 个数字的 票数和 0 则 数组剩余 (n−a) 个数字的 票数和一定仍 0 即后 (n−a) 个数字的 众数仍为 x 。 摩尔投票法Boyer-Moore Voting Algorithm是一种用于寻找数组中众数的高效算法。众数是指在数组中出现次数超过数组长度一半的元素。该算法的主要特点是时间复杂度为 O(N)且空间复杂度为 O(1)非常适合处理这个问题。
算法原理
摩尔投票法的核心思想是利用计数来确定候选众数。具体步骤如下 初始化 定义一个变量 candidate 来存储当前候选的众数和一个 count 来记录候选众数的计数初始值为 0。 遍历数组 对于数组中的每个元素 如果 count 为 0更新 candidate 为当前元素并将 count 设为 1。如果当前元素等于 candidate则 count 加 1。如果当前元素不等于 candidate则 count 减 1。 返回结果 因为题目保证存在众数所以在结束遍历后candidate 就是众数。
代码实现
class Solution {public int inventoryManagement(int[] stock) {// 变量 x 用于存储当前认为的候选众数votes 用于统计支持度count 用于验证候选众数的出现次数int x 0, votes 0, count 0;// 第一遍历找出候选众数for (int num : stock) {// 如果当前支持度为 0则更新候选众数为当前元素 numif (votes 0)x num;// 更新支持度如果 num 与候选众数相同支持度加 1否则减 1votes (num x) ? 1 : -1;}// 第二遍历验证候选众数 x 是否为真正的众数for (int num : stock)// 统计候选众数 x 的出现次数if (x num)count;// 如果候选众数的出现次数大于数组长度的一半则返回众数 x否则返回 -1表示无众数return count (stock.length / 2) ? x : -1;}
}4.总结 本题主要考察寻找中位数中的摩尔投票法该方法可提高算法性能。
4.库存管理III 仓库管理员以数组 stock 形式记录商品库存表其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量返回 顺序不限。
示例 1
输入stock [2,5,7,4], cnt 1
输出[2]示例 2
输入stock [0,2,3,6], cnt 2
输出[0,2] 或 [2,0]
提示
0 cnt stock.length 10000 0 stock[i] 10000
4.1快速排序法 本题使用排序算法解决最直观对数组 stock 执行排序再返回前 cnt 个元素即可。 快速排序Quick Sort是一种高效的排序算法采用分治法Divide and Conquer策略通过一个称为“基准”pivot的元素将数组分为两个子数组然后递归地对这两个子数组进行排序。快速排序的平均时间复杂度为 O(NlogN)但最坏情况下为 O(N^2)。空间复杂度 O(N) 快速排序的递归深度最好平均为 O(logN) 最差情况即输入数组完全倒序为 O(N)。
算法原理 选择基准从数组中选择一个元素作为基准pivot可以选择第一个元素、最后一个元素或随机选择。 分区操作重新排列数组将比基准小的元素放到基准的左边将比基准大的元素放到右边。经过分区后基准元素在其最终位置上。 递归排序对基准左边和右边的子数组递归进行快速排序。 终止条件当子数组的大小为 0 或 1 时表示该子数组已经排好序递归结束。
代码实现
class Solution {public int[] inventoryManagement(int[] stock, int cnt) {quickSort(stock, 0, stock.length - 1); // 调用快速排序return Arrays.copyOf(stock, cnt); // 返回前 cnt 个库存项}private void quickSort(int[] stock, int l, int r) {// 子数组长度为 1 时终止递归if (l r) return;// 哨兵划分操作以 stock[l] 作为基准数int i l, j r;while (i j) {while (i j stock[j] stock[l]) j--; // 从右向左找到第一个小于基准数的元素while (i j stock[i] stock[l]) i; // 从左向右找到第一个大于基准数的元素swap(stock, i, j); // 交换这两个元素}swap(stock, i, l); // 把基准数放到它最终的位置// 递归左右子数组执行哨兵划分quickSort(stock, l, i - 1); // 对左子数组排序quickSort(stock, i 1, r); // 对右子数组排序}private void swap(int[] stock, int i, int j) {int tmp stock[i]; // 交换元素stock[i] stock[j];stock[j] tmp;}
}4.2快速选择法 根据给出的题目要求我们需要返回库存余量最少的 cnt 个商品余量且返回顺序不限。可以使用快速选择算法Quick Select来高效地实现这个目标。以下是实现的详细步骤和代码。
算法原理 选择基准在数组中选择一个基准元素可以选择最后一个元素。 哨兵划分对数组进行哨兵划分将小于等于基准的元素放在基准的左侧将大于基准的元素放在右侧。 判断基准位置 每次划分后检查基准元素的索引。如果基准元素的索引正好等于 cnt则返回数组中前 cnt 个元素。如果基准元素的索引小于 cnt则说明最小的 cnt 个数在基准的右侧需要对右侧部分继续进行划分。如果基准元素的索引大于 cnt则说明最小的 cnt 个数在基准的左侧需要对左侧部分继续进行划分。 本方法优化时间复杂度的本质是通过判断舍去了不必要的递归哨兵划分。时间复杂度 O(N) 其中 N 为数组元素数量对于长度为 N 的数组执行哨兵划分操作的时间复杂度为 O(N) 空间复杂度 O(logN) 划分函数的平均递归深度为 O(logN) 。
代码实现
class Solution {// 主方法返回库存余量最少的 cnt 个商品余量public int[] inventoryManagement(int[] stock, int cnt) {// 如果 cnt 大于等于数组长度直接返回整个数组if (cnt stock.length) return stock;// 调用快速选择方法寻找最小的 cnt 个商品余量return quickSort(stock, cnt, 0, stock.length - 1);}// 辅助方法快速选择算法用于找到最小的 cnt 个元素private int[] quickSort(int[] stock, int cnt, int l, int r) {// 初始化左右指针int i l, j r;// 哨兵划分过程while (i j) {// 从右向左找到第一个小于基准元素的元素while (i j stock[j] stock[l]) j--;// 从左向右找到第一个大于基准元素的元素while (i j stock[i] stock[l]) i;// 交换这两个元素swap(stock, i, j);}// 交换基准元素到正确的位置swap(stock, i, l);// 判断基准元素的位置if (i cnt) {// 如果基准元素位置大于 cnt继续在左侧查找return quickSort(stock, cnt, l, i - 1);}if (i cnt) {// 如果基准元素位置小于 cnt继续在右侧查找return quickSort(stock, cnt, i 1, r);}// 如果基准位置等于 cnt返回前 cnt 个最小的元素return Arrays.copyOf(stock, cnt);}// 交换数组中两个元素的辅助方法private void swap(int[] stock, int i, int j) {int tmp stock[i]; // 保存第一个元素的值stock[i] stock[j]; // 将第二个元素赋值给第一个元素stock[j] tmp; // 将保存的第一个元素值赋给第二个元素}
}4.3总结 本题考查快速排序和快速选择两种高效的查找和选择算法。
