笔试算法day01

目录

1.除2

 2.Fibonacci数列（Fib 数列）

3.单词搜索

---

1.除2

除2！ (nowcoder.com)

算法思路：

只需要对最大的n个偶数进行/2即可。

 将所有的偶数存进大根堆中，执行k次操作即可

#include <iostream>
#include <queue>

using namespace std;
int main()
{
    long long n = 0, k = 0;
    cin >> n >> k;
    priority_queue<long long> heap;
    long long ret = 0;
    long long tmp = 0;
    for(int i = 0; i < n ;i++)
    {
        cin >> tmp;
        ret += tmp;
        if(tmp % 2 == 0)
        {
            heap.push(tmp);
        }
    }
    
    for(int j = 0; j < k; j++)
    {
         if(heap.empty())
        {
            break;
        }
        long long t = heap.top() / 2;
        heap.pop();
        ret -= t;
        if(t % 2 == 0)
        {
            heap.push(t);
        }
       
     }
     cout << ret << endl;
    return 0;
}

 2.Fibonacci数列（Fib 数列）

Fibonacci数列_牛客题霸_牛客网

算法思路：找到N前后两个斐波那契数，分别与N做差，最小值就是最小步数。

可以使用三个数来进行模拟斐波那契数列。

#include <iostream>
using namespace std;

int main() 
{
    int n = 0;
    cin >> n;
    int a = 0, b = 1, c = 1;

    while(c < n)
    {
        a = b;
        b = c;
        c = a + b;
    }
    int ret = min(c-n, n-b);
    cout << ret << endl;
    return 0;    
}

3.单词搜索

单词搜索_牛客题霸_牛客网 (nowcoder.com)

算法思路：遍历数组找到与单词首字母相同的位置，上下左右搜寻是否有和单词下个字母相同的位置。

例：给出单词SEE

遍历到第一个S,搜寻上下左右，都没有E，直接继续向后遍历。

遍历到第二个S发现上是E,搜寻E的上下左右没发现E,回到S。

搜寻S的左没发现E。

搜寻s的下发现E，继续搜寻E的上下左右，左发现E，返回true

class Solution {
public:
    bool vis[101][101] = { 0 };//将遍历过的位置设为true,防止重复遍历
    const int dy[4] = {1, -1, 0, 0};//为了方便模拟上下左右遍历的过程
    const int dx[4] = {0, 0, 1 , -1};//
    int m = 0, n = 0;//数组的边界
    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])//在数组中找到与单词首字母相同的位置
                {
                    if(dfs(board, word, i, j, 0))
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    bool dfs(const vector<string>& board, const string &word, int i, int j, int pos)//pos 是遍历单词的哪个字符
    {
        if(pos == word.size() - 1)//遍历到单词末尾跳出递归
        {
            return true;
        }

        vis[i][j] = true;//防止重复遍历同一个位置
        for(int k = 0; k < 4; k++)
        {   
            int a = i + dx[k], b = j + dy[k];
            if((a >= 0 && a < m) && (b >= 0 && b < n) && !vis[a][b] && board[a][b] == word[pos + 1])
            {
                if(dfs(board, word, a, b, pos + 1))
                return true;
            }
        }
        vis[i][j] = false;//当单词不存在时，将位置复原
        return false;
    } 
};

原文地址：https://blog.csdn.net/W2155/article/details/142614016

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！