【Java版oj 】 day17杨辉三角形的变形、计算某字符出现次数
目录
一、杨辉三角形的变形
(1)原题再现
(2)问题分析
(3)完整代码
二、计算某字符出现次数
(1)原题再现
(2)问题分析
(3)完整代码
一、杨辉三角形的变形
(1)原题再现
杨辉三角的变形_牛客题霸_牛客网
描述
以上三角形的数阵,第一行只有一个数1,以下每行的每个数,是恰好是它上面的数、左上角数和右上角的数,3个数之和(如果不存在某个数,认为该数就是0)。
求第n行第一个偶数出现的位置。如果没有偶数,则输出-1。例如输入3,则输出2,输入4则输出3,输入2则输出-1。
输入描述:
输入一个int整数
输出描述:
输出返回的int值
示例1
输入:
4
输出:
3
(2)问题分析
本题第一次写的时候可能会被误解,以为要写出杨辉三角形求解,这是一个方法,但是会超出时间限制。其实这套题本质上是一道数学找规律题,我们多列出几行三角矩阵,观察出现第一个偶数的下标,不难发现第一二行是没有偶数的,从第三行往后开始偶数出现的下标按照2,3,2,4的规律。
最后我也会附上一个构建杨辉三角形的求解方法。
(3)完整代码
import java.util.*; public class Main {public static void main(String[] args) {Scanner sc = new Scanner (System.in);int n = sc.nextInt();if (n == 1 || n == 2) {System.out.println(-1);} else if (n % 4 == 0) {System.out.println(3);} else if (n % 4 == 2) {System.out.println(4);} else {System.out.println(2);}} }
构建杨辉三角形
public static void main(String[] args) {Scanner sc=new Scanner (System.in);int n=sc.nextInt();int bino[][]=new int [n][2*n-1];createBion(bino, n);int i=0;for(i=0;i<2*n-1;i++) {if(bino[n-1][i]%2==0) {System.out.println(i+1);break;}}if(i==2*n-1) {System.out.println(-1);}}public static void createBion(int [][]bino,int n) {int row=n;int col=2*n-1;for (int i = 0; i <row; i++) {for (int j = 0; j <col; j++) {if(j==n-i-1) {bino[i][j]=1;}if(j==n+i-1) {bino[i][j]=1;} } }for (int i = 1; i <row; i++) {for (int j = 0; j <col; j++) {if(j>n-i-1&&j<n+i-1) {bino[i][j]=bino[i-1][j-1]+bino[i-1][j]+bino[i-1][j+1];} } }
二、计算某字符出现次数
(1)原题再现
计算某字符出现次数_牛客题霸_牛客网
描述
写出一个程序,接受一个由字母、数字和空格组成的字符串,和一个字符,然后输出输入字符串中该字符的出现次数。(不区分大小写字母)
输入描述:
第一行输入一个由字母、数字和空格组成的字符串,第二行输入一个字符(保证该字符不为空格)。
输出描述:
输出输入字符串中含有该字符的个数。(不区分大小写字母)
示例1
输入:
ABCabc
A
输出:
2
(2)问题分析
很显然我们可以使用一个map容器将出现的字符(不区分大小写)作为key关键词,将某个字符出现的次数作为value值。
核心部分:如果map集合里曾经没有出现过,就将该字符加入集合中,值为1。如果曾经出现过,就在原来的值上加1。最后分情况讨论一下,区分字母和数字。字母查找两次,大写加小写,数字和其他字符大小写是一样的,只要加一次就够了。当然可以在一开始的时候,就进行大小写转换,那被查找的字符也要进行大小写转换。我这里写的可能有点复杂了
(3)完整代码
import java.util.*; public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();String c = sc.nextLine();Map <Character, Integer> map = new HashMap<>();int count = 1;for (int i = 0; i < str.length(); i++) {if (!map.containsKey(str.charAt(i))) {count = 1;map.put(str.charAt(i), count);} else {count = map.get(str.charAt(i));map.put(str.charAt(i), count + 1);}}char samllC = c.toLowerCase().charAt(0);char bigC = c.toUpperCase().charAt(0);int ans = 0;if (map.containsKey(samllC) && map.containsKey(bigC)) {if (samllC >= '0' && samllC <= '9') {ans = map.get(samllC);} else {ans = map.get(samllC) + map.get(bigC);}System.out.println(ans);} else if (map.containsKey(samllC) && !map.containsKey(bigC)) {ans = map.get(samllC);System.out.println(ans);} else if (!map.containsKey(samllC) && map.containsKey(bigC)) {ans = map.get(bigC);System.out.println(ans);} else {System.out.println(0);}} }