专栏首页desperate633LintCode 寻找丢失的数 II代码

LintCode 寻找丢失的数 II代码

给一个由 1 - n 的整数随机组成的一个字符串序列,其中丢失了一个整数,请找到它。

注意事项

n <= 30

样例 给出 n = 20, str = 19201234567891011121314151618

丢失的数是 17 ,返回这个数。

代码

public class Solution {
    /**
     * @param n an integer
     * @param str a string with number from 1-n
     *            in random order and miss one number
     * @return an integer
     */   
    public boolean flag = false;
    public int ans = 0;
    public int findMissing2(int n, String str) {
        boolean[] happen = new boolean[n + 1];
        dfs(0, n, str, happen);
        return ans;
    }
    
    public void dfs(int i, int n, String s, boolean[] happen) {
        if (i >= s.length() || flag) {
            if (!flag)
            for (int k = 1; k <= n; k++) {
                if (!happen[k]) {
                    ans = k;
                }
            }
            flag = true;
            return;
        }
        int sum = s.charAt(i) - '0';
        int j = i;
        if (sum == 0) {
            return;
        }
        while (sum <= n) {
            if (!happen[sum]) {
                happen[sum] = true;
                dfs(j+1, n, s, happen);
                happen[sum] = false;
            }
            j++;
            if (j >= s.length()) {
                break;
            }
            sum = sum * 10 + (s.charAt(j) - '0');
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 设计模式之装饰者模式(Decorator Pattern)问题提出引出装饰者模式定义装饰者模式实现装饰者模式总结与分析

    装饰者模式可以做到在不修改任何底层代码的情况下,给对象增加的新的方法。 首先,我们通过对一个现实问题的模拟分析,了解什么是装饰者模式以及装饰者模式的作用。

    desperate633
  • LintCode 爬楼梯题目分析代码小结

    假设你正在爬楼梯,需要n步你才能到达顶部。但每次你只能爬一步或者两步,你能有多少种不同的方法爬到楼顶部?

    desperate633
  • 设计模式之命令模式(Command Pattern)

    “行为请求者”与“行为实现者”通常呈现一种“紧耦合”。比如要对行为进行“记录、撤销/重做、事务”等处理,这种无法抵御变化的紧耦合是不合适的。在这种情况下,如何将...

    desperate633
  • Java开发GUI之GridLayout网格布局

        GridLayout是简单的网格布局,使用其可以方便的实现多行多列的布局样式。

    珲少
  • 阶段01Java基础day14常用对象03

    声明:本文为原创,作者为 对弈,转载时请保留本声明及附带文章链接:http://www.duiyi.xyz/c%e5%ae%9e%e7%8e%b0%e9%9b%...

    对弈
  • Java基础笔记14

    dreamkong
  • Java1.8新特性--方法的引用

    上面的car2::repair为什么报错?点开forEach源码你会发现它需要的参数是:Consumer<? super T> ,而对象::空参方法得到的返回值...

    Java深度编程
  • 骰子点数之和问题

    从独立概率入手可能可以更好地解决问题,因为不需要单独考虑每个点数和的概率。6个骰子,每个骰子出现1、2、3、4、5、6的概率相等且独立随机的,所以总的情况有6^...

    冰之角
  • ASP.NET Core 3.0 原生DI拓展实现IocManager

    昨天.NET Core 3.0正式发布,创建一个项目运行后发现:原来使用的Autofac在ConfigureServices返回IServiceProvider...

    梁规晓
  • Spring Security 权限控制

      这个注解支持必须卸载 MVC 的配置文件中,这是因为我们将注解加载 Controller 层上,该层由前端控制器加载,故位于 Spring Ioc 的子容器...

    Demo_Null

扫码关注云+社区

领取腾讯云代金券