头像

lh359149153


访客:432

离线:2天前



题目描述

运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中,则获取关键字的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字/值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

样例

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4


算法1

(python内置:dict + collections.OrderedDict) $O(1)$

一.dict:缓存k/v键值对(但无序)
二.OrderedDict:维护:实现更新最近访问的key
注:
1.OrderedDict是按照key的插入顺序排列(插入越后;就放越后)
2.popitem:last=True(默认)最后一个;last=False第一个

时间复杂度

参考文献

python 代码

class LRUCache:

    def __init__(self, capacity: int):
        #难点1.OrderedDict()用法:move_to_end函数;del函数;popitem函数
        self.od=OrderedDict()
        self.capacity=capacity


    def get(self, key: int) -> int:#查找
        if key in self.od:
            val=self.od[key]
            self.od.move_to_end(key) #用了就把它放到末尾
            return val
        else:
            return -1



    def put(self, key: int, value: int) -> None: #更新k/v
        #更新key到表头
        if key in self.od:
            #记得先删旧的再更新新的
            del self.od[key]
            #难点2.od写前面(它才是要维护的)
            self.od[key]=value
        else: #插入
            self.od[key]=value

            #判断
            if len(self.od)>self.capacity:
                #last=False 删除第一个
                self.od.popitem(last=False)


算法2

(字典+循环双端链表) $O(n^2)$

一.字典:存储节点
二.head+tail:维护双向链表(手写链表)
注:考点
1.add函数:加到链表尾部
2.remove函数:删除指定节点

时间复杂度

参考文献

python 代码

#难点1.创建双向链表
class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None


class LRUCache:

    def __init__(self, capacity: int):
        # 构建首尾节点, 使之相连
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head

        self.lookup = dict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key in self.lookup:
            node = self.lookup[key]
            self.remove(node)
            self.add(node)
            return node.val
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self.lookup:
            self.remove(self.lookup[key])
        if len(self.lookup) == self.max_len:
            # 把表头位置节点删除(说明最近的数据值)
            self.remove(self.head.next)
        #难点2.与法一不同,最后add(注意写法Node;add的node.key;配套)
        self.add(Node(key, value))

    # 删除链表节点
    def remove(self, node):
        del self.lookup[node.key]
        node.prev.next = node.next
        node.next.prev = node.prev

    #难点3.双向链表加点的写法(指针指向搞清楚)
    # 加在链表尾
    def add(self, node):
        self.lookup[node.key] = node
        #先暂存;因为不知道tail的前一个节点
        pre_tail = self.tail.prev
        node.next = self.tail
        self.tail.prev = node
        pre_tail.next = node
        node.prev = pre_tail





题目描述

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict,判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明:

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词

样例

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2:

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
  注意你可以重复使用字典中的单词。

示例 3:

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false



算法1

(动态规划) $O(n^2)$

一.转态方程:dp[i] 前i个字符能否拆分
二.状态计算:dp[j]=dp[i] and check(s[i+1,j])
即s[i+1,j]是否是wordDict里的元素

时间复杂度

参考文献

1.https://leetcode-cn.com/problems/word-break/solution/dan-ci-chai-fen-ju-jue-zhuang-xcong-jian-dan-de-xi/
2.https://leetcode-cn.com/problems/word-break/solution/dong-tai-gui-hua-ji-yi-hua-hui-su-zhu-xing-jie-shi/

python 代码

class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n=len(s)
        dp=[False]*(n+1)
        dp[0]=True

        for i in range(n):
            for j in range(i+1,n+1):
                #难点1.因为i从0开始
                if dp[i] and (s[i:j] in wordDict):
                    dp[j]=True
        return dp[-1]      

```



活动打卡代码 AcWing 840. 模拟散列表

模拟哈希表

一.插入+解决冲突(开放寻址法)

二.装载因子+动态扩容

#注:初始化+输入
n = int(input())
N = 200003
h = [float('inf')] * N 
flag = float('inf') #判断坑位是否有人



#注:初始化   
class Slot(object):
    def __init__(self, key, value):
        self.key, self.value = key, value
#一.插入
    UNUSED = None  # 没被使用过
    EMPTY = Slot(None, None)  # 使用却被删除过


    def __init__(self):
        self.h = [0]*8   # 开一个数组
        self.length = 0

    #装载因子
    def _load_factor(self):
        # load_factor 超过 0.8 重新分配
        return self.length / float(len(self.h))

    def __len__(self):
        return self.length

    def _hash(self, key):
        return abs(hash(key)) % len(self._table)

#二.寻找:开放寻址法
    def find(x):
        k = (x % N + N ) % N 
        while h[k] != flag and h[k] != x:
            k += 1
            if k == N:   #找一圈都不行回来接着找
                k = 0
        return k         #while结束条件:找到x或找到可以放x的位置

#三.重哈希

    def _rehash(self):
        old_table = self.h
        newsize = len(self.h) * 2

        self.length = 0

        for slot in old_table:
            #只把旧数组中有值的才插入
            if slot is not HashTable.UNUSED and slot is not HashTable.EMPTY:
                index = self._find_slot_for_insert(slot.key)
                self._table[index] = slot
                self.length += 1













题目描述

给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。

样例

输入: 1->2->3->3->4->4->5
输出: 1->2->5

算法1

(线性扫描) $O(n)$

1.构建虚拟头dummy
2.从前往后扫描:
1)找是否相同
2)找相同的有几个(区间:双指针)
注:是把重复了的都去除

时间复杂度

参考文献

python 代码

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


def deleteDuplicates( head):
    #构建虚拟头
    dummy = ListNode(-1)
    dummy.next = head
    a = dummy
    b = head
    while b and b.next:
        #难点1.理解是a.next和b.next的值
        if a.next.val != b.next.val:
            a = a.next
            b = b.next
        else:
            #难点2.while结束条件是a.next和b.next值不等
            while b and b.next and a.next.val == b.next.val:
                b = b.next
            a.next = b.next
            b = b.next
    return dummy.next


# 写一个测试用例
if __name__ == "__main__":

    nums = [1, 2, 2, 5, 6, 7, 8, 8, 9]

    #遍历链表
    for i in range(len(nums)):
        if i ==0:
            tmp = ListNode(nums[i])
            head = tmp
        else:
            node = ListNode(nums[i])
            #难点3.构建链表node
            tmp.next = node
            tmp = node

    l2 = deleteDuplicates(head)
    while l2:
        print(l2.val,end=" ")
        l2 = l2.next




基础算法(一)

排序

一.剑指offer

40.最小的K个数(Top k) (一串)

一.思路

核心考点:堆排序
1.注意:维护大根堆(因为max堆顶弹出);始终保证堆内k个最小
2.时间 o(nlogk)

二.python语法

1.导入:import heapq
2.函数使用:压入当前值:heapq.heappush;弹出最小值+压入当前值heapq.replace;弹出最小值heapq.heappop

40变形.最小的第k个数(一个)

一.思路

核心考点:快排(快选)
1.y总模板;(不同之处)多引入参数k、递归左or右 注:记得特判边界
2.时间o(nlogn)

35.数组中的逆序对

一.思路

核心考点:归并排序
1.归并:特判+确定分界点+递归+合并(比较、扫尾、物归原主)
2.难点:逆序对数量思考:三种情况:全左;全右;一左一右(res+=mid-i+1)

二.python语法

1.def与return配对使用

二.Leetcode高频

后续补充

二分+查找

一.剑指offer

4.二维数组查找

一.思路

核心考点:对象是二维
1.难点:二维数组有序–>从右上角开始找(注意先特判行;再求列;舍弃)
2.时间o(n^2) –> O(n+m) 一维

二.python语法

1.二维矩阵matrix
2.行数:rows = len(array);列数:cols = len(array[0])

11.旋转数组的最小值

一.思路

核心考点:需要预处理的二分+特判
旋转数组.png
1.预处理:去重(如上图红圈所示):n指针左移
2.满足二段性:二分(特判单增情况-直接返回[0];仔细考虑l r变化)
3.时间:o(n) 因为存在重复

53-I-在排序数组中查找数字

一.思路

核心考点:端点–>区间
排序数组查找.png 1.有序数组:二分
2.次数:即计算区间:右端点-左端点(求左;判断[l]?=k;存储l;求右;相减)

53-II-0-n-1中缺失的数字

一.思路

核心考点:二段性的选取+特判
1.递增数组:二分(仔细考虑l r )
2.while循环结束之后:特判 r++(若缺的是最后一位)

二分+查找的一些总结

核心考点:在一些地方变化之后的二分
1.预处理(e.g.去重)
2.特判(e.g.二分可以走完;但未必就是答案)

二.Leetcode高频

4.寻找两个有序数组的中位数

[ x ]349.两个数组的交集(set+哈希表)

7430894_1569830438206_2DED0BE4AF3760A39EADD3F7B142C0CE.png
后续再补充

位运算

一.剑指offer

15-二进制中1的个数

一.思路

核心考点:位运算两个常用操作
1.有符号数–>无符号数
2.常用操作:取个位(n&1);去个位(n>>1)

二.python语法

1.变为无符号数:python强行32位:n=n&0xFFFFFFFF

16-数值的整数次方

一.思路

核心考点:次方运算定义+二进制理解+特判
注:直接用for循环会超时
位运算次方.png

1.从次方运算定义出发+结合二进制位运算(把x^n 拆成x^2 和 x)
位运算推导.png
2.难点:指数<0,特判

二.Leetcode高频

位运算leetcode.png

[ X ]78-子集(位运算+DFS)

[ X ]421-数组中两个数的最大异或值(前缀树+异或)

数据结构(一)

链表

一.剑指offer

6-从尾到头打印链表

一.思路

核心考点:
1.先遍历(使用python的列表[ ]数据类型来存储)
2.再翻转([: :-1])

二.python语法

1.列表res=[ ]作为栈来使用,append
2.切片的几种学习:取最后一个元素[-1];取除了最后一个元素[ : -1];翻转[: : -1]

22-链表中倒数第k个结点

一.思路

核心考点:单链表不能“倒序”遍历–>要转换成正序
1.先遍历一次,计数链表长度n
2.转换:倒数k–>正数:n-k+1(注意下标从0开始)

二.链表语法

1.指针:但指向的值val?(return p 返回的是p节点的值?)
2.值:val存储当前值

24-反转链表

一.思路:

核心考点:反转:开一个前驱节点pre
1.初始化:cur从head开始;则pre在head前面为None (常用经验)
2.(做题要结合图理解)进行指针反转;记得先保存cur的next后续使用

25-合并两个或k个有序链表

一.思路:

核心考点:归并排序+不同之处(含有链表的指针next)
1.初始化:虚拟头节点dummy;当前尾节点cur
2.合并(cur.next赋;cur右移;L1/L2右移)+扫尾

二.python语法的使用

1.创建虚拟头节点的方法:dummy=ListNode(-1)
2.返回链表的写法:dummy.next

35-复杂链表的复制

一.思路:

核心考点:(一定要画图理解)多了random;考察对链表的理解
1.新建复制节点–>插入每个原节点后(新建np+给p赋(先存储)+更新p/np)
2.处理random(遍历)
3.串起np复制节点(操作:初始化虚头dummy/当前尾cur+给cur赋+更新cur/p)

二.python语法的使用

1.创建新的头节点:np=ListNode(p.val)

链表总结

1.常用操作:
1)打印:从尾到头;倒数K
2)反转:前驱节点
3)合并:虚拟头节点
4)复制:插入;指针变化
2.经验做法
1.新建虚拟头;新节点
2.链表常用四步:(先存next)赋值+更新两指针

二.Leetcode高频

链表leetcode.png

[ X ]3(链表中)两数相加 (初等数学)

[ X ]24-两两交换链表中的节点(虚拟头+递归)

二叉树

一.剑指offer

7.重建二叉树

一.思路:

核心考点:前序/中序性质(根节点的分布)+递归
1.前序确定根节点(第一个值)+中序索引确定左右子树长度(Python中index函数)
2.递归:不断在前中之间来回,确定“当前”根 (难点:切片的取值/端点)

二.python语法的使用

1.写法细节:前序遍历(数组)preorder ;一个值preorder[0];(以该值的)一个节点TreeNode(preorder[0])
2.index函数:返回某值的索引位置
3.python切片的包含关系:(注:下标从0开始)(含前;不含后)
[:n]第一项到第n项(不含n);[n:]第n+1项到最后一项(含n)

26.树的子结构

一.思路

核心考点:把字符串变成放到树中进行“匹配”
1.寻找(所有可能性),枚举:main
2.匹配(严格当前值),判断:part

二.实现

注:两次递归的不同之处
1.main函数:特判空+part成立True;否则,把2放入1的左or右子树继续找
2.part函数(如何匹配当前:匹配的细节):三种情况–>检查1 2的左/右完全相等(且)
树匹配总结:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/pi-pei-lei-er-cha-shu-ti-mu-zong-jie-by-z1m/

二叉树总结

一.常用操作
1.前/中/后序遍历;层序遍历
2.翻转,合并
二.定义理解

1.节点,叶子节点,度,深度
2.二叉搜索树,平衡树等
三.常考结合
1.dp 95/96 不同的二叉搜索树
2.栈 94 二叉树的中序遍历
3.bfs 层序遍历 从上到下打印
4.dfs 深度 平衡二叉树

二.Leetcode高频

二叉树leetcode.png
详见上一栏

堆leetcode.png

哈希表

哈希表leetcode.png

栈与队列

单调栈

一.思路

核心性质:给一个序列,求每个数,左边(右边),离它最近且比它小(大)的数

单调队列

一.思路

核心性质:对应题型:滑动窗口

基础算法(二)

DFS

一.剑指offer

二.Leetcode高频

[ ]46.全排列

012-矩阵中的路径

034-二叉树中和为某一值的路径

055-I-二叉树的深度

055 – II-平衡二叉树

BFS

一.剑指offer

13.机器人的运动范围

一.思路

核心考点:BFS(每次距离+1)+
(A)预处理1
1.get_sum函数:计算当前值的个+十位和
2.is_valid函数:判断当前点有效(在边界内+值<k)
(B)开始移动
1.特判
2.预处理2
1)标记状态(python set开一个元素集记录)
2)上下移动(难点1.向量表示)
3.开始搜索(难点2.BFS模板)
1)q <– 1
2)q为真:移动+赋值(用is_valid判断)+更新状态

二.Leetcode高频

032-I-从上往下打印二叉树

032-II-从上往下打印二叉树II

032-II-从上往下打印二叉树III

动态规划

一.剑指offer

19.正则表达式匹配

一.思路

核心考点:分情况讨论,‘’号的情况
核心思路:因为代表的是修改“前面”字符的情况,所以是根据“后面”(i+1,j+1等)的状态递推前面的情况
e.g.从后往前走,当遇到‘
’时,看前一个(j)与(i)关系,从而决定0次 or 多次
1.状态表示f[i][j]
即:集合s[i…],与集合p[j…],从i/j相匹配
二.状态计算 (分情况讨论)
1.p[j]是正常字符:s[i]==p[j]; dp[i][j]= dp[i+1][j+1]
2.p[j]是“.”:f[i][j]=f[i+1][j+1](跳过’.’)
3.p[j+1]是“”:分析’‘会代表的次数+’’前面的字符情况(最复杂)
1)0次,f[i][j]=f[i][j+2] (还要考虑j是否为“.”的情况)
2)>=1次,f[i+1][j]

二.Leetcode高频

三.Acwing

2.01背包问题

895.最长上升子序列

897.最长公共子序列

282.石子合并(区间DP)

动态规划总结

按照y总思路:对DP分解+画图

动态规划leetcode.png

回溯

46.全排列

笔试遇到但不太会的

字符串处理

字符串leetcode.png

回文(DP)

注:647与5类似;但先求所有子串个数;再求所有子串中的最长值

647.回文子串

一.思路

核心考点:转移方程 s[i]==s[j] and (j-i<2 or dp[i+1][j-1])
1.难点:边界j-i<2的思考
注:详细分析见下5

二.结合本题

1.简化max_len,答案变成统计res+=1
2.变化之处j–>j+1(j要取到;因为ij可以相同-True)

5.最长回文子串

一.思路

核心考点:动态规划
1.状态表示 dp[j][i]
1)集合:表示以i为起始下标,j为终点下标的是回文子串
2)性质:bool
2.状态计算
1.边界:j-i<3:dp[i][j]=True (结合’aa’‘aba’理解)
2.转移方程:dp[i][j]=(s[i]==s[j])and (dp[i+1][j-1])

二.模板/套路整理

1.初始化 dp(二维)
2.遍历:转移方程+特判(代入转移方程)
3.结合本题要求,返回相应/不同的值(本题max_len)
4.变化之处,有较多边界特判

214.最短回文串(KMP)

564.寻找最近的回文数

括号序列

20.有效的括号

一.思路

考点:栈/队列
有效括号.png
核心思想:有效括号的,部分子表达式仍然是有效括号–>(正是栈的操作)把最小括号对出栈+判空为真
1.出栈
2.优化:用哈希表搜索能否形成括号

二.python语法的使用

1.哈希表的建立和存储
字典:d = {‘a’:1,’b’:2,’c’:3} 冒号’:’表示映射

32.最长有效括号

考点:栈+前缀和

一.思路:

核心思想:
1.每个左括号对应的右括号是一定的
2.括号序列合法 <–> (等价于)所有前缀和>=0 and 总和等于0(数量相等)
注:这两条是括号序列常用经验

二.实现

1.实现:y总三种情况分析
2.完善:翻转+建立work函数
注:因为cnt>0时一直在继续做;当左括号>右括号时,没有破除条件
三.python语法
1.括号的变化:运用ASCII+异或
s=s[::-1]
s2+=chr(ord(s[i])^1)

并查集

后续再补充

数组的处理

39-数组中出现次数超过一半的数字

一.思路

核心考点:题眼:要找的该值次数超过一半(保证下文中cnt起码多1)
1.(y总-消耗的思想)三种情况:cnt=0,把当前值x赋进val;val==x,cnt+1(计数);val!=x,cnt-1(消耗)




最长有效括号

给定一个只包含 ‘(‘ 和 ‘)’ 的字符串,找出最长的包含有效括号的子串的长度。

样例1

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

算法1

(栈+前缀和) $O(n^2)$

一.核心思想:
1.每个左括号对应的右括号是一定的
2.括号序列合法 <–> (等价于)所有前缀和>=0 and 总和等于0(数量相等)
即:求满足上述性质的最长子序列

二.思路
1.双指针:i遍历;start 枚举当前这一段的开头
2.cnt前缀和 (设(=1;)=-1)
1)cnt<0: start=i, cnt=0
2)cnt>0: 继续做
3)cnt=0: [start,i]是一段合法序列,更新最大值
3.(重要理解)还要翻转括号序列(运用ASCII+异或)+从右往左再做一次(建一个work函数)
注:因为有情况e.g.((())) 一开始左括号多于右括号

时间复杂度

参考文献

python 代码

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        res=self.work(s)
        #难点1.如何翻转
        s=s[::-1]
        s2=''
        for i in range(len(s)):
            #同难点1
            s2+=chr(ord(s[i])^1)
        return max(res,self.work(s2))


    def work(self,s):
        #1.初始化
        res=0
        start,cnt=0,0
        i=0
        #2.带入y总分情况分析
        while i<len(s):
            if s[i]=='(':
                cnt+=1
            else:
                cnt-=1
                if cnt<0:
                    start=i+1
                    cnt=0
                elif cnt==0:
                    res=max(res,i-start+1)
            i+=1
        return res   

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



有效的括号

给定一个只包括 ‘(‘,’)’,’{‘,’}’,’[‘,’]’ 的字符串,判断字符串是否有效。

有效字符串需满足:

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

样例

输入: "()"
输出: true

输入: "()[]{}"
输出: true

输入: "([)]"
输出: false

算法1

(栈+哈希表) $O(n)$

一.思路
1.核心思想:有效括号的,部分子表达式仍然是有效括号–>恰为栈格式:把最小括号对出栈+判空为真
2.优化:哈希表寻找括号
二.实现
遍历括号序列s
1.若栈中已有值:
1)找出在哈希表中的映射(对应括号);弹出
2)否则:此括号序列无效
2.若栈中无值:入栈
3.返回not stack (bool)

时间复杂度

参考文献

python 代码

class Solution:
    def isValid(self, s: str) -> bool:
        #难点1.python哈希表存储方式
        #为什么要反着写;因为栈顶弹出+映射吗?
        dic={')':'(', ']':'[', '}':'{'}
        stack=[]

        for i in s:
            if stack and i in dic:
                #i在栈中 且 i映射也在
                if stack[-1]==dic[i]:
                    stack.pop()
                else:
                    return False
            else:
                stack.append(i)
        #难点2.有效时,栈空,真(bool)
        return not stack




回文子串的最大长度


算法1

(动态规划) $O(n^2)$

一.状态表示 dp[j][i]
1.集合:表示以i为起始下标,j为终点下标的是回文子串
2.性质:bool
二.状态计算
1.边界:j-i<3:dp[i][j]=True (结合’aa’‘aba’理解)
2.转移方程:dp[i][j]=(s[i]==s[j])and (dp[i+1][j-1])
三.结合本题
1.要返回的是最大子串
1)最大:更新max_len值
2)子串本身:python切片

时间复杂度

参考文献

python 代码

从Leetcode5.最长回文子串变形

def longestPalindrome(s):
        #特判
        if not s:
            return ''
        #初始化
        n=len(s)
        dp=[[False]*n for _ in range(n)]
        max_len=1
        idx=0

        #特判
        for i in range(n):
            dp[i][i]=True

        #难点1.让j先遍历到最右边
        for j in range(1,n):
            for i in range(j):
                if s[i]==s[j]:
                    #难点2.特判ij边界
                    if j-i<3:
                        dp[i][j]=True
                    else:
                        dp[i][j]=dp[i+1][j-1]
                #找到回文串;更新最大值
                if dp[i][j]:
                    cur_len=j-i+1
                    if max_len<cur_len:
                        max_len=cur_len
                        idx=i
        return max_len

if __name__=="__main__":
    while 1:
        s=input()
        if s == "END":
            break
        x=longestPalindrome(s)
        print(x)


算法2

(马拉车) $O(n)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla



一.状态表示 f[i][j]
1.集合s[i…],与集合p[j…],从i/j相匹配
二.状态计算 (划分子集)
1.p[j]是正常字符:f[i][j]==s[i]==s[j] 且 f[i+1][j+1]
2.p[j]是’.’,f[i][j]=f[i+1][j+1](跳过’.’)
3.p[j]是’‘:分析’‘会代表的次数+’‘前面的字符情况
注:思考核心:因为
代表的是修改“前面”字符的情况,所以是根据“后面”的状态递推前面的情况
e.g.从后往前走,当遇到时,看前一个(j)与(i)关系,从而决定0次 or 多次
1)0次,f[i][j]=f[i][j+2]
2)>=1次,f[i+1][j]

class Solution(object):
    def isMatch(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: bool
        """
        #初始化
        sn,pn=len(s),len(p)
        dp=[[False]*(pn+1) for _ in range(sn+1)] #bool


        dp[0][0]=True 

        #特判2.没看懂这种情况
        #难点1.
        for i in range(pn):
            if p[i]=="*" and dp[0][i-1]:
                dp[0][i+1]=True

        #开始匹配
        for i in range(sn):
            for j in range(pn):
                #情况1.正常字符
                if s[i]==p[j]:
                    dp[i+1][j+1]=dp[i][j]
                #情况2.(跳过'.')
                if p[j]==".":
                    dp[i+1][j+1]=dp[i][j]
                #情况3.
                #难点2.分析多种情况
                if p[j]=="*":
                    #0次
                    if s[i]!=p[j-1] and p[j-1]!=".":
                        dp[i+1][j+1]=dp[i+1][j-1]
                    #多次
                    else:
                        dp[i + 1][j + 1] = dp[i + 1][j] or dp[i][j + 1] or dp[i + 1][j - 1]

        return dp[sn][pn]



思路:广度优先搜索
(一)预处理1
1.get_sum函数:计算当前值的个+十位和
2.is_valid函数:判断当前点有效(在边界内+值<k)
(二)开始移动
1.特判
2.预处理2
1)标记状态(python set开一个元素集记录)
2)上下移动(向量表示)
3.开始搜索(BFS模板:用队遍历/存储走过的坐标 python deque)
1)q <– 1
2)q为真:移动+赋值(用is_valid判断)+更新状态

from collections import deque

class Solution(object):
    def movingCount(self, threshold, rows, cols):
        """
        :type threshold: int
        :type rows: int
        :type cols: int
        :rtype: int
        """
        if not rows or not cols:
            return 0

        #难点1.jiedian元素集用来存储状态(该坐标是否被访问)    
        jiedian=set()
        jiedian.add((0,0))

        #难点2.向量表示移动
        dx=[-1,0,1,0]
        dy=[0,1,0,-1]

        result=1
        #难点3.队的作用;遍历坐标(BFS模板)
        q=deque([(0,0)])
        while q:
            x,y=q.popleft()
            for i in range(4):
                xx=x+dx[i]
                yy=y+dy[i]
                #判断
                if self.get_valid(xx,yy,rows,cols,threshold) and (xx,yy) not in jiedian:
                    result+=1
                    #更新状态
                    q.append((xx,yy))
                    jiedian.add((xx,yy))

        return result

    def get_sum(self,num):
        res=0
        while num:
            res+=num%10
            num=num//10
        return res

    def get_valid(self,x,y,m,n,k):
        return 0<=x<m and 0<=y<n and self.get_sum(x)+self.get_sum(y)<=k