58同城笔试原题+AC代码
1.
//58-1
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void dfs(int x,int y ,vector< vector<int> >&visited,vector< vector<int> >&g)
{
int h=g.size();
int w=g[0].size();
visited[x][y]=1;
for(int i=0;i<4;i++)
{
int x_new=x+dir[i][0];
int y_new=y+dir[i][1];
if(x_new>=0 && x_new<h && y_new>=0 && y_new<w && visited[x_new][y_new]==0 && g[x_new][y_new]==1)
dfs( x_new,y_new ,visited,g);
}
}
int main()
{
int w,h;
cin>>h;
cin>>w;
vector< vector<int> >g(h,vector<int>(w,0));
vector< vector<int> >visited(h,vector<int>(w,0));
for(int i=0;i<h;i++)
for(int j=0;j<w;j++)
cin>>g[i][j];
int count=0;
for(int i=0;i<h;i++)
for(int j=0;j<w;j++)
{
if(g[i][j]==1 && visited[i][j]==0)
{
dfs(i,j,visited,g);
count++;
}
}
cout<<count<<endl;
}
2.
class Solution {
public:
/**
*
* @param node TreeNode类
* @return int整型vector<vector<>>
*/
vector<vector<int> > printNode(TreeNode* node)
{
// write code here
vector< vector<int> >result;
queue<TreeNode*>q;
q.push(node);
while(!q.empty())
{
int n=q.size();
vector<int>v;
while(n)
{
TreeNode* temp=q.front();
v.push_back(temp->val);
q.pop();
n--;
if(temp->left) q.push(temp->left);
if(temp->right)q.push(temp->right);
}
result.push_back(v);
}
return result;
}
};
3.
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for(int i=0;i<n;i++)
{
while(nums[i]>0 && nums[i]<=n && nums[i]!=nums[nums[i]-1])
swap(nums[i],nums[nums[i]-1]);
}
for(int i=0;i<n;i++)
if(nums[i]!=i+1)
return i+1;
return n+1;
}
};
查看29道真题和解析