题解 | #数字构造#
数字构造
https://www.nowcoder.com/practice/01d7d4cc93e44330ae45b4d8b8d06619
解题思路
- 题目要求构造一个十进制数，使得：
- 数位和等于给定值
- 相邻数位不能相同
- 不能包含
- 这个数要尽可能大
- 数位和等于给定值
- 关键发现：
- 要使数尽可能大，应该使用尽可能大的数字
- 由于相邻数位不能相同，最优解应该是交替使用两个数字
- 9和8太大，无法构造出大多数
值，最优解应该使用1和2交替
- 根据
- s除以3余2：使用"21"重复，最后加"2"
代码
#include <iostream>
#include <string>
using namespace std;
int main() {
int s;
cin >> s;
string result;
if (s % 3 == 0) {
int pairs = s / 3;
for (int i = 0; i < pairs; i++) {
result += "21";
}
} else if (s % 3 == 1) {
int pairs = (s - 1) / 3;
for (int i = 0; i < pairs; i++) {
result += "12";
}
result += "1";
} else { // s % 3 == 2
int pairs = (s - 2) / 3;
for (int i = 0; i < pairs; i++) {
result += "21";
}
result += "2";
}
cout << result << endl;
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int s = sc.nextInt();
StringBuilder result = new StringBuilder();
if (s % 3 == 0) {
int pairs = s / 3;
for (int i = 0; i < pairs; i++) {
result.append("21");
}
} else if (s % 3 == 1) {
int pairs = (s - 1) / 3;
for (int i = 0; i < pairs; i++) {
result.append("12");
}
result.append("1");
} else { // s % 3 == 2
int pairs = (s - 2) / 3;
for (int i = 0; i < pairs; i++) {
result.append("21");
}
result.append("2");
}
System.out.println(result);
}
}
s = int(input())
result = ""
if s % 3 == 0:
pairs = s // 3
result = "21" * pairs
elif s % 3 == 1:
pairs = (s - 1) // 3
result = "12" * pairs + "1"
else: # s % 3 == 2
pairs = (s - 2) // 3
result = "21" * pairs + "2"
print(result)
算法及复杂度
- 算法：贪心构造
- 时间复杂度：
- 需要构造长度正比于
- 空间复杂度：
投递美团等公司10个岗位 >