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;
当圆有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]); } } }