0712学习 agile Posted on Jul 12 2023 面试 leetcode学习 - 剑指 Offer 15. 二进制中 1 的个数 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 '1' 的个数（也被称为 汉明重量).）。 提示： 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。 在 Java 中，编译器使用 二进制补码 记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。 输入必须是长度为 32 的 二进制串 。 ---  --- ```C# public int HammingWeight(uint n) { var result = 0; while (n != 0) { if ((n & 1) == 1) { result++; } n >>= 1; } return result; } public int HammingWeight2(uint n) { var result = 0; while (n != 0) { result++; n &= (n - 1); } return result; } ``` --- - 剑指 Offer 65. 不用加减乘除做加法 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。 Q ： 若数字a 和 b 中有负数，则变成了减法，如何处理？ A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。 ---  --- ```C# public int Add(int a, int b) { while (a != 0 && b != 0) { var c = a ^ b; b = (a & b) << 1; a = c; } return a != 0 ? a : b; } ``` --- [](https://tools.nxcloud.club:12500/image/0vvO) --- - 剑指 Offer 56 - I. 数组中数字出现的次数 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 限制： 2 <= nums.length <= 10000 ---  --- ```C# public int[] SingleNumbers(int[] nums) { var x = 0; var y = 0; int a = 0; var m = 1; foreach (var t in nums) { a ^= t; } while ((a & m) == 0)// m 循环左移一位，直到 a & m ！= 0 { m >>= 1; } foreach (var num in nums) { // 若 num & m != 0 , 划分至子数组 1 ，执行遍历异或 if ((num & m) != 0) { x ^= num; }// 若 num & m == 0 , 划分至子数组 2 ，执行遍历异或 else { y ^= num; } } return new[] { x, y }; } ``` --- - 剑指 Offer 56 - II. 数组中数字出现的次数 II 在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。 ---  ```C# public int SingleNumbers2(int[] nums) { int[] orders = new int[32]; foreach (var num in nums) { var index = 0; var t = num; while (t != 0) { if ((t & 1) == 1) { orders[index]++; } t >>= 1; index++; } } var result = 0; var temp = 1; for (var i = 0; i < orders.Length; i++) { orders[i] %= 3; if (orders[i] == 1) { result |= temp; } temp <<= 1; } return result; } ``` --- 状态机实现 ---      --- ```C# public int SingleNumbers3(int[] nums) { var one = 0; var two = 0; foreach (var num in nums) { one = (one ^ num) & ~two; two = (two ^ num) & ~one; } return one; } ``` --- - 剑指 Offer 39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。限制： 1 <= 数组长度 <= 50000   --- ```C# public int MajorityElement(int[] nums) { var candidate = nums[0]; var count = 1; for (int i = 1; i < nums.Length; i++) { if (count == 0) { candidate = nums[i]; } if (candidate != nums[i]) { count--; } else { count++; } } return candidate; } ``` --- - 剑指 Offer 66. 构建乘积数组 给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。 示例: 输入: [1,2,3,4,5] 输出: [120,60,40,30,24] 提示： 所有元素乘积之和不会溢出 32 位整数 a.length <= 100000 --- [](https://tools.nxcloud.club:12500/image/0w2G) --- ```C# public int[] ConstructArr(int[] a) { if (a.Length <= 0) { return Array.Empty<int>(); } var left = new int[a.Length]; var right = new int[a.Length]; left[0] = 1; right[a.Length - 1] = 1; for (int i = 1; i < a.Length; i++) { left[i] = a[i - 1] * left[i - 1]; right[a.Length - i - 1] = a[a.Length - i] * right[a.Length - i]; } for (int i = 0; i < a.Length; i++) { left[i] *= right[i]; } return left; } ``` --- --- [位运算介绍](https://algo.itcharge.cn/09.Algorithm-Base/06.Bit-Operation/01.Bit-Operation/) <table><thead><tr><th>运算符</th><th>描述</th><th>规则</th></tr></thead><tbody><tr><td><code>&</code></td><td>按位与运算符</td><td>只有对应的两个二进位都为 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="47"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.507ex" role="img" focusable="false" viewBox="0 -666 500 666" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="31" xlink:href="#MJX-TEX-N-31"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math></mjx-assistive-mml></mjx-container> 时，结果位才为 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="48"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.507ex" role="img" focusable="false" viewBox="0 -666 500 666" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="31" xlink:href="#MJX-TEX-N-31"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math></mjx-assistive-mml></mjx-container>。</td></tr><tr><td><code>|</code></td><td>按位或运算符</td><td>只要对应的两个二进位有一个为 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="49"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.507ex" role="img" focusable="false" viewBox="0 -666 500 666" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="31" xlink:href="#MJX-TEX-N-31"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math></mjx-assistive-mml></mjx-container> 时，结果位就为 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="50"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.507ex" role="img" focusable="false" viewBox="0 -666 500 666" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="31" xlink:href="#MJX-TEX-N-31"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math></mjx-assistive-mml></mjx-container>。</td></tr><tr><td><code>^</code></td><td>按位异或运算符</td><td>对应的两个二进位相异时，结果位为 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="51"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.507ex" role="img" focusable="false" viewBox="0 -666 500 666" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="31" xlink:href="#MJX-TEX-N-31"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math></mjx-assistive-mml></mjx-container>，二进位相同时则结果位为 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="52"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.557ex" role="img" focusable="false" viewBox="0 -666 500 688" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="30" xlink:href="#MJX-TEX-N-30"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math></mjx-assistive-mml></mjx-container>。</td></tr><tr><td><code>~</code></td><td>取反运算符</td><td>对二进制数的每个二进位取反，使数字 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="53"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.507ex" role="img" focusable="false" viewBox="0 -666 500 666" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="31" xlink:href="#MJX-TEX-N-31"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math></mjx-assistive-mml></mjx-container> 变为 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="54"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.557ex" role="img" focusable="false" viewBox="0 -666 500 688" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="30" xlink:href="#MJX-TEX-N-30"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math></mjx-assistive-mml></mjx-container>，<mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="55"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.557ex" role="img" focusable="false" viewBox="0 -666 500 688" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="30" xlink:href="#MJX-TEX-N-30"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math></mjx-assistive-mml></mjx-container> 变为 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="56"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.507ex" role="img" focusable="false" viewBox="0 -666 500 666" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="31" xlink:href="#MJX-TEX-N-31"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>1</mn></math></mjx-assistive-mml></mjx-container>。</td></tr><tr><td><code><<</code></td><td>左移运算符</td><td>将二进制数的各个二进位全部左移若干位。<code><<</code> 右侧数字指定了移动位数，高位丢弃，低位补 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="57"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.557ex" role="img" focusable="false" viewBox="0 -666 500 688" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="30" xlink:href="#MJX-TEX-N-30"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math></mjx-assistive-mml></mjx-container>。</td></tr><tr><td><code>>></code></td><td>右移运算符</td><td>对二进制数的各个二进位全部右移若干位。<code>>></code> 右侧数字指定了移动位数，低位丢弃，高位补 <mjx-container jax="SVG" tabindex="0" ctxtmenu_counter="58"><svg xmlns="http://www.w3.org/2000/svg" width="1.131ex" height="1.557ex" role="img" focusable="false" viewBox="0 -666 500 688" xmlns:xlink="http://www.w3.org/1999/xlink" aria-hidden="true"><g stroke="currentColor" fill="currentColor" stroke-width="0" transform="scale(1,-1)"><g data-mml-node="math"><g data-mml-node="mn"><use data-c="30" xlink:href="#MJX-TEX-N-30"></use></g></g></g></svg><mjx-assistive-mml unselectable="on" display="inline"><math xmlns="http://www.w3.org/1998/Math/MathML"><mn>0</mn></math></mjx-assistive-mml></mjx-container>。</td></tr></tbody></table> ### 位运算的常用操作总结 <table><thead><tr><th>功 能</th><th>位运算</th><th>示例</th></tr></thead><tbody><tr><td><strong>去掉最后一位</strong></td><td><code>x >> 1</code></td><td><code>101101 -> 10110</code></td></tr><tr><td><strong>在最后加一个 <code>0</code></strong></td><td><code>x << 1</code></td><td><code>101101 -> 1011010</code></td></tr><tr><td><strong>在最后加一个 <code>1</code></strong></td><td><code>(x << 1) + 1</code></td><td><code>101101 -> 1011011</code></td></tr><tr><td><strong>把最后一位变成 <code>1</code></strong></td><td><code>x | 1</code></td><td><code>101100 -> 101101</code></td></tr><tr><td><strong>把最后一位变成 <code>0</code></strong></td><td><code>x | 1 - 1</code></td><td><code>101101 -> 101100</code></td></tr><tr><td><strong>最后一位取反</strong></td><td><code>x ^ 1</code></td><td><code>101101 -> 101100</code></td></tr><tr><td><strong>把右数第 <code>k</code> 位变成 <code>1</code></strong></td><td><code>x | (1 << (k - 1))</code></td><td><code>101001 -> 101101, k = 3</code></td></tr><tr><td><strong>把右数第 <code>k</code> 位变成 <code>0</code></strong></td><td><code>x & ~(1 << (k - 1))</code></td><td><code>101101 -> 101001, k = 3</code></td></tr><tr><td><strong>右数第 <code>k</code> 位取反</strong></td><td><code>x ^ (1 << (k - 1))</code></td><td><code>101001 -> 101101, k = 3</code></td></tr><tr><td><strong>取末尾 <code>3</code> 位</strong></td><td><code>x & 7</code></td><td><code>1101101 -> 101</code></td></tr><tr><td><strong>取末尾 <code>k</code> 位</strong></td><td><code>x & 15</code></td><td><code>1101101 -> 1101, k = 4</code></td></tr><tr><td><strong>取右数第 <code>k</code> 位</strong></td><td><code>x >> (k - 1) & 1</code></td><td><code>1101101 -> 1, k = 4</code></td></tr><tr><td><strong>把末尾 <code>k</code> 位变成 <code>1</code></strong></td><td><code>x | (1 << k - 1)</code></td><td><code>101001 -> 101111, k = 4</code></td></tr><tr><td><strong>末尾 <code>k</code> 位取反</strong></td><td><code>x ^ (1 << k - 1)</code></td><td><code>101001 -> 100110, k = 4</code></td></tr><tr><td><strong>把右边连续的 <code>1</code> 变成 <code>0</code></strong></td><td><code>x & (x + 1)</code></td><td><code>100101111 -> 100100000</code></td></tr><tr><td><strong>把右边起第一个 <code>0</code> 变成 <code>1</code></strong></td><td><code>x | (x + 1)</code></td><td><code>100101111 -> 100111111</code></td></tr><tr><td><strong>把右边连续的 <code>0</code> 变成 <code>1</code></strong></td><td><code>x | (x - 1)</code></td><td><code>11011000 -> 11011111</code></td></tr><tr><td><strong>只保留右边连续的 <code>1</code></strong></td><td><code>(x ^ (x + 1)) >> 1</code></td><td><code>100101111 -> 1111</code></td></tr><tr><td><strong>去掉右边起第一个 <code>1</code> 的左边</strong></td><td><code>x & (x ^ (x - 1))</code> 或 <code>x & (-x)</code></td><td><code>100101000 -> 1000</code></td></tr><tr><td><strong>从右边开始，把最后一个 <code>1</code> 改写成 <code>0</code></strong></td><td><code>x & (x - 1)</code></td><td><code>100101000 -> 100100000</code></td></tr></tbody></table> ----------------------------------------------- 0714学习 0711学习