程序员进阶之算法练习（九十）leetcode
题目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);腾讯云开发者
