笔试专题（二）

除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;
    }
};