著书三年倦写字，如今翻书不识志，若知倦书悔前程 ，无如渔樵未识时
小区便利店正在促销，用 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;
}
}给你一个点数组 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;
}
}给你一个整数数组 nums 。
如果一组数字 (i,j) 满足 nums[i] == nums[j] 且 i < j ，就可以认为这是一组 好数对 。
返回好数对的数目。
示例 1：
输入：nums = [1,2,3,1,1,3] 输出：4 解释：有 4 组好数对，分别是 (0,3), (0,4), (3,4), (2,5) ，下标从 0 开始
示例 2：
输入：nums = [1,1,1,1] 输出：6 解释：数组中的每组数字都是好数对
示例 3：
输入：nums = [1,2,3] 输出：0
提示：
1 <= nums.length <= 1001 <= nums[i] <= 100哈希表边统计数字次数边更新结果，一次遍历
int[] arr = new int[101]统计每个数字出现的次数，题目中已知1 <= nums[i] <= 100int[] nums，统计同一个数字出现的次数，每统计一个数字num，这个数字可以和之前的统计到的所有数字num分别组成好数对，即新增了arr[num]-1对好数对class Solution {
public int numIdenticalPairs(int[] nums) {
int[] arr = new int[101];
int ans = 0;
for (int num : nums) {
arr[num]++;
ans += arr[num]-1;
}
return ans;
}
}在一根无限长的数轴上，你站在0的位置。终点在target的位置。
你可以做一些数量的移动 numMoves :
i 次移动（从 i == 1 开始，到 i == numMoves ），在选择的方向上走 i 步。给定整数 target ，返回 到达目标所需的 最小 移动次数(即最小 numMoves ) 。
示例 1:
输入: target = 2 输出: 3 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 -1 。 第三次移动，从 -1 到 2 。
示例 2:
输入: target = 3 输出: 2 解释: 第一次移动，从 0 到 1 。 第二次移动，从 1 到 3 。
提示:
-109 <= target <= 109target != 0数学分析计算
如图
k次到达M点刚好越过或者达到target点，即k(k+1)/2 ≥ targetDx2x = D这样的结果，即反向移动加折回到原点0的距离就是我们原先应当到达M点，因为折返损耗了距离D而只能达到位置target的情况x = D/2，那么我们知道D必然需要为一个偶数，因为x必然是一个整数举个简单的例子target = 8
那么我们知道 k = 4 的时候，能到达M点位置为10，测试相差距离D为2，即需要往反向移动x = D/2 = 1距离，那么我们就知道应当按照- 1 + 2 + 3 + 4 = 8的方法运行
class Solution {
public int reachNumber(int target) {
if (target==0)return 0;
target = Math.abs(target);
int k = (int) Math.sqrt(2 * target);
k--;
while ((1 + ++k) * k / 2 < target){}
int d = (1 + k) * k / 2 - target;
while (d%2!=0) {
d += ++k;
}
return k;
}
}一个正整数如果能被 a 或 b 整除，那么它是神奇的。
给定三个整数 n , a , b ，返回第 n 个神奇的数字。因为答案可能很大，所以返回答案 对 109 + 7 取模 后的值。
示例 1：
输入：n = 1, a = 2, b = 3 输出：2
示例 2：
输入：n = 4, a = 2, b = 3 输出：6
提示：
1 <= n <= 1092 <= a, b <= 4 * 104
二分查找，最大公约数，最小公倍数
三个必要知识
gcd(long a, long b)求最大公约数 辗转相除法，lcm(long a, long b)求最小公倍数，
二分查找
从简单情况说起，设有一个数字i，从1到i过程中能整除a的数字有i/a个
那么同样的能整除b的数字有i/b个
能同时整除a和b的数字有i/lcm(a, b)个，lcm(a, b)为a``b的最小公倍数，
那么我们就可以知道，数字n以下，符合题意的数字有n/a + n/b - n/lcm(a,b)个，需要减去多计数一遍的最小公倍数个数
那么接下来就是用二分法来找到这个恰好能符合题意的数字
class Solution {
public int nthMagicalNumber(int n, int a, int b) {
long mod = (long)(1e9 + 7);
long l = 2;
long r = (long) n * Math.min(a,b);
while (l < r){
long mid = l + ((r-l)>>1);
if(f(a,b,mid) < n){
l = mid + 1;
}else{
r = mid;
}
}
return (int)(l % mod);
}
long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
long lcm(long a, long b) {
return (a * b) / gcd(a, b);
}
long f(long a, long b, long x) {
return (x / a) + (x / b) - (x / lcm(a, b));
}
}