LeetCode Contest 53 带你飞

2017-10-10 飞起来的 北美加群小助手Jogchat 北美加群小助手Jogchat


正在刷题的同学,从今天开始,PKUSPEED大神周末开车啦🚗🚗!他会带来当周最新leetcode contest的题目和思路,帮助大家第一时间见到新题目、收获新思路!Leetcode contest是Leetcode每周末举办的算法题竞赛,题目有的新颖,有的颇费脑力。而我们的PKUSPEED同学是拿到了9枚金牌🏅️的顶级选手,曾经也在更加正式的奥林匹克竞赛中展露头角。跟着他看一看想一想这些题目,感觉还有点小激动呢~


Problem #1. Binary Number with Alternating Bits

leetCode 题号 693

题目:Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

题解:没啥好说的,把二进制写出来即可。

class Solution {
public:
   bool hasAlternatingBits(int n) {
       vector<int> A;
       while(n){
           A.push_back(n%2);
           n/=2;
       }
       for(int i=1;i<A.size();++i) if(A[i]==A[i-1]) return false;
       return true;
   }
};


Problem #2. Max Area of Island

leetCode 题号 695

题目:Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

题解:遍历一遍matrix,然后对每一个Island进行BFS即可

typedef vector<bool> vb;
typedef vector<int> vi;
class Solution {
   int dx[4] = {1, -1, 0, 0};
   int dy[4] = {0, 0, 1, -1};
   int n,m;
   vector<vb> F;
   int bfs(int i, int j, vector<vi> &grid){
       queue<int> que;
       que.push(i*m + j);
       F[i][j] = true;
       int cnt = 1;
       while(!que.empty()){
           int cor = que.front();
           que.pop();
           int i0 = cor/m, j0 = cor%m;
           for(int k=0;k<4;++k){
               int i1 = i0+dx[k], j1 = j0 + dy[k];
               if(i1>=0 && i1<n && j1>=0 && j1<m && !F[i1][j1] && grid[i1][j1]){
                   que.push(i1*m+j1);
                   F[i1][j1] = true;
                   ++cnt;
               }
           }
       }
       return cnt;
   }
public:
   int maxAreaOfIsland(vector<vector<int>>& grid) {
       if(grid.empty() || grid[0].empty()) return 0;
       n = grid.size();
       m = grid[0].size();
       F = vector<vb>(n, vb(m, false));
       int ans = 0;
       for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(grid[i][j] && !F[i][j]){
           ans = max(ans, bfs(i,j,grid));
       }
       return ans;
   }
};


Problem #3. Number of Distinct Islands

leetCode 题号 694

题目:Given a non-empty 2D array grid of 0's and 1's, an island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

Count the number of distinct islands. An island is considered to be the same as another if and only if one island can be translated (and not rotated or reflected) to equal the other.

题解:跟上题基本完全一样,只不过所求的从面积变成了configuration。对于每一个island,我们可以用一个 set of coordinates 来表征其结构。这里的 coordinates 是相对坐标,也就是相对于最小点的位置矢量,这样每一个一个set 跟 一种configuration 一一对应,我们只需要找distinct set的个数即可。

typedef vector<int> vi;
typedef vector<bool> vb;
typedef pair<int, int> ii;
class Solution {
   int dx[4] = {1, -1, 0, 0};
   int dy[4] = {0, 0, 1, -1};
   int n,m;
   vector<vb> F;
   set<ii> bfs(int i, int j, vector<vi> &grid){
       set<ii> tmp;
       queue<ii> que;
       que.push(ii(i,j));
       F[i][j] = true;
       tmp.insert(ii(i,j));
       while(!que.empty()){
           int i0=que.front().first, j0=que.front().second;
           que.pop();
           for(int k=0;k<4;++k){
               int i1 = i0+dx[k], j1 = j0+ dy[k];
               if(i1>=0 && i1<n && j1>=0 &&j1<m && grid[i1][j1] && !F[i1][j1]){
                   que.push(ii(i1,j1));
                   F[i1][j1] = true;
                   tmp.insert(ii(i1,j1));
               }
           }
       }
       int x = tmp.begin()->first, y = tmp.begin()->second;
       set<ii> ans;
       for(auto p:tmp) ans.insert(ii(p.first-x, p.second-y));
       return ans;
   }
public:
   int numDistinctIslands(vector<vector<int>>& grid) {
       if(grid.empty() || grid[0].empty()) return 0;
       n = grid.size();
       m = grid[0].size();
       F = vector<vb>(n, vb(m, false));
       set<set<ii> > ans;
       for(int i=0;i<n;++i) for(int j=0;j<m;++j) if(grid[i][j] && !F[i][j]){
           ans.insert(bfs(i,j,grid));
       }
       return (int)ans.size();
   }
};



Problem #4. Stickers to Spell Word

leetCode 题号 691

题目:We are given N different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given target string by cutting individual letters from your collection of stickers and rearranging them.

You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

What is the minimum number of stickers that you need to spell out the target? If the task is impossible, return -1.

example:

Input:

["with", "example", "science"], "thehat"

Output:

3

题解:用一个长为26的数组来标记 target 的状态,也就是 target 中每个字母出现的次数。然后通过 dfs + memo dp 来找最少需要的 sticker 的个数。dp 中的 key 就是数组本身,由于题目中交代了,target 的长度不超过15,所以是规模非常小的题目,所以基本上不会出现超空间的问题。另外 -1 的情况单独讨论一下,就是 target 中存在某些字母,这些字母在所有的 stickers 中都没有出现。具体code如下:

typedef vector<int> vi;
class Solution {
   map<vi, int> dp;
   vector<vi> f;
   int dfs(vi state){
       if(dp.count(state)) return dp[state];
       int ans = INT_MAX;
       for(auto v:f){
           vi tmp(26,0);
           bool ok = false;
           for(int i=0;i<26;++i){
               tmp[i] = max(0, state[i] - v[i]);
               if(tmp[i]<state[i] && !ok) ok = true;
           }
           if(ok) ans = min(ans, 1 + dfs(tmp));
       }
       return dp[state] = ans;
   }
public:
   int minStickers(vector<string>& stickers, string target) {
       if(target.empty()) return 0;
       vi state(26, 0);
       dp[state] = 0;
       set<char> s1,s2;
       for(auto c:target){
           state[(int)(c-'a')]++;
           s1.insert(c);
       }
       for(auto s:stickers){
           vi tmp(26, 0);
           for(auto c:s){
               tmp[(int)(c-'a')]++;
               if(s1.count(c)) s2.insert(c);
           }
           f.push_back(tmp);
       }
       if(s1.size() > s2.size()) return -1;
       return dfs(state);
   }
};




长按扫码关注



阅读 5622

微信扫一扫
关注该公众号