题解 | #游游的整数切割#
游游的整数切割
https://www.nowcoder.com/practice/c01b07fe9623425a806c85cdb6f0e0f7
解题思路
给定一个正整数，需要将其切割成两部分，使得这两部分的和为偶数。
要求统计所有可能的切割方案数。
关键发现：
-
一个数被切割成两部分后，这两部分的和是否为偶数，只与这两个数的个位数有关
- 例如：123456 切割成 12 和 3456
- 实际上只需要判断 2 + 6 的和是否为偶数
- 因为其他位数对最终和的奇偶性没有影响
-
对于任意切割点：
- 左边部分的个位就是切割点左边的数字
- 右边部分的个位就是原始数字的最后一位
- 只需要判断这两个数字之和是否为偶数
举例： 输入：12345
- 切割点1：1|2345，判断1+5是否为偶数
- 切割点2：12|345，判断2+5是否为偶数
- 切割点3：123|45，判断3+5是否为偶数
- 切割点4：1234|5，判断4+5是否为偶数
这样的方法避免了处理大数，也不需要考虑前导零的问题，因为前导零不会影响个位数的值。
代码
#include <iostream>
#include <string>
using namespace std;
int countValidSplits(string& num) {
int count = 0;
int n = num.length();
for(int i = 1; i < n; i++) {
// 只需要获取左右两部分的最后一位数字
int leftLastDigit = num[i-1] - '0';
int rightLastDigit = num[n-1] - '0';
// 判断两个数字之和是否为偶数
if((leftLastDigit + rightLastDigit) % 2 == 0) {
count++;
}
}
return count;
}
int main() {
string num;
cin >> num;
cout << countValidSplits(num) << endl;
return 0;
}
import java.util.Scanner;
public class Main {
public static int countValidSplits(String num) {
int count = 0;
int n = num.length();
for(int i = 1; i < n; i++) {
// 只需要获取左右两部分的最后一位数字
int leftLastDigit = num.charAt(i-1) - '0';
int rightLastDigit = num.charAt(n-1) - '0';
// 判断两个数字之和是否为偶数
if((leftLastDigit + rightLastDigit) % 2 == 0) {
count++;
}
}
return count;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String num = sc.next();
System.out.println(countValidSplits(num));
sc.close();
}
}
def count_valid_splits(num):
count = 0
n = len(num)
for i in range(1, n):
# 只需要获取左右两部分的最后一位数字
left_last_digit = int(num[i-1])
right_last_digit = int(num[-1])
# 判断两个数字之和是否为偶数
if (left_last_digit + right_last_digit) % 2 == 0:
count += 1
return count
if __name__ == "__main__":
num = input()
print(count_valid_splits(num))
算法及复杂度
- 算法：数学。利用数字和的奇偶性质，只需要判断个位数之和的奇偶性。
- 时间复杂度：
，其中n是输入数字的位数，需要遍历n-1个切割点。
- 空间复杂度：
，只使用了常数级别的额外空间。
投递建信金科等公司9个岗位 >
