最美情侣中文字幕电影,在线麻豆精品传媒,在线网站高清黄,久久黄色视频

歡迎光臨散文網(wǎng) 會員登陸 & 注冊

2023-05-01：給你一個整數(shù) n ， 請你在無限的整數(shù)序列 [1, 2, 3, 4, 5, 6, 7, 8, 9,

2023-05-01 21:33 作者:福大大架構(gòu)師每日一題  | 我要投稿

2023-05-01：給你一個整數(shù) n ， 請你在無限的整數(shù)序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的數(shù)字。 1 <= n <= 2^31 - 1。 輸入：n = 11 輸出：0 解釋：第 11 位數(shù)字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

答案2023-05-01：

該程序的大體過程：

1.定義數(shù)組?under?和?help，分別用于存儲數(shù)字位數(shù)對應(yīng)能處理的數(shù)的個數(shù)和指示各位數(shù)之間的跨度。

2.實現(xiàn)函數(shù)?findNthDigit，其輸入為整數(shù)?n，表示要查找的數(shù)字在整數(shù)序列中的位置。根據(jù)?under?數(shù)組，找到包含第 n 個數(shù)字的區(qū)間長度?len，并返回調(diào)用子函數(shù)?number?的結(jié)果。

3.實現(xiàn)函數(shù)?number，其輸入為當前路徑?path、數(shù)字的位數(shù)?len、最高位的權(quán)重?offset、最低位的權(quán)重?all?和從開始算起剩余的第幾個數(shù)字?nth。如果?offset?等于 0，則說明已經(jīng)到達最低位，直接返回路徑經(jīng)過的值中的第?nth?個數(shù)字；否則，計算出當前節(jié)點?cur?取值（這可能需要根據(jù)?offset?來進行特殊處理），根據(jù)?all?和?offset?計算下一個節(jié)點的路徑?cur*(all/offset)+path，并遞歸地調(diào)用?number?函數(shù)。

4.在?main?函數(shù)中，定義一個整數(shù)變量?n?表示要查找的數(shù)字在整數(shù)序列中的位置，調(diào)用?findNthDigit?函數(shù)查找第?n?個數(shù)字，并輸出結(jié)果。

時間復雜度和空間復雜度如下：

1.findNthDigit?函數(shù)中的循環(huán)需要遍歷數(shù)組?under，時間復雜度為 O(1) 平均時間復雜度為 O(log n)； 2.?number?函數(shù)實現(xiàn)了一個遞歸結(jié)構(gòu)，每次遞歸除去常數(shù)項的時間復雜度為 O(1), 遞歸深度為 O(log n)，所以總時間復雜度為 O(log n)； 3.數(shù)組?under?和?help?的空間復雜度分別為 O(1)，而遞歸調(diào)用?number?函數(shù)時，棧空間的最大使用量也為 O(log n)。因此，總的空間復雜度為 O(log n)。

綜上所述，該算法的時間復雜度和空間復雜度均為 O(log n)。

go完整代碼如下：

package?main

var?under?=?[]int64{
????0,?9,?189,?2889,?38889,?488889,?5888889,?68888889,?788888889,?8888888889,?98888888889,
}

var?help?=?[]int{
????0,
????1,????//?1
????10,???//?2
????100,??//?3
????1000,?//?4
????10000,
????100000,
????1000000,
????10000000,
????100000000,
????1000000000,
}

func?findNthDigit(n?int)?int?{
????l?:=?0
????for?i?:=?1;?i?<?len(under);?i++?{
????????if?under[i]?>=?int64(n)?{
????????????l?=?i
????????????break
????????}
????}
????return?number(0,?l,?help[l],?help[l],?n-int(under[l-1]))
}

//?path?:?路徑?左(低)?<-?右(高)
//?len?:?n?->?5位數(shù)?len?=?5?固定！
//?offset?:?10000?目前要決定的是高1位
//?1000?目前要決定的是高2位
//?10?目前要決定的是高2位
//?可變
//?all?:?10000?固定
//?nth?:?第幾個
func?number(path,?len,?offset,?all,?nth?int)?int?{
????if?offset?==?0?{
????????return?(path?/?help[nth])?%?10
????}?else?{
????????j?:=?(nth?-?1)?/?(len?*?offset)
????????cur?:=?0
????????if?offset?==?all?{
????????????cur?=?1
????????}
????????cur?+=?j
????????return?number(cur*(all/offset)+path,?len,?offset/10,?all,?nth-j*len*offset)
????}
}

func?main()?{
????n?:=?11
????digit?:=?findNthDigit(n)
????println(n,?"th?digit?is",?digit)
}

在這里插入圖片描述

rust完整代碼如下：

static?mut?UNDER:?[i64;?11]?=?[
????0,
????9,
????189,
????2889,
????38889,
????488889,
????5888889,
????68888889,
????788888889,
????8888888889,
????98888888889,
];
static?mut?HELP:?[i32;?11]?=?[
????0,?1,?10,?100,?1000,?10000,?100000,?1000000,?10000000,?100000000,?1000000000,
];

fn?find_nth_digit(n:?i32)?->?i32?{
????let?under:?&[i64;?11];
????let?help:?&[i32;?11];
????unsafe?{
????????under?=?&UNDER;
????????help?=?&HELP;
????}

????let?mut?len?=?0;
????for?i?in?1..under.len()?{
????????if?under[i]?>=?n?as?i64?{
????????????len?=?i;
????????????break;
????????}
????}

????number(0,?len,?help[len],?help[len],?(n?-?under[len?-?1]?as?i32))
}

//?path?:?路徑?左(低)?<-?右(高)
//?len?:?n?->?5位數(shù)?len?=?5?固定！
//?offset?:?10000?目前要決定的是高1位
//?1000?目前要決定的是高2位
//?10?目前要決定的是高2位
//?可變
//?all?:?10000?固定
//?nth?:?第幾個
fn?number(path:?i32,?len:?usize,?offset:?i32,?all:?i32,?nth:?i32)?->?i32?{
????let?help:?&[i32;?11];
????unsafe?{
????????help?=?&HELP;
????}

????if?offset?==?0?{
????????return?(path?/?help[nth?as?usize])?%?10;
????}?else?{
????????let?j?=?(nth?-?1)?/?(len?as?i32?*?offset);
????????let?cur?=?if?offset?==?all?{?1?}?else?{?0?}?+?j;
????????return?number(
????????????cur?*?(all?/?offset)?+?path,
????????????len,
????????????offset?/?10,
????????????all,
????????????nth?-?j?*?len?as?i32?*?offset,
????????);
????}
}

fn?main()?{
????unsafe?{
????????let?n?=?11;
????????let?digit?=?find_nth_digit(n);
????????println!("{}th?digit?is?{}",?n,?digit);
????}
}

在這里插入圖片描述

c完整代碼如下：

#include?<stdio.h>

const?long?under[]?=?{
????0L,?????//?0位數(shù)，一共能解決幾個位
????9L,?????//?1位數(shù)，一共能解決幾個位
????189L,???//?1~2位數(shù)，一共能解決幾個位
????2889L,??//?1~3位數(shù)，一共能解決幾個位
????38889L,
????488889L,
????5888889L,
????68888889L,
????788888889L,
????8888888889L,
????98888888889L
};

const?int?help[]?=?{
????0,
????1,??????//?1
????10,?????//?2
????100,????//?3
????1000,???//?4
????10000,
????100000,
????1000000,
????10000000,
????100000000,
????1000000000
};

int?findNthDigit(int?n)?{
????int?len?=?0;
????for?(int?i?=?1;?i?<?sizeof(under)?/?sizeof(long);?i++)?{
????????if?(under[i]?>=?n)?{
????????????len?=?i;
????????????break;
????????}
????}
????return?number(0,?len,?help[len],?help[len],?n?-?under[len?-?1]);
}

//?path?:?路徑?左(低)?<-?右(高)
//?len?:?n?->?5位數(shù)?len?=?5?固定！
//?offset?:?10000?目前要決定的是高1位
//?1000?目前要決定的是高2位
//?10?目前要決定的是高2位
//?可變
//?all?:?10000?固定
//?nth?:?第幾個
int?number(int?path,?int?len,?int?offset,?int?all,?int?nth)?{
????if?(offset?==?0)?{
????????return?(path?/?help[nth])?%?10;
????}
????else?{
????????int?j?=?(nth?-?1)?/?(len?*?offset);
????????int?cur?=?(offset?==?all???1?:?0)?+?j;
????????return?number(cur?*?(all?/?offset)?+?path,?len,?offset?/?10,?all,?nth?-?j?*?len?*?offset);
????}
}

int?main()?{
????int?n?=?11;
????int?digit?=?findNthDigit(n);
????printf("%dth?digit?is?%d\n",?n,?digit);
????return?0;
}

在這里插入圖片描述

c++完整代碼如下：

#include?<iostream>
using?namespace?std;

const?long?under[]?=?{
????0L,?????//?0位數(shù)，一共能解決幾個位
????9L,?????//?1位數(shù)，一共能解決幾個位
????189L,???//?1~2位數(shù)，一共能解決幾個位
????2889L,??//?1~3位數(shù)，一共能解決幾個位
????38889L,
????488889L,
????5888889L,
????68888889L,
????788888889L,
????8888888889L,
????98888888889L
};

const?int?help[]?=?{
????0,
????1,??????//?1
????10,?????//?2
????100,????//?3
????1000,???//?4
????10000,
????100000,
????1000000,
????10000000,
????100000000,
????1000000000
};

//?path?:?路徑?左(低)?<-?右(高)
//?len?:?n?->?5位數(shù)?len?=?5?固定！
//?offset?:?10000?目前要決定的是高1位
//?1000?目前要決定的是高2位
//?10?目前要決定的是高2位
//?可變
//?all?:?10000?固定
//?nth?:?第幾個
int?number(int?path,?int?len,?int?offset,?int?all,?int?nth)?{
????if?(offset?==?0)?{
????????return?(path?/?help[nth])?%?10;
????}
????else?{
????????int?j?=?(nth?-?1)?/?(len?*?offset);
????????int?cur?=?(offset?==?all???1?:?0)?+?j;
????????return?number(cur?*?(all?/?offset)?+?path,?len,?offset?/?10,?all,?nth?-?j?*?len?*?offset);
????}
}

int?findNthDigit(int?n)?{
????int?len?=?0;
????for?(int?i?=?1;?i?<?sizeof(under)?/?sizeof(long);?i++)?{
????????if?(under[i]?>=?n)?{
????????????len?=?i;
????????????break;
????????}
????}
????return?number(0,?len,?help[len],?help[len],?n?-?under[len?-?1]);
}

int?main()?{
????int?n?=?11;
????int?digit?=?findNthDigit(n);
????cout?<<?n?<<?"th?digit?is?"?<<?digit?<<?endl;
????return?0;
}

在這里插入圖片描述


標簽：

2023-05-01：給你一個整數(shù) n ， 請你在無限的整數(shù)序列 [1, 2, 3, 4, 5, 6, 7, 8, 9,的評論 (共 條)

分享到微博請遵守國家法律
武宁县| 定安县| 梧州市| 南昌市| 金川县| 石林| 天峨县| 大英县| 郯城县| 宣化县| 平遥县| 萍乡市| 剑河县| 修武县| 穆棱市| 吉木萨尔县| 招远市| 汝南县| 二连浩特市| 万安县| 连江县| 五家渠市| 东兰县| 元阳县| 富阳市| 留坝县| 分宜县| 长顺县| 乌拉特前旗| 建水县| 汶川县| 沙坪坝区| 潞城市| 越西县| 宝坻区| 滨海县| 屯昌县| 大冶市| 犍为县| 柞水县| 彩票|