Day30_顺序_剑指Offer
IT蛋
2023-04-22 00:00
阅读1989
打印从1到最大的n位数
Easy 原题连接：打印从1到最大的n位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例：
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
解题思路
- 扩容结果数组：n是几就扩到几位数
- 遍历补数据
Java代码
class Solution {
public int[] printNumbers(int n) {
int nSize = 1;
while(n>0){
nSize *= 10;
n--;
}
int[] fin = new int[nSize-1];
for(int i=0; i<nSize-1; i++) {
fin[i] = i+1;
}
return fin;
}
}
数组中的逆序对
Hard 原题连接：数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例：
输入: [7,5,6,4]
输出: 5
Java代码
class Solution {
int count = 0;
public int reversePairs(int[] nums) {
//利用归并排序解答，在合并的时候，当左边的大于右边，就计算逆序数。
//计算公式； mid-left+1
//定义一个全局的计数器变量
this.count = 0;
mergeSort(nums, 0, nums.length-1);
return count;
}
public void mergeSort(int[] nums,int left,int right){
//当只有一个节点的时候，直接返回，退出递归
if(left >= right){
return;
}
int mid = (left+right)/2;
//左拆分
mergeSort(nums,left,mid);
//右拆分
mergeSort(nums,mid+1,right);
//合并
merge(nums,left,mid,right);
}
public void merge(int[] nums,int left,int mid,int right){
//定义一个临时数组
int[] temp = new int[right-left+1];
//定义一个指针，指向第一个数组的第一个元素
int i = left;
//定义一个指针，指向第二个数组的第一个元素
int j = mid+1;
//定义一个指针，指向临时数组的第一个元素
int t = 0;
//当两个数组都有元素的时候，遍历比较每个元素大小
while(i <= mid && j <= right){
//比较两个数组的元素，取较小的元素加入到，临时数组中
//并将两个指针指向下一个元素
if(nums[i] <= nums[j]){
temp[t++] = nums[i++];
}else{
//当左边数组的大与右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，
//此时这个数就是，逆序数
//定义一个计数器，记下每次合并中存在的逆序数。
count += mid-i+1;
temp[t++] = nums[j++];
}
}
//当左边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
while(i <= mid){
temp[t++] = nums[i++];
}
//当右边的数组没有遍历完成后，直接将剩余元素加入到临时数组中
while(j <= right){
temp[t++] =nums[j++];
}
//将新数组中的元素，覆盖nums旧数组中的元素。
//此时数组的元素已经是有序的
for(int k =0; k< temp.length;k++){
nums[left+k] = temp[k];
}
}
}
身体有点抱恙，hard是借助已有评论的文字伪代码写的，要好好休息了...
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
内容推荐
刷题经验分享
60
Leetcode文章资源分享：高效刷满500题方法论
170
这几天刷题算法，我也是入门基础，虽然还是难，思路啥的，但是温习了很多，比如map集合的containsKey等等 set的去重 map的计数等等今天刷了一道算法中等二维数组的 零矩阵 虽然还是查阅了资料但是没看题解，就是二维数组的列长度计算。。跌跌撞撞终于写出了一道中等题目[流泪][流泪]，，很开心。想放弃的，但是写出来那种成就感很足，继续加油吧[呲牙]
10
才发现力扣评论区也显示ip属地了，是从今天还是昨天开始的，刚注意到[捂脸]
15
学习总结 Python 算法 前端关于过去一年的学习情况去年尝试学习了MCU学了有一周左右弃了，然后抄网上的flask框架的项目，搞到一半发现有一些前端的问题不怎么明白，然后开始刷前端当前学到BOM，然后是算法刷了100多道 目前除了动态规划不怎么行 其他题目看到都还有点思路
8
