LeetCode 第 164 场周赛

访问所有点的最小时间

不难看出，从点(x1,y1) 到 (x2,y2) 的步数需要 min(dx,dy),其中 dx = abs(x1-x2),dy = abs(y1-y2)

class Solution {

public:

    int minTimeToVisitAllPoints(vector<vector<int>>& points) {

      int ans(0);

      int x = points[0][0],y = points[0][1];

      for(int i = 1,sz = points.size();i < sz;++i){

        ans += dis(x,y,points[i][0],points[i][1]);

        x = points[i][0],y = points[i][1];

      }

      return ans;

    }

  int dis(int x,int y,int x2,int y2){

    return max(abs(x-x2),abs(y-y2));

  }

};

统计参与通信的服务器

题意：给你一个 01 矩阵，求其中哪些 1 所在的行、列和大于1

class Solution {

public:

    int countServers(vector<vector<int>>& grid) {

      int n = grid.size(), m = grid[0].size();

      bool vis[n][m];

      memset(vis,0,sizeof(vis));

      for(int i = 0;i < n;++i){

        queue<int>que;

        for(int j = 0;j < m;++j) if(grid[i][j]) que.push(j);

        if(que.size() > 1){

          while(!que.empty()){

            int u = que.front();que.pop();

            vis[i][u] = true;

          }

        }

      }

      for(int i = 0;i <m; ++i){

        queue<int>que;

        for(int j = 0;j < n;++j) if(grid[j][i]) que.push(j);

        if(que.size() > 1){

          while(!que.empty()){

            int u = que.front();que.pop();

            vis[u][i] = true;

          }

        }

      }

      int ans(0);

      for(int i = 0;i < n;++i) for(int j = 0;j < m;++j) if(vis[i][j]) ans++;

      return ans;

    }

};

上面的做法是每行(列)计数后标记对应点，最后统计。可以用row[],col[]来统计个数优化一下。

class Solution {

public:

    int countServers(vector<vector<int>>& grid) {

        int n = grid.size(),m = grid[0].size();

        int row[n] = {0},col[m] = {0};

        for(int i = 0;i < n;++i) for(int j = 0;j < m;++j)

          if(grid[i][j]) row[i]++,col[j]++;

        int ans(0);

        for(int i = 0;i < n;++i) for(int j = 0;j < m;++j)

          if(grid[i][j] && (row[i] > 1 || col[j] > 1)) ans ++;

        return ans;

    }

};

搜索推荐系统

题意：给定一个查询串 searchWord，对其每个前缀求同前缀模板串(个数多于3则输出字典序最小的 3 个)

class Solution {

public:

    vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) {

      map<string,priority_queue<string,vector<string>,less<string> > >p;

      for(auto i :products){

        for(int j = 1;j <= i.length();++j){

          string subs = i.substr(0,j);

          if(p.find(subs) == p.end()){

            priority_queue<string,vector<string>,less<string>> que;

            p.insert(make_pair(subs,que));

          }

          p[subs].push(i);

          if(p[subs].size() > 3) p[subs].pop();

        }

      }

      vector<vector<string>> ans(searchWord.length());

      for(int j = 1, sz = searchWord.length();j <= sz;++j){

        string subs = j == sz ? searchWord :searchWord.substr(0,j);

        map<string,priority_queue<string> > ::iterator ret = p.find(subs);

        if(ret != p.end()){

          priority_queue<string,vector<string>,less<string> >que = (ret->second);

          while(que.size() > 0){

            ans[j-1].push_back(que.top());que.pop();

          }

          reverse(ans[j-1].begin(),ans[j-1].end());

        }

      }

      //*/

      return ans;

    }

};

停在原地的方案数

题意：长度为 arrLen 的数组，开始在 0 处，每次可左移、右移、不动(不能移动到边界之外)。求 steps 步之后仍在 0 处的方案数，对 1e9+7 取余。

\[dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + dp[i-1][j+1]
\]

其中，i 表示当前步数，j 表示当前位置

class Solution {

public:

  static const int maxn = 5e2+7;

  static const long long MOD = 1e9+7;

  int dp[maxn][maxn];

  int numWays(int steps, int arrLen) {

    arrLen = min(steps,arrLen);

    dp[0][0] = 1;

    for(int i = 1;i <= steps;++i){

      for(int j = 0;j < arrLen;++j){

        dp[i][j] = dp[i-1][j];

        if(j > 0) dp[i][j] = (dp[i][j] + dp[i-1][j-1])%MOD;

        if(j < arrLen-1) dp[i][j] = (dp[i][j] + dp[i-1][j+1])%MOD;

      }

    }

    return dp[steps][0];

  }

};

巴特西

LeetCode 第 164 场周赛

访问所有点的最小时间

统计参与通信的服务器

搜索推荐系统

停在原地的方案数

最新文章

热门文章