给定一个仅包含数字 0-9 的字符串和一个目标值，在数字之间添加二元运算符（不是一元）+、- 或 * ，返回所有能够得到目标值的表达式。
这题显然就是DFS了 搜索每两个数字间可能出现的运算符并组合即可
问题就在于本题的方案如何记录， 这里用到了和线段树类似的运算表达式来简化 我们用一个形如
a + b * _的式子来表示所有方案 这样
+ 如果后面是 + : (a + b * c) + 1 * _
+ 如果后面是 - : (a + b * c) + -1 * _
+ 如果后面是 * : a + (b * c) * _这里我们额外规定最后一个数后面可以跟 +
using LL = long long;
class Solution {
public:
vector<string> ans;
string path;
LL target;
public:
vector<string> addOperators(string num, int target) {
path.resize(100);
this->target = target;
dfs(num, 0, 0, 0, 1); // 最开始 0 + 1 * _
return ans;
}
void dfs(string num, int u, int len, LL a, LL b)
{
if(u == num.size())
{
if(a == target) ans.push_back(path.substr(0, len - 1)); // 除去最后一个加号
}
else
{
LL c = 0;
for(int i = u; i < num.size(); i++)
{
c = c * 10 + num[i] - '0';
path[len++] = num[i];
// +
path[len] = '+';
dfs(num, i + 1, len + 1, a + b * c, 1);
if(i + 1 < num.size())
{
// -
path[len] = '-';
dfs(num, i + 1, len + 1, a + b * c, -1);
// *
path[len] = '*';
dfs(num, i + 1, len + 1, a, b * c);
}
// ! 注意这里前导0的情况
if(num[u] == '0') break;
}
}
}
};除了移动之外要保持非0元素的相对顺序 所以与其是移动0 实际上是移动所有非0元素
class Solution {
public:
void moveZeroes(vector<int>& nums) {
// 除了移动之外要保持非0元素的相对顺序
// 所以与其是移动0 实际上是移动所有非0元素
for(int i = 0, j = 0; i < nums.size(); i++)
{
if(nums[i] != 0)
{
swap(nums[i], nums[j]);
j++;
}
}
}
};这题思路上是比较简单的 无非是增加一个缓存 和一个bool标记，调用peek 相当于提前调用了next, 再调用next的时候直接返回即可；
这里学习一下怎么调用父类同名函数 (指定namespace)
class PeekingIterator : public Iterator {
public:
int curNum;
bool flag;
public:
PeekingIterator(const vector<int>& nums) : Iterator(nums) {
// Initialize any member here.
// **DO NOT** save a copy of nums and manipulate it directly.
// You should only use the Iterator interface methods.
flag = false;
}
// Returns the next element in the iteration without advancing the iterator.
int peek() {
if(flag == false)
{
curNum = Iterator::next();
flag = true;
}
return curNum;
}
// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
int next() {
if(flag == true)
{
flag = false;
return curNum;
}
return Iterator::next();
}
bool hasNext() const {
return flag || Iterator::hasNext();
}
};这题经典套路了，看到1 ~ n 组成的数组就可以往数组元素作为下标想
这题就是把数组元素作为下标 连边 找到图中的环的起点，即为重复元素
图中环的起点怎么找呢？ 快慢指针：1. 找到环 2. 让一个指针领先一个环的长度 3. 同时前进直到相遇 此时为起点
class Solution {
public:
int findDuplicate(vector<int>& nums) {
// 已经是经典套路了 以数组值做下标 转化为找环的入口的问题
// 1. 找到环
int slow = 0, fast = 0;
do
{
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow != fast);
int cur = 0;
// 2. 让cur指针提前走一个环的长度
do
{
cur = nums[cur];
slow = nums[slow];
}while(slow != fast);
// 3. 从头 直到相遇
int head = 0;
while(head != cur)
{
head = nums[head];
cur = nums[cur];
}
return cur;
}
};你可以使用原地算法解决本题吗？ 请注意，面板上所有格子需要同时被更新： 你不能先更新某些格子，然后使用它们的更新后的值再更新其他格子。
很显然就是要额外定义状态
上一个状态 + 这一个状态 1 - 0 -> 2 1 - 1 -> 3
计算附近格子数的时候按照原来的状态 而不是更新过的状态
class Solution {
public:
int n, m;
public:
void gameOfLife(vector<vector<int>>& board) {
// 1 - 0 记作 2 0 - 1 记作 3
n = board.size();
m = board[0].size();
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
int cnt = getActivateCellsCount(board, i, j);
if(board[i][j] == 1)
{
if(cnt < 2 || cnt > 3) board[i][j] = 2;
}
else
{
if(cnt == 3) board[i][j] = 3;
}
}
// 把 2 和 3 都改写为 0 1
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
{
if(board[i][j] == 2) board[i][j] = 0;
if(board[i][j] == 3) board[i][j] = 1;
}
}
int getActivateCellsCount(vector<vector<int>>& board, int si, int sj)
{
int cnt = 0;
for(int i = si - 1; i <= si + 1; i++)
{
if(i < 0 || i >= n) continue;
for(int j = sj - 1; j <= sj + 1; j++)
{
if(j < 0 || j >= m) continue;
if(i == si && j == sj) continue;
if(board[i][j] == 1 || board[i][j] == 2) cnt++;
}
}
return cnt;
}
};还是比较基础的 之前应该是有一道一样的题（忘了是哪个了）
记录单词间的映射 注意这里不能只记录pattern 到 s 的映射 还要记录s中的单词是否曾经出现过（避免一个pattern对应多个单词）
最后通过判断i是否遍历到最后一个 来保证是一一对应的映射
class Solution {
public:
bool wordPattern(string pattern, string s) {
stringstream ss(s);
string str;
unordered_map<char, string> hash;
unordered_set<string> sset;
int i = 0;
while(ss >> str)
{
if(i >= pattern.size()) return false;
char c = pattern[i++];
if(!hash.count(c))
{
if(sset.count(str)) return false;
hash[c] = str;
sset.insert(str);
}
else
{
if(hash[c] != str) return false;
}
}
return i == pattern.size();
}
};