蛇梯棋
题目：N x N 的棋盘 board 上，按从 1 到 N*N 的数字给方格编号，编号 从左下角开始，每一行交替方向。例如，一块 6 x 6 大小的棋盘，编号如下：
r 行 c 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 board[r][c] != -1，那个蛇或梯子的目的地将会是 board[r][c]。
玩家从棋盘上的方格 1 （总是在最后一行、第一列）开始出发。
每一回合，玩家需要从当前方格 x 开始出发，按下述要求前进：
选定目标方格：选择从编号 x+1，x+2，x+3，x+4，x+5，或者 x+6 的方格中选出一个目标方格 s ，目标方格的编号 <= N*N。
该选择模拟了掷骰子的情景，无论棋盘大小如何，你的目的地范围也只能处于区间 [x+1, x+6] 之间。
传送玩家：如果目标方格 S 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 S。
注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，你也不会继续移动。
返回达到方格 N*N 所需的最少移动次数，如果不可能，则返回 -1。
示例：
输入：[
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
输出：4
解释：
首先，从方格 1 [第 5 行，第 0 列] 开始。
你决定移动到方格 2，并必须爬过梯子移动到到方格 15。
然后你决定移动到方格 17 [第 3 行，第 5 列]，必须爬过蛇到方格 13。
然后你决定移动到方格 14，且必须通过梯子移动到方格 35。
然后你决定移动到方格 36, 游戏结束。
可以证明你需要至少 4 次移动才能到达第 NN 个方格，所以答案是 4。
提示：
2 <= board.length = board[0].length <= 20
board[i][j] 介于 1 和 NN 之间或者等于 -1。
编号为 1 的方格上没有蛇或梯子。
编号为 N*N 的方格上没有蛇或梯子。
思路：这个题的题目的广度优先。这没啥问题。但是完完全全的广搜肯定超时，这里应该是还要加个记忆功能。比如到了点x用3步，那么以后4,5,6步到x的都不要计算了。除了这个应该没什么了，毕竟就是一个中等题目，我去试试代码。
第一版代码：
class Solution {
public int snakesAndLadders(int[][] board) {
int len = board.length;
//其实图是顺着跑的，所以我们完全能把这个抻直了
int[] b = new int[len*len];
boolean flag = true;
int idx = 0;
for(int i = len-1;i>=0;i--) {
if(flag) {
for(int j = 0;j<len;j++) b[idx++] = board[i][j];
flag = false;
}else {
for(int j = len-1;j>=0;j--) b[idx++] = board[i][j];
flag = true;
}
}
//现在只要把b跳通关就行了。
boolean[] d = new boolean[b.length];
int ans = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(0);
while(!queue.isEmpty()) {
int size = queue.size();
for(int t = 0;t<size;t++) {
int temp = queue.poll();
for(int i = 1;i<=6;i++) {
if(temp+i>=d.length) break;
int v = b[temp+i];
//减1是因为填充数字从1开始，下标从0开始
int next = b[temp+i] == -1? temp+i:b[temp+i]-1;
if(next == len*len-1) return ans+1;
if(!d[next]) {
queue.add(next);
d[next] = true;
}
}
}
ans++;
}
return -1;
}
}
讲真这个题思路上和我最开始想的差别不大，但是细节处理上，比如矩阵理直了计算。还有如果在子集中返回的话ans要+1.还有判断temp+i是不是溢出。反正各种细节我都是面向测试案例改的。。细节比较多。因为这个代码已经是超过百分百了，所以我就不多说了，直接下一题。
最小差值
题目：给你一个整数数组 A，对于每个整数 A[i]，可以选择 x = -K 或是 x = K （K 总是非负整数），并将 x 加到 A[i] 中。在此过程之后，得到数组 B。返回 B 的最大值和 B 的最小值之间可能存在的最小差值。
示例 1：
输入：A = [1], K = 0
输出：0
解释：B = [1]
示例 2：
输入：A = [0,10], K = 2
输出：6
解释：B = [2,8]
示例 3：
输入：A = [1,3,6], K = 3
输出：3
解释：B = [4,6,3]
提示：
1 <= A.length <= 10000
0 <= A[i] <= 10000
0 <= K <= 10000
思路：这个题怎么说呢，乍一看还挺简单的。但是细想也不是。本来觉得是最大值减k，最小值+k，后来发现万一最大最小就差1，这样加减k指不定差的更大了，所以说这个题还要具体情况具体分析。但是总的来讲一个我的想法第一次遍历找出最大值和最小值。然后如果这两个值同向加减的差值（比如都+k或者都-k）小于最大值减，最小值加。那么这个差值就是最大值。反正大的减，小的加。然后中间的每一个元素看往上加的差值大还是往下减的差值大。大概思路就这样，我去实现下试试。
第一版代码：
class Solution {
public int smallestRangeII(int[] nums, int k) {
Arrays.sort(nums);
int len = nums.length-1;
int cha = nums[len]-nums[0];
//说明最大值最小值的差异小于大减k，小加k的结果，所以应该做相同符号的操作。
if(cha <= Math.abs(cha-2*k)) return cha;
//到这说明一定是有加有减，所以肯定存在相邻的两个元素，一个是加k，一个是-k。
for(int i = 0;i<nums.length-1;i++) {
//因为数组排序了，所以小的加大的减是肯定的。
int max1 = Math.max(nums[len]-k, nums[i]+k);
int min1 = Math.min(nums[0]+k, nums[i+1]-k);
cha = Math.min(cha, max1-min1);
}
return cha;
}
}
注意这里的最小值是最大值和最小值的差值。因为所有元素+k或者-k的结果就是这个差值。所以这个差值也算是保底。然后注释里说的比较明确了，排序好了的元素，绝对有一个分解点，前一个元素-k，后一个元素+k。我们只要遍历一遍取最小结果就行了。我这个代码性能还好，超过百分之九十四的人就不多说了，继续下一题。
在线选举
题目：在选举中，第 i 张票是在时间为 times[i] 时投给 persons[i] 的。现在，我们想要实现下面的查询函数： TopVotedCandidate.q(int t) 将返回在 t 时刻主导选举的候选人的编号。在 t 时刻投出的选票也将被计入我们的查询之中。在平局的情况下，最近获得投票的候选人将会获胜。
示例：
输入：["TopVotedCandidate","q","q","q","q","q","q"], [[[0,1,1,0,0,1,0],[0,5,10,15,20,25,30]],[3],[12],[25],[15],[24],[8]]
输出：[null,0,1,1,0,0,1]
解释：
时间为 3，票数分布情况是 [0]，编号为 0 的候选人领先。
时间为 12，票数分布情况是 [0,1,1]，编号为 1 的候选人领先。
时间为 25，票数分布情况是 [0,1,1,0,0,1]，编号为 1 的候选人领先（因为最近的投票结果是平局）。
在时间 15、24 和 8 处继续执行 3 个查询。
提示：
1 <= persons.length = times.length <= 5000
0 <= persons[i] <= persons.length
times 是严格递增的数组，所有元素都在 [0, 10^9] 范围中。
每个测试用例最多调用 10000 次 TopVotedCandidate.q。
TopVotedCandidate.q(int t) 被调用时总是满足 t >= times[0]。
思路：这个题感觉比较简单，实现容易，但是怎么性能好的实现是考点。首先因为time是严格递增的，并且范围是10的九次方，所以数组下标代替值是不行的。所以初步想法是一个多维数组。然後其实比如我们想知道第12分钟的结果，其实本质上不用知道票数，只要知道谁领先就行了。这样在查询的时候也比较方便。所以我打算在初始化的时候就获取到个个时间点的领先人。然後在查询的时候用二分来确定当前截止时间的领先人是谁。至于保存方法初步决定用二维数组，第一个元素存时间，第二个元素存领先人。主要逻辑代码写在构造函数中。思路就是这样，我去实现试试。
第一版代码：
class TopVotedCandidate {
List<Vote> A;
public TopVotedCandidate(int[] persons, int[] times) {
A = new ArrayList();
Map<Integer, Integer> count = new HashMap();
int leader = -1; // current leader
int m = 0; // current number of votes for leader
for (int i = 0; i < persons.length; ++i) {
int p = persons[i], t = times[i];
int c = count.getOrDefault(p, 0) + 1;
count.put(p, c);
if (c >= m) {
if (p != leader) { // lead change
leader = p;
A.add(new Vote(leader, t));
}
if (c > m) m = c;
}
}
}
public int q(int t) {
int lo = 1, hi = A.size();
while (lo < hi) {
int mi = lo + (hi - lo) / 2;
if (A.get(mi).time <= t)
lo = mi + 1;
else
hi = mi;
}
return A.get(lo - 1).person;
}
}
class Vote {
int person, time;
Vote(int p, int t) {
person = p;
time = t;
}
}
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* TopVotedCandidate obj = new TopVotedCandidate(persons, times);
* int param_1 = obj.q(t);
*/
emmm...这是参考了题解的代码，自己写越写越麻烦。所以直接搬运代码了，哈哈。总而言之这个题我是觉得难度还好，我之前因为没想到单独写个数据结构的类然後各种list套map啥的才写崩了的。而且不得不吐槽这个官方题解的性能也不咋地，我再去看看性能第一的代码：
class TopVotedCandidate {
int[] lead ;
Map<Integer,Integer> num = new HashMap<>();
public TopVotedCandidate(int[] persons, int[] times) {
lead = new int[times[times.length-1]+1];
int leadnow = persons[0];
int vote = 1;
Arrays.fill(lead,-1);
lead[times[0]]=leadnow;
num.put(leadnow,vote);
for(int i = 1;i<persons.length;i++){
if(persons[i]==leadnow){
vote++;
}else{
int intnow = num.getOrDefault(persons[i],0)+1;
num.put(persons[i],intnow);
if(intnow>=vote){
leadnow=persons[i];
vote=intnow;
}
}
lead[times[i]]=leadnow;
num.put(leadnow,vote);
}
for(int i=1;i<lead.length;i++){
if(lead[i]==-1){
lead[i]=lead[i-1];
}
}
}
public int q(int t) {
if(t>=lead.length){
return lead[lead.length-1];
}
return lead[t];
}
}
/**
* Your TopVotedCandidate object will be instantiated and called as such:
* TopVotedCandidate obj = new TopVotedCandidate(persons, times);
* int param_1 = obj.q(t);
*/
这个代码中是用了一个数组把所有时间的当前领先人都记录了。因为时间范围是10的九次方，所以这个数组最大也是10的九次方长度。但是每次查询不用二分了，可以直接定位到时间点。感觉就是典型是空间换时间的做法。别的也没啥了。这个题就这样吧，下一题。
最后一块石头的重量2
题目：有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
示例 2：
输入：stones = [31,26,33,21,40]
输出：5
示例 3：
输入：stones = [1,2]
输出：1
提示：
1 <= stones.length <= 30
1 <= stones[i] <= 100
思路：这个题怎么说呢，最后一次粉碎，肯定是尽可能两个石头越相似结果越小。所以这个题目可以变种为：将所有石子分成两堆，尽量两堆的重量相等。也就是算出石子总和/2，然後尽量从stones中挑出部分元素组成最接近target的元素。思路就这样，我去实现试试。
第一版本的dfs代码超时了，但是因为我觉得总思路是对的，所以依然贴出来分享下：
class Solution {
int ans;
double target;
public int lastStoneWeightII(int[] stones) {
//这个题怎么说呢，最后一次粉碎，肯定是尽可能两个石头越相似结果越小。
//所以这个题目可以变种为：将所有石子分成两堆，尽量两堆的重量相等
int sum = 0;
for(int i : stones) sum += i;
Arrays.sort(stones);
target = sum*1.0/2;
ans = 0;
//现在的做法变成了尽量从stones中挑出部分元素组成最接近target的元素。
//每个元素可以选择选或者不选。然後去遍历。不知道超时不超时
dfs(stones,stones.length-1,0);
return sum-2*ans;
}
public void dfs(int[] stones,int temp,int sum) {
if(temp<0) return;
if(sum == target) {
ans = sum;
return;
}else if(sum>target){
return;//当前sum都已经比结果集大了。不用继续走了。
}else if(sum>ans && sum< target){
ans = sum;
}
dfs(stones, temp-1, sum+stones[temp]);//选择当前元素
dfs(stones, temp-1, sum);//不选当前元素
}
}
第二版代码（01背包问题）：
class Solution {
public int lastStoneWeightII(int[] stones) {
//这个题怎么说呢，最后一次粉碎，肯定是尽可能两个石头越相似结果越小。
//所以这个题目可以变种为：将所有石子分成两堆，尽量两堆的重量相等
int sum = 0;
for(int i : stones) sum += i;
Arrays.sort(stones);
int target = sum/2;
//现在的做法变成了尽量从stones中挑出部分元素组成最接近target的元素。
//每个元素可以选择选或者不选。然後去遍历。不知道超时不超时
//这里递归超时，所以改用dp。这个题也可以简化为01背包问题
int[][] dp = new int[stones.length+1][target+1];//因为下标从0开始。
for(int i = 1;i<dp.length;i++) {
for(int j = 1;j<dp[0].length;j++) {
if(j>=stones[i-1]) {
dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-stones[i-1]]+stones[i-1]);
}else {
dp[i][j] = dp[i-1][j];
}
}
}
return sum-2*dp[stones.length][target];
}
}
首先该说不说这个问题确实是01背包问题。其次我也确实是过了。问题是同样的dp。人家性能那样，我这个性能这样。。上面代码的优化空间我能想到的是当前行数据只和上一行有关，所以这里可以用压缩的方式两个一维数组来回倒腾，省空间。但是又因为数据范围最大才30.省的也有限。至于别的暂时想不到了，我直接去看看性能第一的代码：
class Solution {
public int lastStoneWeightII(int[] stones) {
int sum=0;
for(int st:stones)
sum+=st;
for(int i=(sum>>1);;i--){
if(helper(stones,0,0,i))
return sum-2*i;
}
}
boolean helper(int[] nums,int idx,int sum,int target){
if(sum==target)
return true;
if(sum>target)
return false;
if(idx==nums.length)
return false;
return helper(nums,idx+1,sum+nums[idx],target)
||helper(nums,idx+1,sum,target);
}
}
代码逻辑比较简单，也挺好懂的。但是问题是，为什么性能定义的代码是用dfs做出来的？我的思路就超时。。。有点小心痛。总而言之这个代码挺容易懂的。就是从sum/2开始判断。如果能凑出这个数则true，否则false。sum/2凑不出来则递减继续凑。其实本质上还是找最接近target的点。可能是人家处理的复杂度低吧，哎 ，下一题下一题。
排序数组
题目：给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
思路：很奇怪这个题为什么在这里出来了。还是中等难度的。。难不成是会超时么？我目前的想法是快排。毕竟这个用的比较习惯。我去试试这个题的考点是什么。
第一版代码：
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
if(left>=right) return;
int mid = (right-left)/2+left;
quickSort(nums, left, mid);
quickSort(nums, mid+1, right);
merge(nums,left,right,mid+1);
}
public void merge(int[] nums,int left,int right,int mid) {
int[] temp = new int[right-left+1];
int l = left;
int r = mid;
int idx = 0;
while(l<mid && r<=right) {
if(nums[l]<nums[r]) {
temp[idx++] = nums[l++];
}else {
temp[idx++] = nums[r++];
}
}
while(l<mid) temp[idx++] = nums[l++];
while(r<=right) temp[idx++] = nums[r++];
for(int i = left;i<=right;i++) {
nums[i] = temp[i-left];
}
}
}
我也很难说明白为什么写着写着变成归并排序了。。但是既然都写出来了所以就对付写完了。归并性能不咋地，下面继续用快排试试，第二版代码：
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
public void quickSort(int[] nums, int left, int right) {
if(left>=right) return;
int l = left;
int r = right;
int temp = nums[(r-l)/2+l];//把最左元素看成标准值
while(l<r) {
while(r>=left && nums[r]>temp) r--;//找到第一个小于目标值的元素
while(l<right && nums[l]<temp) l++;//前面都比temp小。找到第一个大于的元素
if(l <= r) {//这里添加等于是为了让r是
int cur = nums[r];
nums[r] = nums[l];
nums[l] = cur;
r--;
l++;
}
}
//到这里我们确定left-r的值都是小于等于
quickSort(nums, left, r);
quickSort(nums, l, right);
}
}
快排倒是实现了，性能依然不行，所以我决定做个大胆的尝试，用空间换时间。数据范围正负5w依然打算用数组下标代替值试试。最终版代码：
class Solution {
public int[] sortArray(int[] nums) {
int[] d = new int[100001];
for(int i : nums) d[i+50000]++;
int idx = 0;
for(int i = 0;i<d.length;i++) {
int n = d[i];
while(n>0) {
nums[idx++] = i-50000;
n--;
}
}
return nums;
}
}
这个性能一下子就上来了。怎么说呢，当数据量多的时候确实是这样最性能好，反正是超过百分之九十九的人了，所以这个排序就这样了。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注。也祝大家工作顺顺利利，生活健健康康！另外最近在看面试题，欢迎小伙伴们推荐下比较好的课程或者学习资料哟~
