状态压缩

概述

状态压缩就是通过位运算来将字符串、数组等数据压缩进一个32位的整数型变量。例如，对于一个只包含小写字母的字符串，我们可以用一个32位整数的低26位表示，其中1代表该字符串包含对应的小写字母，0表示该字符串不包括对应的小写字母，即字符串”ac”可以被压缩为整数5（0101）。通过状态压缩，我们可以节省内存、加快运算过程。

---

例题 1

LeetCode 318. 最大单词长度乘积

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

示例 1：

输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16 
解释：这两个单词为 "abcw", "xtfn"。

示例 2：

输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4 
解释：这两个单词为 "ab", "cd"。

示例 3：

输入：words = ["a","aa","aaa","aaaa"]
输出：0 
解释：不存在这样的两个单词。

---

题解 1

我们可以通过上文提到的状态压缩方法将 words 中的所有字符串都压缩为一个int。由于题目只需返回最大的乘积，对于多个字符串压缩为同一个int的情况，我们只需要储存长度最长的一个。然后我们两两组合得到的int，如果对他们进行或运算得到的结果为0的话，就代表他们没有重复的字母。

代码：

class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> map;
        vector<int> conditions;
        for (string str : words) {
            int i = 0;
            for (char c : str) {
                i |= 1 << (c - 'a');
            }
            if (map.count(i) <= 0) conditions.push_back(i);
            map[i] = max(map[i], (int)str.length());
        }
        int res = 0;
        for (int i = 0; i < conditions.size(); i++) {
            int num1 = conditions[i];
            for (int j = 1; j < conditions.size(); j++) {
                int num2 = conditions[j];
                if ((num1 & num2) == 0) {
                    res = max(res, map[num1] * map[num2]);
                }
            }
        }
        return res;
    }
};

注意： 在C++中，位运算的优先级是低于判断的。所以if ((num1 & num2) == 0) 不可以写为if (num1 & num2 == 0) 。

---

例题 2

LeetCode 464. 我能赢吗

在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。

如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？

例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。

给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。

示例 1：

输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。

示例 2：

输入：maxChoosableInteger = 10, desiredTotal = 0
输出：true

示例 3：

输入：maxChoosableInteger = 10, desiredTotal = 1
输出：true

---

题解 2

状态压缩往往和一些别的编程技巧配合使用，比如记忆化搜索、动态规划等。由于待搜索的状态被压缩进了一个int里，我们就可以很容易地储存和查找该状态对应的结果。本题就是一个例子，我们可以将所有可取的整数（题目规定不超过20）压缩进一个int中，然后进行记忆化搜索。如果当前状态此前已经搜索过了，则可以直接从字典中查找其搜索结果并返回，无需重复搜索。记忆化搜索是基于深度优先搜索的，如果当前状态未搜索过，就进行常规的深度优先搜索。

代码：

class Solution {
private:
    unordered_map<int, bool> map;
    bool dfs(int state, int cursum, int maxnum, int target) {
        if (map.count(state) <= 0) {
            bool res = false;
            for (int i = 0; i < maxnum; i++) {
                if (((state >> i) & 1) == 0) {  
                    //当前数字未被取到
                    if (cursum + i + 1 >= target) {
                        //取了当前数字就可以达到target
                        res = true;
                        break;
                    }
                    if (!dfs(state | (1 << i), cursum + i + 1, maxnum, target)) {
                        //取了当前数字无法达到target，则继续进行深度优先搜索。
                        //如果取了该数字下家无论如何都赢不了，则代表必胜，返回true.
                        res = true;
                        break;
                    }
                }
            }
            map[state] = res;//记录当前状态的胜负结果，以便后续直接查询。
        }
        return map[state];
    }
public:
    bool canIWin(int maxChoosableInteger, int desiredTotal) {
        //如果全部数字加起来都不能到达desiredTotal，则两个人都不能赢，返回false.
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
        return dfs(0, 0, maxChoosableInteger, desiredTotal);
    }
};

有的没的

为什么这么久没更新

最近在忙一些别的事情。具体地说，是在忙着当优秀学长（确实准备的很辛苦！就允许我臭屁一下吧），嘿嘿。一个丹青学生会的同学邀请我去给学弟学妹们 （主要是学妹） 分享一些Python的考试技巧，作为一位热心水友 （好为人师） ，我当然不会推辞了。于是花了一个多星期准备，一边准备一边焦虑怕自己舌头捋不顺或者讲的内容大家不爱听。还好顺利搞定了。临近期末了，可能又有一阵子要肝大作业没闲工夫来更新了。

校庆日

5月21日是浙江大学的校庆日，学校为了纪念，特地为大家放了一天假 。在这美好的一天，我喝了心心念念已久的芝士椰椰。虽然再一次喝到了椰椰，但是我再也回不到那个第一次喝到椰椰的夏天了。最美好的时代永远是在过去，我一直在怀念曾经无数次想要逃离的生活。然后我在寝室里写了一整天的代码。花了数小时手搓了大数据分析的Apriori算法，虽然在4条测试数据时表现良好，但在面对9000+条的数据集时它卡死了，白忙活，最后还是老老实实地用R语言调包。

那年今日

去年520我一个人去电影院看了《情书》的重映。第一次接触《情书》是在高中语文书附带的读本上，看到了寻找藤井树的片段。然后就跟同学借来了书，晚上睡觉前在寝室点上灯读个两章，那段时间可能是我最文艺青年的一段时间了。

没事听点歌（李荣浩 - 王牌冤家）