文章目录
1. 单词搜索2. 除 2 操作3. dd 爱框框
1. 单词搜索
题目链接
解题思路：
DFS (深度优先遍历)，用一个 pos 记录要匹配单词 word 的位置，每次与 pos 进行匹配判断（这样做的好处是不用把答案存下来） 注意细节❗： ①没有用 flag 来记录的话，所有在 DFS 暴搜的时候需要对返回的结果进行及时的判断
实现代码：
class Solution {
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int vis[110][110] = {0};
public:
bool exist(vector
for (int i = 0; i < board.size(); i ++)
{
for (int j = 0; j < board[0].size(); j ++)
{
if (board[i][j] == word[0])
{
// 此处细节点：必须要对结果进行及时判断
if (dfs(board, word, i, j, 0))
return true;
}
}
}
return false;
}
bool dfs(vector
{
if (pos + 1 == word.size())
{
return true;
}
vis[x][y] = 1;
for (int i = 0; i < 4; i ++)
{
int x1 = x + dx[i];
int y1 = y + dy[i];
if (x1 >= 0 && x1 < board.size() && y1 >= 0 && y1 < board[0].size() && !vis[x1][y1] && pos < word.size() - 1 && board[x1][y1] == word[pos + 1])
{
// 注意： 要及时收集结果判断
if (dfs(board, word, x1, y1, pos + 1))
return true;
}
}
vis[x][y] = 0;
return false;
}
};
2. 除 2 操作
题目链接
解题思路：
贪心 + 优先队列，将偶数存入优先队列里面，每次取最大的元素减半 注意细节❗： ① priority_queue 插入一个元素的时间复杂度是 O(log n)，删除堆顶元素也是 O(log n)；
实现代码：
#include
#include
using namespace std;
int n, k;
typedef long long LL;
int main()
{
priority_queue
cin >> n >> k;
LL x, sum = 0;
for (int i = 0; i < n; i++)
{
cin >> x;
if (x % 2 == 0)
heap.push(x);
sum += x;
}
while (!heap.empty() && k --)
{
LL t = heap.top() / 2;
heap.pop();
sum -= t;
if (t % 2 == 0)
heap.push(t);
}
cout << sum << endl;
return 0;
}
3. dd 爱框框
题目链接
解题思路：
滑动窗口的思想（同向双指针） 注意细节❗： ① ✌ 滑动窗口要想清楚四个问题： 什么时候进窗口、什么时候出窗口、判断条件、什么时候更新结果
实现代码：
#include
using namespace std;
const int N = 1e7 + 10;
typedef long long LL;
LL n, x;
LL arr[N];
int main()
{
scanf("%d%d", &n, &x);
for (int i = 1; i <= n; i ++)
scanf("%lld", &arr[i]);
// 滑动窗口的思想 （同向双指针）
LL left = 0, right = 1;
LL RetLeft = -1, RetRight = -1, sum = 0, RetLen = N;
while (right <= n)
{
sum += arr[right];
while (sum >= x)
{
sum -= arr[left];
left ++;
if (sum >= x && right - left < RetLen)
{
RetLeft = left;
RetRight = right;
RetLen = RetRight - RetLeft;
}
}
right ++;
}
cout << RetLeft << " " << RetRight << endl;
return 0;
}
好文链接
发表评论