25字节笔试第一第二题

两题通过率均为100%。
第一题思路:结构类似邻接表,
用例1:
3
0 4 0
4 0 0
0 0 0
对应邻接表
1->2;
3;

用例2:
3
0 4 0
4 0 6
0 6 0
对应邻接表
1->2->3;

因为矩阵的第i,i个元素为0,我用矩阵的第 i,i个元素表示是否是首元素,如果是0表示是邻接表首元素,-1则不是,首元素的个数就是输出结果;
代码如下:
package zijie;

import java.util.Scanner;
/**
 * @ClassName Main
 * @Description TODO
 * @Author Wlison
 * @Date 2019/8/25 20:11
 * @Version 1.0
 **/
public class Main01 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int n= sc.nextInt();
            int[][] matrix = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    matrix[i][j]=sc.nextInt();
                }
            }
            int res =0;
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    if(matrix[i][j]>=3){
                        //如果目标已经并入其他链表,则将本身也并入,感谢大佬指出BUG
                        if(matrix[j][j]==-1){
                            matrix[i][i]=-1;
                        }else{
                            matrix[j][j]=-1;
                        }
                    }
                }
            }
            for (int i = 0; i < n; i++) {
                if(matrix[i][i]!=-1){
                    res++;
                }
            }
            System.out.println(res);
        }
    }
}


第二题思路:
由用例知道:
当圆有2个点的时候 f(2)=1;
当圆有4个点的时候 f(4)=2;
当圆有6个点的时候 f(6)=5;
...
当圆有n个点的时候 f(n)=f(n-2)+f(n-4)*f(2)+......f(2)*f(n-4)+f(n-2);    (别问我怎么想到的,我头痛起来自己都害怕,考试的时候发烧)
代码如下:
package zijie;

import java.util.Scanner;
public class Main02 {
    public static void main(String[] args) {
        Scanner sc  = new Scanner(System.in);
        while(sc.hasNext()){
            int n = sc.nextInt();
            long[] res = new long[501];
            res[0]=1;
            res[1]=1;
            res[2]=2;
            for(int i=3;i<501;i++){
                int j=i;
                while(j!=0){
                    j--;
                    res[i]+=res[j]*res[i-1-j];
                    res[i]%=10000007;//这里忘记取多少模了
                }
            }
            System.out.println(res[n/2]);
        }
    }
}


#字节跳动##笔试题目#
全部评论
第一题并查集,第二题卡特兰数
点赞 回复
分享
发布于 2019-08-25 21:03
这两道都是100%吗?
点赞 回复
分享
发布于 2019-08-25 21:04
小红书
校招火热招聘中
官网直投
第二次我还以为 是斐波那契, A了20% 再见··~
点赞 回复
分享
发布于 2019-08-25 21:07
第二道我也想到这个了,不过把递归没时间改写成动态规划了,纯递归正确率50%
点赞 回复
分享
发布于 2019-08-25 21:08
是大于等于3吗。我条件是大于3 一直百分之90
点赞 回复
分享
发布于 2019-08-25 21:37
这个测试用例答案应该是2,但你的结果输出是3 4 0,0,0,3 0,0,0,0 0,0,0,3 3,0,3,0
点赞 回复
分享
发布于 2019-08-26 13:30

相关推荐

点赞 评论 收藏
转发
9 14 评论
分享
牛客网
牛客企业服务