Java算法---华为oj挑7

时间:2021-11-09 13:37:01

题目描述:

输出7有关数字的个数,包括7的倍数,还有包含7的数字(如17,27,37...70,71,72,73...)的个数 

输入描述:

一个正整数N。(N不大于30000)

输出描述:

不大于N的与7有关的数字个数,例如输入20,与7有关的数字包括7,14,17.

  这个题其实也不难,但是主要是考虑时间复杂度,纯属编码技巧,最笨的方法是每次来一个数N ,然后统计1-N之间与“7”相关的个数,但是这就存在一个问题,如果每次的数不一样,而且非常大的话,肯定会超时。而且会重复的计算。可以换个思路,原题中给定了N的范围,我们可以开辟一个30000的数组,先将30000中每一个数之前所有与“7”相关的个数保存起来,最后我们只是输出给定数字对于数组中的值即可。其实也是利用了动态规划的思想。

  可以这样实现,判断当前值是否与“7”相关,如果相关dp[i]=dp[i]+1;否则dp[i]=dp[i-1];这样每次我们只需要计算当前值是否与“7”相关,然后加上之前与“7”相关的个数。

<span style="font-size:18px;">for (int i = 8; i < save.length; i++) {
if (String.valueOf(i).contains("7") && i % 7 == 0) {
save[i] = save[i - 1] + 1;
} else if (i % 7 == 0) {
save[i] = save[i - 1] + 1;
} else if (String.valueOf(i).contains("7")) {
save[i] = save[i - 1] + 1;
}else {
save[i] = save[i - 1];
}
}</span>
  这里要注意的是,在写程序时,将计算这一部分写在死循环前面,这样每次执行程序只需要执行一个30000个数字的计算,然后针对测试用例,只是输出对应的数组值,即可。下面贴上全部代码:
<span style="font-size:18px;">import java.util.Scanner;public class Main {    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int[] save = new int[30000];        save[7] = 1;            for (int i = 8; i < save.length; i++) {                if (String.valueOf(i).contains("7") && i % 7 == 0) {                    save[i] = save[i - 1] + 1;                } else if (i % 7 == 0) {                    save[i] = save[i - 1] + 1;                } else if (String.valueOf(i).contains("7")) {                    save[i] = save[i - 1] + 1;                }else {                    save[i] = save[i - 1];                }            }            while (sc.hasNext()) {                int n = sc.nextInt();                System.out.println(save[n]);            }        }    }</span>
   其实这个对参加竞赛可能会有用处,大大减少运算的时间。