青蛙过河

题目描述

小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里 的石头跳到对岸。

河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就 会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上（某次跳跃 后使石头高度下降到 0 是允许的)。

小青蛙一共需要去学校上 x 天课, 所以它需要往返 2x 次。当小青蛙具有 一个跳跃能力 y 时, 它能跳不超过
y 的距离。

请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

输入格式

输入的第一行包含两个整数 n,x, 分别表示河的宽度和小青蛙需要去学校 的天数。请注意 2x 才是实际过河的次数。
第二行包含 n−1 个非负整数 $1,2,\cdots ,H_1,H_2,\cdots ,H_n-1$ , 其中 $H_i$ 表示在河中与 小青蛙的家相距 i 的地方有一块高度为 $H_i$ 的石头, $H_i$ =0 表示这个位置没有石头。

输出格式

输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。

样例

样例输入

5 1
1 0 1 0

样例输出

4

样例说明

由于只有两块高度为 1 的石头，所以往返只能各用一块。第 1 块石头和对岸的距离为
4，如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。

评测用例规模与约定

30% ： n <= 100
50% ： n <= 1000
100%：$1<=n<=10^5,1<=x<=10^9,1<=H_I<=10^4$

运行限制

• 最大限制时间: 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 = n+1;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[i+x-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]

提示

• $0<=nums.length<=10^5$
• $-10^9<=nums[i]<=10^9$
• $nums是一个非递减数组$
• $-10^9<=target<=10^9$

思路

标准二分咯，今天就是做完上一题后，感觉自己的二分还不够熟练，今天特地练习一下。

代码实现

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得向上取整，即（left+right+1）/ 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 <= 5000
• rollMax.length == 6
• 1 <= rollMax[i] <= 15

思路

最优结果肯定为动态规划，但是，动态规划的转移转移方程式并不是很容易就想出来的。借此题使得如何将算法优化至动态规划。

代码实现

暴力递归模拟，递归程序中有几个需要关注的信息，上一个点数，持续了几个次，当前投掷了几个骰子。
暴力递归模拟，时间复杂度属于指数级，还是很容易超时的。

class Solution {private static final int MOD = (int)1e9+7;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)1e9+7;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)1e9+7;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);}
}