罗湖附近公司做网站建设哪家便宜,特殊字体,怎么接广告赚钱,wordpress不要焦点图剑指 Offer第二版 43. 1#xff5e;n 整数中 1 出现的次数51. 数组中的逆序对56 - II. 数组中数字出现的次数 II 43. 1#xff5e;n 整数中 1 出现的次数 题目#xff1a;输入一个整数 n #xff0c;求1#xff5e;n这n个整数的十进制表示中1出现的次数。 例如#xff0c… 剑指 Offer第二版 43. 1n 整数中 1 出现的次数51. 数组中的逆序对56 - II. 数组中数字出现的次数 II 43. 1n 整数中 1 出现的次数 题目输入一个整数 n 求1n这n个整数的十进制表示中1出现的次数。 例如输入12112这些整数中包含1 的数字有1、10、11和121一共出现了5次。 示例 1 输入n 12 输出5 **思路分析**将n的每一位数分别处理计算出每个位数上1的个数然后将所有位数上1的个数相加即可。具体来说首先判断n是否为0如果n为0直接返回0。然后从低位到高位依次处理每一位数计算当前位数上1的个数。如果当前位数的数字小于11的个数为高位数当前位数即highbit如果当前位数的数字等于11的个数为高位数当前位数低位数1即highbitlow1如果当前位数的数字大于11的个数为(high1)*bit即高位数加一乘以当前位数。最后将所有位数上1的个数相加即为最终结果。 时间复杂度需要处理n的每一位数因此时间复杂度为 O ( log n ) O(\log n) O(logn)。 空间复杂度只需要使用常量级别的额外空间因此空间复杂度为 O ( 1 ) O(1) O(1)。 class Solution {public int countDigitOne(int n) {if (n 0) { // 如果n为0直接返回0return 0;}long bit 1; // bit表示当前处理的位数long cur n / bit % 10; // cur表示当前处理的数字long low n % bit; // low表示当前位数以下的数字long high n / bit / 10; // high表示当前位数以上的数字long res 0; // res表示1的个数while (bit n) { // 当位数小于等于n的位数时继续处理if (cur 1) { // 如果当前位数的数字小于11的个数为high*bitres high * bit;} else if (cur 1) { // 如果当前位数的数字等于11的个数为high*bitlow1res high * bit low 1;} else { // 如果当前位数的数字大于11的个数为(high1)*bitres (high 1) * bit;}bit * 10; // 处理下一位数cur n / bit % 10;low n % bit;high n / bit / 10;}return (int) res; // 返回1的个数}
}
51. 数组中的逆序对 题目在数组中的两个数字如果前面一个数字大于后面的数字则这两个数字组成一个逆序对。输入一个数组求出这个数组中的逆序对的总数。 示例 1 输入: [7,5,6,4] 输出: 5 思路分析 在归并排序的过程中每次合并两个有序的子数组时需要统计逆序对数量。具体实现时在合并过程中如果左半段的数大于等于右半段的数则说明左半段中剩余的数都比右半段的数大因此可以直接统计逆序对数量。 时间复杂度归并排序的时间复杂度为O(nlogn)而在归并排序的过程中每次合并两个有序的子数组时需要遍历所有元素一次因此合并的时间复杂度也是O(nlogn)。因此总的时间复杂度为O(nlogn)。 空间复杂度归并排序需要使用一个临时数组来存储合并过程中的数据因此空间复杂度为O(n)。 class Solution {int res 0; // 记录逆序对数量public int reversePairs(int[] nums) {if (nums null || nums.length 0) {return 0;}mergeSort(nums, 0, nums.length - 1); // 归并排序return res; // 返回逆序对数量}private void mergeSort(int[] nums, int l, int r) {if (l r) {return;}int mid (r - l) / 2 l; // 计算中间位置mergeSort(nums, l, mid); // 对左半段进行归并排序mergeSort(nums, mid 1, r); // 对右半段进行归并排序merge(nums, l, mid, r); // 合并左右两个有序的子数组}private void merge(int[] nums, int l, int mid, int r) {int i l; // 左半段的起始位置int j mid 1; // 右半段的起始位置int[] temp new int[r - l 1]; // 用于存储合并过程中的数据int index 0; // 临时数组的下标while (i mid j r) { // 合并左右两个有序的子数组if (nums[i] nums[j]) { // 如果左半段的数小于右半段的数temp[index] nums[i]; // 将左半段的数加入临时数组中} else { // 如果左半段的数大于等于右半段的数res mid - i 1; // 统计逆序对数量temp[index] nums[j]; // 将右半段的数加入临时数组中}}// 将剩余的元素复制到临时数组中while (i mid) {temp[index] nums[i];}while (j r) {temp[index] nums[j];}// 将临时数组中的元素复制回原数组中index 0;for (i l; i r; i) {nums[i] temp[index];}}
}56 - II. 数组中数字出现的次数 II 题目在一个数组 nums 中除一个数字只出现一次之外其他数字都出现了三次。请找出那个只出现一次的数字。 示例 1 输入nums [3,4,3,3] 输出4 思路分析 对于每一位统计所有数字在该位上出现的次数然后对3取模得到出现1次的数字在该位上的值。最后将所有位的值合并起来即得到最终结果。 时间复杂度为O(nk)其中n为数字数量k为数字的二进制位数因为需要遍历所有数字和所有位数。 空间复杂度为O(k)因为需要使用一个长度为k的数组来记录每个数字在每个位上出现的次数。 class Solution {public int singleNumber(int[] nums) {if(nums null || nums.length 0){return -1;}int res 0; // 用于存储最终结果int bit 1; // 用于表示当前位的值从最低位开始int[] count new int[32]; // 用于记录所有数字在当前位上出现的次数for(int i 0; i 32; i){ // 遍历所有位for(int j 0; j nums.length; j){ // 遍历所有数字if((nums[j] bit) ! 0){ // 如果当前数字在当前位上为1count[i]; // 记录出现次数}}count[i] % 3; // 对3取模得到出现1次的数字在当前位上的值res bit * count[i]; // 将当前位的值加入最终结果bit 1; // 判断下一位}return res; // 返回最终结果}
}
