个人主页 ： zxctscl
专栏 【C++】、 【C语言】、 【Linux】、 【数据结构】、 【算法】
如有转载请先通知

1 Fibonacci数列

WY22 Fibonacci数列

#include <iostream>
using namespace std;


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

}
// 64 位输出请用 printf("%lld")

2 NC242 单词搜索

NC242 单词搜索

dfs

class Solution {
  public:
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { -1, 1, 0, 0 };
    bool vis[101][101];
    int m, n;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board string字符串vector
     * @param word string字符串
     * @return bool布尔型
     */
    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, i, j, word, 0)) return true;
                }
            }
        }
        return false;
    }
    bool dfs(vector<string>& board, int i, int j, string& word, int 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, a, b, word, pos + 1)) return true;
            }
        }
        vis[i][j] = false;
        return false;
    }
};

3 BC140 杨辉三角

BC140 杨辉三角

dp

#include <iostream>
using namespace std;
int dp[31][31];
int main() {
    int n;
    cin >> n;

    dp[1][1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 1; j <=i; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            printf("%5d",dp[i][j]);
        }
        printf("\n");
    }

}
// 64 位输出请用 printf("%lld")

4 NC109 岛屿数量

NC109 岛屿数量

dfs

class Solution {
    int m,n;
  
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 判断岛屿数量
     * @param grid char字符型vector<vector<>> 
     * @return int整型
     */
    int solve(vector<vector<char> >& grid) 
    {
        int ret=0;
        // write code here
        m=grid.size(),n=grid[0].size();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1')
                {
                    ret++;
                    dfs(grid,i,j);
                }
            }
        }
        return ret;
    }
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};

    void dfs(vector<vector<char> >& grid,int i,int j)
    {
        grid[i][j]='0';
        
        for(int k=0;k<4;k++)
        {
            int x=dx[k]+i;
            int y=dy[k]+j;
            if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]=='1')
            dfs(grid,x,y);
        }
    }
};

5 拼三角

拼三角

#include <iostream>
#include <algorithm>
using namespace std;
int t;
int arr[6];

int main() 
{ 
    
    cin>>t;
   while(t--)
    {
        for(int i=0;i<6;i++)
        {
            cin>>arr[i];
        }
        sort(arr, arr + 6);
       if(arr[0] + arr[1] > arr[2] && arr[3] + arr[4] > arr[5] || 
          arr[0] + arr[2] > arr[3] && arr[1] + arr[4] > arr[5] ||
          arr[0] + arr[3] > arr[4] && arr[1] + arr[2] > arr[5] ||
          arr[0] + arr[4] > arr[5] && arr[1] + arr[2] > arr[3])
        {
            cout << "Yes" << endl;
        }
        else cout << "No" << endl;
    }
    return 0;
       

}
// 64 位输出请用 printf("%lld")

6 DP39 字母收集

字母收集

动态规划

#include <iostream>
using namespace std;
char arr[510][510];
int dp[510][510];
int m, n;

int main() {
    cin >> m >> n;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }

    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int ret = 0;
            if (arr[i][j] == 'l')ret = 4;
            else if (arr[i][j] == 'o')ret = 3;
            else if (arr[i][j] == 'v')ret = 2;
            else if (arr[i][j] == 'e')ret = 1;
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]) + ret;
        }
    }
    cout << dp[m][n] << endl;
    return 0;

}
// 64 位输出请用 printf("%lld")