加油站
题目：在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
说明:
如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。
示例 1:
输入:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:
输入:
gas = [2,3,4]
cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。
思路：我感觉这个题应该不算太难，我目前的想法是从第一个数开始当做开始点，然后走一圈，如果到了不能到达的点则从第二个开始，以此类推。当某一条路走通以后直接返回这个开始节点。可能还有简单的办法，但是目前我用最直接的方法来做吧。
好了，做完了，不说性能代码还是很可以的：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
if(gas.length==1 && gas[0]>=cost[0]) return 0;
for(int i = 0;i<gas.length;i++){
//始发位置油不够不用继续往下判断了
if(gas[i]<cost[i]) continue;
int n = (i+1)%gas.length;
int soil = gas[i]-cost[i];
while(n!=i){
soil += (gas[n]-cost[n]);
if(soil<0) break;
n = (n+1)%gas.length;
if(n==i) return n;
}
}
return -1;
}
}
我自己看看还有什么优化的可能。因为上面代码是从第二个开始判断的，所以如果只有一个元素需要特别处理。我先优化再说。
呵，越优化性能越差怎么破？上第二版代码:
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int l = gas.length;
int cg = gas[0];
int co = cost[0];
for(int i = 1;i<l;i++){
cg += gas[i];
co += cost[i];
}
if(cg<co) return -1;
if(l==1 && cg>=co) return 0;
for(int i = 0;i<l;i++){
if(gas[i]<cost[i]) continue;
int soil = gas[i]-cost[i];
int n = (i+1)%l;
while(n!=i){
soil += (gas[n]-cost[n]);
if(soil<0) break;
n = (n+1)%l;
if(n==i) return i;
}
}
return -1;
}
}
然后我直接去看性能排行第一的代码了：
好了，膜拜完回来了，就差跪舔了。不得不说一声服。我先贴代码在解说：
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;
int totalTank = 0;
int currentTank = 0;
int startStation = 0;
for (int i = 0; i < n; i++) {
totalTank += gas[i] - cost[i];
currentTank += gas[i] - cost[i];
if (currentTank < 0) {
startStation = i + 1;
currentTank = 0;
}
}
return totalTank >= 0 ? startStation : -1;
}
}
我直接复制一段我感觉说的比较好的解说吧:
题目想要达成开一圈必然要满足两个条件：
- 车从i站能开到i+1。
- 所有站里的油总量要>=车子的总耗油量。
那么，假设从编号为0站开始，一直到k站都正常，在开往k+1站时车子没油了。这时，应该将起点设置为k+1站。
问题1: 为什么应该将起始站点设为k+1？
因为k->k+1站耗油太大，0->k站剩余油量都是不为负的，每减少一站，就少了一些剩余油量。所以如果从k前面的站点作为起始站，剩余油量不可能冲过k+1站。
问题2: 为什么如果k+1->end全部可以正常通行，且rest>=0就可以说明车子从k+1站点出发可以开完全程？
因为，起始点将当前路径分为A、B两部分。其中，必然有(1)A部分剩余油量<0。(2)B部分剩余油量>0。
所以，无论多少个站，都可以抽象为两个站点（A、B）。(1)从B站加满油出发，(2)开往A站，车加油，(3)再开回B站的过程。
重点：B剩余的油>=A缺少的总油。必然可以推出，B剩余的油>=A站点的每个子站点缺少的油。
其实我来回看了这段话两三遍，才真正的理解并且惊为天人。（接下来是我的个人理解了）
这道题分两种情况:
- 总油数不够总花费数，那么肯定是跑不了了，所以返回-1.这个没疑问。
- 其实有一点题目没说，但是隐含的条件：总油数大于等于总花费数，那么肯定是可以跑的！重点只不过是从哪里开始跑而已。
而能跑的情况怎么找到起跑点呢？就像上面解释中说的，大概可以分两个路段：- 前半段路是油不够的，后半段是油够的。又因为前提是总油数大于等于总花费数。所以我们可以先跑后半段，然后用剩下的油贴补前半段。
- 其实这里还有一种情况，前半段油够的，后半段不够，那么就是前半段贴补后半段。这种就是从第一个开始跑的。
因为题目说了只有一种可能是能跑完全程的，所以只要知道这个分界点就行了。这个分界点不是两段路程的分界点，而是油够的路程的起始点，也就是我们要求的始发点。
嗯，这道题就这么过了，下一题了。
只出现一次的数字2
题目：给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
思路：哎，我怕不是老了哟，现在怎么总想以前了呢。依稀记得当时做只出现一次的数字1的时候题目是别的都出现两次，问哪个只出现了一次。然后我是用…完成的，相同的数就没了，从头^到尾，剩下的数字就是想求的那个。而现在这个题进化成出现三次，然后还不能用额外空间（能用的话一个数组代替下标可以实现）只能说有点难啊，我先好好理理思路。刚刚百度了半天二进制运算，与或非啥的，不直接看评论和题解是我最后的倔强。然后别说，还真灵机一动有点小发现。我先说一下我的思路：首先从二进制来讲，只有0，1之分。其次二进制是32位。我打算建立一个String s = "0000 0000 0000 0000 0000 0000 0000 0000" ，然后每个0代表位数（不要空格，现在有空格只是为了好看），然后每个数字的二进制编码，是1的对应下标数字+1.如果变成3了则继续变为0.这样最后这个字符串剩下的还是1的位置，就是剩下的数字的二进制中1对应的位置。把这个字符串当成二进制改为数字就行了。emmmm...我是觉得我的方法挺好的，就不是实现了哈（字符串来回来去改，数字二进制来回来去换，想想性能就好不了。哈哈）
然后我的倔强用完了，我去看题解了直接。本来二进制这块工作中接触太少了，就是弱项。。。
好了，看了半天题解，我才理解。。但是让我自己写还是写不出来的，绝对超出了一看就会的水平，甚至到了怎么看都不咋会的地步。
其实理论很简单，跟我这个类似，只不过我要用二进制的32位来计数，人家的意思直接用数字的位运算就给操作了。大概思路两个变量：一个是one。计算每个二进制位上出现1次的数（这个数上的二进制位上是1说明出现一次），还有一个是two，计算每个二进制位上出现两次的数（也是用1表示这个位上的数出现两次，并且一次变成两次，one上的位会变成0）。最后当这一个二进制位上的数出现三次了，则one，two中这个位上的数字都变成0，也就是到三次就清0，和我之前的数字操作思路差不多。但是！！！！我明白思路了，代码中用到的各种二进制运算符晕的一笔。我直接贴代码吧，没啥可讲的，我有时间一定要补二进制的知识！！！
普通版:
public int singleNumber(int[] nums) {
int one = 0, two = 0, three;
for (int num : nums) {
// two的相应的位等于1，表示该位出现2次
two |= (one & num);
// one的相应的位等于1，表示该位出现1次
one ^= num;
// three的相应的位等于1，表示该位出现3次
three = (one & two);
// 如果相应的位出现3次，则该位重置为0
two &= ~three;
one &= ~three;
}
return one;
}
进阶版：
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for(int num : nums){
ones = ones ^ num & ~twos;
twos = twos ^ num & ~ones;
}
return ones;
}
然后这个题就这样了，下一题吧。
复制带随机指针的链表
题目：给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。要求返回这个链表的 深拷贝。
我们用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
示例 4：
输入：head = []
输出：[]
解释：给定的链表为空（空指针），因此返回 null。
提示：
-10000 <= Node.val <= 10000
Node.random 为空（null）或指向链表中的节点。
节点数目不超过 1000 。
思路：这个题怎么说呢，目前的我觉得应该不难，因为是复制，所以重新建立一个链表，然后照着一个个往上挂，我现在的思路是这样，反正昨天做的克隆图里的就是差不多的思路，这种题不做做是不能知道坑在哪的 ，我去敲代码啦
好了，回来了，首先这个题不怎么难，就是墨迹，我是一次次试。
第一次直接返回node，虽然明知道应该不行但是也得试试啊。果然不行
第二次节点都新建，下一个顺序挂，但是random直接挂原树上的，果然还是不行，提示就是random不在当前链表上。
第三次大概明白题怎么做了，用的map做辅助（昨天的克隆图也是用的map。下意识反应就是他）。然后key存老节点，value存新节点。然后因为存的就是节点，所以在节点上改next和random都会作用在节点本身。我不知道我说明白没有。
所以这个需要两次遍历链表。第一个遍历是为了把每个节点都存到map里。第二次遍历是为了把之前存的节点的下一个和随机指针补全了。
然后我贴代码了：
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head==null) return null;
HashMap<Node,Node> map = new HashMap<Node,Node>();
Node temp = head;
while(temp != null){
Node n = new Node(temp.val);
//克隆的节点只有val是一样的
map.put(temp,n);
temp = temp.next;
}
//上一步操作把所有的节点值都用新节点赋值了一遍。
temp = head;
while(temp != null){
//赋值 下一个节点
map.get(temp).next = map.get(temp.next);
map.get(temp).random = map.get(temp.random);
temp = temp.next;
}
return map.get(head);
}
}
另一种做法;
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
class Solution {
public Node copyRandomList(Node head) {
if(head==null) return null;
HashMap<Node,Node> map = new HashMap<Node,Node>();
Node temp = head;
Node f = new Node(0);
Node res = f;
while(temp != null){
Node n = new Node(temp.val);
map.put(temp,n);
res.next = n;
res = res.next;
temp = temp.next;
}
temp = head;
while(temp != null){
//每一个新节点的随即指针安置好
map.get(temp).random = map.get(temp.random);
temp = temp.next;
}
return f.next;
}
}
因为上面代码的性能1ms，拍了第四十多，我就微调了下，调成下面的代码，0ms，性能超过百分之百。
其实这道题的重点和难点就在一随机指针。必须要都排列完了，挨个节点添加随机指针，我反正想不出来在原地操作。也可能是个人水平问题。反正我这道题就这么解了。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！
