南京网站建设制作,移动官网网站建设,wordpress 兼容ie,中国品牌策划网青蛙过河
题目描述
小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头…青蛙过河
题目描述
小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。
河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上某次跳跃 后使石头高度下降到 0 是允许的)。
小青蛙一共需要去学校上 x 天课, 所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过 y 的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。
输入格式
输入的第一行包含两个整数 n,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x 才是实际过河的次数。 第二行包含 n−1 个非负整数 1,2,⋯,H1,H2,⋯,Hn−11,2,⋯,H _1,H_2,⋯,H_n−11,2,⋯,H1,H2,⋯,Hn−1 , 其中 HiH_iHi 表示在河中与 小青蛙的家相距 i 的地方有一块高度为 HiH_iHi 的石头, HiH_iHi 0 表示这个位置没有石头。
输出格式
输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。
样例
样例输入 5 1 1 0 1 0 样例输出 4 样例说明
由于只有两块高度为 1 的石头所以往返只能各用一块。第 1 块石头和对岸的距离为 4如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。
评测用例规模与约定
30% n 100 50% n 1000 100%1n105,1x109,1HI1041 n 10^5, 1 x 10^9, 1 H_I 10^41n105,1x109,1HI104
运行限制
最大限制时间: 1s最大空间限制256MB
思路
尽量大的里面选最小很有可能是要使用二分做题做出来的规律能够跳跃的长度即为区间长度能够跳过当前区间的条件是当前区间的石头的长度和大于等于2x区间长度在枚举的过程中需要逐步递增且当前区间的石头总和在递增这便有了单调性然后就是在满足条件后取最小值。
代码实现
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int n, k;static int[] arr;public static void main(String[] args) {Scanner sc new Scanner(System.in);//在此输入您的代码...n sc.nextInt();k sc.nextInt();arr new int[n];for(int i 1; i n; i){arr[i] arr[i-1] sc.nextInt();}int l 0, r n1;while(l r){int mid (l r) 1;if(judge(mid)) r mid;else l mid 1;}System.out.println(l);sc.close();}private static boolean judge(int x){int min Integer.MAX_VALUE;for(int i 1; i x n; i){min Math.min(min, arr[ix-1] - arr[i-1]);}if(min 2 * k) return true;return false;}
}在排序数组中查找元素的第一个和最后一个位置
题目描述
给你一个按照非递减顺序排列的整数数组 nums和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target返回 [-1, -1]。
你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。
样例
样例输入 nums [5,7,7,8,8,10], target 8 nums [5,7,7,8,8,10], target 6 nums [], target 0 样例输出 [3,4] [-1,-1] [-1,-1] 提示
0nums.length1050 nums.length 10^50nums.length105−109nums[i]109-10^9 nums[i] 10^9−109nums[i]109nums是一个非递减数组nums 是一个非递减数组nums是一个非递减数组−109target109-10^9 target 10^9−109target109
思路
标准二分咯今天就是做完上一题后感觉自己的二分还不够熟练今天特地练习一下。
代码实现
class Solution {public int[] searchRange(int[] nums, int target) {if(nums.length 0) return new int[]{-1, -1};int[] ans new int[2];int l 0, r nums.length;// 左闭右开区间当nums[mid] target时r mid, 也是一直在缩小区间范围。// 单一个开区间开右区间好点开左区间mid似乎得向上取整。// 这个二分的结果为第一个出现target的位置。while(l r){int mid (l r) / 2;if(nums[mid] target) l mid 1;else r mid;}if(l nums.length || nums[l] ! target) return new int[]{-1, -1};ans[0] (nums[l] target ? l : -1);l 0;r nums.length - 1;// 左闭右闭区间这样子容易求的第一个出现target和最后一个出现target的位置。// 改改if的条件技能修改结果为第一个出现target的位置或最后一个出现target的位置。while(l r){int mid (l r) / 2;if(nums[mid] target) r mid - 1;else l mid 1;}/* 左闭由开区间但是mid得向上取整即leftright1/ 2;求的是最后一个出现target的位置。while(l r){int mid (l r 1) / 2;if(nums[mid] target) r mid - 1;else l mid;}*/ans[1] (nums[r] target ? r : -1);return ans;}
}掷骰子模拟
题目描述
有一个骰子模拟器会每次投掷的时候生成一个 1 到 6 的随机数。
不过我们在使用它时有个约束就是使得投掷骰子时连续 掷出数字 i 的次数不能超过 rollMax[i]i 从 1 开始编号。
现在给你一个整数数组 rollMax 和一个整数 n请你来计算掷 n 次骰子可得到的不同点数序列的数量。
假如两个序列中至少存在一个元素不同就认为这两个序列是不同的。由于答案可能很大所以请返回 模 10^9 7 之后的结果。
样例
样例输入 n 2, rollMax [1,1,2,2,2,3] n 2, rollMax [1,1,1,1,1,1] n 3, rollMax [1,1,1,2,2,3] 样例输出 34 我们掷 2 次骰子如果没有约束的话共有 6 * 6 36 种可能的组合。但是根据 rollMax 数组数字 1 和 2 最多连续出现一次所以不会出现序列 (1,1) 和 (2,2)。因此最终答案是 36-2 34。 30 181 提示
1 n 5000rollMax.length 61 rollMax[i] 15
思路
最优结果肯定为动态规划但是动态规划的转移转移方程式并不是很容易就想出来的。借此题使得如何将算法优化至动态规划。
代码实现
暴力递归模拟递归程序中有几个需要关注的信息上一个点数持续了几个次当前投掷了几个骰子。 暴力递归模拟时间复杂度属于指数级还是很容易超时的。
class Solution {private static final int MOD (int)1e97;int[] rollMax;public int dieSimulator(int n, int[] rollMax) {int max Arrays.stream(rollMax).max().getAsInt();this.rollMax rollMax;cache new int[n][6][max];for(int i 0; i n; i)for(int j 0; j 6; j)Arrays.fill(cache[i][j], -1);long res 0;for(int i 0; i 6; i){res dfs(n-1, i, rollMax[i]-1);}return (int)(res % MOD);}private int dfs(int i, int last, int left){if(i 0) return 1;long res 0;for(int k 0; k 6; k){if(k ! last) res dfs(i-1, k, rollMax[k]-1);else if(left 0) res dfs(i-1, k, left-1);}return (int)(res % MOD);}
}记忆化搜索将已经计算过的结果记录下来下次遇到同等情况直接返回记录的结果即可。 将已经计算的结果记录下来能过很大程度的降低时间复杂度。
class Solution {private static final int MOD (int)1e97;int[] rollMax;int[][][] cache;public int dieSimulator(int n, int[] rollMax) {int max Arrays.stream(rollMax).max().getAsInt();this.rollMax rollMax;cache new int[n][6][max];for(int i 0; i n; i)for(int j 0; j 6; j)Arrays.fill(cache[i][j], -1);long res 0;for(int i 0; i 6; i){res dfs(n-1, i, rollMax[i]-1);}return (int)(res % MOD);}private int dfs(int i, int last, int left){if(i 0) return 1;if(cache[i][last][left] ! -1) return cache[i][last][left];long res 0;for(int k 0; k 6; k){if(k ! last) res dfs(i-1, k, rollMax[k]-1);else if(left 0) res dfs(i-1, k, left-1);}return cache[i][last][left] (int)(res % MOD);}
}动态规划 记忆化的递归即是自上向下的执行程序其实在递归的时候状态转移方程式就已经写在递归函数中了。 只需将自上向下的程序修改为自下向上就是动态规划。
class Solution {private static final int MOD (int)1e97;public int dieSimulator(int n, int[] rollMax){int len rollMax.length;int max Arrays.stream(rollMax).max().getAsInt();var dp new long[n][6][max];for(int i 0; i 6; i)Arrays.fill(dp[0][i], 1);for(int i 1; i n; i){for(int last 0; last 6; last){for(int left 0; left max; left){long res 0;for(int j 0; j len; j){if(j ! last) res dp[i-1][j][rollMax[j]-1];else if(left 0) res dp[i-1][j][left-1];}dp[i][last][left] res % MOD;}}}long ans 0;for(int i 0; i 6; i) ans dp[n-1][i][rollMax[i]-1];return (int)(ans % MOD);}
}
