著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
给定一个整数数组 arr，如果它是有效的山脉数组就返回 true，否则返回 false。
让我们回顾一下，如果 arr 满足下述条件，那么它是一个山脉数组：
arr.length >= 30 < i < arr.length - 1 条件下，存在 i 使得：
arr[0] < arr[1] < ... arr[i-1] < arr[i] arr[i] > arr[i+1] > ... > arr[arr.length - 1]
示例 1：
输入：arr = [2,1] 输出：false
示例 2：
输入：arr = [3,5,5] 输出：false
示例 3：
输入：arr = [0,3,2,1] 输出：true
提示：
1 <= arr.length <= 1040 <= arr[i] <= 104双指针从两头往中间遍历
双指针从两头往中间遍历
最终判断两个指针是否在中间相遇，相遇点不能是左边界也不能是又边界
class Solution {
public boolean validMountainArray(int[] arr) {
int l = 0;
int r = arr.length-1;
while (l<r && arr[l+1] > arr[l]){
l++;
}
while (r>0 && arr[r-1] > arr[r]){
r--;
}
return l==r && l!=0 && l != arr.length-1;
}
}小区便利店正在促销，用 numExchange 个空酒瓶可以兑换一瓶新酒。你购入了 numBottles 瓶酒。
如果喝掉了酒瓶中的酒，那么酒瓶就会变成空的。
请你计算 最多 能喝到多少瓶酒。
示例 1：
输入：numBottles = 9, numExchange = 3
输出：13
解释：你可以用 3 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 9 + 3 + 1 = 13 瓶酒。
示例 2：
输入：numBottles = 15, numExchange = 4
输出：19
解释：你可以用 4 个空酒瓶兑换 1 瓶酒。
所以最多能喝到 15 + 3 + 1 = 19 瓶酒。
示例 3：
输入：numBottles = 5, numExchange = 5 输出：6
示例 4：
输入：numBottles = 2, numExchange = 3 输出：2
提示：
1 <= numBottles <= 1002 <= numExchange <= 100模拟，记得一次换不了的剩余空瓶可以攒着一起换
没啥好说的，直接模拟，需要有一天个注意的地方，我们需要记录下没被换掉的剩余的空瓶
可以几次攒下来不够换的空瓶，攒够了numExchange个后来换
所以
numBottles瓶，喝了这么多之后就有这么多空瓶left = numBottles%numExchange;瓶无法兑换numBottles /= numExchange;瓶，即喝到的瓶数增加了这么多numBottles + left瓶空瓶，重新回到步骤1开始模拟class Solution {
public int numWaterBottles(int numBottles, int numExchange) {
int ans = numBottles;
int left = 0;
while (numBottles >= numExchange){
left = numBottles%numExchange;
numBottles /= numExchange;
ans += numBottles;
numBottles += left;
}
return ans;
}
}你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。
示例 1：
输入：a = 2, b = [3] 输出：8
示例 2：
输入：a = 2, b = [1,0] 输出：1024
示例 3：
输入：a = 1, b = [4,3,3,8,5,2] 输出：1
示例 4：
输入：a = 2147483647, b = [2,0,0] 输出：1198
提示：
1 <= a <= 231 - 11 <= b.length <= 20000 <= b[i] <= 9b 不含前导 0快速幂使用，注意识别中途取余的情况
先了解下快速幂相关的知识，可以尝试下做下剑指 Offer 16. 数值的整数次方
另外一个知识点同底数幂相乘,底数不变,指数相加即 a^m * a^n = a^(m+n)
所以当我们面对int[] b次幂的时候，即等同于
a^(b[0] * 100...0) * ... * a^(b[i])
举个栗子假设int[] b为[2,3,4]
那么结果即为a^200 * a^30 * a^4 等同于a^(100+100) * a^(10+10+10) * a^4a^100 * a^100 * a^10 * a^10 * a^10 * a^1 * a^1 * a^1 * a^1
最终我们可以得到(a^100)^2 * (a^10)^3 * (a^1)^4
这样我们从末位开始往前遍历，中间可以重复利用 a^(10^n)的结果
自定义快速幂函数pow(int a, int b)中注意处理各种要取模的情况
class Solution {
int mod = 1337;
public int superPow(int a, int[] b) {
int ans = 1;
for (int i = b.length - 1; i >= 0; i--) {
ans *= pow(a,b[i]);
ans %= mod;
a = pow(a,10);
}
return ans;
}
public int pow(int a, int b){
if (b==0) return 1;
if (b==1) return a%mod;
int ans = pow(a,b/2);
return ((ans * ans)%mod) * pow(a,b%2) % mod;
}
}冬季已经来临。 你的任务是设计一个有固定加热半径的供暖器向所有房屋供暖。
在加热器的加热半径范围内的每个房屋都可以获得供暖。
现在，给出位于一条水平线上的房屋 houses 和供暖器 heaters 的位置，请你找出并返回可以覆盖所有房屋的最小加热半径。
说明：所有供暖器都遵循你的半径标准，加热的半径也一样。
示例 1:
输入: houses = [1,2,3], heaters = [2] 输出: 1 解释: 仅在位置2上有一个供暖器。如果我们将加热半径设为1，那么所有房屋就都能得到供暖。
示例 2:
输入: houses = [1,2,3,4], heaters = [1,4] 输出: 1 解释: 在位置1, 4上有两个供暖器。我们需要将加热半径设为1，这样所有房屋就都能得到供暖。
示例 3：
输入：houses = [1,5], heaters = [2] 输出：3
提示：
1 <= houses.length, heaters.length <= 3 * 1041 <= houses[i], heaters[i] <= 109简单粗暴点的二分
class Solution {
public int findRadius(int[] houses, int[] heaters) {
Arrays.sort(heaters);
int ans = 0;
for (int house : houses) {
int l = 0;
int r = heaters.length-1;
int tmp = (int) 1e9+1;
while (l<=r){
int mid = (l + r)/2;
//怕遗漏边缘情况不好处理就每次二分的结果都比较下
tmp = Math.min(tmp, Math.abs(heaters[mid] - house));
if (heaters[mid] > house){
r = mid-1;
}else if (heaters[mid] < house){
l = mid+1;
}else {
break;
}
}
ans = Math.max(ans,tmp);
}
return ans;
}
}给你一个点数组 points 和一个表示角度的整数 angle ，你的位置是 location ，其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。
最开始，你面向东方进行观测。你 不能 进行移动改变位置，但可以通过 自转 调整观测角度。换句话说，posx 和 posy 不能改变。你的视野范围的角度用 angle 表示， 这决定了你观测任意方向时可以多宽。设 d 为你逆时针自转旋转的度数，那么你的视野就是角度范围 [d - angle/2, d + angle/2] 所指示的那片区域。
对于每个点，如果由该点、你的位置以及从你的位置直接向东的方向形成的角度 位于你的视野中 ，那么你就可以看到它。
同一个坐标上可以有多个点。你所在的位置也可能存在一些点，但不管你的怎么旋转，总是可以看到这些点。同时，点不会阻碍你看到其他点。
返回你能看到的点的最大数目。
示例 1：
输入：points = [[2,1],[2,2],[3,3]], angle = 90, location = [1,1] 输出：3 解释：阴影区域代表你的视野。在你的视野中，所有的点都清晰可见，尽管 [2,2] 和 [3,3]在同一条直线上，你仍然可以看到 [3,3] 。
示例 2：
输入：points = [[2,1],[2,2],[3,4],[1,1]], angle = 90, location = [1,1] 输出：4 解释：在你的视野中，所有的点都清晰可见，包括你所在位置的那个点。
示例 3：
输入：points = [[1,0],[2,1]], angle = 13, location = [1,1] 输出：1 解释：如图所示，你只能看到两点之一。
提示：
1 <= points.length <= 105points[i].length == 2location.length == 20 <= angle < 3600 <= posx, posy, xi, yi <= 100相对坐标信息转换为弧度信息，排序后滑窗统计
前置基本知识
基本步骤
List<List<Integer>> points数组和List<Integer> location数组分别计算，得到各个点对应的弧度值，如果你直接用角度计算的话也一样List<Integer> location位置相同，则这个点永远可见，不做计算，并计数永远可见点数量加1Math.atan2计算的弧度值是从-π到π范围的，直接用于后续计算不行，所以我们将0到-π范围内的数据统一加2π，即将最终结果映射到0到2π区间中永远可见点占位清理下，同时记得对现在已经计算出来的弧度数组重新排序，因为题面中给的List<List<Integer>> points数组位置顺序并非按照弧度顺序排序的转链为环，因为这边得到结果是一个数组，不方便计算从结尾到开头时候的情况，即滑窗开始在结尾，滑窗结束在开头的情况，所以我们使用了常用的作法之一，数组复制双倍，这样环的数据就可以处理了，不过不需要整个数组复制双倍，只需把弧度0到窗口弧度内的数据重新接在数组结尾即可永远可见点数量没做过画图或者3d之类的开发的话这题拿到手可能有点懵，有幸之前学习研究过一段时间ThreeJS，空间、平面信息的转换上能稍微有点感觉，拿到手之后思路还是非常明确的。就是各种边边角角的细节逻辑采坑略多，想想下location点是一个相机Camera，这个angle就是对应的相机镜头的视角应该还是比较好理解的
从坐标转换为弧度，
最终将弧度信息映射在从0到2π区间的数据
class Solution {
public int visiblePoints(List<List<Integer>> points, int angle, List<Integer> location) {
double x1 = (double) location.get(0);
double y1 = (double) location.get(1);
double[] radianList = new double[points.size()];
double radianWin = angle * Math.PI / 180;
int alwaysSee = 0;
int idx = -1;
for (List<Integer> point : points) {
double x2 = (double) point.get(0);
double y2 = (double) point.get(1);
if (x1 == x2 && y1 == y2){
alwaysSee++;
continue;
}
radianList[++idx] = Math.atan2(y2-y1,x2-x1);
if (radianList[idx] < 0){
radianList[idx] += Math.PI * 2;
}
}
Arrays.sort(radianList);
if (alwaysSee>0){
double[] tmp = new double[radianList.length-alwaysSee];
System.arraycopy(radianList,alwaysSee,tmp,0,radianList.length-alwaysSee);
radianList = tmp;
}
//开始滑窗统计
int l = 0;
int r = 0;
int max = 0 ;
//窗口初始化
while (r + 1 < radianList.length && radianList[r+1] <= radianList[l] + radianWin ){
r++;
max = r-l+1;
}
//在原来的radianList数组之后,在拼上一段radianWin弧度的数据，这段数据为从弧度0开始到弧度radianWin之内的所有数据
//而这里得0到滑窗弧度范围内的点的值
if (radianList.length>0 && radianList[l] <= radianWin){
double[] tmp = new double[radianList.length + max];
System.arraycopy(radianList,0,tmp,0,radianList.length);
System.arraycopy(radianList,0,tmp,radianList.length,max);
for (int i = radianList.length; i < tmp.length; i++) {
tmp[i] += Math.PI * 2;
}
radianList = tmp;
}
//开始滑动
while (l<radianList.length && radianList[l]+ radianWin <= radianList[radianList.length-1]){
l++;
while (r + 1 < radianList.length && radianList[r+1] <= radianList[l]+radianWin ){
r++;
}
max = Math.max(max,r-l+1);
}
return max+alwaysSee;
}
}给你 n 笔订单，每笔订单都需要快递服务。
请你统计所有有效的 收件/配送 序列的数目，确保第 i 个物品的配送服务 delivery(i) 总是在其收件服务 pickup(i) 之后。
由于答案可能很大，请返回答案对 10^9 + 7 取余的结果。
示例 1：
输入：n = 1 输出：1 解释：只有一种序列 (P1, D1)，物品 1 的配送服务（D1）在物品 1 的收件服务（P1）后。
示例 2：
输入：n = 2 输出：6 解释：所有可能的序列包括： (P1,P2,D1,D2)，(P1,P2,D2,D1)，(P1,D1,P2,D2)，(P2,P1,D1,D2)，(P2,P1,D2,D1) 和 (P2,D2,P1,D1)。 (P1,D2,P2,D1) 是一个无效的序列，因为物品 2 的收件服务（P2）不应在物品 2 的配送服务（D2）之后。
示例 3：
输入：n = 3 输出：90
提示：
1 <= n <= 500数学求解推导过程
简单来说，第n对快递在原来的排序中插入放置的情况有先P后D的依赖性，不妨来分析下摆放情况，如上图，分别确定D的位置为蓝色，P的情况为绿色的可能性，
那么总和的结果为
(2n-1) + (2n-2) + (2n-3) + ... + 1
这就是一个从1到(2n-1)的求和过程，转化之后为
(2n-1) * 2n / 2
即
2 * n^2 - n
这是第n对快递的情况，而第(n-1)的情况可以由之前求得，这里简单的用f(n-1)表示
所以最终我们知道
f(n) = f(n-1) * ( 2 * n^2 - n )
这样我们从1开始滚动求解得到f(n)的具体数值中途记得模1e9+7
class Solution {
public int countOrders(int n) {
long ans = 1;
long mod = (long) (1e9+7);
for (int i = 2; i <= n; i++) {
ans *= (2 * i * i - i);
ans %= mod;
}
return (int)ans;
}
}这里有 n 个一样的骰子，每个骰子上都有 k 个面，分别标号为 1 到 k 。
给定三个整数 n , k 和 target ，返回可能的方式(从总共 kn 种方式中)滚动骰子的数量，使正面朝上的数字之和等于 target 。
答案可能很大，你需要对 109 + 7 取模 。
示例 1：
输入：n = 1, k = 6, target = 3 输出：1 解释：你扔一个有6张脸的骰子。 得到3的和只有一种方法。
示例 2：
输入：n = 2, k = 6, target = 7 输出：6 解释：你扔两个骰子，每个骰子有6个面。 得到7的和有6种方法1+6 2+5 3+4 4+3 5+2 6+1。
示例 3：
输入：n = 30, k = 30, target = 500 输出：222616187 解释：返回的结果必须是对 109 + 7 取模。
提示：
1 <= n, k <= 301 <= target <= 1000二维简单DP
简单DP算法，想要得到结果target，那么我们单独拿出来假定的最后一个骰子，这个骰子有1到k种可能性
继而对应在得到target之前，没有这个骰子的时候需要算出的target-1到target-k种情况的总和，
那么我们就很容易的知道了转移方程
dp[i][target] = dp[i-1][target-1] + .... + dp[i-1][target-k]初始一个情况，只有一个骰子的时候，1到k的值都只有1种组合情况
class Solution {
/**
* dp[i][target] = dp[i-1][target-1] + .... + dp[i-1][target-k]
*/
public int numRollsToTarget(int n, int k, int target) {
int mod = (int) 1e9 + 7;
int[][] dp = new int[n][target+1];
for (int i = 1; i <= k && i <= target; i++) {
dp[0][i] = 1;
}
for (int row = 1; row < n; row++) {
for (int col = row+1; col <= target; col++) {
for (int i = 1; i <= k; i++) {
if (i>col){
continue;
}
dp[row][col] += dp[row-1][col-i];
dp[row][col] %= mod;
}
}
}
return dp[n-1][target];
}
}