牛牛很喜欢在数字序列中跳跃，每次可以向后跳一步或跳到往后任意一个与该位置数字相同的位置，问最少几次跳到尾部。提示：小数据量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) 回帖