leetCode进阶算法题+解析（四十五）
以前日更的现在改成周更了，哈哈~直接开始刷题吧。
随机数索引
题目：给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。 您可以假设给定的数字一定存在于数组中。
注意：数组大小可能非常大。 使用太多额外空间的解决方案将不会通过测试。
示例:
int[] nums = new int[] {1,2,3,3,3};
Solution solution = new Solution(nums);
// pick(3) 应该返回索引 2,3 或者 4。每个索引的返回概率应该相等。
solution.pick(3);
// pick(1) 应该返回 0。因为只有nums[0]等于1。
solution.pick(1);
思路：这个题怎么说呢，我感觉题目的意思是不适用额外的空间，所以我的想法是每次都便利，和给定值相同的下标开始随机赋值，一次遍历过后每个索引的返回概率是相等的，我去代码试一下。
额，这个题有点奇怪啊，提交报错了，但是我不知道错在哪里了。我觉得代码应该没问题啊。因为这个我现在也很费解，所以附上代码：
未通过的代码
因为是未通过的，所以直接上截图了。刚刚在群里问了下，说有可能问题出在random.nextInt(2)上，这个产生的是伪随机啥的。。
群里截图
然后目前我能想到的也觉得别的都没哈问题，可能这个不通过真的是随机这块？13个测试案例通过了11个，卡在第12个，，啧啧，百度了半天没有好思路，我打算直接看题解了。
找到错误原因了，我这个算法有问题，不是每次都是1/2的几率选或者不选，不然最后的元素占便宜。应该是每次元素数分之一的几率选。说起来很复杂，我直接贴代码：
class Solution {
int[] nums;
public Solution(int[] nums) {
this.nums = nums;
}
public int pick(int target) {
Random r = new Random();
int res = 0;
int n = 0;
for(int i = 0;i<nums.length;i++){
if(nums[i]==target){
n++;//总共的下标数
//每个元素选中的几率是1/n
if(r.nextInt()%n == 0) res = i;
}
}
return res;
}
}
咳咳，如上代码，其实这个题和真随机伪随机啥的关系不大，主要还是算法问题。然后上面的代码是通过的代码。这个题我一开始是想错了，在这里留下也算是一个警醒吧。题目的重点就是随机问题，我之前看题解也发现了，这个也叫作蓄水池抽样问题。又学到了一点东西。
蓄水池抽样问题
首先从最简单的例子出发：数据流只有一个数据。我们接收数据，发现数据流结束了，直接返回该数据，该数据返回的概率为1。
看来很简单，那么我们试试难一点的情况：假设数据流里有两个数据。我们读到了第一个数据，这次我们不能直接返回该数据，因为数据流没有结束。我们继续读取第二个数据，发现数据流结束了。因此我们只要保证以相同的概率返回第一个或者第二个数据就可以满足题目要求。因此我们生成一个0到1的随机数R,如果R小于0.5我们就返回第一个数据，如果R大于0.5，返回第二个数据。
接着我们继续分析有三个数据的数据流的情况。为了方便，我们按顺序给流中的数据命名为1、2、3。我们陆续收到了数据1、2和前面的例子一样，我们只能保存一个数据，所以必须淘汰1和2中的一个。应该如何淘汰呢？不妨和上面例子一样，我们按照二分之一的概率淘汰一个，例如我们淘汰了2。继续读取流中的数据3，发现数据流结束了，我们知道在长度为3的数据流中，如果返回数据3的概率为1/3,那么才有可能保证选择的正确性。也就是说，目前我们手里有1,3两个数据，我们通过一次随机选择，以1/3的概率留下数据3，以2/3的概率留下数据1。那么数据1被最终留下的概率是多少呢？
数据1被留下：（1/2）(2/3) = 1/3
数据2被留下概率：（1/2）(2/3) = 1/3
数据3被留下概率：1/3
如是可满足所有元素的被选中概率是一样的。
除法求值
题目：给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。
示例 :
给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]
输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。
基于上述例子，输入如下：
equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。
思路：这个字有点多。而且看似很复杂。但是我觉得如果拆开来，，仍然可能很复杂。。毕竟单纯的题目的话这几个demo很容易，但是如果一串几十个变量来计算，也是脑壳够痛的了。。毕竟可能a和b有关系，b和c有，c和d有...最后y和z有，最后求a和z的关系这种，简直是折磨。目前有的想法就是有向图，我已经预料这道题代码少不了了，哈哈。我先尝试去直接写代码吧。遇到什么问题回来再说。
唔，我成功的看了题解回来了。写了几十行代码，然后最终还是放弃在了繁琐的逻辑里，我直接去看了题解，大体思路分两种：dfs查并集？还有一个就是Floyd算法。
简单说下，第一个所谓的dfs查并集我觉得和构有向图挺像的，我也不知道为啥名字叫这个，可能是数学上的东西吧。然后我发现最好理解的方法就是Floyd构二维图，所以我也嫖了这种方式的代码，整体而言逻辑是很清晰的，下面贴代码：
class Solution {
public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
int count = 0;
Map<String,Integer> map = new HashMap<String,Integer>();
for (List<String> list:equations){
for (String s:list){
if(!map.containsKey(s)){
map.put(s,count++);
}
}
}
//构建一个矩阵来代替图结构
double[][] graph=new double[count+1][count+1];
//初始化
for (String s:map.keySet()){
int x=map.get(s);
graph[x][x]=1.0;
}
int index=0;
for (List<String> list:equations){
String a=list.get(0);
String b=list.get(1);
int aa=map.get(a);
int bb=map.get(b);
double value=values[index++];
graph[aa][bb]=value;
graph[bb][aa]=1/value;
}
//通过Floyd算法进行运算
int n=count+1;
for (int i=0;i<n;i++){
for (int j=0;j<n;j++){
for (int k=0;k<n;k++){
if(j==k||graph[j][k]!=0) continue;
if(graph[j][i]!=0&&graph[i][k]!=0){
graph[j][k]=graph[j][i]*graph[i][k];
}
}
}
}
//直接通过查询矩阵得到答案
double[] res=new double[queries.size()];
for (int i=0;i<res.length;i++){
List<String> q=queries.get(i);
String a=q.get(0);
String b=q.get(1);
//保证两个字母都在图里，则取值，否则直接-1.0
if(map.containsKey(a)&&map.containsKey(b)){
double ans=graph[map.get(a)][map.get(b)];
//如果这个是0说明没有这个数值，也是-1.0
res[i]=(ans==0?-1.0:ans);
}else {
res[i]=-1.0;
}
}
return res;
}
}
这段代码其实核心逻辑只有通过Floyd算法进行运算这段，别的都一目了然，我反正是用测试案例，在编译器上debug看的一步步走向，跟着跑两个demo就能明白代码的逻辑所在。
简单的代码逻辑
这三段代码：
- 第一段是把所有有值的字母添加到map中，这样确保在获取结果的时候很清楚的能知道某表达式是-1.0还是真的会有结果值。
- 第二段代码是二维矩阵赋值，首先一个数/它本身肯定是1，所以第一次for循环只是把所有的自己/自己赋值1.0。
- 第三段代码是根据已给的表达式，能知道两个字符之间的数值结果：A/B的值是已给的，B/A的值是已给值的1/n，这个没啥问题。
一直到这里逻辑都很清晰。重点就是接下来的通过Floyd算法进行运算（其实我对这个算法也是才知道，但是代码的逻辑是从调试中看出规律的，然后一点点去理解。所以我这里也不主要说这个算法，还是回归到这个题的代码逻辑）：
三层for循环不说，代码里面的逻辑：
j==k||graph[j][k]!=0
这两个判断条件，j==k其实就落实到了自己/自己，已经确定是1.0了。还有如果jk不等于0 说明是已经被赋值过，所以没必要重新写什么，这两个条件都属于在矩阵中已经有值了，直接continue就行。
图解
如图，当出现蓝色框框无值，并且左边和下边的黄色框框都有值，则可以计算出蓝色框框的值。a/b = 2，b/c = 3.那么a/c结果是2*3。
这个就是代码中是那一行：
if(graph[j][i]!=0&&graph[i][k]!=0) graph[j][k]=graph[j][i]*graph[i][k];
同样当算到c/b = 0.3333,b/a = 0.5的时候。也可以算出c/a = 0.333*0.5。
由此，所有能算出结果的两个数，都可以被填充完数值。
最后只要按照问题将答案一一对应写入（没有值的-1）就好了。
整个代码中不好理解的只有填充数据那一块。我只能说在debug的调试下，能够看懂代码了。但是！！让我自己写的话，仍然写！不！出！来！对，哪怕跟着调试无数次，仍然觉得处于勉强能看懂，但是写不出来的程度。
至于别的不说理解了，代码都麻烦的一批。所以我也不多说了，感觉这个题的难度真的不仅仅是中等，哎，下一题。
第N个数字
题目：在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...中找到第 n 个数字。
注意:n 是正数且在32位整数范围内 ( n < 231)。
示例 1:
输入:
3
输出:
3
示例 2:
输入:
11
输出:
0
说明:
第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。
思路：刷题的一大好处，会的会，不会的依旧不会，哎。别不多谈，这个题我觉得最笨的做法就是按顺序遍历，按位数累加，直到n，但是我不知道会不会超时啥的，毕竟这么暴力无脑。我还是觉得应该稍微用点技巧。看这个序列。1,2,3...9,10,11,12...19,20,21,22...29,30。我感觉其实是有一些规律的吧。1-9是九个数。10-19是10乘2个数，20-29又是10乘2个。总结起来 10-99是9乘10乘2。不出意外的话，100-999是9乘100乘3，暂时而言规律不明显，但是肯定有。我去代码实现下。
我直接贴代码：
class Solution {
public int findNthDigit(int n) {
if(n<=9)return n;
long base=1; //由于输入是int所以n不爆，但是base*10是可能爆的
int w=1;
n--; //是因为n>=10的时候前面是一共0-9有10个数，10对应于base第0个数的第0位，如果不减接下去循环就变成base的第0个数第1位
while(n>9*base*w){
n-=9*base*w;
base*=10;
w++;//位数+1
return String.valueOf(base+n/w).charAt(n%w)-'0';
}
}
其实这个题真的是个找规律的题目。简单来说一来判断这个n落在哪个区间例如320，由于320>9所以320-10，即求第10位开始的第310位，然后由于310>9乘10乘2所以变成求100开始的（310-180）130位，130/3=43，130%3=1所以求的是100开始的第43个数字的第1位也就是143的第一位4.
不难，挺有意思的题目，细心点就能做出来，跟上一个题比简直简单的不要不要的，哈哈，下一题。
移掉k位数字
题目：给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
思路:这个题审完题就有个大胆的想法，是不是当前一个数字大于后一个数字，就可以被移掉了？我感觉是这样，先去代码试一下。
简单评价一下这个题：思路很容易想到，然后代码比较墨迹。最开始我是用是char数组，然后发现删除不方便，用了字符串截取，最后思路对了优化的时候才改成stringBuffer的。直接贴代码:
class Solution {
public String removeKdigits(String num, int k) {
if (num.length() == k) return "0";
StringBuilder s = new StringBuilder(num);
for (int i = 0; i < k; i++) {
int idx = 0;
for (int j = 1; j < s.length() && s.charAt(j) >= s.charAt(j - 1); j++) idx = j;
s.delete(idx, idx + 1);
while (s.length() > 1 && s.charAt(0) == '0') s.delete(0, 1);
}
return s.toString();
}
}
逻辑上就是这样，前面的数大于后面的数就删除，然后重头来。分多种情况：元素都删除完了，返回“0”。最后一个数字最大，则删除最后一个数。
今天的笔记就到这吧，端午放假了，也祝大家节日快乐！另外java技术交流群130031711，欢迎各位踊跃加入！
