Thursday, April 30, 2015

LeetCode [205] Isomorphic Strings

 205. Isomorphic Strings

Easy

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

Example 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Note:
You may assume both s and t have the same length.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int ns = s.size(), nt = t.size();
        if(ns!=nt) return false;
        unordered_map<char, char> hash1, hash2;
        
        for(int i=0; i<ns; ++i){
            if(hash1.count(s[i])>0 && hash1[s[i]]!=t[i]) return false;
            hash1[s[i]] = t[i];
            
            if(hash2.count(t[i])>0 && hash2[t[i]]!=s[i]) return false;
            hash2[t[i]] = s[i];           
        }
        return true;
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution {
    Map<Character, Character> map1 = new HashMap<>();
    Map<Character, Character> map2 = new HashMap<>();
    public boolean isIsomorphic(String s, String t) {
        for(int i=0; i<s.length(); ++i){
            char c1 = s.charAt(i), c2 = t.charAt(i);
            if(!map1.containsKey(c1)) map1.put(c1, c2);
            if(!map2.containsKey(c2)) map2.put(c2, c1);
            
            if(map1.get(c1)!=c2 || map2.get(c2)!=c1) return false;
        }
        return true;
    }
}
Posted by at No comments:
Labels: ,

LeetCode [204] Count Primes

 204. Count Primes

Easy

Count the number of prime numbers less than a non-negative number, n.

 

Example 1:

Input: n = 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

Example 2:

Input: n = 0
Output: 0

Example 3:

Input: n = 1
Output: 0

 

Constraints:

  • 0 <= n <= 5 * 106
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int countPrimes(int n) {
        if(n==0) return 0;
        bool p[n];
        memset(p, true, (n)*sizeof(bool));
        
        for(int i=2; i<sqrt(n); ++i){
            if(!p[i]) continue;
            for(int j=i; i*j<n; ++j){
                p[i*j] = false;
            }
        }
        
        int ret = 0;
        for(int i=2; i<n; ++i){
            if(p[i]) ret++;
        }
        
        return ret;
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
    int countPrimes(int n) {
        if(n<=2) return 0;
        bool I[n-1];//1,2,3,4,...,n-1
        memset(I,true,n-1);
        I[0] = false;//the first number 1 is not a prime;
        int count = n-2;
        int next_prime_index=1;//the first prime is 2 at index 1;
        int p, q;
        while(next_prime_index<n-1){
            p = next_prime_index+1;//p is prime
            q = p;//q is multiple of p
            while(q+p<n){
                q += p;
                if(I[q-1] == true){
                    I[q-1] = false;//q must not be a prime
                    count--;
                }
            }

            next_prime_index++;
            while(next_prime_index<n-1 && I[next_prime_index]==false){
                next_prime_index++;
            }
        }

        return count;
        
    }
};
Posted by at No comments:
Labels: ,

Wednesday, April 29, 2015

LeetCode [203] Remove Linked List Elements

Ref
[1] https://leetcode.com/problems/remove-linked-list-elements/
OJ
Posted by at No comments:
Labels:

LeetCode [202] Happy Number

202. Happy Number
Easy

Write an algorithm to determine if a number n is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Return True if n is a happy number, and False if not.

Example: 

Input: 19
Output: true
Explanation: 
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
Accepted
526,479
Submissions
1,044,315
//C++: 10ms
class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> cycle;
        while(n>1 && cycle.find(n)==cycle.end()){
            cycle.insert(n);
            int sum = 0;
            while(n){
                int t = n%10;
                sum += t*t;
                n = (n-t)/10;
            }
            n = sum;
        }
        return n==1;
    }
};

//Java
class Solution {
    int getNext (int n)
    {
        int ret = 0;
        while(n>0)
        {
            int d = n%10;
            ret += d*d;
            n = n/10;
        }
        return ret;
    }

    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while(n!=1 && !set.contains(n))
        {
            set.add(n);
            n = getNext(n);
        }
        return n == 1;
    }
}
Posted by at No comments:
Labels:

Thursday, April 16, 2015

LeetCode [201] Bitwise AND of Numbers Range




Note
  • the result of AND is 1 <==> all the operands are 1s.
  • thus the problem is equivalent to finding the continuous 1s starting from the most significant position over all the operands,
  • which is also equivalent to finding the continuous 1s starting from the most significant position over m (the minimum number) and n (the maximum number). 
  • eg., for the 4 number 24, 25, 26,27, there are two continuous 1s starting from the most significant position. Thus, the result is 11000. 
                           11000, 11001, 11010, 11011

  • after the while loop (line 6-8), 
                    mask:       11111111111111111111111111111100
                    mask&m: 00000000000000000000000000011000
                    mask&n:  00000000000000000000000000011000

Ref
[1] https://leetcode.com/problems/bitwise-and-of-numbers-range/
OJ
method1
Posted by at No comments:
Labels: ,

Saturday, April 11, 2015

LeetCode [200] Number of Islands

 200. Number of Islands

Medium

Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

 

Example 1:

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'.
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
vector<vector<int>> dir = {{-1,0},{1,0},{0,-1},{0,1}};

class Solution_dfs {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m==0) return 0;
        int n = grid[0].size();
        if(n==0) return 0;

        int cnt = 0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]=='1'){
                    cnt++;
                    dfs(grid, i, j, m, n);
                }
            }
        }
        return cnt;
    }

    void dfs(vector<vector<char>>& grid, int i, int j, int m, int n){
        grid[i][j] = '0';
        for(int d=0; d<4; ++d){
            int ii = i + dir[d][0];
            int jj = j + dir[d][1];
            if(ii>=0 && ii<m && jj>=0 && jj<n && grid[ii][jj]=='1'){
                dfs(grid, ii, jj, m, n);
            }
        }
    }
};

/****/
class Solution_bfs {
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m==0) return 0;
        int n = grid[0].size();
        if(n==0) return 0;

        int cnt = 0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]=='1'){
                    cnt++;
                    queue<pair<int, int>> que;
                    que.push(pair<int, int>(i, j));
                    grid[i][j] = '0';
                    while(que.size()){
                        int x = que.front().first;
                        int y = que.front().second;
                        que.pop();
                        for(int d=0; d<4; ++d){
                            int x1 = x+dir[d][0];
                            int y1 = y+dir[d][1];
                            if(x1>=0 && x1<m && y1>=0 && y1<n && grid[x1][y1]=='1'){
                                que.push(pair<int, int>(x1, y1));
                                grid[x1][y1] = '0';
                            }
                        }
                    }
                }
            }
        }
        return cnt;
    }
};

/****/
class Solution_union {
    vector<int> id;
    int find(int i){
        while(id[i]!=i){
            i = id[i];
        }
        return i;
    }
    void myUnion(int i, int j){
        int ri = find(i);
        int rj = find(j);
        if(ri<=rj){
            id[rj] = ri;
        }else{
            id[ri] = rj;
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int m = grid.size();
        if(m==0) return 0;
        int n = grid[0].size();
        if(n==0) return 0;
        int N = m*n;
        id.resize(N);

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                id[i*n+j] = i*n+j;
            }
        }

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]=='1'){
                    for(int d=0; d<4; ++d){
                        int ii = i+dir[d][0];
                        int jj = j+dir[d][1];
                        if(ii>=0 && ii<m && jj>=0 & jj<n && grid[ii][jj]=='1'){
                            myUnion(i*n+j, ii*n+jj);
                        }
                    }
                }
            }
        }

        int cnt = 0;

        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]=='1' && id[i*n+j]==i*n+j){
                    cnt++;
                }
            }
        }
        return cnt;
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    int[][] dirs = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    int m, n;
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        int ret = 0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]=='1'){
                    ret++;
                    dfs(grid, i, j);
                }
            }
        }
        return ret;
    }
    
    void dfs(char[][] grid, int i, int j){
        for(int[] d : dirs){
            int ii = i+d[0], jj = j+d[1];
            if(ii>=0 && ii<m && jj>=0 && jj<n && grid[ii][jj]=='1'){
                grid[ii][jj]='0';
                dfs(grid, ii, jj);
            }
        }
    }
}

Follow up1: count rank 2 islands, where a rank 2 island is an island inside a lake located on a continent. A continent is a piece of land located in the ocean; the ocean is any body of water that touches the edges of the map. 

 

Example:

000000000

000001100

001111100

011000100

001010100

001000100

001111100

000000000

It should return 1.

 

=============

Follow up2: If the input 2d array is too large to fit in memory, how to handle?


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include "head.h"

class Solution{
public:
    int rank2island(vector<vector<char> > &board){
        int m = board.size();
        if(!m) return 0;
        int n = board[0].size();
        if(!n) return 0;

 //       PrintVV(board, "board: the original board");
        queue<pair<int ,int>> que;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j]=='0' && (i==0 || j==0 || i==m-1 || j==n-1)){
                    board[i][j] = '2';
                    que.push(pair<int, int>(i, j));
                }
            }
        }
        while(!que.empty()){
            int i = que.front().first, j = que.front().second;
            que.pop();
            bfs(board, i, j, m, n, que, '0', '2');
        }
 //       PrintVV(board, "\nboard:set ocean to 2");//2 is ocean
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j]=='2'){
                    bfs(board, i, j, m, n, que, '1', '3');
                }
            }
        }
        while(!que.empty()){
            int i = que.front().first, j = que.front().second;
            que.pop();
            bfs(board, i, j, m, n, que, '1', '3');
        }
//        PrintVV(board, "\nboard:set continent to 3");

        int cnt = 0;
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(board[i][j]=='1') cnt++;
            }
        }

//        cout<<"\nthe number of rank 2 islands is "<<cnt<<endl;
        return cnt;
    }

    void bfs(vector<vector<char>> &board, int i, int j, int m, int n, queue<pair<int, int>> &que, char a, char b){
        if(i-1>=0 && board[i-1][j]==a){board[i-1][j]=b; que.push(pair<int, int>(i-1, j));}
        if(i+1<m && board[i+1][j]==a){board[i+1][j]=b; que.push(pair<int, int>(i+1, j));}
        if(j-1>=0 && board[i][j-1]==a){board[i][j-1]=b; que.push(pair<int, int>(i, j-1));}
        if(j+1<n && board[i][j+1]==a){board[i][j+1]=b; que.push(pair<int, int>(i, j+1));}
        if(i-1>=0 && j-1>=0 && board[i-1][j-1]==a){board[i-1][j-1]=b; que.push(pair<int, int>(i-1, j-1));}
        if(i-1>=0 && j+1<n && board[i-1][j+1]==a){board[i-1][j+1]=b; que.push(pair<int, int>(i-1, j+1));}
        if(i+1<m && j-1>=0 && board[i+1][j-1]==a){board[i+1][j-1]=b; que.push(pair<int, int>(i+1, j-1));}
        if(i+1<m && j+1<n && board[i+1][j+1]==a){board[i+1][j+1]=b; que.push(pair<int, int>(i+1, j+1));}
    }

};

int main(){
  vector<vector<char> > board1{{'0','0','0','0','0','0','0','0','0'},\
                               {'0','0','0','0','0','1','1','0','0'},\
                               {'0','0','1','1','1','1','1','0','0'},\
                               {'0','1','1','0','0','0','1','0','0'},\
                               {'0','0','1','0','1','0','1','0','0'},\
                               {'0','0','1','0','0','0','1','0','0'},\
                               {'0','0','1','1','1','1','1','0','0'},\
                               {'0','0','0','0','0','0','0','0','0'}};

  vector<vector<char> > board2{{'0','0','1','0','0','0','0','0','0'},\
                               {'0','1','1','1','1','1','0','0','0'},\
                               {'0','1','0','0','0','1','0','0','0'},\
                               {'0','1','0','1','0','1','0','0','0'},\
                               {'0','1','0','0','0','1','0','0','0'},\
                               {'0','1','1','1','1','1','0','0','0'},\
                               {'0','0','0','0','0','0','0','0','0'},\
                               {'0','0','0','0','0','0','0','0','0'},\
                               {'0','1','1','1','1','1','0','0','0'},\
                               {'0','1','0','0','0','1','0','0','0'},\
                               {'0','1','0','1','0','1','0','0','0'},\
                               {'0','1','0','0','0','1','0','0','0'},\
                               {'0','1','1','1','1','1','0','0','0'},\
                               {'0','0','0','0','0','0','0','0','0'}};
  Solution sol;
  sol.rank2island(board2);
  return 0;
}

YMSF

follow up: 返回每个island的面积。当有被陆地包围的湖泊时，湖泊面积也算在island内。

e.g.

[0,0,0,0,1]

[0,1,1,1,0]

[0,1,0,1,0]

[0,1,1,1,0]

[0,0,0,0,0]

两个island，第一个面积为1，第二个为9.


请问第一题有啥思路吗？我的做法是先遍历一遍，然后把所有的和边界相连的'0‘ 变成 ’*‘， 第二次遍历的时候剩下的'0' 和 '1' 就是岛屿面积。

不知道还有什么更好的方法


我给的也是这个办法。感觉复杂度应该很难提高了。


想问一下楼主第一题下面这三种算不算包围呢? 谢谢


[0,1,0]

[1,0,1]

[0,1,0]


[0,1,1]

[1,0,1]

[1,1,0]


[0,1,1]

[1,0,1]

[1,1,1]

算的，相邻按四个方向的来算。

题目问每个岛屿面积分别多少，没想明白被环绕的湖泊面积（环绕的0）怎么算，比如

0 0 0 0 1 0

0 1 1 1 0 1

0 1 0 1 0 1

0 1 1 1 1 0

0 0 0 0 0 0


难道是标完*以后第二次遍历的时候，不管是1还是0 都算同时分别计数0和1的数量？是我想简单了么...

求指教


YMSF

后头的followup貌似是正题，因为前头那个写的还挺快，但确确实实是正题，scenario不重要，但建议大家要review一下Dijkstra Algorithm。。。回头看了下刷题网竟然没有这个算法在矩阵上头应用的题。。。sooooo good luck

Posted by at No comments:
Labels: , , , , ,
Subscribe to: Posts (Atom)