友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

微信

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

28. 数学

28.1. 典型技巧

28.1.1. 位运算

binar fundamentals

28.1.2. 最大公约数

\(gcd(max, min)=gcd(min,max mod min)\)

592. 分数加减运算

28.1.3. 通过减法求补数

最典型的例子： 476. 数字的补数。

28.1.4. 计算数组的汉明距离

在 461. 汉明距离 中，计算两个数的汉明距离，可以将两个数先异或，然后再使用 Brian Kernighan 算法，\(f(x)=x & (x−1)\)，求解包含的比特位数。

而在 477. 汉明距离总和 中，则可以通过求所有数字在一个指定比特位上的 1（c） 和 0（n - c） 数量，再相乘 \(c*(n-c)\)，就这个比特位上的汉明距离，最后把每一位的汉明距离相加，得到汉明距离的总和。

28.1.5. 1 和 2 与 3 异或就可以交替出现 1 和 2

0481 18

例题： 481. 神奇字符串

28.1.6. 通过异或可以找出只出现过一次的数字

136. 只出现一次的数字

28.1.7. 二进制最低位的 1

\(lowbit = num & -num\)

     s = 101100
    ~s = 010011
(~s)+1 = 010100 // 根据补码的定义，这就是 -s   效果：s 的最低 1 左侧取反，右侧不变
s & -s = 000100 // lowbit

260. 只出现一次的数字 III - 【图解】一张图秒懂！转换成 136！

28.1.8. 二进制转换成十进制

从二进制转换成十进制，可以通过“移位”+“相或”来完成。

137. 只出现一次的数字 II

28.1.9. 乘法原理

  1. 823. 带因子的二叉树

  2. 2316. 统计无向图中无法互相到达点对数

28.1.10. Boyer-Moore 投票算法

摩尔投票法：从零开始，相同就增加，不同就减少，循环往复。

  1. 169. 多数元素

  2. 229. 多数元素 II

28.1.11. 鸽巢原理

  1. 539. 最小时间差

28.1.12. 凸包问题

  1. 587. 安装栅栏

28.1.13. 矩阵旋转

  1. 593. 有效的正方形

28.1.14. ASCII 藏有大秘密

大小写转换的技巧

  • 大小写转换： letter ^ 0b10_0000(32) — 第六位会在 0 和 1 之间转换

  • 转换成小写： letter | 0b10_0000(32) — 第六位会直接转成 1

  • 转换成大写： letter & 0b1101 1111(-33) — 第六位会直接转成 0

  1. 709. 转换成小写字母

  2. 771. 宝石与石头

  3. 819. 最常见的单词

28.1.15. 上取整下取整转换公式

\[\left\lceil \frac{a}{b} \right\rceil = \left\lfloor \frac{a+b-1}{b} \right\rfloor\]

  1. 781. 森林中的兔子

28.1.16. 杨辉三角

  1. 799. 香槟塔

28.1.17. 三角形面积

一般情况下，平面上任意三点 \(A(x_1,y_1)\)， \(B(x_2,y_2)\)， \(P(x_3,y_3)\)，可以构成 \(\triangle APB\)。

\[\overrightarrow{PA} = (x_1-x_3,y_1-y_3)， \overrightarrow{PB} = (x_2-x_3,y_2-y_3)\]
\[S_{\triangle APB} = \frac{1}{2}|(x_1-x_3)(y_2-y_3)-(x_2-x_3)(y_1-y_3)|\]
0812 10

  1. 812. 最大三角形面积

28.1.18. 几何投影

  1. 836. 矩形重叠

28.2. 经典例题

  1. 29. Divide Two Integers

  2. 37. 解数独 — 用比特位标记使用和撤销标记真是太妙了！

  3. 67. Add Binary

  4. 78. 子集

  5. 89. Gray Code

  6. 90. 子集 II

  7. 136. 只出现一次的数字

  8. 137. 只出现一次的数字 II

  9. 187. 重复的DNA序列

  10. 190. Reverse Bits

  11. 191. Number of 1 Bits

  12. 201. 数字范围按位与

  13. 222. Count Complete Tree Nodes

  14. 231. 2 的幂

  15. 260. 只出现一次的数字 III

  16. [0266-palindrome-permutation]

  17. 268. Missing Number

  18. 287. 寻找重复数

  19. 318. 最大单词长度乘积

  20. [0320-generalized-abbreviation]

  21. 338. Counting Bits

  22. 342. 4的幂

  23. [0351-android-unlock-patterns]

  24. 371. Sum of Two Integers

  25. 389. 找不同

  26. 393. UTF-8 编码验证

  27. 397. 整数替换

  28. 401. 二进制手表

  29. 405. 数字转换为十六进制数

  30. [0411-minimum-unique-word-abbreviation]

  31. 421. 数组中两个数的最大异或值

  32. 461. 汉明距离

  33. [0464-can-i-win]

  34. [0465-optimal-account-balancing]

  35. 473. 火柴拼正方形

  36. 476. 数字的补数

  37. 477. 汉明距离总和

  38. [0491-non-decreasing-subsequences]

  39. 526. 优美的排列

  40. 638. 大礼包

  41. 645. 错误的集合

  42. 672. 灯泡开关 Ⅱ

  43. [0691-stickers-to-spell-word]

  44. 693. 交替位二进制数

  45. 698. Partition to K Equal Sum Subsets

  46. [0751-ip-to-cidr]

  47. [0756-pyramid-transition-matrix]

  48. 762. 二进制表示中质数个计算置位

  49. 779. 第K个语法符号

  50. [0782-transform-to-chessboard]

  51. 784. 字母大小写全排列

  52. [0805-split-array-with-same-average]

  53. [0810-chalkboard-xor-game]

  54. 832. 翻转图像

  55. [0847-shortest-path-visiting-all-nodes]

  56. 861. 翻转矩阵后的得分

  57. [0864-shortest-path-to-get-all-keys]

  58. 868. 二进制间距

  59. [0898-bitwise-ors-of-subarrays]

  60. [0943-find-the-shortest-superstring]

  61. [0957-prison-cells-after-n-days]

  62. 980. 不同路径 III

  63. [0982-triples-with-bitwise-and-equal-to-zero]

  64. [0995-minimum-number-of-k-consecutive-bit-flips]

  65. [0996-number-of-squareful-arrays]

  66. [1009-complement-of-base-10-integer]

  67. [1018-binary-prefix-divisible-by-5]

  68. [1066-campus-bikes-ii]

  69. [1125-smallest-sufficient-team]

  70. [1177-can-make-palindrome-from-substring]

  71. [1178-number-of-valid-words-for-each-puzzle]

  72. [1238-circular-permutation-in-binary-representation]

  73. [1239-maximum-length-of-a-concatenated-string-with-unique-characters]

  74. [1255-maximum-score-words-formed-by-letters]

  75. [1256-encode-number]

  76. [1284-minimum-number-of-flips-to-convert-binary-matrix-to-zero-matrix]

  77. [1310-xor-queries-of-a-subarray]

  78. [1318-minimum-flips-to-make-a-or-b-equal-to-c]

  79. [1342-number-of-steps-to-reduce-a-number-to-zero]

  80. 1349. 参加考试的最大学生数

  81. [1356-sort-integers-by-the-number-of-1-bits]

  82. [1371-find-the-longest-substring-containing-vowels-in-even-counts]

  83. [1386-cinema-seat-allocation]

  84. [1404-number-of-steps-to-reduce-a-number-in-binary-representation-to-one]

  85. [1434-number-of-ways-to-wear-different-hats-to-each-other]

  86. 1442. 形成两个异或相等数组的三元组数目

  87. 1457. 二叉树中的伪回文路径

  88. [1461-check-if-a-string-contains-all-binary-codes-of-size-k]

  89. [1486-xor-operation-in-an-array]

  90. [1494-parallel-courses-ii]

  91. [1506-find-root-of-n-ary-tree]

  92. [1521-find-a-value-of-a-mysterious-function-closest-to-target]

  93. [1525-number-of-good-ways-to-split-a-string]

  94. [1542-find-longest-awesome-substring]

  95. [1558-minimum-numbers-of-function-calls-to-make-target-array]

  96. [1595-minimum-cost-to-connect-two-groups-of-points]

  97. [1601-maximum-number-of-achievable-transfer-requests]

  98. [1611-minimum-one-bit-operations-to-make-integers-zero]

  99. [1617-count-subtrees-with-max-distance-between-cities]

  100. [1655-distribute-repeating-integers]

  101. [1659-maximize-grid-happiness]

  102. [1680-concatenation-of-consecutive-binary-numbers]

  103. [1681-minimum-incompatibility]

  104. [1684-count-the-number-of-consistent-strings]

  105. [1707-maximum-xor-with-an-element-from-array]

  106. [1720-decode-xored-array]

  107. [1723-find-minimum-time-to-finish-all-jobs]

  108. [1734-decode-xored-permutation]

  109. [1738-find-kth-largest-xor-coordinate-value]

  110. [1755-closest-subsequence-sum]

  111. [1763-longest-nice-substring]

  112. [1787-make-the-xor-of-all-segments-equal-to-zero]

  113. [1799-maximize-score-after-n-operations]

  114. [1803-count-pairs-with-xor-in-a-range]

  115. [1815-maximum-number-of-groups-getting-fresh-donuts]

  116. [1829-maximum-xor-for-each-query]

  117. [1835-find-xor-sum-of-all-pairs-bitwise-and]

  118. [1863-sum-of-all-subset-xor-totals]

  119. [1879-minimum-xor-sum-of-two-arrays]

  120. [1908-game-of-nim]

  121. [1915-number-of-wonderful-substrings]

  122. [1930-unique-length-3-palindromic-subsequences]

  123. [1938-maximum-genetic-difference-query]

  124. [1947-maximum-compatibility-score-sum]

  125. [1986-minimum-number-of-work-sessions-to-finish-the-tasks]

  126. [1994-the-number-of-good-subsets]

  127. [2002-maximum-product-of-the-length-of-two-palindromic-subsequences]

  128. [2032-two-out-of-three]

  129. [2035-partition-array-into-two-arrays-to-minimize-sum-difference]

  130. [2044-count-number-of-maximum-bitwise-or-subsets]

  131. [2128-remove-all-ones-with-row-and-column-flips]

  132. [2135-count-words-obtained-after-adding-a-letter]

  133. [2151-maximum-good-people-based-on-statements]

  134. [2152-minimum-number-of-lines-to-cover-points]

  135. [2157-groups-of-strings]

  136. [2172-maximum-and-sum-of-array]

  137. [2174-remove-all-ones-with-row-and-column-flips-ii]

  138. [2184-number-of-ways-to-build-sturdy-brick-wall]

  139. [2206-divide-array-into-equal-pairs]

  140. [2212-maximum-points-in-an-archery-competition]

  141. [2220-minimum-bit-flips-to-convert-number]

  142. [2247-maximum-cost-of-trip-with-k-highways]

  143. [2275-largest-combination-with-bitwise-and-greater-than-zero]

  144. [2305-fair-distribution-of-cookies]

  145. [2306-naming-a-company]

  146. [2317-maximum-xor-after-operations]

  147. [2322-minimum-score-after-removals-on-a-tree]

  148. [2351-first-letter-to-appear-twice]

  149. [2354-number-of-excellent-pairs]

  150. [2397-maximum-rows-covered-by-columns]

  151. [2401-longest-nice-subarray]

  152. [2403-minimum-time-to-kill-all-monsters]

  153. [2411-smallest-subarrays-with-maximum-bitwise-or]

  154. [2419-longest-subarray-with-maximum-bitwise-and]

  155. [2425-bitwise-xor-of-all-pairings]

  156. [2429-minimize-xor]

  157. [2433-find-the-original-array-of-prefix-xor]

  158. [2438-range-product-queries-of-powers]

  159. [2505-bitwise-or-of-all-subsequence-sums]

  160. [2506-count-pairs-of-similar-strings]

  161. [2527-find-xor-beauty-of-array]

  162. [2546-apply-bitwise-operations-to-make-strings-equal]

  163. [2564-substring-xor-queries]

  164. [2568-minimum-impossible-or]

  165. [2571-minimum-operations-to-reduce-an-integer-to-0]

  166. [2572-count-the-number-of-square-free-subsets]

  167. [2588-count-the-number-of-beautiful-subarrays]

  168. [2595-number-of-even-and-odd-bits]

  169. [2657-find-the-prefix-common-array-of-two-arrays]

  170. [2680-maximum-or]

  171. [2683-neighboring-bitwise-xor]

  172. [2708-maximum-strength-of-a-group]

  173. [2732-find-a-good-subset-of-the-matrix]

  174. [2741-special-permutations]

  175. [2749-minimum-operations-to-make-the-integer-zero]

  176. [2791-count-paths-that-can-form-a-palindrome-in-a-tree]

  177. [2802-find-the-k-th-lucky-number]

  178. [2835-minimum-operations-to-form-subsequence-with-target-sum]

  179. [2836-maximize-value-of-function-in-a-ball-passing-game]

  180. [2857-count-pairs-of-points-with-distance-k]

  181. [2859-sum-of-values-at-indices-with-k-set-bits]

  182. [2869-minimum-operations-to-collect-elements]

  183. [2871-split-array-into-maximum-number-of-subarrays]

  184. [2897-apply-operations-on-array-to-maximize-sum-of-squares]

  185. [2917-find-the-k-or-of-an-array]

  186. [2920-maximum-points-after-collecting-coins-from-all-nodes]

  187. [2932-maximum-strong-pair-xor-i]

  188. [2935-maximum-strong-pair-xor-ii]

  189. [2939-maximum-xor-product]

  190. [2959-number-of-possible-sets-of-closing-branches]

  191. [2980-check-if-bitwise-or-has-trailing-zeros]

  192. [2992-number-of-self-divisible-permutations]

  193. [2997-minimum-number-of-operations-to-make-array-xor-equal-to-k]

  194. [3003-maximize-the-number-of-partitions-after-operations]

  195. [3007-maximum-number-that-sum-of-the-prices-is-less-than-or-equal-to-k]

  196. [3011-find-if-array-can-be-sorted]

  197. [3022-minimize-or-of-remaining-elements-using-operations]

  198. [3064-guess-the-number-using-bitwise-questions-i]

  199. [3068-find-the-maximum-sum-of-node-values]

  200. [3094-guess-the-number-using-bitwise-questions-ii]

  201. [3095-shortest-subarray-with-or-at-least-k-i]

  202. [3097-shortest-subarray-with-or-at-least-k-ii]

  203. [3108-minimum-cost-walk-in-weighted-graph]

  204. [3116-kth-smallest-amount-with-single-denomination-combination]

  205. [3117-minimum-sum-of-values-by-dividing-array]

  206. [3133-minimum-array-end]

  207. [3141-maximum-hamming-distances]

  208. [3145-find-products-of-elements-of-big-array]

  209. [3149-find-the-minimum-cost-array-permutation]

  210. [3154-find-number-of-ways-to-reach-the-k-th-stair]

  211. [3158-find-the-xor-of-numbers-which-appear-twice]

  212. [3171-find-subarray-with-bitwise-or-closest-to-k]

  213. [3173-bitwise-or-of-adjacent-elements]

  214. [3181-maximum-total-reward-using-operations-ii]

  215. [3191-minimum-operations-to-make-binary-array-elements-equal-to-one-i]

  216. [3199-count-triplets-with-even-xor-set-bits-i]

  217. [3209-number-of-subarrays-with-and-value-of-k]

  218. [3211-generate-binary-strings-without-adjacent-zeros]

  219. [3215-count-triplets-with-even-xor-set-bits-ii]

  220. [3226-number-of-bit-changes-to-make-two-integers-equal]

  221. [3276-select-cells-in-grid-with-maximum-score]

  222. [3283-maximum-number-of-moves-to-kill-all-pawns]

  223. [3287-find-the-maximum-sequence-value-of-array]

  224. [3304-find-the-k-th-character-in-string-game-i]

  225. [3307-find-the-k-th-character-in-string-game-ii]

  226. [3309-maximum-possible-number-by-binary-concatenation]

  227. [3314-construct-the-minimum-bitwise-array-i]

  228. [3315-construct-the-minimum-bitwise-array-ii]

  229. [3344-maximum-sized-array]

  230. [3370-smallest-number-with-all-set-bits]

  231. [3376-minimum-time-to-break-locks-i]

  232. [3393-count-paths-with-the-given-xor-value]

  233. [3435-frequencies-of-shortest-supersequences]

  234. [3444-minimum-increments-for-target-multiples-in-an-array]

  235. [3495-minimum-operations-to-make-array-elements-zero]

  236. [3513-number-of-unique-xor-triplets-i]

  237. [3514-number-of-unique-xor-triplets-ii]

  238. [3530-maximum-profit-from-valid-topological-order-in-dag]

  239. [3533-concatenated-divisibility]

28.3. 参考资料

  1. 分享｜从集合论到位运算，常见位运算技巧分类总结！

← Previous: Greedy Algorithms 贪心算法 | ↑ Up: LeetCode 解题笔记 | Next: 1. 两数之和 →