本文主要是介绍JS/TS算法---状态压缩，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

位运算

位运算符

• '&'(与)，有0则0
• '|'(或)，有1则1
• '^'(异或) ，相同为0，不同为1-----------位运算中常用
• '~'(按位取反) ，有1为0，有0为1
• '<<' (左移)，先求该数的补码，再向左移动右边的位数，空位补0，最高位丢弃，最后将移动后的二进制数转为十进制数
• '>>' (右移)，先求该数的补码，再向右移动右边的位数，最高位为0，空位补0，最高位是1，空位补1，最后将移动后的二进制数转为十进制数
• '>>>'(无符号右移)，先求该数的补码，再向右移动右边的位数，空位补0，最高位丢弃，最后将移动后的二进制数转为十进制数

原码(-100)：1110 0100
      反码：1001 1011(符号位不变，其他位取反)
      补码：1001 1100(反码+1，1为二进制的)
原码(9)：0000 1001--------------->正数的原、反、补码是一样的
   反码：0000 1001
   补码：0000 1001
    
左移：将-100左移三位是：-32
          |1 0 0 1  1 1 0 0|
       1 |0 0 1 1  1 0 0 0|------->左移一位 
    1 0 |0 1 1 1  0 0 0 0|------->左移一位 
  1 0 0|1 1 1 0  0 0 0 0|------->左移一位            
       |左移三位后的数的补码
    补码：1 1 1 0  0 0 0 0(被左移的数为负数)
    反码：1 1 0 1  1 1 1 1---------------->补码求原码，给补码-1 
    原码：1 0 1 0  0 0 0 0------->左移三位的数为-32
    
右移：将-100右移三位是：
             |1 0 0 1  1 1 0 0|
          1 |1 0 0  1 1 1 0|0------------->右移一位
       1 1 |1 0  0 1 1 1|0 0------------->右移一位
    1 1 1 |1  0 0 1 1|1 0 0------------>右移一位 
      右移三位的数     |----->再求它的反码---原码就是要求的数
          | 原数的补码  |
    
无符号右移：将-100右移三位是：    
             |1 0 0 1  1 1 0 0|
           0|1 0 0  1 1 1 0|0------------->右移一位
        0 0|1 0  0 1 1 1|0 0------------->右移一位
     0 0 0|1  0 0 1 1|1 0 0------------>右移一位 
      右移三位的数     |----->再求它的反码---原码就是要求的数
          | 原数的补码      |       

左移，右移的求法(针对于正数)：

左移<<:给原数乘以2的移动次数幂 100<<3 是 100*2^3=800

右移>>:给原数除以2的移动次数幂 100>>3 是 100/2^3=12

leetcode题精选

[169] 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3]

输出: 3

示例 2:

输入: [2,2,1,1,1,2,2]

输出: 2

这道题使用了Moore Voting算法，即摩尔投票算法求众数，对于求众数的问题复杂度降到了惊人的时间O(n)，空间O(1)。

算法思想是：设定一个候选者，每出现相同的元素计数器+1，否则-1。当计数器为0时，说明当前元素与候选者出现次数相同，更换候选者为当前元素。遍历完数组时当前的候选者即为所求众数。

var majorityElement = function(nums) {
  let res = nums[0];
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (count === 0) {
      res = nums[i];
      count++;
    } else {
      res === nums[i] ? count++ : count--;
    }
  }
  return res;
};

[136] 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

根据题目，我们很直观的想出：可以利用hash表的方式存储第一次得到的值，之后每次查询hash表看是否有相同的值，若有则删除。遍历结束后hash表中剩下的值即为所求。

这样做时间复杂度O(n)，空间复杂度O(n)。

var singleNumber = function(nums) {
  const hash = {};
  for (let i = 0; i < nums.length; i++) {
    if (hash[nums[i]] === undefined) {
      hash[nums[i]] = nums[i];
    } else {
      Reflect.deleteProperty(hash, nums[i]);
    }
  }
  return hash[Reflect.ownKeys(hash)[0]];
};

当然也可以利用排序后的数组相邻的值若不同则可得唯一性来解，这样的时间复杂度O(nlgn)，空间复杂度O(1)。这里就不多说了。

但由于题目要求时间复杂度O(n)，空间复杂度O(1)，因此不能使用排序算法，也不能使用hash-table。

本题使用二进制异或的性质来完成：两个数字异或 a^b 是将 a 和 b 的二进制每一位进行运算，如果同一位的数字相同则为0，不同则为1。

var singleNumber = function(nums) {
  let res = 0;
  for (let i = 0; i < nums.length; i++) {
    res = res ^ nums[i];
  }
  return res;
};

[187] 重复的DNA序列

DNA序列 由一系列核苷酸组成，缩写为 'A', 'C', 'G' 和 'T'.。

例如，"ACGAATTCCG" 是一个 DNA序列 。
在研究 DNA 时，识别 DNA 中的重复序列非常有用。

给定一个表示 DNA序列 的字符串 s ，返回所有在 DNA 分子中出现不止一次的 长度为 10 的序列(子字符串)。你可以按 任意顺序 返回答案。

示例 1：

输入：s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出：["AAAAACCCCC","CCCCCAAAAA"]
示例 2：

输入：s = "AAAAAAAAAAAAA"
输出：["AAAAAAAAAA"]

子区间----一下联想到滑动窗口和哈希表的方法

方法一：哈希表

• 我们可以用一个哈希表统计 s 所有长度为 10 的子串的出现次数，返回所有出现次数超过 10的子串。
• 代码实现时，可以一边遍历子串一边记录答案，为了不重复记录答案，我们只统计当前出现次数为 2的子串。

function findRepeatedDnaSequences(s: string): string[] {
	const res = [];
    const map = new Map();
	for(let i = 0; i <= s.length-10; i++) {
        const sub = s.slice(i,i+10);
        map.set(sub,(map.get(sub)||0)+1)  //次数加一，没有设为1

        if(map.get(sub)===2){
            res.push(sub);
        }
    } 
    return res;
};

复杂度分析

时间复杂度：O(NL)，其中 N 是字符串s 的长度，L=10 即目标子串的长度。

空间复杂度：O(NL)。

方法二：哈希表 + 滑动窗口 + 位运算

由于s中只含有4种字符，我们可以将每个字符用2个比特表示，即：

A 表示为二进制00；
C 表示为二进制01；
G 表示为二进制10；
T 表示为二进制11。

如此一来，一个长为 10 的字符串就可以用 20 个比特表示，而一个 int 整数有 32 个比特，足够容纳该字符串，因此我们可以将 s 的每个长为 10 的子串用一个int整数表示。

注意到上述字符串到整数的映射是一一映射，每个整数都对应着一个唯一的字符串，因此我们可以将方法一中的哈希表改为存储每个长为 10 的子串的整数表示。

如果我们对每个长为 10 的子串都单独计算其整数表示，那么时间复杂度仍然和方法一一样为 O(NL)。为了优化时间复杂度，我们可以用一个大小固定为 10 的滑动窗口来计算子串的整数表示。设当前滑动窗口对应的整数表示为 x，当我们要计算下一个子串时，就将滑动窗口向右移动一位，此时会有一个新的字符进入窗口，以及窗口最左边的字符离开窗口，这些操作对应的位运算，按计算顺序表示如下：

• 滑动窗口向右移动一位：x = x << 2，由于每个字符用 2 个比特表示，所以要左移 2 位；

• 一个新的字符ch 进入窗口：x = x | bin[ch]，这里 bin[ch] 为字符 ch 的对应二进制；

• 窗口最左边的字符离开窗口：x = x & ((1 << 20) - 1)，由于我们只考虑 x 的低 20 位比特，需要将其余位置零，即与上 (1 << 20) - 1。

将这三步合并，就可以用 O(1) 的时间计算出下一个子串的整数表示，即 x = ((x << 2) | bin[ch]) & ((1 << 20) - 1)。

function findRepeatedDnaSequences(s: string): string[] {
	
    const L = 10;
    const bin = new Map();
    bin.set('A', 0);
    bin.set('C', 1);
    bin.set('G', 2);
    bin.set('T', 3);
    
    const ans = [];
    const n = s.length;
    if (n <= L) {
        return ans;
    }
    let x = 0;
    for (let i = 0; i < L - 1; ++i) {
        x = (x << 2) | bin.get(s[i]);
    }
    const cnt = new Map();
    for (let i = 0; i <= n - L; ++i) {
        x = ((x << 2) | bin.get(s[i + L - 1])) & ((1 << (L * 2)) - 1);
        cnt.set(x, (cnt.get(x) || 0) + 1);
        if (cnt.get(x) === 2) {
            ans.push(s.slice(i, i + L));
        }
    }
    return ans;


};

[1371] 每个元音包含偶数次的最长子字符串

给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u' ，在子字符串中都恰好出现了偶数次。

示例 1：

输入：s = "eleetminicoworoep"
输出：13
解释：最长子字符串是 "leetminicowor" ，它包含 e，i，o 各 2 个，以及 0 个 a，u 。
示例 2：

输入：s = "leetcodeisgreat"
输出：5
解释：最长子字符串是 "leetc" ，其中包含 2 个 e 。
示例 3：

输入：s = "bcbcbc"
输出：6
解释：这个示例中，字符串 "bcbcbc" 本身就是最长的，因为所有的元音 a，e，i，o，u 都出现了 0 次。

提示：

1 <= s.length <= 5 x 10^5
s 只包含小写英文字母。

因为出现字母 -------考虑使用前缀和 位运算加哈希表来算

引入前缀和：将双变量转为单变量

• [0,j]的元音次数 - [0，i-1]对应发元音次数 = 偶数；
• 求[0,x]的元音次数，变量就只有1个了

我们只关心【差值】是否是偶数，不关心偶数到底是多少

• 偶数 - 奇数 = 奇数；奇偶性相同时均为奇数；
• 可等价于：
• [0,j]出现的元音次数的奇偶，相同于，[0,i-1]对应的原因次数的奇偶
• 【特别注意】出现0次（没有出现），也是出现了偶次

奇偶是相对的状态

• 两个相反的状态，可以抽象为 —— 用 0 代表偶数，1 代表奇数
• [0,x] 的五个元音各自出现次数的奇偶性用 0/1 表示，组成一个5位二进制数。比如 00001 代表 u o i e 都出现偶次（0 次也是偶次），a 出现奇次
• 管这叫[0,x] 区间的 state，记录区间中元音出现次数的奇偶信息

题目再次等价转化

• [ 0, j ] 的 state 等于[ 0, i - 1] 的 state，即两个二进制数相等。找出满足该条件且 j - i 最大的 i、j 组合，因为两个前缀区间相距越远，所形成的子串越长。
• 遍历字符串，求出 [0,x] 的 state，看看哪些 state 相同，找出离得最远的

怎么求前缀区间的 state

• 比方说 [0:1] 的 state 是 00110 ，出现 e 和 i 奇数次，假如下一字符是 i，则 [0,2] 区间出现 i 的次数变为偶数，state 为 00010
• 二进制数的第三位从 1 翻转为 0，其他位不变
• 使特定位置翻转正是异或的作用，第三位翻转，就是异或了 00100
• 其实异或相当于不带二进制的加法，所以有00110^00100 = 00010
• u o i e a 分别有对应的二进制数：10000、01000、00100、00010、00001
• 当前前缀区间的 state = 前一个前缀区间 state ^ 当前字符对应的二进制数

预置 -1 的情况，使通式普遍适用

• [ i, j ] 的 u o i e a 出现偶次 <=> [0, j ] 的 state 等于 [0, i - 1] 的 state
• i 显然可以为 0 ，则 i-1 为 -1 ，我们让 [0,-1] 的 state 为 00000，表示在字符串 -1 的位置，所有元音都出现偶次（0次）
• 预置了一种不存在的情况，看似荒谬，其实只是为了让边界情况也能套用通式

前缀区间的 state 怎么存

• 可以存入数组，索引和字符位置一一对应

• 也可以存入Map，这里选择Map

  • key： state 值

  • value：对应在字符串中的位置

• 为了书写方便，转成十进制，比如 00110 就存 6

寻找满足条件的state

• 遍历过程中，边存state,要边在Map中查找；
• 看看有没有之前存过的，与当前state相同的state
• 如果有，则可能不止一个，要根据value值，求出它离当前位置的距离，找出有着最长距离的那个，就是我们想要的最大子串长度。

思路

• 准备一些变量

​ - vowel，元音对照表，元音和对应的二进制数

​ - map，初始放入 0: -1 键值对，代表 [0,-1] 对应的 state 为 00000 ，即十进制 0

​ - state，保存当前前缀区间的 state ，初始值 0

• 遍历，如果遍历到元音，获取它对应的二进制数，异或「上一个 state」，求出当前 state
• 往 map 存入 state，边存边查看「与当前 state 相等的、过去存下的 state 的位置」
• 求出它们间的距离，取到最大的。

时间复杂度：O(n) 空间复杂度：O(常数)

function findTheLongestSubstring(s: string): number {
    
    let state = 0;
    const map = new Map();
    map.set(0,-1);
    let vowels = { a:1 , e:2 , i:4 , o:8 , u:16 };
    let res = 0;

    for(let i = 0; i < s.length ; i++ ){   //进行一次遍历
        if (vowels[s[i]] !== undefined) {     //判断当前字符串是否是元音字符
            state ^= vowels[s[i]];
            if(map.get(state) === undefined){
                map.set(state,i); // 如若没有，在哈希表中储存
             } 
        }

        let distance = i - map.get(state);
        res = Math.max(res,distance);
    }

    return res;
    
};

这篇关于JS/TS算法---状态压缩的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！