前四道题都是LeetCode原题,题号在注释中给出
//求字符串最大不重复子串 LeetCode 第3题#include <iostream>#include <cstring>#include <cstdlib>#include <math.h>#include <algorithm>using namespace std;int getLongestSubString(string s){int arr[256]; //数组中存放的是每一个字符的下标位置;memset(arr, -1, sizeof(arr));int pre = 0;int maxLen = 0; //pre用来存放出现不重复子串的首地址int n = s.length();for (int i=0; i<n; i++){if (arr[s[i]] != -1){if (arr[s[i]] >= pre){pre = arr[s[i]] + 1;}arr[s[i]] = i;}else{arr[s[i]] = i;}maxLen = max(maxLen, i-pre+1);}return maxLen;}int main(){string str;getline(cin, str);cout << getLongestSubString(str) << endl;return 0;}
//LeetCode 第200题#include <iostream>#include <vector>using namespace std;int dfs(vector<vector<int>>& numOfBG, int x, int y,vector<vector<bool>>& vis){if(x >= numOfBG.size() || y >= numOfBG[0].size() || x < 0 || y < 0)return 0;if(vis[x][y] == true)return 0;if(numOfBG[x][y] == 0)return 0;// 对于点[x,y]搜索上下左右4个点是否是岛屿// 即[x-1,y],[x+1,y],[x,y-1],[x,y+1]// 对于已经搜索过的点要进行标记vis[x][y] = true;// 遍历周围4个点return 1 + dfs(numOfBG, x+1, y, vis) + dfs(numOfBG, x-1, y, vis) + dfs(numOfBG, x, y+1, vis) + dfs(numOfBG, x, y-1, vis);}void maxOfBG(vector<vector<int>>& numOfBG) {if(numOfBG.empty())return;int num = 0;//int res = 0;vector<vector<bool>> vis(numOfBG.size(),vector<bool>(numOfBG[0].size(),false));// 定义标记数组// 定义搜索边界int mostDeep = numOfBG.size();int mostRight = numOfBG[0].size();//开始搜索for(int i = 0;i < mostDeep;i++){for(int j = 0;j < mostRight;j++){if(vis[i][j] == true)continue;if(numOfBG[i][j] == 0){vis[i][j] = true;continue;}dfs(numOfBG, i, j, vis);int temp = dfs(numOfBG, i, j, vis);++num;//grid[i][j] = 8;//res = res>temp ? res : temp;}}cout << num << endl;}int main(){int m;cin >> m;vector<vector<int>> numOfBG(m, vector<int>(m,0));for(int i=0; i<m; i++){for(int j=0; j<m; j++){cin >> numOfBG[i][j];}}maxOfBG(numOfBG);return 0;}
//LeetCode 第93题#include <iostream>#include <vector>#include <algorithm>#include <string>#include <bits/stdc++.h>using namespace std;bool isValidIP(string str){if (str.size()>1 && str[0]=='0')return false;int res = atoi(str.c_str());return res<=255 && res>=0;}void DFS(string str, string half, int &res, int count){if (count==3 && isValidIP(str)){res++;return;}//可以取1-3个字符for (int i=1; i<=3&&i<str.size(); ++i){//特别需要注意i<s.size(){string stemp = str.substr(0, i);if(isValidIP(stemp))DFS(str.substr(i), half+stemp+".", res, count+1);}}int main(){string str;getline(cin, str);if (str.size()<4 || str.size()>12)return 0;int res = 0;//如果需要统计所有IP,只需要将res换成数组,在res++的地方进行push_back即可DFS(str, "", res, 0);cout << res << endl;return 0;}
//LeetCode 第393题#include <bits/stdc++.h>using namespace std;bool isUTF8(vector<int>& arr) {int mask1=128, mask2=192, cnt=0;for(int i = 0; i < arr.size(); i++){int cur = arr[i];if (cnt == 0) {while ((cur & mask1) != 0){cur <<= 1;cnt++;}if (cnt == 1)return false;cnt = max(0, cnt - 1);}else{if ((arr[i] & mask2) != mask1)return false;cnt--;}}return cnt == 0;}int main(){int n;cin >> n;vector<int> arr;for(int i=0; i<n; i++){int temp;cin >> temp;arr.push_back(temp);}cout << isUTF8(arr) << endl;return 0;}
这个题当时没搞出来,主要是Tarjan算法 有向连通图问题
#include <iostream>using namespace std;void eee(int **canshu,int ki,int * aswdd,int cc);int main() {int N,M;int x,y,result=0;scanf("%d",&N);scanf("%d",&M);int ** a =new int*[N];for (int i = 0;i<N;i++)a[i] = new int[N];for(int i=0;i<N;i++){for (int j =0;j<N;j++){a[i][j]=0;}}for (int i =0;i<M;i++){cin >> x >> y;a[x-1][y-1] = 1;}int * b =new int[N];int flag =0;for (int i = 0;i<N;i++){flag = 0;for (int j =0;j<N;j++)b[j]=0;b[i]=1;eee(a,N,b,i);for (int j=0;j<N;j++)if (b[j]==0)flag = 1;if (flag == 0)result++;}cout << result <<endl;for (int i=0;i<N;i++)delete [] a[i];delete [] a;system("pause");return 0;}void eee(int **canshu,int ki,int * aswdd,int cc){int **a1 =canshu;int a2 =ki;int *a3 =aswdd;int a4=cc;if (aswdd[cc]>1)return;for (int i = 0;i<ki;i++){if (canshu[i][cc]==1){aswdd[i]++;eee(a1,a2,a3,i);}}}
如果觉得《字节跳动校园招聘研发岗位第三次笔试-.09.09》对你有帮助,请点赞、收藏,并留下你的观点哦!