笔试专题（二）

除2!

题目链接

题解

1. 可以使用一个大根堆，把所有的偶数都加入到堆中，堆顶的元素就是最大的偶数，然后除2，再把堆顶的元素弹出，防止影响后面的数，sum再减去这个除2后的数，如果这个数除2后还是偶数，就把它重新加入堆中

代码

我写的时候没有考虑要选出最大再除2,只是从数组的尾部开始选如果是偶数就一直除2#include<iostream>
#include<queue>using namespace std;typedef long long LL;
LL n,k;
priority_queue<LL> heap;
LL sum;int main()
{cin >> n >> k;for(int i = 0;i < n;i++){int x;cin >> x;sum += x;if(x % 2 == 0) heap.push(x);}// 没有偶数或者k为0不做处理// heap.size()不为0并且k不为0进入循环while(heap.size() && k--){int t = heap.top() / 2;heap.pop();sum -= t;if(t % 2 == 0) heap.push(t);}cout << sum << '\n';return 0;
}

单词搜索

题目链接

题解

1. 细节问题：不能往回找单词，所以设计一个bool数组标记已经使用过的字符
2. 全局变量：vis标记使用过的字符，dx，dy表示向量，向上，向下，向左或者向右搜索
3. 回溯：需要将使用过的字符恢复现场
4. 递归出口：到达字符串的最后一个位置的下一个位置，表示字符串已经搜索完成
5. 算法原理：简单来说就是遍历方格，找到方格中符合字符串的第一个字符，从这个字符往下搜索，如果找到符合字符串的就返回

代码

class Solution 
{
public:bool vis[101][101];int m,n;bool exist(vector<string>& board, string word) {m = board.size(),n = board[0].size();for(int i = 0;i < m;i++){for(int j = 0;j < n;j++){if(board[i][j] == word[0]){vis[i][j] = true;if(dfs(board,i,j,word,1)) return true;// 必须恢复现场,不然后续使用前面的字符被标记过了,又恰巧是正确字符的位置// 这个字符又被使用过了,就找不到了vis[i][j] = false;}}}return false;}int dx[4] = {-1,1,0,0};int dy[4] = {0,0,-1,1};bool dfs(vector<string>& board,int i,int j,string word,int pos){if(pos == word.size()) return true;for(int k = 0;k < 4;k++){int x = dx[k] + i,y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && board[x][y] == word[pos]){vis[x][y] = true;if(dfs(board,x,y,word,pos+1)) return true;vis[x][y] = false;}}return false;}
};

孩子们的游戏

题目链接

题解

1. 用动态规划的思路：如何找到子问题呢?
根据题目的意思，每次都会出去一个孩子且孩子不会再回来，这样一个大圈就慢慢变成了一个小圈
2. 状态表示如何写呢？
根据题目就是题目要你找的那个答案，这题就是有n个孩子围成一圈，最终获胜孩子的编号是什么
3. 状态转移方程：dp[i] = (dp[i-1] + m) % i
4. 这题主要考察的是下标映射的关系
5. 可以使用一个变量进行空间优化，f = 0 -> dp[1]，只有一个孩子时，不管怎样他都是那个获胜的孩子，下标为0

1. 也可以使用环形链表模拟
2. 还可以使用数组模拟

代码

class Solution 
{
public:int LastRemaining_Solution(int n, int m) {// dp[i] = (dp[i-1] + m) % i// dp[n]:表示有n个孩子,最终获胜的那个小孩的下标是多少// f -> dp[1]int f = 0;for(int i = 2;i <= n;i++){f = (f + m) % i;}return f;}
};