JS/TS算法---状态压缩

2022/7/10 1:22:39

本文主要是介绍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算法---状态压缩的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程