以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数、左上角数和右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。
求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3，输入2则输出-1。
数据范围：
[编程题]杨辉三角的变形
import java.util.Scanner;
// n 1 2 3 4 5 6 7 8 9 10 11 ……
//index -1 -1 2 3 2 4 2 3 2 4 2 ……
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int a = in.nextInt();
if ( a <= 2) {// 1 2
System.out.println(-1);
} else if (a % 4 == 0) {// 4 8
System.out.println(3);
} else if (a % 4 == 1 || a % 4 == 3) { // 3 5 7 9 11
System.out.println(2);
} else if (a % 4 == 2) {// 6 10
System.out.println(4);
}
}
}
}
发表于 2024-09-12 15:51:13
回复(0)
投机取巧
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int a = in.nextInt();
if(a <= 2){
System.out.println(-1);
}else if(a % 2 == 1){
System.out.println(2);
}else if(a % 4 == 0){
System.out.println(3);
}else{
System.out.println(4);
}
}
}
发表于 2024-08-21 11:35:24
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int row = in.nextInt();
if (row == 1 || row == 2){
System.out.println(-1);
}else if ((row & 1) == 1){//奇数
System.out.println(2);
}else if ((row & 2) == 2){//偶数但不是4的倍数
System.out.println(4);
}else
System.out.println(3);//4的倍数
}
}
发表于 2024-07-07 11:24:59
回复(0)
这可是简单题，都在找规律……
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int a = in.nextInt();
if (a < 3) {
System.out.println("-1");
return;
}
if((a & 1) == 1) {
System.out.println("2");
return;
}
if((a & 2) == 2) {
System.out.println("4");
return;
}
System.out.println("3");
return;
}
}
}
发表于 2024-06-29 12:02:58
回复(0)
尝试过两轮无果：
1、构造n行的二维数组存储，但那个10000行的用例会OOM。
2、递归表达(i,j)位置的数，只求第n行的每个数，找到偶数为止。但因为方法递归到底还是等于在栈空间中构造了一遍完整的三角，要么超时要么栈溢出。
3、换个思路，题目只关心是不是偶数，又没说要求算出来，于是找规律，3分钟找到了... O(1)算法秒杀。
发表于 2024-06-17 11:28:06
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int length = in.nextInt();
if(length<=2){
System.out.println("-1");
}else if(length%2 == 1){
System.out.println("2");
}else{
if((length/2)%2==0){
System.out.println("3");
}else{
System.out.println("4");
}
}
}
}
发表于 2024-06-04 10:15:15
回复(0)
可以跑通用例，但其实并不符合要求。暴力破解的，虽然没有oom，有个异常值是手动推导的：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int len = in.nextInt();
if (len > 2 && len % 2 == 1) {
System.out.println(2) ;
return;
}
if (len > 500) {
System.out.println(3) ;
return;
}
int[] old = new int[1];
int[] ne = new int[1];
ne[0] = 1;
//组织树
for (int i = 2; i <= len; i++) {
old = ne;
ne = new int[i * 2 - 1];
for (int j = 0; j < ne.length; j++) {
int s1 = j - 2;
int s2 = j - 1;
int s3 = j;
int sum = 0;
if (s1 >= 0 && s1 <= old.length - 1) {
sum = sum + old[s1];
}
if (s2 >= 0 && s2 <= old.length - 1) {
sum = sum + old[s2];
}
if (s3 >= 0 && s3 <= old.length - 1) {
sum = sum + old[s3];
}
if (i > 0) {
// System.out.print(sum + " ") ;
}
ne[j] = sum;
}
if (i > 0) {
// System.out.println("") ;
}
}
for (int i = 0; i < ne.length; i++) {
if (ne[i] % 2 == 0) {
System.out.println(i + 1) ;
return;
}
}
System.out.println(-1) ;
}
}
编辑于 2024-04-08 15:02:58
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int a = in.nextInt();
int[] wb = function(a);
boolean find = false;
for (int i = 0; i < wb.length; i++) {
if (wb[i] % 2 == 0) {
System.out.println(i + 1);
find = true;
break;
}
}
if (find == false) {
System.out.println(-1);
}
}
}
private static int[] function(int a) {
if (a == 1) {
return new int[]{1};
} else if (a == 2) {
return new int[]{1, 1};
}
else if(a==3){
return new int[]{1,2,3};
}else {
int t = (2 * a - 1) / 2 + 1;
int[] res = new int[t];
int[] arr = function(a - 1);
for (int i = 0; i < res.length; i++) {
if (i == 0) {
res[i] = 1;
} else if (i == 1) {
res[i] = arr[0] + arr[1];
} else if (i == res.length-1) {
res[i] = arr[i - 2] * 2 + arr[i - 1];
} else {
res[i] = arr[i - 2] + arr[i - 1] + arr[i];
}
}
return res;
}
}
}我本地编译没问题，但是为什么在OJ系统里面说我OutOfMemoryError: Java heap space了
编辑于 2024-03-29 13:56:14
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
// 1
// 1 1 1
// 1 2 3 2 1
// 1 3 6 7 6 3 1
// 1 4 10 16 19 16 10 4 1
// 会超时
// int lineNum = in.nextInt();
// if (lineNum < 3) {
// System.out.println(-1);
// continue;
// }
// List<Integer> rowList = new ArrayList<Integer>();
// List<Integer> preRowList = new ArrayList<Integer>();
// preRowList.add(1);
// for (int row = 1; row < lineNum; row++) {
// rowList.add(1);
// for (int col = 1; col < row * 3 + 1; col++) {
// int num = 0;
// num += col - 2 >= 0 && col - 2 < preRowList.size() ? preRowList.get(col - 2) :0;
// num += col - 1 >= 0 && col - 1 < preRowList.size() ? preRowList.get(col - 1) :0;
// num += col >= 0 && col < preRowList.size() ? preRowList.get(col) :0;
// rowList.add(col, num);
// if (row == lineNum - 1 && (num & 1) == 0) {
// System.out.println(col + 1);
// break;
// }
// }
// preRowList = rowList;
// rowList = new ArrayList<>();
// }
// 找规律
// 1 2 3 4 5 6 7 8 9 10 11 12
// -1 -1 2 3 2 4 2 3 2 4 2 3
int lineNum = in.nextInt();
if (lineNum < 3) {
System.out.println(-1);
continue;
}
if ((lineNum & 1) == 1) // 奇数
System.out.println(2);
else if (lineNum % 4 == 0) // 4的倍数
System.out.println(3);
else
System.out.println(4); // 偶数但不是4的倍数
}
}
}
发表于 2023-12-11 14:40:04
回复(0)
就是一个找规律的题目，如果模仿杨辉三角就是会导致运行时间超出限制。
下面这段代码是模拟杨辉三角，然后去寻找偶数，但是测试用例10000会超时。
import java.util.ArrayList;
import java.util.Scanner;
public class T53 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNextInt()) {
int n = sc.nextInt();
if (n <= 2) {
System.out.println("-1");
return;
}
if (n % 2 != 0) {
System.out.println("2");
return;
}
int flag = 3;
ArrayList<Integer> reference = new ArrayList<>();
reference.add(1);
reference.add(2);
reference.add(3);
reference.add(2);
reference.add(1);
while (true) {
ArrayList<Integer> current = new ArrayList<>();
int length = 2 * (flag+1) - 1;
//对当前行数据生成
for (int i = 1; i <= length; i++) {
if (i == 1 || i == length) {
current.add(1);
continue;
}
if (i == 2) {
current.add(reference.get(0) + reference.get(1));
continue;
}
if (i == length - 1) {
current.add(reference.get(reference.size() - 1) + reference.get(reference.size() - 2));
continue;
}
current.add(reference.get(i - 3) + reference.get(i - 2) + reference.get(i - 1));
}
reference = current;
flag++;
if (flag == n) {
break;
}
}
for (int i = 0; i < reference.size(); i++) {
if (reference.get(i) % 2 == 0) {
System.out.println(i + 1);
return;
}
}
}
}
}
发表于 2023-11-29 14:59:44
回复(0)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int [] m = {2, 3, 2, 4};
System.out.println(n >= 3 ? m[(n - 3) % 4] : -1);
}
}
发表于 2023-11-25 15:21:06
回复(1)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
//方法1；直接开辟二维数组进行赋值遍历，超内存且超时
public static int solve(int n){
int m = 2*n-1;
int[][] arr = new int[n][m];
//初始化第一层(因为int型默认值为0，所以为赋值的地方就为0)
arr[0][m/2] = 1;
int left=0;
int right=0;
int up=0;
//开始遍历
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
if(j-1 >= 0){
left = arr[i-1][j-1];
}
if(j+1<m){
right = arr[i-1][j+1];
}
up = arr[i-1][j];
arr[i][j] = left+up+right;
}
left = up = right = 0;
}
for(int j=0;j<m;j++){
if(arr[n-1][j]%2==0)
return j+1;
}
return -1;
}
//方法2：开辟两个一维数组，交替遍历赋值，不超内存，但超时
public static int solve2(int n){
int m = 2*n-1;
int[] pre = new int[m];
int[] now = new int[m];
int[] tmp;
//初始化第一层
pre[m/2] = 1;
int left=0;
int right=0;
int up=0;
//开始循环赋值，
for(int i=1;i<n;i++){
for(int j=0;j<m;j++){
if(j-1>=0){
left = pre[j-1];
}
if(j+1<m){
right = pre[j+1];
}
up = pre[j];
now[j] = left+up+right;
}
left = up = right = 0;
//交换上下层
tmp = now;
now = pre;
pre = tmp;
}
//最后一层遍历赋值之后，由于交换了引用，最后一层其实在pre上
for(int j=0;j<m;j++){
if(pre[j]%2==0)
return j+1;
}
return -1;
}
//方法3：寻找规律，可以发现，从第3行开始，偶数出现的位置依次为 2,3,2,4
//且这个规律呈现周期性，即从第7行开始，偶数出现的位置也依次是：2，3，2，4，故可以直接计算
public static int solve3(int n){
if(n==1 || n==2){
return -1;
}
if(n%4==3 || n%4==1){
return 2;
}
if(n%4==0){
return 3;
}
if(n%4==2){
return 4;
}
return -1;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
System.out.println(solve3(n));
}
}
}
发表于 2023-03-05 14:33:06
回复(0)
这种解*** n = 10000时 会导致OOM 如何优化？
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNextInt()) {
int N = in.nextInt();
int[][] dp = new int[N + 1][2 * N];
dp[1][1] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= 2 * N - 1; j++) {
for (int k = j - 2; k <= j; k++) {
if (k < 1 || k > (2 * (i - 1) - 1)) {
continue;
}
dp[i][j] += dp[i - 1][k];
}
}
}
int ans = -1;
for (int m = 1; m <= 2 * N - 1; m++) {
if (dp[N][m] % 2 == 0) {
ans = m;
break;
}
}
System.out.println(ans);
}
}
}
发表于 2023-02-05 01:53:48
回复(4)
oom了，不按出题人想的找规律就不行，感觉构建完整的杨辉三角难度大些
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
int n = in.nextInt();
int[][] arrray = new int[n][2*n-1];
for(int i=0;i<n;i++){
arrray[i][0] = 1;
}
for(int i = 1;i<n;i++){
for(int j=1;j<(2*(i+1)-1);j++){
if(j==1){
arrray[i][j]=0+1+arrray[i-1][j];
}else if(j>=2){
arrray[i][j]=arrray[i-1][j-2]+arrray[i-1][j-1]+arrray[i-1][j];
}
}
}
int flag = -1;
for(int i = 0;i<2*n-1;i++){
if(arrray[n-1][i]%2==0){
flag=i+1;
break;
}
}
System.out.print(flag);
}
}
// 1
// 1 1 1
// 1 2 3 2 1
// 1 3 6 7 6 3 1
// a[i][j]=a[i-1][j-2]+a[i-1][j-1]+a[i-1][j]
// 2n-1
发表于 2023-01-07 21:14:28
回复(2)
/*其实就是个找规律题*/
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
if(n>=3){
if((n-1)%2==0){
System.out.print("2");
}else{
if(n%4==0){
System.out.print("3");
}else{
System.out.print("4");
}
}
}else{
System.out.print("-1");
}
}
}
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n=sc.nextInt();
if(n>=3){
if((n-1)%2==0){
System.out.print("2");
}else{
if(n%4==0){
System.out.print("3");
}else{
System.out.print("4");
}
}
}else{
System.out.print("-1");
}
}
}
发表于 2022-08-30 16:39:03
回复(0)
被骗惨了，老老实实构造了个杨辉三角，结果内存吵了（OOM）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String str = reader.readLine();
int n = Integer.parseInt(str);
int[][] arr = new int[n][(2 * n) - 1];
for(int i = 0; i < n; i++){
if(i == 0){
arr[i][n - 1] = 1;
continue;
}
if(i == n - 1){
arr[i][0] = 1;
arr[i][2 * i] = 1;
}
for(int k = 1; k <= 2 * n - 3; k++){
arr[i][k] = arr[i - 1][k - 1] + arr[i - 1][k] + arr[i - 1][k + 1];
}
}
for (int i = 0; i < arr[n - 1].length; i++) {
if(arr[n - 1][i] % 2 == 0) {
System.out.println(i + 1);
return;
}
}
System.out.println(-1);
}
}
发表于 2022-08-14 23:38:34
回复(2)
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
if (num == 1 || num == 2) {
System.out.println(-1);
return;
} else if (num % 4 == 1 || num % 4 == 3) {
System.out.println(2);
return;
} else if (num % 4 == 0) {
System.out.println(3);
return;
} else if (num % 4 == 2) {
System.out.println(4);
return;
}
}
}
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int num = in.nextInt();
if (num == 1 || num == 2) {
System.out.println(-1);
return;
} else if (num % 4 == 1 || num % 4 == 3) {
System.out.println(2);
return;
} else if (num % 4 == 0) {
System.out.println(3);
return;
} else if (num % 4 == 2) {
System.out.println(4);
return;
}
}
}
发表于 2022-06-11 16:59:32
回复(0)
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int result = -1;
if (num > 2) {
int[] mod = {4, 2, 3, 2};
result = mod[(num - 2) % 4];
}
System.out.println(result);
}
}
public class Main {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
int result = -1;
if (num > 2) {
int[] mod = {4, 2, 3, 2};
result = mod[(num - 2) % 4];
}
System.out.println(result);
}
}
发表于 2022-06-01 09:57:23
回复(0)
找规律
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
if(n <= 2){
System.out.print("-1");
}else if(n % 4 == 1 || n % 4 == 3){
System.out.print("2");
}else if(n % 4 == 0){
System.out.print("3");
}else if(n % 4 == 2){
System.out.print("4");
}
}
}
发表于 2022-05-30 20:37:27
回复(0)
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int num = sc.nextInt();
System.out.println(res(num));
}
public static int res(int num){
if(num == 1 || num == 2){
return -1;
}
num -= 2;
if(num%2 == 1){
return 2;
}
if(num%2 == 0 && num%4 != 0){
return 3;
}
if(num%2 == 0 && num%4 == 0){
return 4;
}
return 0;
}
} 找规律
发表于 2022-04-21 10:38:54
回复(0)
问题信息
难度：
47条回答
1888收藏
33177浏览
通过挑战的用户
查看代码-
2023-01-08 10:48:50 -
2022-11-05 18:25:40 -
2022-10-29 22:21:04
-
2022-10-28 23:55:58 -
2022-10-28 13:54:48
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
