当前位置:网站首页>386. Dictionary order (medium) - iteration - full arrangement
386. Dictionary order (medium) - iteration - full arrangement
2022-04-23 17:33:00 【hequnwang10】
One 、 Title Description
Give you an integer n , Returns the range in dictionary order [1, n] All integers in .
You have to design a time complexity of O(n) And the use of O(1) Extra space algorithm .
Example 1:
Input :n = 13
Output :[1,10,11,12,13,2,3,4,5,6,7,8,9]
Example 2:
Input :n = 2
Output :[1,2]
Two 、 Problem solving
iteration
share n The number needs to be processed , Suppose the number of currently processed data is j, According to the dictionary order rule , On the premise that the conditions are met , Our priority is j Add 0( namely j * 10 < n Satisfy ), Otherwise, we consider fallback the previous bit and add one .
class Solution {
public List<Integer> lexicalOrder(int n) {
// iteration
List<Integer> res = new ArrayList<>();
int number = 1;
for(int i = 0;i<n;i++){
res.add(number);
// First try at number Back plus 0
if(number * 10 <= n){
number *= 10;
}else{
// If added 0 Later is greater than n 了 , Then add only one at a time 1. Of course, you also need to judge whether to carry such as 19,29,39... Reach the carry requirement and then go back to the previous bit .
while( number % 10 == 9 || number+1>n){
number /= 10;
}
number++;
}
}
return res;
}
}
Time complexity :O(n);
Spatial complexity :O(1).
版权声明
本文为[hequnwang10]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231732009048.html
边栏推荐
- RPC核心概念理解
- Summary of common SQL statements
- 2.Electron之HelloWorld
- Flash project cross domain interception and DBM database learning [Baotou cultural and creative website development]
- How does matlab draw the curve of known formula and how does excel draw the function curve image?
- Websocket (basic)
- 41. The first missing positive number
- ASP. NET CORE3. 1. Solution to login failure after identity registers users
- ClickHouse-SQL 操作
- Come out after a thousand calls
猜你喜欢
2. Electron's HelloWorld
JS, entries(), keys(), values(), some(), object Assign() traversal array usage
Qt error: /usr/bin/ld: cannot find -lGL: No such file or directory
Future 用法详解
For the space occupation of the software, please refer to the installation directory
102. 二叉树的层序遍历
ASP. Net core JWT certification
. net type transfer
Clickhouse table engine
Collection of common SQL statements
随机推荐
Node template engine (EJS, art template)
How to use the input table one-way service to send (occupy less) picture files (body transmission)? FileReader built-in object involved
Understanding of RPC core concepts
Advantages and disadvantages of several note taking software
If you start from zero according to the frame
Qt 修改UI没有生效
Basic case of Baidu map
C dapper basically uses addition, deletion, modification and query transactions, etc
[二叉数] 二叉树的最大深度+N叉树的最大深度
[simple understanding of database]
48. 旋转图像
Use of Shell sort command
EF core in ASP Generate core priority database based on net entity model
How to change input into text
tidb-server 的配置文件在哪里?
PC电脑使用无线网卡连接上手机热点,为什么不能上网
开期货,开户云安全还是相信期货公司的软件?
matlab如何绘制已知公式的曲线图,Excel怎么绘制函数曲线图像?
Indexes and views in MySQL
常用SQL语句总结