年就这么不声不响的过去了，放了个长假，发生了很多事，东家长西家短，现在回归工作学习（ps：从2月7号开始就只刷每天一题，现在打算把刷题捡回来）。其实我现在刷题的心态到不再是以前那样为了进步啥的了，而且为了不退步。
简单来说以前会的东西希望能一直保持，我觉得算法最重要的就是思路，而思路长期不用就容易忘。希望2021能依旧坚持刷题。给自己定个小目标，每周最少三道题。
其实刷题真的是一个很矛盾的问题。一方面低起点让我觉得刷题对我来说不是帮助最大的。身边有前辈和我说过我现在主要还是要背八股文。但是另一方面我又切实的喜欢并且享受做出题的快乐。而且也有很多刷题的伙伴们在20年该去微软的去了微软，该进阿里的进了阿里，所以说有时候有这个时间又真的不想打开leetcode，但是有时候又像打了鸡血一样刷题上头。挺矛盾的心态，反正最终给自己的目标也比较容易，一周三道题，不算压力大，但是也不会彻底扔下。
不多BB了，直接开始吧。
K连续为的最小翻转次数
题目：在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。
示例 1：
输入：A = [0,1,0], K = 1
输出：2
解释：先翻转 A[0]，然后翻转 A[2]。
示例 2：
输入：A = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。
示例 3：
输入：A = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A变成 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A变成 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A变成 [1,1,1,1,1,1,1,1]
提示：
1 <= A.length <= 30000
1 <= K <= A.length
思路：这个题是今天的每日一题，而且是困难难度的（ps：说个题外话，2月每日一题是滑窗月），但是我读了题目发现这个题不太对得起这个难度。简单的思路：从第一个数开始，是0的都要转成1.其次是一个子数组只转一次就行。所以遍历就可以。最后转到不够k个，不能转了，看有没有0，有就-1，没有就是之前转的次数。
第一版代码：
class Solution {
public int minKBitFlips(int[] A, int K) {
int n = A.length;
int ans = 0;
//有两点：从第一个数开始，是0的都要转成1.其次是一个子数组只转一次就行。所以遍历就可以
for(int i = 0;i<n-K+1;i++){
//A[i]是1直接往下遍历
if(A[i] == 0){
ans++;
for(int j = 0;j<K;j++) A[i+j] = A[i+j]==0?1:0;
}
}
for(int i = n-K;i<n;i++){
if(A[i] == 0) return -1;
}
return ans;
}
}
说实话我觉得这个思路一点问题都没有。。但是！！！超时了，其实我是觉得时间复杂度还好啦。。但是就是没过。而且看测试案例代码应该没问题，所以确实很纠结。因为代码比较简单，所以优化的空间也比较小，想来想去也就是那个三目运算可以优化了。优化的空间可以往位操作想，但是我自己想不出来，但是我有群友啊，在群友的指点下，把三目运算换成了.如果是11变成0.如果是0^1变成1。就这样改了一行代码ac了：
class Solution {
public int minKBitFlips(int[] A, int K) {
int n = A.length;
int ans = 0;
//有两点：从第一个数开始，是0的都要转成1.其次是一个子数组只转一次就行。所以遍历就可以
for(int i = 0;i<n-K+1;i++){
//A[i]是1直接往下遍历
if(A[i] == 0){
ans++;
for(int j = 0;j<K;j++) A[i+j] = A[i+j]^1;
}
}
for(int i = n-K;i<n;i++){
if(A[i] == 0) return -1;
}
return ans;
}
}
虽然性能确实有点问题，不过这个问题不大。但是我还是没明白这个题的优化点在哪里。反正我去看看题解吧。
回来了，这个题居然也可以滑窗！虽然我看了好几遍也没咋看懂。。但是挑能看懂的说：
class Solution {
public int minKBitFlips(int[] A, int K) {
int n = A.length;
int[] diff = new int[n + 1];
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
revCnt += diff[i];
if ((A[i] + revCnt) % 2 == 0) {
if (i + K > n) {
return -1;
}
++ans;
++revCnt;
--diff[i + K];
}
}
return ans;
}
}
这里增加了一个 diff数组，用来存储字符翻转的次数。这里其实挺好理解的。比如说翻转的子串K是3， 如下数组 [0 1 0] 1 0 1 。正常在第一个0 翻转，变成了[1 0 1] 1 0 1 。
重点是 第二个0 的时候，还要翻转。 也就是变成了 1 [1 0 0] 0 1.我们重点看第三个数：一开始是0，第一次翻转变成了1，第二次翻转有变成了0.这里我们可以很明显的理解到：翻转再翻转，其实就是回到了最开始的原点了。
所以我们不用每次翻转都记录当前值。只要知道这个元素翻转了多少次，就能知道当前值了。
当然还有一点我们要清楚： A , B , C。三个数。A翻转X次B只能翻转X或者X-1次（原因是除了A作为最后一个元素翻转过，那么A会比B多翻转一次，否则到B 的时候B会和A翻转一样的次数。）
注意我这里说的，是到B的时候翻转的次数。如果发现B是0，那么B还要起头自己翻转的。
上文的代码是把每一次翻转的下一个元素-1.这样也就能确定了挨着的两个元素为计算的翻转次数的数值一定的相同的。我不确定我说没说明白。如果没理解的建议debug几次就理解了。
然后这个就是线性的时间复杂度了，比我之前的要好的多，当然了性能也不错。
至于进阶版的就是只计算翻转的单双次数，连数都不计了：
class Solution {
public int minKBitFlips(int[] A, int K) {
int n = A.length;
int[] diff = new int[n + 1];
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
revCnt ^= diff[i];
if (A[i] == revCnt) { // A[i] ^ revCnt == 0
if (i + K > n) {
return -1;
}
++ans;
revCnt ^= 1;
diff[i + K] ^= 1;
}
}
return ans;
}
}
这个代码已经是比较完善版的了，性能也百分百。和上次除了计算方式（一个是数字计算，一个是位运算）剩下思路也差不多，就不多说了。
值得一说的是滑窗的思路：我直接贴截图吧：
滑窗思路
只能说每个字我都认识，连在一起....反正勉强好像也许是懂了，我直接贴代码：
class Solution {
public int minKBitFlips(int[] A, int K) {
int n = A.length;
int ans = 0, revCnt = 0;
for (int i = 0; i < n; ++i) {
if (i >= K && A[i - K] > 1) {
revCnt ^= 1;
A[i - K] -= 2; // 复原数组元素，若允许修改数组 A，则可以省略
}
if (A[i] == revCnt) {
if (i + K > n) {
return -1;
}
++ans;
revCnt ^= 1;
A[i] += 2;
}
}
return ans;
}
}
因为这种方式我也不是很明白，所以就不瞎BB了，直接下一题了。
最大连续1的个数3
题目：给定一个由若干 0 和 1 组成的数组 A，我们最多可以将 K 个值从 0 变成 1 。返回仅包含 1 的最长（连续）子数组的长度。
示例 1：
输入：A = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：
[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
示例 2：
输入：A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：
[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
提示：
1 <= A.length <= 20000
0 <= K <= A.length
A[i] 为 0 或 1
思路：这个题怎么说呢，因为是今天的每日一题，所以可以直接往着滑窗的方向想。目前为止的想法就是从第一个元素开始到初始窗。如果遇到0那么k--。知道k为0初始窗扩充完毕。然后开始往后移动。前面出个0k++，后面出个0k--。大概思路就这个，下面我去代码实现下。
emmmm....第一版代码直接性能超过百分百，我有点飘：
class Solution {
public int longestOnes(int[] A, int K) {
int ans = 0;
int n = K;
int start = 0;
for(int i = 0;i<A.length;i++) {
//如果当前元素是1直接扩进去就行，所以不用管
if(A[i] == 0) {
if(n>0) {//当前元素是0但是可以用k转，所以继续扩窗
n--;//减去一次机会
}else {//说明不能继续扩了，只能滑窗
ans = Math.max(i-start, ans);
//获取最左侧的0，左侧窗从0后开始
while(A[start]!=0) {
start++;
}
start++;//其实位置从第一个0以后开始计算，当前的0就可以包含了
}
}
}
return Math.max(ans, A.length-start);
}
}
总而言之这个题我的思路是没啥毛病的，至于细节处理的话，应该可以直接用K而不使用n？反正是有点优化点，但是因为影响不大所以我就优化了，这个题就这样了。
爱生气的书店老板
题目：今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
提示：
1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1
思路：简单来讲我觉得应该是这个x要最大有用话，也就是能留住的最多的人。实现起来第一步获取所有正常就能满意的客人，然后滑窗看看x范围能改成满意的最大客人数，两个相加就是结果，我去代码试试。
第一版本代码写完了，我先贴出来：
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
//不抑制的话有多少人满意
int ans = 0;
//抑制x分钟能让人变为满意的最大数
int max = 0;
int temp = 0;
int start = 0;
for(int i = 0;i<customers.length;i++){
if(grumpy[i] == 0) ans += customers[i];
//说明X+1分钟了，要把最开始那分钟去掉(如果最开始就是不生气没必要计算)
if(i-start == X){
if(grumpy[start] == 1) temp -= customers[start];
start++;
}
if(grumpy[i] == 1){
temp += customers[i];
max = Math.max(max,temp);
}
}
return ans+max;
}
}
但是其实我写着的时候就发现了，滑窗的好处就是不用额外的空间，但是这里如果单纯的用一个同等数组用来统计，可能写着更简单，虽然我不知道性能会不会更好，我去实现下试试吧：
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
//不抑制的话有多少人满意
int ans = 0;
//抑制x分钟能让人变为满意的最大数
int max = 0;
int[] arr = new int[customers.length+1];
for(int i = 0;i<customers.length;i++){
if(grumpy[i] == 0) ans += customers[i];
arr[i+1] = arr[i]+(grumpy[i] == 1?customers[i]:0);
}
for(int i = arr.length-1;i>=X;i--) {
max =Math.max(max, arr[i]-arr[i-X]);
}
return ans+max;
}
}
这种方式果然性能变好了，至于再往上的优化我直接去看题解吧：
emmmm....我竟然觉得性能第一代码也就那样，我是飘了吧。。其实思路差不多，可能性能更好一点，但是没我的简洁，我先贴出来：
class Solution {
public int maxSatisfied(int[] customers, int[] grumpy, int X) {
int len=customers.length;
int arr[]=new int[len];
int count=0;
for(int i=0;i<len;i++)
count+=customers[i];
for(int i=0;i<len;i++)
arr[i]=customers[i]*grumpy[i];
int count1=0;
for(int i=0;i<len;i++)
count1+=arr[i];
int temp=0;
for(int j=0;j<X;j++)
temp+=arr[j];
int max=temp;
for(int i=1;i<len-X+1;i++)
{
temp+=arr[i+X-1]-arr[i-1];
if(temp>max)
max=temp;
}
return count-(count1-max);
}
}
我觉得亮点就是可以把我的各种三目直接换成乘法，我去改动下试试,,好吧，乘法以后性能也还就那样，所以算了，这道题就过吧。
打开转盘锁
题目：你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
示例 1:
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:
输入: deadends = ["0000"], target = "8888"
输出：-1
提示：
死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
思路：这道题其实我觉得挺复杂的，不是说难，而是这个题的思路可以一套单独的逻辑，简单来说就是bfs广度优先搜索。其实也就是穷举啦，我去代码试试吧。思来想去这个题的麻烦点都是上下拨的8中选择，因为字符串挺不好处理的。我想想怎么实现吧。
我直接贴代码：
class Solution {
public int openLock(String[] deadends, String target) {
HashSet<String> dead = new HashSet<>(Arrays.asList(deadends));
Set<String> visited = new HashSet<>();
String start="0000";
Queue<String> queue1 = new LinkedList<>();
Queue<String> queue2 = new LinkedList<>();
queue1.offer(start);
int step=0;
if(dead.contains(target)||dead.contains("0000")) return -1;
while(!queue1.isEmpty()){
String cur=queue1.poll();
if(target.equals(cur)){
return step;
}
List<String> nexts= getNexts(cur);
for(String s:nexts){
if(!dead.contains(s)&&!visited.contains(s)){
visited.add(s);
queue2.offer(s);
}
}
if(queue1.isEmpty()){
queue1=queue2;
queue2=new LinkedList<String>();
step++;
}
}
return -1;
}
/**
*获取邻接的所有节点
*/
public List<String> getNexts(String cur){
List<String> list = new ArrayList<>();
for(int i=0;i<4;i++){
StringBuilder curSb= new StringBuilder(cur);
curSb.setCharAt(i,cur.charAt(i)=='0'?'9':(char)(cur.charAt(i)-1));
list.add(curSb.toString());
curSb.setCharAt(i,(char)cur.charAt(i)=='9'?'0':(char)(cur.charAt(i)+1));
list.add(curSb.toString());
}
return list;
}
}
这个题可以用标准的bfs模板，就是相邻的几个节点需要单独的方法来获取。这个代码的性能不咋地，我觉得还是在字符串处理这块了，其实我之前想过能不能直接用数组来表示当前数。0000就是0. 0010就是10.1001也是1001.反正不确定性能是不是卡在这。但是这样的话跟死亡数组比较的时候还要换算，也挺麻烦的，我直接去看性能第一的代码吧：
class Solution {
private int[] x = {1, 10, 100, 1000};
private int[] vis = new int[10000];//索引表示密码，值为1时，为死亡数字
private int[] dis1 = new int[10000];//索引表示密码，值表示步数
private int[] dis2 = new int[10000];//索引表示密码，值表示步数
private int touch = 0;//两个队列在哪里相交
private boolean flag = false;
private Queue<Integer> q1 = new LinkedList<>();
private Queue<Integer> q2 = new LinkedList<>();
public int openLock(String[] deadends, String target) {
int t1, t2;
int[] temp = new int[2];
for (String s : deadends)
vis[Integer.parseInt(s)] = 1;//死亡数字
//q1从0000开始
if (vis[0] == 1)
return -1;
q1.offer(0);
vis[0] = 1;
dis1[0] = 1;
//q2从target开始
int tar = Integer.parseInt(target);
if (tar == 0)
return 0;
if (vis[tar] == 1)
return -1;
q2.offer(tar);
vis[tar] = 1;
dis2[tar] = 1;
while (q1.size() > 0 && q2.size() > 0) {
t1 = q1.poll();//去队列数字,并弹出
t2 = q2.poll();//去队列数字,并弹出
if (flag) {
return dis1[touch];
}
for (int i = 0; i < 4; i++) {
temp = js(t1, i);
add(temp[0], dis1[t1], 1);
add(temp[1], dis1[t1], 1);
}
for (int i = 0; i < 4; i++) {
temp = js(t2, i);
add(temp[0], dis2[t2], 2);
add(temp[1], dis2[t2], 2);
}
}
return -1;
}
int[] js(int t, int i) {
int mid = t / x[i] % 10;//返回第i位的数字
int des = t - mid * x[i];//返回数字t，且第i位为0
int i1 = 0, i2 = 0;
i1 = (mid - 1 + 10) % 10;
i2 = (mid + 1) % 10;
i1 = des + i1 * x[i];//第i位的数-1，遇0为9
i2 = des + i2 * x[i];//第i位的数+1，遇9为0
return new int[]{i1, i2};
}
void add(int t, int d, int type) {
if (vis[t] == 1) {
if (!flag) {
if ((type == 1 && dis2[t] != 0) || (type == 2 && dis1[t] != 0)) {
dis1[t] += dis2[t] + d - 1;
touch = t;
flag = true;
}
}
return;
}
vis[t] = 1;
if (type == 1) {
q1.offer(t);
dis1[t] = d + 1;
} else if (type == 2) {
q2.offer(t);
dis2[t] = d + 1;
}
return;
}
}
能看懂，写不出来，代码的话首先是双向bfs，因为知道起点和中点，只要找交叉点就行了。然后我之前说的字符串的处理，这里直接用数组来处理了，不用想都知道比字符串来回来去比较强。多了的就不夸了，反正这道题知道bfs就能做出来，然后大佬这种做法除了膜拜也没啥好说的了，下一题了。
到达终点数字
题目：在一根无限长的数轴上，你站在0的位置。终点在target的位置。每次你可以选择向左或向右移动。第 n 次移动（从 1 开始），可以走 n 步。返回到达终点需要的最小移动次数。
示例 1:
输入: target = 3
输出: 2
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 3 。
示例 2:
输入: target = 2
输出: 3
解释:
第一次移动，从 0 到 1 。
第二次移动，从 1 到 -1 。
第三次移动，从 -1 到 2 。
注意:
target是在[-10^9, 10^9]范围中的非零整数。
思路：这个题怎么说呢，虽然题目没说，但是是有个最大值的：那就是进一步退一步是1，也就是说不管target是多少，当我们在向着target跳的时候如果下一步要超了就往回跳，再往前跳，这样是走了一步。然后退一步往前一步，这样一步一步往前蹭。大概思路就这样，我去写代码试试。
这个思路有点问题，因为在做的时候发现这种一步一跳不是最优解，最优解是超出多少，如果是偶数，直接数值/2那步往回跳。这样不仅没加反而减，也就是正好到达终点了。
假如说当前跳过终点4个单位。
那么我们在4/2也就是往前跳2个格子的时候不要往前反而往后，这样的实际差值是2 * 2等于4，正好抹平了现在多出的4个格子的值。
但是如果是奇数差值，比如比target多3的时候就很尴尬了。因为原本往前实际往后对结果的影响是n * 2，一定是偶数，所以这个时候还要继续往前蹦跶，如果下一个n是奇数，那么凑成偶数就行了，但是下一个还是偶数那么继续往前蹦跶，直到凑成奇数。大概思路就这样，下面是实现代码：
class Solution {
public int reachNumber(int target) {
target = Math.abs(target);
int n = 1;
int temp = 0;
while(temp != target) {
if(temp+n == target) {
return n;
}else if(temp+n<target) {
temp += n;
n++;
}else {
int cur = temp+n-target;
if((cur&1) == 0) return n;
//当前n是偶数，那么下一个是奇数，正好凑成偶数了
if((n&1)== 0) return n+1;
return n+2;//当前差值是奇数，下一个是偶数，只能继续往下蹦跶，所以是n+2
}
}
return n;
}
}
这个真的是数学题，思路清楚了很容易做出来，当然我这个代码性能不是很好，我觉得应该是细节处理的问题，我去看看性能第一的代码：
class Solution {
public int reachNumber(int target) {
if (target < 0) {
target = -target;
} else if (target == 0) {
return 0;
}
int sqrt = (int) (Math.sqrt(target * 2)) - 1;
if (sqrt % 2 == 1) {
sqrt--;
}
int sum = (1 + sqrt) * sqrt / 2;
for (int n = sqrt + 1; ; n++) {
sum += n;
if (sum == target || (sum > target && ((sum - target) % 2 == 0))) {
return n;
}
}
}
}
好吧，不得不承认和细节没关系，还是思路不行。比如说人家取平方根这个操作，压根想不到。不过这个问题不大，主要思路懂了就行，这个题就这样吧。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利，生活健健康康！
网友评论