【刷题】最新刷的3道题目
题目一
考虑你从家出发步行去往一处目的地，该目的地恰好离你整数单位步长（大于等于1）。
你只能朝向该目的地或者背向该目的地行走，而你行走的必须为单位步长的整数倍，且要求你第N次行走必须走N步。
请就给出目的地离你距离，判断你是否可以在有限步内到达该目的地。
如果可以到达的话，请计算到达目的地的最短总步数(不能到达则输出-1)
假设我们的目的地是s，我们需要走n步才能到达。
最理想的情况是，我们直接走n步，不需要回退就到达了。这个时候 s1 = 1+2+...+n 。
假设我们已经走了p-1步，如果直接走完p步，(1+...+p)-n = x，也就是会比目的地多x步。
如果 x 是偶数，这个时候只需要在x/2步的时候回退。因为 (1+...+x/2+...+p) - (1+...-x/2+...+p) = x.也就是 (1+...+p) - x= (1+...-x/2+...+p) = n;
如果 x 是奇数，假设 x = 2m+1 。 也就是 (1+...+p) - n = 2m+1 。
这个时候怎么办？
我们可以把它化成偶数的情况 (1+...+p) - (2m+1) = n -> (1+...-m+...+p) -(p+1)+p+2 = (1+...+p) - (2m+1) = n 。
也就是说如果是奇数的情况，我们不仅需要在m处回退，还要 p+1处回退，p+2处往前走。
这里求的是步数，
对于差值是偶数的情况，我们可以看到，不需要多走，只需要再中间的某一步回退；
对于差值是奇数的情况，我们可以看到是需要多走两步的。
我们用代码描述一下上面这些过程
private static int getStep(int n){
int sum = 0;
int step = 0;
while(sum < n){
step ++;
sum += step;
}
if((sum-n)%2 == 1){
step = step + 2;
}
return step;
}
题目二
序列找数
从非负整数序列 0, 1, 2, ..., n中给出包含其中n个数的子序列，请找出未出现在该子序列中的那个数。
输入描述:
输入为n+1个非负整数，用空格分开。
其中：首个数字为非负整数序列的最大值n，后面n个数字为子序列中包含的数字。
输出描述:
输出为1个数字，即未出现在子序列中的那个数。
例如：输入：3 3 0 1 输出： 2
一种很容易想到的思路是，使用标记的方式。先将n以下的自然数作为key写入map， value 就是出现的次数，然后再循环遍历输入队列，最后map中value为0的数就是没有出现的数。
用代码实现就如下所示：
private static int getOne(int n, int[] nums){
Map<Integer, Integer> map = new HashMap<>(n+1);
for(int i=0;i<=n;i++){
map.put(i,0);
}
Arrays.stream(nums).forEach(x -> {
int value = Optional.ofNullable(map.get(x)).orElse(0);
map.put(x, ++value);
});
for(int i=0;i<=n;i++){
if(map.get(i) == 0){
return i;
}
}
return -1;
}
题目三
题目描述
小喵喜欢在数轴上跑来跑去，假设它现在站在点n处，它只会3种走法，分别是：
1.数轴上向前走一步，即n=n+1
2.数轴上向后走一步,即n=n-1
3.数轴上使劲跳跃到当前点的两倍，即n=2*n
现在小喵在原点，即n=0，它想去点x处，快帮小喵算算最快的走法需要多少步？
假设小喵要到达x处，有下面几种情况：
如果x是偶数，有两种方法到达x处，
一种是， 在到达 x/2 的地方，纵身一跃，跳到x处；
一种是，在到达 x-1 的地方，往前走一步
如果x是奇数，有三种方法到达x处，
一种是，在 (x+1)/2 的地方纵身一跃，跳到 x+1 处，然后后退一步
一种是，在 (x-1)/2 的地方纵身一跃，跳到 x-1 处，然后前进一步
一种是，在 x-1 的地方，往前走一步
从分析上看走到第 x 处的步数依赖之前的情况，我们可以想到动态规划
假设 step[i] 表示跳到 i 处需要的步数，根据上面的分析可以得出：
if(i%2 == 0){
step[i] = Math.min(step[i/2] + 1, step[i-1] +1);
}else{
int min = Math.min(step[(i+1)/2] + 2, step[(i-1)/2] + 2);
step[i] = Math.min(min, step[i-1] + 1);
}
需要考虑一些边界情况:
如果到达点是0， 需要的步数是0；如果到大殿是1，需要的步数是1；
完整的代码如下：
private static int getStep(int x){
if(x < 0){
x = -x;
}
if(x < 2 && x >= 0){
return x;
}
//step[i] 表示走到i，小招喵需要最少的次数
int[] step = new int[x+1];
step[0] = 0;
step[1] = 1;
for(int i=2; i<=x; i++){
if(i%2 == 0){
step[i] = Math.min(step[i/2] + 1, step[i-1] +1);
}else{
int min = Math.min(step[(i+1)/2] + 2, step[(i-1)/2] + 2);
step[i] = Math.min(min, step[i-1] + 1);
}
}
return step[x];
}