首页 > 百度3.30笔试第一题:数字跳跃
头像
勇敢牛牛不怕困难~
编辑于 2021-04-05 20:11
+ 关注

百度3.30笔试第一题:数字跳跃

牛牛很喜欢在数字序列中跳跃,每次可以向后跳一步或跳到往后任意一个与该位置数字相同的位置,问最少几次跳到尾部。提示:小数据量30%,大数据量70%
我第一次的思路是:动态规划,dp[i]=min(dp[i-1],从某个相同数字跳过来的最小值)+1
从某个相同数字跳过来的最小值:用for循环,找到前n个相同数字分别跳过来的最小值
所以这个就是O(n^2)复杂度,只过了30%
public  int Find(int[] nums){
        int count=Integer.MAX_VALUE;
        //用map存 某一个数字都会在哪些地方出现
        HashMap<Integer, ArrayList<Integer>> map=new HashMap<>();
        int[] dp=new int[nums.length];
        dp[0]=0;
        ArrayList<Integer> st=new ArrayList<>();
        st.add(0);
        map.put(nums[0],st);
        for(int i=1;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                //找到每一个同数字的跳过来的最小值,这个是比较耗时的
                for(int j=0;j<map.get(nums[i]).size();j++){
                    count=Math.min(count,dp[map.get(nums[i]).get(j)]);
                }
                //再比较从前一位跳过来和从同数字跳过来的最小值
                dp[i]=Math.min(dp[i-1],count)+1;
                map.get(nums[i]).add(i);
                count=Integer.MAX_VALUE;
            }else{
                dp[i]=dp[i-1]+1;
                ArrayList<Integer> list=new ArrayList<>();
                list.add(i);
                map.put(nums[i],list);
            }
        }
        return dp[nums.length-1];
    }
然后我又优化了下代码:
思路是 新建一个map,里面存的就是到某一个数字所需的最少的步数,但是考试来不及提交了不知道这样做对不对,代码如下:
public int Find(int[] nums){
        int count=Integer.MAX_VALUE;
        HashMap<Integer, ArrayList<Integer>> map=new HashMap<>();
        //存储到每个数字需要跳的最少的步子
        HashMap<Integer,Integer> map1=new HashMap<>();
        int[] dp=new int[nums.length];
        dp[0]=0;
        ArrayList<Integer> st=new ArrayList<>();
        st.add(0);
        map.put(nums[0],st);
        map1.put(nums[0],0);
        for(int i=1;i<nums.length;i++){
            if(map.containsKey(nums[i])){
               
                dp[i]=Math.min(dp[i-1],map1.get(nums[i]))+1;
                map.get(nums[i]).add(i);
                //跳到当前这个数字的时候,判断此时的步子是否比之前存储的步数少,如果是就更新最短记录
                if(dp[i]<map1.get(nums[i])){
                    map1.put(nums[i],dp[i]);
                }
                //count=Integer.MAX_VALUE;
            }else{
                dp[i]=dp[i-1]+1;
                ArrayList<Integer> list=new ArrayList<>();
                list.add(i);
                map.put(nums[i],list);
                map1.put(nums[i],dp[i]);
            }
        }
        return dp[nums.length-1];
    }
这个方法是否能够AC呢,或者有什么好的方法吗?恳请各位指教呀~


全部评论

(4) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐