杨辉三角的变形_

Java

无梦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)

Java

黑客永不服输

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)

Java

牛客700990974号

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)

Java

徐墨耀

就是一个找规律的题目，如果模仿杨辉三角就是会导致运行时间超出限制。

下面这段代码是模拟杨辉三角，然后去寻找偶数，但是测试用例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)

Java

Kili_66

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)

Java

Fox_man

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)

Java

zzloveyou

这种解*** 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 回复(3)

Java

、前

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)

Java

UnYee

/*其实就是个找规律题*/

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");
}
}
}

发表于 2022-08-30 16:39:03 回复(0)

Java

牛客200498065号

被骗惨了，老老实实构造了个杨辉三角，结果内存吵了（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)

Java

醉饮荷风

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;
}
}
}

发表于 2022-06-11 16:59:32 回复(0)

Java

牛客209430515号

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);
    }
}

发表于 2022-06-01 09:57:23 回复(0)

Java

gwyn1

找规律

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)

Java

M870RushB

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)

Java

godjoke

这道题有意义吗？？？？？？

class Solution {

    int iTemp;
    public int solve(int row) {
        this.iTemp = row;
        if (iTemp > 2) {
            if ((iTemp - 1) % 2 == 0) {
                return 2;
            } else if (iTemp % 4 == 0) {
                return 3;
            } else {
                return 4;
            }
        } else {
            return -1;
        }
    }
}

发表于 2022-03-04 16:04:04 回复(0)

Java

牛客190869186号

原来是要用打表法，耽误了。。。

发表于 2022-02-28 22:56:25 回复(0)

Java

区嘛黑

感觉这样搞到底，把最后一行算出来再去找应该是大多数解法才对，为啥测试用例会安排那么大一个值呢，这个测试用例是否不合理

private static int getRes(int row) {

int[][] yanghui = new int[row][row];
for (int i = 0;i < row;i++){
for (int j = 0; j< row; j++){
if ((i==0 && j==0 ) || (i==1 && j==0)|| (i==1 && j==1)|| (i==1 && j==2)) {
yanghui[i][j] = 1;
}
if (i>1 && j==0){
yanghui[i][j] = 1;
}
if (i>1 && j==1){
yanghui[i][j] = i;
}
if (i>1 && j>1){
yanghui[i][j] = yanghui[i-1][j-2]+yanghui[i-1][j-1] + yanghui[i-1][j];
}
if (i == row-1 && yanghui[i][j]%2 == 0){
return j+1;
}
}
}
return -1;
}

发表于 2022-01-04 22:06:11 回复(0)

Java

陌路201811271113739

自测运行通过，但是提交的时候堆内存溢出了，实在是提交的测试数据太大了啊，搞不出来来那么大的内存

最老实的办法，构建数组，找规律什么的感觉就不符合本题的考点了；；；；；

讨论区的答案，除了找规律的都试过了，全都堆内存溢出= =

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            if(n <= 2){
                System.out.println(-1);
            }
            if(n > 2){
                int[][] yanghui = new int[n][2 * n - 1];
                for(int i = 0; i < n; i++){
                    for(int j = 0; j < (2 * n - 1); j++){
                        if(i == 0){
                            if(j == (n - 1)) yanghui[i][j] = 1;
                            else yanghui[i][j] = 0;
                        }
                        else{
                            if(j == 0){
                                yanghui[i][j] = yanghui[i - 1][j] + yanghui[i - 1][j + 1];
                            }
                            else if(j == (2 * n-2)){
                                yanghui[i][j] = yanghui[i - 1][j - 1] + yanghui[i - 1][j];
                            }
                            else{
                                yanghui[i][j] = yanghui[i - 1][j - 1] + yanghui[i - 1][j] + yanghui[i - 1][j + 1];
                            }
                        }
                    }
                }
                for(int i = 0; i < (2 * n - 1); i++){
                    if(yanghui[n - 1][i] % 2 == 0){
                        System.out.println(i + 1);
                        break;
                    }
                    if(i == (2 * n - 1)){
                        System.out.println(-1);
                    }
                }
            }
        }
    }
}

发表于 2022-01-02 23:01:14 回复(1)

Java

牛客916367296号

import java.util.Scanner; /**  * 杨辉三角  * 解题思路：用二维数组存储数据，内存问题这里只创建两行数据（不知道为什么，还是内存溢出）  */ public class Test01 { public static void main(String[] args) {
        Scanner scan = new Scanner(System.in); while (scan.hasNext()) {
            Integer input = Integer.valueOf(scan.nextLine());
            Integer output = getOut(input);
            System.out.println(output);
        }
    } private static Integer getOut(Integer input) { int[][] arr = new int[2][input * 2 - 1]; // 内存占用，缩短行数为两行  arr[0][input - 1] = 1; for (int i = 2; i <= input; i++) {
            arr[1][input - i] = 1;
            arr[1][input + i - 2] = 1; for (int j = i; j > 1; j--) {
                arr[1][input - j + 1] = arr[0][input - j] + arr[0][input - j + 1] + arr[0][input - j + 2];
                arr[1][input + j - 3] = arr[0][input + j - 4] + arr[0][input + j - 3] + arr[0][input + j - 2];
            } // 将第二行数据复制到第一行  System.arraycopy(arr[1], 0, arr[0], 0, input * 2 - 1);
        } if (input == 1) { return getIndex(arr[0]);
        } return getIndex(arr[1]);
    } private static Integer getIndex(int[] row) { for (int i = 0; i < row.length / 2 + 1; i++) { if (row[i] != 0 && row[i] % 2 == 0) { return i + 1;
            }
        } return -1;
    }
}

发表于 2021-12-22 14:51:43 回复(0)

Java

奥因克

找规律

import java.util.Scanner;
public class Main {
    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);
            }else{
                if((n+1)%4==0){
                    System.out.println(2);
                }else if((n+1)%4==1){
                    System.out.println(3);
                }else if((n+1)%4==2){
                    System.out.println(2);
                }else if((n+1)%4==3){
                    System.out.println(4);
                }
            }
        }
    }
}

发表于 2021-12-04 21:40:58 回复(0)

杨辉三角的变形

输入描述:

输出描述:

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题