首页 > 其他分享 >2023-07-11：给定正整数 n， 返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。 输入：n = 100。 输出：10。

2023-07-11：给定正整数 n， 返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。 输入：n = 100。 输出：10。

时间：2023-07-11 19:22:10浏览次数：34  
标签：11 10 正整数 07 int ans len offset cur

2023-07-11：给定正整数 n，
返回在 [1, n] 范围内具有 至少 1 位 重复数字的正整数的个数。
输入：n = 100。
输出：10。

答案2023-07-11：

函数的主要思路如下：

1.若n小于等于10，则直接返回0，因为在[1, 10]范围内不存在重复数字的情况。

2.计算n的位数和偏移量。首先计算n的位数和一个偏移量offset，其中偏移量初始值为1，算法通过迭代计算tmp = n / 10的商，直到商为0为止，每次迭代位数加1，偏移量乘以10。

3.计算每个长度的非重复数字的个数。通过一个辅助函数numAllLength计算不同位数下，每个位都是唯一的数字的个数，并将其累加到变量noRepeat上。

4.计算长度为len的非重复数字的个数。当长度小于等于10时，通过包含位运算的算法进行计算，具体步骤如下：

4.1.初始化一个十进制数status为2^10-1，二进制表示为0b1111111111，用于标记当前数字的可用状态，初始状态为每位都可用。（1表示不可用，0表示可用）

4.2.根据n的位数和偏移量计算出n除以offset的商，即当前数字的最高位first。

4.3.将分三种情况：

4.3.1.若first大于0，则对于0到first-1的数字cur，如果status的第cur位为1，说明该数字可用，将offset/10和status的第cur位取反异或，并调用辅助函数numberRest计算剩余位和可用状态下的数字个数，将结果累加到变量ans上。

4.3.2.若first等于0，则直接跳过该步骤。

4.3.3.若first在0到9之间，则如果status的第first位为1，说明该数字可用，将offset/10和status的第first位取反异或，并调用递归函数process计算剩余位和可用状态下的数字个数，将结果累加到变量ans上。

5.最后的结果为n加1减去noRepeat，即在[1, n]范围内至少有1位重复数字的正整数的个数。

该代码在给定正整数n的范围内采用了一种比较高效的算法，通过一系列的位运算和迭代计算，找出了每个位数下非重复数字的个数，然后根据n的位数和偏移量来计算在该位数下包含至少1位重复数字的正整数的个数，并将它们相加得出最终结果。

该代码的时间复杂度为O(log10(n) * 2 ^ 10)，其中n是输入的正整数。主要消耗时间的是计算每个位数下非重复数字的个数，该计算的时间复杂度为O(log10(n))，而计算每个长度为len的非重复数字的个数的时间复杂度为O(2 ^ len)。因为长度为len的数字有2 ^ len个，所以计算每个长度为len的非重复数字的个数的时间复杂度为O(2 ^ len)。

该代码的空间复杂度为O(1)，因为它只使用了常量级的额外空间来保存一些临时变量，不随输入规模的增长而增加。

go完整代码如下：

package main

import (
	"fmt"
)

func numDupDigitsAtMostN(n int) int {
	if n <= 10 {
		return 0
	}

	// Calculate the length of n and the offset
	len, offset := 1, 1
	tmp := n / 10
	for tmp > 0 {
		len++
		offset *= 10
		tmp /= 10
	}

	// Calculate the count of non-repeating numbers of each length
	noRepeat := 0
	for i := 1; i < len; i++ {
		noRepeat += numAllLength(i)
	}

	// Calculate the count of non-repeating numbers for length len
	if len <= 10 {
		status := 0b1111111111
		noRepeat += ((n / offset) - 1) * numberRest(offset/10, status^1)
		noRepeat += process(offset/10, status^(1<<(n/offset)), n)
	}

	return n + 1 - noRepeat
}

// Returns the count of numbers where each digit is unique for a given length
func numAllLength(len int) int {
	if len > 10 {
		return 0
	}
	if len == 1 {
		return 10
	}

	ans, cur := 9, 9
	for len--; len > 0; len-- {
		ans *= cur
		cur--
	}

	return ans
}

// Returns the count of numbers where the remaining digits are unique
func process(offset, status, n int) int {
	if offset == 0 {
		return 1
	}

	ans := 0
	first := (n / offset) % 10
	for cur := 0; cur < first; cur++ {
		if (status & (1 << cur)) != 0 {
			ans += numberRest(offset/10, status^(1<<cur))
		}
	}

	if (status & (1 << first)) != 0 {
		ans += process(offset/10, status^(1<<first), n)
	}

	return ans
}

// Returns the count of numbers with remaining length and available digits
func numberRest(offset, status int) int {
	c := hammingWeight(status)
	ans := 1
	for offset > 0 {
		ans *= c
		c--
		offset /= 10
	}
	return ans
}

// Returns the number of set bits (1s) in a binary representation
func hammingWeight(n int) int {
	n = (n & 0x55555555) + ((n >> 1) & 0x55555555)
	n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
	n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f)
	n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff)
	n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff)
	return n
}

func main() {
	n := 1000
	result := numDupDigitsAtMostN(n)
	fmt.Println(result)
}

在这里插入图片描述

rust完整代码如下：

pub fn num_dup_digits_at_most_n(n: i32) -> i32 {
    if n <= 10 {
        return 0;
    }

    let len = get_length(n);
    let mut offset = 1;
    let mut tmp = n / 10;
    while tmp > 0 {
        offset *= 10;
        tmp /= 10;
    }

    let mut no_repeat = 0;
    for i in 1..len {
        no_repeat += num_all_length(i);
    }

    if len <= 10 {
        let status = 0b1111111111;
        no_repeat += ((n / offset) - 1) * number_rest(offset / 10, status ^ 1);
        no_repeat += process(offset / 10, status ^ (1 << (n / offset)), n);
    }

    n + 1 - no_repeat
}

fn get_length(n: i32) -> i32 {
    let mut len = 1;
    let mut tmp = n / 10;
    while tmp > 0 {
        len += 1;
        tmp /= 10;
    }
    len
}

fn num_all_length(len: i32) -> i32 {
    if len > 10 {
        return 0;
    }
    if len == 1 {
        return 10;
    }
    let mut ans = 9;
    let mut cur = 9;
    let mut len = len - 1;
    while len > 0 {
        ans *= cur;
        cur -= 1;
        len -= 1;
    }
    ans
}

fn process(offset: i32, status: i32, n: i32) -> i32 {
    if offset == 0 {
        return 1;
    }

    let mut ans = 0;
    let first = (n / offset) % 10;
    for cur in 0..first {
        if (status & (1 << cur)) != 0 {
            ans += number_rest(offset / 10, status ^ (1 << cur));
        }
    }

    if (status & (1 << first)) != 0 {
        ans += process(offset / 10, status ^ (1 << first), n);
    }

    ans
}

fn number_rest(offset: i32, status: i32) -> i32 {
    let mut c = hamming_weight(status);
    let mut ans = 1;
    let mut offset = offset;
    while offset > 0 {
        ans *= c;
        c -= 1;
        offset /= 10;
    }
    ans
}

fn hamming_weight(mut n: i32) -> i32 {
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
    n
}

fn main() {
    let n = 1000;
    let result = num_dup_digits_at_most_n(n);
    println!("Result: {}", result);
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <cmath>

int numAllLength(int len);

int process(int offset, int status, int n);

int numberRest(int offset, int status);

int hammingWeight(int n);

int numDupDigitsAtMostN(int n) {
    if (n <= 10) {
        return 0;
    }
    int len = 1;
    int offset = 1;
    int tmp = n / 10;
    while (tmp > 0) {
        len++;
        offset *= 10;
        tmp /= 10;
    }
    int noRepeat = 0;
    for (int i = 1; i < len; i++) {
        noRepeat += numAllLength(i);
    }
    if (len <= 10) {
        int status = 0b1111111111;
        noRepeat += ((n / offset) - 1) * numberRest(offset / 10, status ^ 1);
        noRepeat += process(offset / 10, status ^ (1 << (n / offset)), n);
    }
    return n + 1 - noRepeat;
}

int numAllLength(int len) {
    if (len > 10) {
        return 0;
    }
    if (len == 1) {
        return 10;
    }
    int ans = 9;
    int cur = 9;
    while (--len > 0) {
        ans *= cur;
        cur--;
    }
    return ans;
}

int process(int offset, int status, int n) {
    if (offset == 0) {
        return 1;
    }
    int ans = 0;
    int first = (n / offset) % 10;
    for (int cur = 0; cur < first; cur++) {
        if ((status & (1 << cur)) != 0) {
            ans += numberRest(offset / 10, status ^ (1 << cur));
        }
    }
    if ((status & (1 << first)) != 0) {
        ans += process(offset / 10, status ^ (1 << first), n);
    }
    return ans;
}

int numberRest(int offset, int status) {
    int c = hammingWeight(status);
    int ans = 1;
    while (offset > 0) {
        ans *= c;
        c--;
        offset /= 10;
    }
    return ans;
}

int hammingWeight(int n) {
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);
    return n;
}

int main() {
    int n = 1000;
    int result = numDupDigitsAtMostN(n);
    std::cout << "Result: " << result << std::endl;
    return 0;
}

在这里插入图片描述

c完整代码如下：

#include <stdio.h>
#include <stdbool.h>

int numAllLength(int len);

int process(int offset, int status, int n);

int numberRest(int offset, int status);

int hammingWeight(int n);

int numDupDigitsAtMostN(int n) {
    if (n <= 10) {
        return 0;
    }

    int len = 1;
    int offset = 1;
    int tmp = n / 10;
    while (tmp > 0) {
        len++;
        offset *= 10;
        tmp /= 10;
    }

    int noRepeat = 0;
    for (int i = 1; i < len; i++) {
        noRepeat += numAllLength(i);
    }

    if (len <= 10) {
        int status = 0b1111111111;
        noRepeat += ((n / offset) - 1) * numberRest(offset / 10, status ^ 1);
        noRepeat += process(offset / 10, status ^ (1 << (n / offset)), n);
    }

    return n + 1 - noRepeat;
}

int numAllLength(int len) {
    if (len > 10) {
        return 0;
    }
    if (len == 1) {
        return 10;
    }

    int ans = 9;
    int cur = 9;
    while (--len > 0) {
        ans *= cur;
        cur--;
    }

    return ans;
}

int process(int offset, int status, int n) {
    if (offset == 0) {
        return 1;
    }
    int ans = 0;
    int first = (n / offset) % 10;

    for (int cur = 0; cur < first; cur++) {
        if ((status & (1 << cur)) != 0) {
            ans += numberRest(offset / 10, status ^ (1 << cur));
        }
    }

    if ((status & (1 << first)) != 0) {
        ans += process(offset / 10, status ^ (1 << first), n);
    }

    return ans;
}

int numberRest(int offset, int status) {
    int c = hammingWeight(status);
    int ans = 1;

    while (offset > 0) {
        ans *= c;
        c--;
        offset /= 10;
    }

    return ans;
}

int hammingWeight(int n) {
    n = (n & 0x55555555) + ((n >> 1) & 0x55555555);
    n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
    n = (n & 0x0f0f0f0f) + ((n >> 4) & 0x0f0f0f0f);
    n = (n & 0x00ff00ff) + ((n >> 8) & 0x00ff00ff);
    n = (n & 0x0000ffff) + ((n >> 16) & 0x0000ffff);

    return n;
}

int main() {
    int n = 1000;
    int result = numDupDigitsAtMostN(n);
    printf("Result: %d\n", result);
    return 0;
}

在这里插入图片描述

标签：11,10,正整数,07,int,ans,len,offset,cur
From： https://www.cnblogs.com/moonfdd/p/17545713.html

相关文章

  • 2023.7.11 训练
    1.dp相关1.1path给定一个\(n∗m\)的网格，你在左下角\((n,1)\)，一开始你面向上方，你只能往前走或者右拐，障碍和走过的点不能走。求走到\((x,y)\)的方案数的值，取模。\(n,m\le40\)观察到一右拐，就会进入一个子矩形，并只能在这里面移动了。设状态\(f(a,b,x,y,0..3)\)表示从......
  • 「NOIP 2023 模拟赛 20230711 B」过往未来
    summarization给定一个\(n\)个节点的树，定义\(x_1,x_2,\cdots,x_k\)生成的子树为树中边数最少的包含\(x_1,x_2,\cdots,x_k\)的连通块。对所有可能的\(x_1,x_2,\cdots,x_k\quad(1\lex_1<x_2<\cdots<x_k\len)\)，求\(x_1,x_2,\cdots,x_k\)生成的子树的大小（边数和）总和。so......
  • 力扣---1911. 最大子序列交替和
    一个下标从 0 开始的数组的 交替和 定义为 偶数 下标处元素之 和 减去 奇数 下标处元素之 和 。比方说，数组 [4,2,5,3] 的交替和为 (4+5)-(2+3)=4 。给你一个数组 nums ，请你返回 nums 中任意子序列的 最大交替和 （子序列的下标 重新 从0开始......
  • C++自助点餐系统[2023-07-06]
    C++自助点餐系统[2023-07-06]面向对象程序课程设计任务书【题目】自助点餐系统【目的】通过设计一个小型的自助点餐系统，训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念，使自己的程序设计与调试水平有一个明显的提高。【要求】1、每个学生必须独立完成；2......
  • Spring中最常用的11个扩展点
    1.自定义拦截器springmvc拦截器根spring拦截器相比，它里面能够获取HttpServletRequest和HttpServletResponse等web对象实例。springmvc拦截器的顶层接口是：HandlerInterceptor，包含三个方法：1.2）preHandle目标方法执行前执行1.2）postHandle目标方法执行后执行1.3）afterCompletio......
  • C++停车场管理系统[2023-07-06]
    C++停车场管理系统[2023-07-06]停车场管理系统简介一、 问题描述设停车场是一个可停放若干辆辆汽车的狭多层平面区域，且只有一个大门可供汽车进出。若车场内已停满汽车，则后来的汽车只能在门外的狭长便道上等候，一旦停车场内有车开走，则排在便道上的第一辆车即可进入。每辆停放在车......
  • 《C++程序设计》[2023-07-06]
    《C++程序设计》[2023-07-06]智能与工程学院《C++程序设计》小组学习任务书第2次专业年级：2022级计算机指导教师：李佳佳2022-2023学年第2学期一、任务根据课程所学，利用C++泛型编程思想、STL、模板、I\O流和异常处理等，以小组为单位完成基于STL泛化......
  • C/C++学生成绩管理系统[2023-07-06]
    C/C++学生成绩管理系统[2023-07-06]学生成绩管理系统开发一个可以管理学生成绩以及学生基本信息的一个信息系统，至少实现如下功能：信息管理，支持信息的增、删、改、查操作，具体信息类型如下：(1) 管理学生信息 ，包括学号，姓名，年龄，班级等等信息。(2) 班级信息，包括班级编号、班级人数，......
  • 2023-07-11 《数值优化方法》-庞丽萍，肖现涛-无约束最优化（六）
    2023-07-11《数值优化方法》-庞丽萍，肖现涛-无约束最优化（六）数值优化方法Matlab共轭梯度法共轭方向法回顾上节的最速下降法的特征：最速下降法迭代路径呈锯齿状，即.这一节给出共轭的概念，其是正交性的推广，然后给出共轭方向（梯度）法.**定义1.7**设是对称正定矩阵，是维非零向量.如果......
  • 行业追踪，2023-07-11，新增加 rps50 排名，汽车零部件回落 10 日均线，直接反弹
    自动复盘2023-07-11成交额超过100亿排名靠前，macd柱由绿转红成交量要大于均线有必要给每个行业加一个上级的归类，这样更能体现主流方向rps有时候比较滞后，但不少是欲杨先抑，应该持续跟踪，等macd反转时参与一线红：第一次买点出现后往往是顶峰，等回调，macd反转，rps50还一直红......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99