无重复字符的最长子串](https://leetcode.cn/problems/longest-substring-without-repeating-characters/)
给定一个字符串s，请你找出其中不含有重复字符的 **最长子串 **的长度。hash set space O(n), time O(|n|) n string len, |n| char set
dynamic time O(n2) , space O(n)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
if (s.length() <= 1) {
return s.length();
}
vector<int> dp(s.length(), 0);
dp[0] = 1;
int imx = 0;
for (int i = 1; i < s.length(); i++) {
int j = i - 1;
while (j >= 0 && s[j] != s[i]) {
j--;
}
dp[i] = dp[i - 1] < i - j ? dp[i - 1] + 1 : i - j;
imx = max(imx, dp[i]);
}
return imx;
}
};
- 给两组数据，order = {time stamp, customer id, order id}, sale ad event = {time stamp, customer id, event id}, 给每一个order找之前最近的sale ad event or null if not found.
例如 order = {100, 1, 20}, sale event ad = {{90, 1, 33}, {110, 1, 45}}, 那么合适的sale ad event 是{90, 1, 33}
return type需要自己定义，需要同时return order and its matching sale event ad.
sort -> binary search
struct Node{
long long timeStam;
long long id;
long long orderid;
operator < (const Node &a) {
timeStam < a.timeStam;
}
operator > (const Node &a) {
timeStam > a.timeStam;
}
};
sort(nodes.begin(), nodes.end());
bs(node, 0, nodes.size(), target);
- LRU 缓存
typedef struct NodeSt {
struct NodeSt* pre;
struct NodeSt* next;
int key;
int val;
NodeSt(int key, int val):pre(NULL), next(NULL) {
this->key = key;
this->val = val;
}
}Node;
LRUCache(int capacity): size(0)
int get(int key)
void put(int key, int value)
void moveToTail(Node* n)
void pushToTail(Node* n)
void removeFromHead()
private:
unordered_map<int, Node*> table;
Node *head;
Node *tail;
int size;
int capacity;
- 1487 保证文件名唯一
给你一个长度为 n 的字符串数组 names 。你将会在文件系统中创建 n 个文件夹：在第 i 分钟，新建名为 names[i] 的文件夹。
由于两个文件 不能 共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以 (k) 的形式为新文件夹的文件名添加后缀，其中 k 是能保证文件名唯一的 最小正整数 。
返回长度为 n 的字符串数组，其中 ans[i] 是创建第 i 个文件夹时系统分配给该文件夹的实际名称。
unorder_map<string, sub> mp;
5pre. 单词拆分 O(n2) space O(n)
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> mp;
for (int i = 0; i < wordDict.size(); i++) {
mp.insert(wordDict[i]);
}
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for (int j = 0; j <= s.size(); j++) {
for (int i = 0; i < j; i++) {
if (!dp[i]) {
continue;
}
string str = s.substr(i, j - i);
dp[j] = dp[i] & (mp.count(str));
if (dp[j]) {
break;
}
}
}
return dp[s.size()];
}
};
- 472 连接词
给你一个 不含重复 单词的字符串数组 words ，请你找出并返回 words 中的所有 连接词 。
pre的进阶， 遍历一遍数组。。
class Solution {
public:
bool check(string s , unordered_set<string> &mp)
{
mp.erase(s);
vector<int> dp(s.size() + 1, 0);
dp[0] = 1;
for (int j = 1; j <= s.size(); j++) {
for (int i = 0; i < j; i++) {
if (dp[i]) {
string str = s.substr(i, j - i);
if (mp.count(str)) {
dp[j] = true;
break;
}
}
}
}
mp.insert(s);
return dp[s.size()];
}
vector<string> findAllConcatenatedWordsInADict(vector<string>& words) {
vector<string> ret;
unordered_set<string> mp;
for (string s : words) {
mp.insert(s);
}
for (string s : words) {
if (check(s, mp)) {
ret.push_back(s);
}
}
return ret;
}
};
- 295 中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
class MedianFinder {
public:
MedianFinder() {
}
void addNum(int num) {
if (maxheap.empty()) {
maxheap.push(num);
return;
}
int k = maxheap.top();
if (num <= k) {
maxheap.push(num);
} else {
minheap.push(num);
}
// adjust
int a = minheap.size();
int b = maxheap.size();
while (abs(a - b) > 1) {
if (minheap.empty()) {
int t2 = maxheap.top();
maxheap.pop();
minheap.push(t2);
a = minheap.size();
b = maxheap.size();
continue;
}
int t1 = minheap.top();
int t2 = maxheap.top();
if (a > b) {
minheap.pop();
maxheap.push(t1);
} else {
maxheap.pop();
minheap.push(t2);
}
a = minheap.size();
b = maxheap.size();
}
}
double findMedian() {
if (minheap.size() == maxheap.size()) {
int t1 = minheap.top();
int t2 = maxheap.top();
return (double)(t1 + t2) / 2;
}
if (minheap.size() > maxheap.size()) {
return minheap.top();
}
return maxheap.top();
}
private:
priority_queue<int, vector<int>, greater<int>> minheap;
priority_queue<int> maxheap;
};
罗马数字，注意时间，空间复杂度都是O(1)
class Solution {
public:
string intToRoman(int num) {
string ret;
vector<int> sub = {
1,4,5,9,10,40,50,90,100,400, 500, 900, 1000
};
map<int,string> mp = {
pair(1, "I"),
pair(4, "IV"),
pair(5, "V"),
pair(9, "IX"),
pair(10, "X"),
pair(40, "XL"),
pair(50, "L"),
pair(90, "XC"),
pair(100, "C"),
pair(400, "CD"),
pair(500, "D"),
pair(900, "CM"),
pair(1000, "M")
};
// O(1)
for (int i = sub.size() - 1; i >= 0; i--) {
while (num >= sub[i]) {
num -= sub[i];
ret += mp[sub[i]];
}
if (num == 0) {
break;
}
}
return ret;
}
};
45 跳跃游戏II greed(贪心)
int jump(vector<int>& nums)
{
int imx = 0;
int end = 0;
int ans = 0;
int j = 0;
vector<int> pos;
for (int i = 0; i < nums.size() - 1; i++) {
if (imx < i + nums[i]) {
j = i;
imx = i + nums[i];
}
if (i == end) {
end = imx;
imx = 0;
ans++;
pos.push_back(nums[j]);
}
}
pos.push_back(nums[nums.size() - 1]);
return ans;
}
994 腐烂的橘子
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
vector<pair<int,int>> dir = {
{1,0},
{0,1},
{-1, 0},
{0, -1}
};
// bfs
// init
queue<pair<int,int>> que;
int m = grid.size();
int n = grid[0].size();
int miu = 0;
int cnt = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] == 2) {
que.push(pair(i, j));
} else if (grid[i][j] == 1) {
cnt++;
}
}
}
// bfs
while (cnt && !que.empty()) {
int len = que.size();
miu++;
for (int i = 0; i < len; i++) {
auto bad = que.front();
// search in 4 dir & push new bad
for (int d = 0; d < 4; d++) {
int x = bad.first + dir[d].first;
int y = bad.second + dir[d].second;
if (!(x < m && y < n && x >= 0 && y >= 0)) {
continue;
}
if (grid[x][y] == 1) {
grid[x][y] = 2;
cnt--;
que.push(pair(x, y));
}
}
que.pop();
}
}
// check all grid, and no == 1, return min, else return -1
if (cnt > 0) {
return -1;
}
// first que element is aready bad.
return miu;
}
};
