数学

1. 改变数组元素使数组元素都相等
2. Minimum Moves to Equal Array Elements II

Given a non-empty integer array, find the minimum number of moves required to make all array elements equal, where a move is incrementing a selected element by 1 or decrementing a selected element by 1.

You may assume the array's length is at most 10,000.
Example:
Input:
[1,2,3]
Output:2
Explanation:
Only two moves are needed (remember each move increments or decrements one element):
[1,2,3] => [2,2,3] => [2,2,2]

class Solution:
    def minMoves2(self, nums: List[int]) -> int:
        nums = sorted(nums)
        i, j = 0, len(nums)-1
        step = 0
        while i<j:
            step += nums[j]-nums[i]
            j -= 1
            i += 1
        return step

最少步数即所有元素集中到数组中位数所需的步数之和

位运算

基本原理
0s 表示一串 0，1s 表示一串 1。
x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1s
x ^ x = 0 x & x = x x | x = x
利用 x ^ 1s = ~x 的特点，可以将一个数的位级表示翻转；利用 x ^ x = 0 的特点，可以将三个数中重复的两个数去除，只留下另一个数。

1¹2 = 2
利用 x & 0s = 0 和 x & 1s = x 的特点，可以实现掩码操作。一个数 num 与 mask：00111100 进行位与操作，只保留 num 中与 mask 的 1 部分相对应的位。

01011011 &
00111100

00011000
利用 x | 0s = x 和 x | 1s = 1s 的特点，可以实现设值操作。一个数 num 与 mask：00111100 进行位或操作，将 num 中与 mask 的 1 部分相对应的位都设置为 1。

01011011 |
00111100

01111111
位与运算技巧

n&(n-1) 去除 n 的位级表示中最低的那一位 1。例如对于二进制表示 01011011，减去 1 得到 01011010，这两个数相与得到 01011010。

01011011 &
01011010

01011010
n&(-n) 得到 n 的位级表示中最低的那一位 1。-n 得到 n 的反码加 1，也就是 -n=~n+1。例如对于二进制表示 10110100，-n 得到 01001100，相与得到 00000100。

10110100 &
01001100

00000100
n-(n&(-n)) 则可以去除 n 的位级表示中最低的那一位 1，和 n&(n-1) 效果一样。

移位运算

n 为算术右移，相当于除以 2n，

n 为无符号右移，左边会补上 0。
<< n 为算术左移，相当于乘以 2n。

mask 计算
要获取 111111111，将 0 取反即可，~0。

要得到只有第 i 位为 1 的 mask，将 1 向左移动 i-1 位即可，1<<(i-1) 。例如 1<<4 得到只有第 5 位为 1 的 mask ：00010000。

要得到 1 到 i 位为 1 的 mask，(1<<i)-1 即可，例如将 (1<<4)-1 = 00010000-1 = 00001111。

要得到 1 到 i 位为 0 的 mask，只需将 1 到 i 位为 1 的 mask 取反，即 ~((1<<i)-1)。

231. Power of Two 二的数幂

Given an integer, write a function to determine if it is a power of two.

Example 1:
Input: 1
Output: true
Explanation: 20 = 1

class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n>0 and (n &(n-1))==0

利用 (n &(n-1)) 去除最低位，由此检验是不是2的幂，6666

计算两个数的二进制表示有多少位不同

461. Hamming Distance
     The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

def hammingDistance(self, x: int, y: int) -> int:
        return bin(x^y).count('1')

计算两个数之和

位计算：a^b 得到两个数各位之和，(a&b)<<1得到进位

class Solution:
    def getSum(self, a: int, b: int) -> int:
        if a==0:
            return b
        #mask = 0xffffffff

        # in Python, every integer is associated with its two's complement and its sign.
        # However, doing bit operation "& mask" loses the track of sign. 
        # Therefore, after the while loop, a is the two's complement of the final result as a 32-bit unsigned integer. 
        while b != 0:
            a, b = (a ^ b) & mask, ((a & b) << 1) & mask

        # a is negative if the first bit is 1
        if (a >> 31) & 1:
            return ~(a ^ mask)
        else:
            return a

计算数组中最长乘积

318. Maximum Product of Word Lengths
     Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:
Input: ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        n = len(words)
        ans = [0] * n
        for i in range(n):
            for l in set(words[i]):
                long = ord(l)-97
                ans[i] += 1<<long
        
        maxlen = 0
        for i in range(n):
            for j in range(i+1, n):
                if ans[i] & ans[j]==0:
                    maxlen = max(maxlen, len(words[i]) * len(words[j]))
        return maxlen 

优化：

def maxProduct(self, words):
        d = {}
        for w in words:
            mask = 0
            for c in set(w):
                mask |= (1 << (ord(c) - 97))
            d[mask] = max(d.get(mask, 0), len(w))
        return max([d[x] * d[y] for x in d for y in d if not x & y] or [0])

计算数组序列中1的个数（DP+找规律+位运算）

338/. Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.

Example 1:
Input: 2
Output: [0,1,1]

利用位运算， count(n) = count(n & (n-1)) + 1

class Solution:
    def countBits(self, num: int) -> List[int]:
        ans = [0] * (num+1)  
        for i in range(1,num+1):
            ans[i] = ans[i & (i-1)] + 1
        return ans

找规律：双击66666

 def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        res=[0]
        while len(res)<=num:
            res+=[i+1 for i in res]
        return res[:num+1]

牛客网 数学

1. 剪绳子

题目描述
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

解法一：动态规划思想，

class Solution:
    def cutRope(self, number):
        # write code here
        
        memo = [1] * (number+1)
        for i in range(2, number+1):
            for j in range(1, (i)//2 + 1):
                memo[i] = max(max(j, memo[j]) * max((i-j), memo[i-j]), memo[i])
        
        return memo[number]

解法二：作为一道数学问题，其实有规律可循
当绳子长度大于等于4时，设绳子长度为n，可分解为2，n-2，有：
f = 2(n-2) = 2n - 4 >= n
即分解后绳子长度一定大于原长，所以绳分解后的结果为 1， 2， 3
1.1 结果为1
则可以将上一段长度为3的绳子结合，重新分为 22, f(n) = 22(3 ** (number // 3 -1))
1.2 j结果为2
f(n) = 2 * ( 3 ** (number // 3))
1.3 结果为3
f(n) = 3 ** (number // 3)

巧用乘法原理

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.
Example 1:
Input:num1 = "2", num2 = "3"Output:"6"
Example 2:
Input:num1 = "123", num2 = "456"Output:"56088"
思路
123 * 456 = 3 * 456 + 20456+ 100 * 456
3456=......

逐位相乘后注意进位

class Solution {
public:
    string multiply(string num1, string num2) {
        int m=num1.size(), n=num2.size();
        if(m==0 || n==0 || num1=="0"||num2=="0")
            return "0";
        string s;
        vector<int> pos(m+n, 0);
        for(int i=m-1;i>=0;i--){  //注意相乘时应该从低位算起
            for(int j=n-1;j>=0;j--){
                int num = (num1[i]-'0') * (num2[j]-'0') + pos[i+j+1];
                pos[i+j+1]= num%10;
                pos[i+j] += num/10;
            }
        }
        for(auto x:pos){
            if(s == "" && x == 0)
                continue;
            s.push_back(x+'0');
        }
        if(s=="")
            return "0";
        return s;
    }
};

拼多多笔试

巧用位运算求不同数目值的公倍数

#include <bits/stdc++.h>
using namespace std;
#define LL long long
LL a[40];
int main(){
    LL N,M,ans=0,gd;
    scanf("%d%d",&N,&M);
    for(int i=1;i<=M;i++) {
        scanf("%d",&a[i-1]);
    }
    LL F=(1<<M)-1;
    for(int i=1;i<=F;i++){
        LL cnt=0;
        for(int j=0;j<M;j++){
            if(i&(1<<j)){
                cnt++;
                if(cnt==1) gd=a[j];
                else gd=gd*a[j]/(__gcd(a[j],gd));
            }
        }
        if(cnt&1){
            ans+=N/gd;
        }
        else ans-=N/gd;
    }
    printf("%d\n",ans);
    return 0;
}