刷題day_4

繼續加油！！！

一、Fibonacci數列

題目鏈接：Fibonacci數列

題目解析

題目要求，輸入一個數N，我們可以對N進行+1/-1操作；題目讓我們輸出對N進行至少多少步可以變成Fibonacci數。

這里題目上說了我們對N的操作是+1或者-1，那我們就可以理解成求離N最近的Fibonacci數。

算法思路

我們需要尋找離N最近的Fibonacci數

這里定義三個變量a，b，c用來求Fibonacci數；在求的過程中，讓N處于b和c之間即可

最后返回N-b和c-N的最小值即可。

代碼實現

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

二、單詞搜索

題目鏈接：單詞搜索

題目描述

這里時一道經典的搜索題

題目給定一個二維字符數組board，給定一個單詞word；

讓我們在這個字符數組中查找單詞word（單詞由相鄰單元格的字母組成）并且同一個單元格的字符不能重復使用。

如果存在就返回true，如果不存在就返回false

算法思路

這一個經典的查找題目，在第一次做的時候可以說毫無思路；這里就直接說解法了。

首先，我們在二維字符數組中查找到單詞word的第一個字符；

然后從這個位置開始進行深度優先遍歷，來查找字符存在。

這里對于dfs深度優先遍歷，來看一下如何實現

首先，遍歷結束的條件（遞歸結束）：當我們的pos遍歷到word單詞的結尾時，遞歸就結束了。

其次，我們要先修改當前位置的標記，修改成true；意思是已經查找過

然后，依次遍歷當前位置的上、下、左、右四個位置，繼續進行深度優先遍歷，如果遍歷查找到word單詞就返回true。

最后，執行完for循環（查找結束其上、下、左、右四個位置沒有返回true，就表示沒有查找到），我們需要將當前位置標記修改回來，再返回false。

代碼實現

Ok，有了思路，直接開始寫代碼

class Solution {
public:int m,n; //表示二維字符數組的長和寬bool vis[101][101]; //用來標記每個位置是否被使用int dx[4] = {0,0,1,-1}; //上、下、左、右位置的x坐標變化int dy[4] = {1,-1,0,0}; //上、下、左、右位置的y坐標變化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;}}}//如果執行完for循環還沒有返回，就說明沒有找到//返回 falsereturn 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];int b = j+dy[k];//如果這個位置沒有越界，當前位置沒有用過；當前位置與要查找的字符相同if(a>=0 && a<m && b>=0 && b<n && vis[a][b] == false && board[a][b] == word[pos+1]){//深度優先遍歷這個位置if(dfs(board,a,b,word,pos+1)){return true;}}}vis[i][j] = false;return false;}
};

三、楊輝三角

題目鏈接：楊輝三角

題目解析

對于題目，楊輝三角再熟悉不過了；這里需要注意的是

• 輸出時需要注意，每個數輸出域寬為5

算法思路

楊輝三角，相信都早已熟悉了，這里提供兩個做法

1. 使用vector來存儲楊輝三角的數據

• 定義vector<vector<int>> vp，對vp的第i行開辟i+1個空間，并且都初始化為1(方便進行數據操作)
• 然后從第二行(下標為2)，第一個(下標為1)位置開始填充數據。
• 填充完成之后進行輸出（注意輸出使用printf，%5d來保證每個數據寬為5

2. 定義一個dp表

• 定義一個dp[31][31]的表，表中存儲的是楊輝三角的數據；將表中所以數據初始化為0
• 將dp[1][1]初始化成1，然后進行填充數據
• 這里dp[31][31]確保了我們在進行操作時不會越界。

代碼實現

對于第一種做法

#include<iostream>
#include<vector>using namespace std;int main()
{int n;cin>>n;vector<vector<int>> vp(n);for(int i=0;i<n;i++){vp[i].resize(i+1,1);}for(int i=2;i<n;i++){for(int j=1;j<i;j++){vp[i][j] = vp[i-1][j] + vp[i-1][j-1];}}for(int i=0;i<n;i++){for(int j =0;j<=i;j++){printf("%5d",vp[i][j]);}cout<<endl;}return 0;
}

第二種，定義一個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]);}cout<<endl;}return 0;
}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]);}cout<<endl;}return 0;
}