题解 | #杨辉三角的变形#
杨辉三角的变形
https://www.nowcoder.com/practice/8ef655edf42d4e08b44be4d777edbf43
解题思路
- 这是一个变形的杨辉三角，每个数是由它上面的数和左上角、右上角的数的和构成
- 观察规律：
- 第1行有1个数：1
- 第2行有3个数：1 1 1
- 第3行有5个数：1 2 3 2 1
- 第4行有7个数：1 3 6 7 6 3 1
- 第5行有9个数：1 4 10 16 19 16 10 4 1
- 题目要求找第一个偶数出现的位置，如果没有偶数则返回-1
- 通过仔细观察可以发现：
或
时，没有偶数，返回-1
为奇数时，第2个位置必定是偶数，返回2
- 其他情况（
代码
#include<iostream>
using namespace std;
int main() {
int num;
while (cin >> num) {
if (num == 1 || num == 2) cout << -1 << endl;
else if (num & 1) cout << 2 << endl;
else if (num % 4) cout << 4 << endl;
else cout << 3 << endl;
}
return 0;
}
import java.util.Scanner;
public class Main {
public static int findFirstEven(int n) {
if (n == 1 || n == 2) return -1;
if (n % 2 == 1) return 2;
if (n % 4 != 0) return 4;
return 3;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
System.out.println(findFirstEven(n));
}
}
}
def find_first_even(n):
if n == 1 or n == 2:
return -1
if n % 2 == 1:
return 2
if n % 4 != 0:
return 4
return 3
while True:
try:
n = int(input())
print(find_first_even(n))
except EOFError:
break
算法及复杂度
- 算法：数学规律总结
- 时间复杂度：
- 直接通过判断得到结果
- 空间复杂度：
查看30道真题和解析