Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

2133-Jammy

发表文章数:226

首页 » 算法 » 正文

剑指 Offer 12. 矩阵中的路径

Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, k):
            if not 0 <= i < len(board) or not 0 <= j < len(board[0]) or board[i][j] != word[k]: return False
            if k == len(word) - 1: return True
            board[i][j] = ''
            res = dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)
            board[i][j] = word[k]
            return res

        for i in range(len(board)):
            for j in range(len(board[0])):
                if dfs(i, j, 0): return True
        return False

心得总结:在判断i,j边界的时候,用了语句:

if not 0 <= i < len(board) or not 0 <= j < len(board[0])

这样的写法是我之前没有写过的。要记住。

另外关于在矩阵中的游走代码:

dfs(i + 1, j, k + 1) or dfs(i - 1, j, k + 1) or dfs(i, j + 1, k + 1) or dfs(i, j - 1, k + 1)

这样的写法也是要学习的。
要注意最后要把走过的路,改回去。

剑指 Offer 13. 机器人的运动范围

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

def movingCount(self, m: int, n: int, k: int) -> int:

        def dfs(i, j):
            # 边界定义
            if not 0 <= i < m or not 0 <= j < n or (self.cal_sum(i) + self.cal_sum(j)) > k or (i, j) in visited: return 0
            visited.add((i, j))
            return 1 + dfs(i+1, j) + dfs(i, j+1)

        visited = set()
        return dfs(0, 0)
        
    def cal_sum(self, num):
        s = 0
        while num > 0:
            s += num % 10
            num = num // 10
        return s

心得总结:这里关于位数和的方法要会:

def cal_sum(self, num):
        s = 0
        while num > 0:
            s += num % 10
            num = num // 10
        return s

另外注意visted是一个set集合。走的路径是向下和向右,退出条件就是i,j过界,以及特殊的题目条件:位数和不大于k。

Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

class Solution:
    def movingCount(self, m: int, n: int, k: int) -> int:
        queue, visited = [(0, 0, 0, 0)], set()
        while queue:
            i, j, si, sj = queue.pop(0)
            if i >= m or j >= n or k < si + sj or (i, j) in visited: continue
            visited.add((i,j))
            queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))
            queue.append((i, j + 1, si, sj + 1 if (j + 1) % 10 else sj - 8))
        return len(visited)

注意这里的语句:

queue.append((i + 1, j, si + 1 if (i + 1) % 10 else si - 8, sj))

用到了一个概念:
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
心得总结:求解多少可能路径问题,一般要往BFS、DFS以及动态规划想。BFS一般用queue解决,DFS一般用递归解决。

剑指 Offer 65. 不用加减乘除做加法

写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

class Solution:
    def add(self, a: int, b: int) -> int:
        x = 0xffffffff
        a, b = a & x, b & x
        while b != 0:
            a, b = (a ^ b), (a & b) << 1 & x
        return a if a <= 0x7fffffff else ~(a ^ x)

心得总结:这道题,我复习时,可以直接想到如何通过位运算进行加法运算。但是关于越界问题,还是没太搞懂。
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

剑指 Offer 56 – I. 数组中数字出现的次数

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
这里补充了一个知识点,就是当是数据时候,and or 和 | & 结果是不一样的。后2个是位运算,前两个是与和或。
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

class Solution:
    def singleNumbers(self, nums: List[int]) -> List[int]:
        x, y, n, m = 0, 0, 0, 1
        for num in nums:         # 1. 遍历异或
            n ^= num
        while n & m == 0:        # 2. 循环左移,计算 m
            m <<= 1       
        for num in nums:         # 3. 遍历 nums 分组
            if num & m: x ^= num # 4. 当 num & m != 0
            else: y ^= num       # 4. 当 num & m == 0
        return x, y              # 5. 返回出现一次的数字


心得总结:之前做这题就没看懂,如今返回来看,更看不懂了。先放弃了。

剑指 Offer 39. 数组中出现次数超过一半的数字

Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

def majorityElement(self, nums: List[int]) -> int:
        votes = 0
        for num in nums:
            if votes == 0:
                mode = num
                votes += 1
            elif num == mode:
                votes += 1
            else: votes -= 1
        return mode

心得总结:一开始想到的就是排序法,哈希都没想起来。
后来看到答案想到了摩尔voting的方法。也可以快速想起来怎么做。

剑指 Offer 66. 构建乘积数组

Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

def constructArr(self, a: List[int]) -> List[int]:
        if not a: return []
        length = len(a)
        left, right = [1] * length, [1] * length
        left[0], right[-1] = 1, 1
        res = [1] * length
        for i in range(1, length):
            left[i] = left[i-1] * a[i-1]
        for i in range(length-2, -1, -1):
            right[i] = right[i+1] * a[i+1]
        for i in range(length):
            res[i] = left[i] * right[i]
        return res

心得总结:这个代码是leetcode官方的,就是把数组分成2半,然后相乘,这个方法我第一时间可以想到。另外K神上下三角的,我已经忘记具体的了。我就记得有一个上下三角的图,怎么画的已经忘了。

Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)
Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)

class Solution:
    def constructArr(self, a: List[int]) -> List[int]:
        b, tmp = [1] * len(a), 1
        for i in range(1, len(a)):
            b[i] = b[i - 1] * a[i - 1] # 下三角
        for i in range(len(a) - 2, -1, -1):
            tmp *= a[i + 1]            # 上三角
            b[i] *= tmp                # 下三角 * 上三角
        return b


拜师教育学员文章:作者:2133-Jammy, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《Leetcode 刷题必须Review 一(剑指offer 12 13 65 56 39 66)》 发布于2022-01-25

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录