[10.15] 1441. 用栈操作构建数组@中等

解题思路

一个看上去是中等但是实际上是简单的题目，总体来说思路什么的都很简单，根据已知信息甚至可以直接暴力推。

观察样例可以发现每一个target中所包含的数字对应一个["Push"]，而每个不包含的对应一个["Push", "Pop"]，也就是“先进栈再直接出栈”。如果之后没有了（如示例3）就不再向栈中加入元素。

代码[Python3]

class Solution:
    def buildArray(self, target: List[int], n: int) -> List[str]:
        returnlist = []
        for i in range(1,n+1):
            if i in target:
                returnlist.append("Push")
            elif i > target[-1]:
                break
            else:
                returnlist.append("Push")
                returnlist.append("Pop")
        return returnlist

[10.16] 886. 可能的二分法@中等*

思路

深度优先搜索DFS，不过官方给的题解可读性有点差，之后找了个时间专门看才看懂。以及应该巩固一下DFS了，之后可能专门找一下对应的DFS相关的题目练习一下。

代码[Python3]

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        g = [[] for _ in range(n)]
        for x, y in dislikes:
            g[x - 1].append(y - 1) 
            g[y - 1].append(x - 1) #先把所有不喜欢的都加入字典
        color = [0] * n  # color[x] = 0 表示未访问节点 x

        def dfs(x: int, c: int) -> bool:
            '''
            先为对应颜色涂色，然后遍历g[x]即x不喜欢的所有y之后
            ①如果color[y]和color[x]不同，通过此节点
            ②color[y]未涂色而且dfs(y,-c)即给y涂色-c然后再按照这样递归下去（即深度优先搜索），涂完之后会递归回去
            如果都ok则通过all()函数，所有节点均为True，结果为True，否则为False
            '''
            color[x] = c
            return all(color[y] != c and (color[y] or dfs(y, -c)) for y in g[x])

        return all(c or dfs(i, 1) for i, c in enumerate(color))
        #c的意思是如果已经通过之前节点对节点c进行了涂色（即为1或者-1了），则不再验证了，因为已经刚才验证过了

[10.17] 904. 水果成篮@中等

解题思路

【不定长滑动窗口】根据题目要求设置前后两个位置作为滑动窗口（left, right或者i, j），前方right窗口不断滑动，当遇到水果种类达到三种的时候就：①计算上一步的时候的滑动窗口长度right-left；②比较刚才计算出的结果和目前为止最大的结果哪个更长；②移动后方left窗口，直至水果种类回到小于3的状态；

遇到的问题

在使用Python3进行计算的时候，想使用set()函数每次计算滑动窗口内的水果种类总数，结果发现这样会超时——也就是说set()的时间复杂度还是很高的，特别是当元素数量比较大的时候。后来更改为使用Counter()进行计算。

代码[Python3]

from collections import Counter
class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        maxfruits = 0
        if len(set(fruits)) <= 2:
            return len(fruits)
        #distance = 0
        i = 0
        j = 0
        cnt = Counter()
        while j<len(fruits):
            if len(cnt) <= 2:
                cnt[fruits[j]] += 1
                j+=1
            if len(cnt) <= 2 and (j==len(fruits)):
                maxfruits = max(maxfruits,j-i)
            if len(cnt) == 3:
                cnt[fruits[i]] -= 1
                if cnt[fruits[i]] <= 0:
                    cnt.pop(fruits[i])
                i+=1
                maxfruits = max(maxfruits,j-i)
        return maxfruits

[10.18] 902. 最大为 N 的数字组合@困难*

解题思路

一开始想的是：①小于当前位数的肯定随便加②等于当前位数的根据情况进行计算

也许思想是没问题的但是执行的时候太复杂加上变量太不清晰，把自己给弄自闭了。

最后选择学习动态规划的解法，也是为了增加自己的动态规划能力，我动态规划真不行。

正确思路

根据题目要求设置动态规划，由前n-1位时的结果可以推出前n位的结果。

比如n=578, digits=[1,3,5,7]根据思路，一步一步算：

n=5的结果 → n=57的结果 → n=578的结果

代码里还有部分思路，可以参考着一起看

代码[Python3]

class Solution:
    def atMostNGivenDigitSet(self, digits: List[str], n: int) -> int:
        m = len(digits)
        s = str(n) #n的string表示
        k = len(s) #n的位数
        dp = [[0, 0] for _ in range(k + 1)] 
        #生成n位数+1的表，其中dp[x][0]为比前i位小的数字数量，dp[x][1]为相等的
        dp[0][1] = 1 #初始化
        for i in range(1, k + 1):
            for d in digits:
                if d == s[i - 1]:
                    dp[i][1] = dp[i - 1][1] 
                    #如果某位相等则找上一位是否也相等，是则赋1
                elif d < s[i - 1]:
                    dp[i][0] += dp[i - 1][1]
                    #小于前i位的数的数量（比如n=578,digits=[1,3,5,7],dp[2][0]就是小于57的数）
                    #如果前一位相同（dp[i-1][1]==1，即比如为5x）则加上小于当前数量的（51，53，55）
                else:
                    break
            if i > 1:
                dp[i][0] += m + dp[i - 1][0] * m
                #小于前i位的数的数量（比如n=578,digits=[1,3,5,7],dp[2][0]就是小于57的数）
                #dp[2][0]为小于57的数，则dp[2][0]= dp[1][0](第一位小于5的)*len([1,3,5,7]) + m(m是上一轮计算出的，位数本身小于当前位数的数(本例中即为1,3,5,7))
                #实际上除了最后一个数组，前面的只为了作为转移方程转移到后面的计算
        return sum(dp[k]) #=总数

[10.19] 1700. 无法吃午餐的学生数量@简单

解题思路

暴力就行。

代码[Python3]

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        lenth = len(students)
        count = 0
        while True:
            if students[0] == sandwiches[0]:
                del(students[0])
                del(sandwiches[0])
                lenth -= 1
                count = 0
            else:
                students.append(students[0])
                del(students[0])
                count += 1
                if count == lenth:
                    return len(students)
            if len(students) == 0:
                return 0

[10.20] 779. 第K个语法符号@中等

解题思路

可以先写出前面几行，查找一下规律

1                           0
2                          0 1
3                        0 1 1 0
4                    0 1 1 0 1 0 0 1
5            0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0          

可以看出这很像一个二叉树，假设是n=5, k=10。则二进制bin(k-1)=1001相当于从第一行开始，1向右下选，0向左下选，进行n-1次选择：右左左右。

而根据异或的性质可以看出这其实就是上一位与bin(k-1)逐位进行异或。

代码[Python3]

class Solution:
    def kthGrammar(self, n: int, k: int) -> int:   
        flag = 0
        k-=1
        n-=1
        kList = list(bin(k)[2:])
        if k==0:
            return 0
        for i in kList:
            flag = flag^int(i)
        return flag

[10.21] 901. 股票价格跨度@中等

解题思路

这个题按理说有更好的解答方式，但是我暴力了。最终的结果是Python3超时了，但是使用C++写一样思路的代码的时候发现没有问题。

代价是代码速度超慢：

执行用时: 1140 ms < 11% C++

内存消耗: 86.9 MB < 6% C++

代码[C++]

class StockSpanner {
    int stock[10000];
    int index;
public:
    StockSpanner() {
        int stock[10000] = {0};
        int index = 0;
    }
    
    int next(int price) {
        stock[index] = price;
        index ++;
        int lowerDays = 0;
        int maxLowerDays = 0;
        for(int i=0;i<index;i++){
            if (stock[i] <= price){
                lowerDays ++;
            }
            if (stock[i] > price || i == index){
                lowerDays = 0;
                maxLowerDays = max(maxLowerDays,lowerDays);
            }
        }
        return lowerDays;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */