Python - 深夜数据结构与算法之 位运算

这篇具有很好参考价值的文章主要介绍了Python - 深夜数据结构与算法之 位运算。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

目录

一.引言

二.位运算简介

1.二进制与十进制

2.左/右移

3.位运算

4.异或 XOR

5.指定位置的位运算

6.实战要点

三.经典算法实战

1.Number-1-of-bits [191]

2.Power-Of-Two [231]

3.Reverse-2-Bits [190]

4.N-Queens [51]

四.总结


一.引言

通常情况下我们计数采取十进制,这是因为日常生活中我们习惯了 0-9 的数字习惯,而对于计算机而言,其通过 0-1 的二进制方式表示和存储数字。本节开始我们学习二进制以及其对应的位运算。

二.位运算简介

1.二进制与十进制

机器中数字的表示和存储格式就是二进制,给定数字 0101 其等于从后向前:

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

即对应位置的索引作为 2 的指数,对应位置的值作为指数幂的系数,累加即为 10 进制的数字。

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

相反的,如果想把一个 10 进制的数字转换为 2 进制,则我们依次除 2 取余,把得到的数字反转即可得到其二进制。这里不好理解的话可以对照着上面 10 进制转 2 进制的公式再思考思考。上面的图片来自: wikihow,是一个很好玩的百科网站,大家可以去搜索你想了解的内容。

2.左/右移

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

左移右移就是把当前二进制数字向左或向右移动一个位置,空出来的位置补 0 ,被顶出去的位置就不要了。我们老式的计算机一般是采用 32 位表示,而新的计算机则都采用了 64 位表示。

3.位运算

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

- 按位或  有一个 1,则或出来就是 1

- 按位与  有一个 0 ,则与出来就是 0 

- 按位取反 0 变成 1,1 变成 0 

- 按位异或   相同为 0,不同为 1

以上位运算都是在两个二进制数字之间展开。

4.异或 XOR

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

这里 1s 代表全为 1,即把 0 取反 ~0。 后面两条定律使用的比较少,前面四条性质比较常用。

5.指定位置的位运算

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

上面给出了一些位运算常见的位置操作,用于我们处理对应位置的位数。 

6.实战要点

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

判断奇偶以及 /2 的常规操作,我们都可以改写为位运算的方式提高效率,除此之外通过 & 方法可以得到清除、得到最低位 1 的操作。

三.经典算法实战

1.Number-1-of-bits [191]

位1的个数: https://leetcode.cn/problems/number-of-1-bits/description/

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

◆ 题目分析

& 操作是, 1 & x = x,所以我们可以遍历 32 位数的每一位 & 1 的值,如果为 1 则说明该位为 1,则 cnt += 1,或者使用上面实战要点中 X = X & (X-1) 清零最低位 1 的操作,能清几次代表有几个 1。

◆ 1 & x = x

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        cnt = 0

        for i in range(32):
            if n & (1 << i):
                cnt += 1
        
        return cnt

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

 ◆ x & (x-1) 

class Solution(object):
    def hammingWeight(self, n):
        """
        :type n: int
        :rtype: int
        """
        cnt = 0

        while n:
            n = n & (n-1)
            cnt += 1
        
        return cnt

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

 n & (n-1) 的示意图可以参考上面的过程。

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

2.Power-Of-Two [231]

2的幂: https://leetcode.cn/problems/power-of-two/description/

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

◆ 题目分析

套用上面的 1 bits 方法,由于2的幂次一定只有 1 位有 1,所以判断 cnt 是否为 1 即可。也可以一直 % 2 并 / 2,看能不能一直除下去。

◆ x & (x-1)

class Solution(object):

    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n == 0:
            return False

        return n & (n-1) == 0

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

◆ x % 2 - x / 2

class Solution(object):

    def isPowerOfTwo(self, n):
        """
        :type n: int
        :rtype: bool
        """
        if n == 1:
            return True
        
        if n <= 0 or n % 2:
            return False
        
        return self.isPowerOfTwo(n / 2)

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

3.Reverse-2-Bits [190]

颠倒 2 进制: https://leetcode.cn/problems/reverse-bits/description/ 

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

◆ 题目分析

把 n 的 32 位,每一位拿出来再往后追加,类似于一位一位 reverse。

◆ x << 1

class Solution:
    # @param n, an integer
    # @return an integer
    def reverseBits(self, n):
        res = 0
        for i in range(32):
            # 有 1 就 1,没 1 就 0
            res = (res << 1) | (n & 1)
            n >>= 1
        return res

res << 1: 把最后一位空出来

n & 1: 0 是 0、1 是 1

|: 前面 res 部分不动,后面 0 是 0、1 是 1 

通过这三部分实现反转与追加。 

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

4.N-Queens [51]

N 皇后: https://leetcode.cn/problems/n-queens/description/ 

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

◆ 题目分析

老生常谈的问题了, 传统的办法我们是构造了 pie、na、row 三个 set 进行去重,学习了位运算后,我们也可以将棋盘按 45 度划分 2n-1 个对角线,这样 pie、na 就只需要位运算判重而不需要 set 了,提高了空间利用率和时间效率。

◆ DFS + Set

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """

        results = []
        # 行 左 右 是否可以放置
        cols = set()
        pie = set()
        na = set()

        def dfs(n, row, cur):
            if row >= n:
                results.append(cur)
            
            for col in range(n):
                if col in cols or (row + col) in pie or (row - col) in na:
                    continue
                
                # 判断有效
                cols.add(col)
                pie.add(row + col)
                na.add(row - col)

                dfs(n, row + 1, cur + [col])

                # 恢复状态
                cols.remove(col)
                pie.remove(row + col)
                na.remove(row - col)
        
        dfs(n, 0, [])
        return self.genResult(n, results)

    def genResult(self, n, results):
        return [[ '.' * i + 'Q' + (n - i - 1) * '.' for i in result] for result in results]

    def genResultV2(self, n, results):
        re = []
        for result in results:
            re.append([ '.' * i + 'Q' + (n - i - 1) * '.' for i in result])
        return re

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

◆ DFS + Simple Set

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """

        results = []

        def dfs(queue, diff, total):

            row = len(queue)
            if row == n:
                results.append(queue)
                return None
            
            for col in range(n):
                if col not in queue and row + col not in total and row - col not in diff:
                    dfs(queue + [col], diff + [row - col], total + [row + col])

        dfs([], [], [])
        return [[ '.' * i + 'Q' + (n - i - 1) * '.' for i in result] for result in results]


Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

◆ DFS + Bit

class Solution(object):

    def power_of_two(self, num):
        power = 0
        while num % 2 == 0:
            power += 1
            num = num / 2
        return power

    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        if n < 1:
            return []

        results = []

        def DFS(n, row, cols, pie, na, cur):
            if row >= n:
                results.append(cur)
                return

            # 得到当前所有空位
            bits = (~(cols | pie | na) & ((1 << n) - 1))

            while bits:
                p = bits & -bits  # 取最低位的 1
                bits = bits & (bits - 1)  # P 位置放置皇后
                DFS(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1, cur + [p])

        DFS(n, 0, 0, 0, 0, [])

        return [['.' * self.power_of_two(i) + 'Q' + (n - self.power_of_two(i) - 1) * '.' for i in result] for result in results]

这里 bits 以及一些递进的操作直接看容易懵,大家可以在 n=4 的情况下,打印每一次运算的 2 进制,感受下如何通过位运算求解,这里可以通过 bin() 方法获取二进制表示。

Python - 深夜数据结构与算法之 位运算,夜深人静写算法,Python,python,位运算,Bit

四.总结

位运算的解法和题目相对来说比较抽象,不理解的时候还是多转换为 2 进制数字,查看其演进的过程,更好的熟悉其推导过程。文章来源地址https://www.toymoban.com/news/detail-799662.html

到了这里,关于Python - 深夜数据结构与算法之 位运算的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【夜深人静学数据结构与算法 | 第一篇】KMP算法

    目录  前言:  KMP算法简介: 引入概念: 前缀后缀 前缀表: 简单例子: 暴力遍历: KMP算法:​  KMP算法难点: 总结: 本篇我们将详细的从理论层面介绍一下什么是KMP算法,相对应的力扣刷题专栏里也会有相对应的习题,欢迎各位前往阅读。           KMP算法是一种字符

    2024年02月08日
    浏览(70)
  • 【夜深人静学数据结构与算法 | 第十一篇】枚举算法

    目录 前言: 枚举算法: 优点: 枚举算法的种类: 枚举算法案例: 343. 整数拆分 - 力扣(LeetCode) 12. 整数转罗马数字 - 力扣(LeetCode) 总结: 本文我们将为大家介绍什么是枚举算法,以及枚举算法的优点,在后面我们也会为大家讲解几道枚举算法的经典例题,各位感兴趣的

    2024年02月13日
    浏览(52)
  • 【夜深人静学数据结构与算法 | 第十篇】动态规划

    目录 前言: 动态规划: 常见应用: 解题步骤:  动态规划的简化步骤: 案例: 509. 斐波那契数 - 力扣(LeetCode) 70. 爬楼梯 - 力扣(LeetCode) 62. 不同路径 - 力扣(LeetCode) 总结:         本文我们将为大家讲解一下动态规划的理论知识,并且会讲解几道力扣的经典例题。

    2024年02月11日
    浏览(53)
  • 【夜深人静学数据结构与算法 | 第三篇】 二叉树

    目录  前言:  二叉树: 二叉树的种类:  二叉树的存储方式: 1. 链式存储 2. 数组存储 二叉树的遍历方式 深度优先遍历 广度优先遍历 总结: 本文将会详细的介绍各种常见的树以及相对应的概念,存储方式,遍历方式。树是经典的数据结构,因此我们虽然不能做到手撕各

    2024年02月11日
    浏览(51)
  • 【夜深人静学数据结构与算法 | 第九篇】栈与队列

    目录 ​前言: 栈: 栈的实际应用:  队列: 队列的实际应用: 总结:         栈与队列是我们学习的两个经典的数据结构,这两个数据结构应用广泛,在计算机内有很多底层应用,而很多算法也是依靠栈和队列来实现的,因此我们要想学好数据结构与算法,就要学好栈与

    2024年02月15日
    浏览(45)
  • 【夜深人静学习数据结构与算法 | 第十二篇】动态规划——背包问题

      目录  前言:  01背包问题: 二维数组思路: 一维数组思路: 总结:       在前面我们学习动态规划理论知识的时候,我就讲过要介绍一下背包问题,那么今天我们就来讲解一下背包问题。 在这里我们只介绍 01背包 ,至于分组背包和混合背包这种的已经属于竞赛级别的

    2024年02月12日
    浏览(53)
  • 【夜深人静学数据结构与算法 | 第二篇】后缀(逆波兰)表达式

    目录 前言:  中缀表达式:  后缀表达式: 中缀表达式转后缀表达式: 后缀表达式计算结果: 总结:  计算机在计算四则运算的时候,由于括号以及运算优先级的存在,并不能够很好的处理所有的运算,为了处理这种情况,我们引入了后缀表达式来优化算法。         

    2024年02月13日
    浏览(58)
  • 【夜深人静学数据结构与算法 | 第四篇】手撕二叉树遍历

    目录 前言: 二叉树遍历方式: 手撕前中后序遍历(递归)的三大准备 深度优先搜索:  手撕前中后遍历(递归): 手撕前中后序遍历(迭代): 深度优先搜索: 总结:         今天我们将带领大家手撕二叉树的遍历,本篇会分别讲解深度优先搜索法和广度优先有搜索法下

    2024年02月09日
    浏览(51)
  • 【夜深人静学数据结构与算法 | 第七篇】时间复杂度与空间复杂度

    前言:  引入:  时间复杂度:  案例: 空间复杂度: 案例: TIPS:        总结:         今天我们将来介绍时间复杂度和空间复杂度,我们代码的优劣就是依靠这个在评判,以此为背景,我们诞生出了不少的经典思路:用时间换空间,用空间换取时间。而大多数同学

    2024年02月10日
    浏览(67)
  • 【数据结构】:实现顺序表各种基本运算的算法

    领会顺序表存储结构和掌握顺序表中各种基本运算算法设计。 编写一个程序sqlist.cpp,实现顺序表的各种基本运算和整体建表算法(假设顺序表的元素类型ElemType为char),并在此基础上设计一个主程序,完成如下功能: 初始化顺序表L 依次插入a,b,c,d,e元素 输出顺序表L 输出顺

    2024年02月07日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包