题解 | #游游的整数切割#
游游的整数切割
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个切割点。
- 空间复杂度：
，只使用了常数级别的额外空间。
看哭了，恋爱那一段你女朋友说你不够关心她，可你毕竟也愿意遇到矛盾写几千字来和她慢慢分析；说不愿意给她花钱，我感觉可能只是消费观不一样；如果她想留在长沙，也应该提前跟你说开。不过她也许会心疼你放弃大厂offer转向数字马力？我也因为同样的原因有过一段幸福而充满遗憾的感情，不过跟爱情相比确实前途更重要一点。至于offer的选择，换我我也会这么选。把这些旧事记录下来以后，接下来就好好向前看吧，加油兄弟