首页 > 58同城笔试原题+AC代码

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;
    }
};


全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐