题目1 二进制求和

题目链接
题目大意：
给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。

示例 1：
输入:a = "11", b = "1"
输出："100"

示例 2：
输入：a = "1010", b = "1011"
输出："10101"

题目解析：
大数加法的简化版本。
注意事项：
1、逆序，从右到左操作；
2、不等长处理，长度上 a>b、a=b、a<b三种情况的考虑；
3、字符和整数转化；
4、进位考虑，累加过程，以及最后进位处理；
5、输出再重新逆序；

class Solution {
public:
    string addBinary(string a, string b) {
        string ret;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int x = 0, y = 0, add = 0;
        while (x < a.length() || y < b.length()) {
            int temp = add;
            if (x < a.length()) {
                temp += a[x] - '0';
            }
            if (y < b.length()) {
                temp += b[y] - '0';
            }
            ret.push_back('0' + temp % 2);
            add = temp / 2;
            ++x, ++y;
        }
        if (add) {
            ret.push_back('1');
        }
        reverse(ret.begin(), ret.end());
        return ret;
    }
}leetcode;

题目2 单词搜索

题目链接
题目大意：
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

示例 ：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

题目解析：
题目给出的条件非常明确，就是按照格子进行搜索；
搜索有广度/深度优先搜索，从题目的要求来看，采用深度优先搜索能够更加方便去匹配结果和剪枝；
剪枝：
1、如果某个字符不相同，不进行搜索；
2、如果下一个字符不相同，则停止搜索；

class Solution {
    int dir[4][2] = {
        0, 1,
        0, -1,
        1, 0,
        -1, 0
    };
    bool dfs(vector<vector<char>>& board, vector<vector<char>>& vis, int x, int y, int index, string &word) {
        if (board[x][y] != word[index]) {
            return false;
        }
        if (index + 1 == word.size()) {
            return true;
        }
        for (int i = 0; i < 4; ++i) {
            int nextX = dir[i][0] + x, nextY = dir[i][1] + y;
            if (nextX < 0 || nextX >= board.size() || nextY < 0 || nextY >= board[0].size() || vis[nextX][nextY]) continue;;
            
            vis[nextX][nextY] = 1;
            if (dfs(board, vis, nextX, nextY, index + 1, word)) {
                return true;
            }
            vis[nextX][nextY] = 0;
            
        }
        return false;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        bool ret = 0;
        vector<vector<char>> vis;
        for (int i = 0; i < board.size(); ++i) {
            vector<char> tmp(board[0].size());
            vis.push_back(tmp);
        }
        for (int i = 0; i < board.size() && !ret; ++i) {
            for (int j = 0; j < board[0].size() && !ret; ++j) {
                vis[i][j] = 1;
                ret = dfs(board, vis, i, j, 0, word);
                vis[i][j] = 0;
            }
        }
        return ret;
    }
}leetcode

题目3 Longest Consecutive Sequence

题目链接
题目大意：
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1：
输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2：
输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

题目解析：
把数字x看成一个点，题意变成有若干个点，点x和点x-1、点x+1能够联通，问点数最多的联通子集有几个点。
两个点集的合并，可以采用并查集的思想，每个点有个指针指向自己的父节点，初始状态是每个点指向自己；
当点x,y合并的时候，只需要把f[x]=y，相当于把x的父节点指向y。
从左到右遍历，做一遍并查集，就可以得到点数最多的集合。

接下来是如何计算集合的点数，特别是题目数据存在重复的情况。

复杂度解析：
时间复杂度是O(N)
空间复杂度是O(N)

class Solution {
public:
    int find(unordered_map<int, int> &f, int x) {
        if (f[x] == x)
            return x;
        return f[x] = find(f, f[x]);
    }
    
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int, int> f;
        unordered_map<int, int> vis;
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            f[nums[i]] = nums[i];
            vis[nums[i]] = 1;
        }
        
        for (int i = 0; i < nums.size(); ++i) {
            if (vis[nums[i] - 1] && find(f, nums[i] - 1) != find(f, nums[i])) { //nums[i] - 1有出现这个数字，并且两个集合的顶点不相同
                f[f[nums[i] - 1]] = f[nums[i]];
            }
            if (vis[nums[i] + 1] && find(f, nums[i] + 1) != find(f, nums[i])) {
                f[f[nums[i] + 1]] = f[nums[i]];
            }
        }
        
        unordered_map<int, int> count;
        for (int i = 0; i < nums.size(); ++i) {
            if (vis[nums[i]] && find(f, nums[i]) != nums[i]) {
                vis[nums[i]] = 0;
                count[f[nums[i]]]++;
            }
            ans = max(ans, count[f[nums[i]]] + 1);
        }
        return ans;
    }
}leetcode;

题目4 丑数 II

题目链接
题目大意：
给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 or 5 的正整数。

题目解析：
如果不考虑复杂，可以从1、2、3开始枚举，不断判断数字是否满足要求；（判断方式就是用2、3、5去除，最终结果是1）
但是这样复杂度会比较高，中间会经历较多无用的数字。

考虑刚刚的判断方式，是用2、3、5去判断是否整除，那么直接用2、3、5相乘，来得到整数即可保证得到的整数都满足要求，从而过滤掉很多无用的整数。
那怎么保证是从小到大呢？

这里可以用优先队列，每次吐出队列中的最小数字；
初始状态则只需要放入2、3、5，每次拿到最小数字，则继续乘以2、3、5再放回队列中。

思考：
注意int越界的问题。

class Solution {
public:
    int nthUglyNumber(int n) {
        if (n == 1) return 1;
        priority_queue<lld, vector<lld>, greater<lld> > q;
        unordered_map<lld, lld> h;
        lld cnt = 1, cur = 1;
        q.push(1);
        while (cnt <= n) {
            cur = q.top();
            q.pop();
            ++cnt;
            if (!h[cur * 2]) {
                h[cur * 2] = 1;
                q.push(cur * 2);
            }
            
            if (!h[cur * 3]) {
                h[cur * 3] = 1;
                q.push(cur * 3);
            }
            
            if (!h[cur * 5]) {
                h[cur * 5] = 1;
                q.push(cur * 5);
            }
            
        }
        
        return cur;
    }
}lc;

题目5 LFU Cache

题目链接
题目大意：
实现LRU(最近最少使用)算法。如果有相同的使用频率，保留最近使用的（put操作不算使用）。
要求，get、put操作O（1）实现；

LFUCache cache = new LFUCache(2);
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.get(3);       // returns 3.
cache.put(4, 4);    // evicts key 1.
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

题目解析：
put操作先考虑key是否存在：
1、key存在，直接更新key值；
2、key不存在， 如果cache没满，直接放入cache；
如果当前cache已满，去掉最不经常使用的key，再把key放入cache；

get操作考虑key是否存在：
1、key存在，返回key对应的值，并+1最近使用频率；
2、key不存在，返回-1；

如果使用朴素实现，list来存(key, value)对，并且在需要更新时直接去掉list节点，重新查找插入位置；
每次的操作复杂度都是O(N)，并不符合要求。

优化思路：
耗时在于查找key值和插入key值；

unordered_map<int, pair<int, int> > keyMap; // key = <value, freq>
unordered_map<int, list<int>::iterator> iterMap; // 对应key的list迭代器，用于快速获得值
unordered_map<int, list<int> > freqMap; // 使用频率是map

引入三个map，分别是keyMap、iterMap和freqMap；
keyMap记录对应key的value和出现频率，这样可以O(1)得到对应key值的pair(值value，出现频率freq)；
freqMap的索引是出现频率freq，value是链表，存储当前使用频率为freq的数字；（比如说put(1, 2)，put(3, 4)，两次put操作之后，key值1、3都出现了（初始出现频率=1），所以有freq=1的链表(3，4)，即使freqMap[1]=(3,4)；
iterMap的索引是输入的key，这样可以O(1)得到对应key值的链表迭代器，方便的更新key值的出现频率；（比如说在put(1, 2)，put(3, 4)之后，又出现一次get(1)，此时key=1出现频率为2，所以应该挪到freqMap[2]=(1)这样，此时需要把freqMap[1]中链表的4移除，此时如果遍历会很慢，所以引入iterMap以快速访问）
这样就解决了key值的查找、插入带来的更新问题；

同时为了解决cache满了之后，需要快速定位到抛弃哪个key值的问题，我们引入整数minFreq；
因为出现频率总是从1、2、3.。这样递增，每次淘汰的时候从出现频率为minFreq的链表中选择1个即可；
ps：get操作也需要更新minFreq，比如说put(1, 2)后minFreq=1，如果再出现get（1）此时minFreq=2，因为唯一的key值1已经出现了两次；仔细看代码，minFreq的更新并没有while循环，这就是额外的思考题。

class LFUCache {
public:
    int cap, curSize, minFreq; // cap是容量，curSize是当前大小，minFreq是最小的使用频率
    unordered_map<int, pair<int, int> > keyMap; // key = <value, freq>
    unordered_map<int, list<int>::iterator> iterMap; // 对应key的list迭代器，用于快速获得值
    unordered_map<int, list<int> > freqMap; // 使用频率是map
    LFUCache(int capacity) {
        cap = capacity;
        curSize = 0;
        minFreq = 0;
    }
    
    int get(int key) {
        if (keyMap.count(key) == 0) {
            return -1;
        }
        freqMap[keyMap[key].second].erase(iterMap[key]);
        ++keyMap[key].second;
        freqMap[keyMap[key].second].push_back(key);
        iterMap[key] = --freqMap[keyMap[key].second].end();
        
        if (freqMap[minFreq].size() == 0) {
            ++minFreq;
        }
        return keyMap[key].first;
    }
    
    void put(int key, int value) {
        if (cap <= 0) {
            return ;
        }
        int storgeValue = get(key);
        if (storgeValue != -1) {
            keyMap[key].first = value;
            return ;
        }
        if (curSize >= cap) {
            keyMap.erase(freqMap[minFreq].front());
            iterMap.erase(freqMap[minFreq].front());
            freqMap[minFreq].pop_front();
            --curSize;
        }
        keyMap[key] = make_pair(value, 1);
        freqMap[1].push_back(key);
        iterMap[key] = --freqMap[1].end();
        minFreq = 1;
        ++curSize;
    }
}leetcode(3);