LeetCode Weekly Contest 22

LeetCode Weekly Contest 22
[2017-03-05]

1. k-diff Pairs in an Array
2. Lonely Pixel I
3. Lonely Pixel II
4. Freedom Trail

---

K-diff Pairs in an Array

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.
Example 1:

Input: [3, 1, 4, 1, 5], k = 2
Output: 2
Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

Input:[1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

Input: [1, 3, 1, 5, 4], k = 0
Output: 1
Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won’t exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].

Code

class Solution {
public:
    /**
     * for every number in the array:
     *  - if there was a number previously k-diff with it, save the smaller to a set;
     *  - and save the value to a set;
     */
    int findPairs(vector<int>& nums, int k) {
        if (k < 0) {
            return 0;
        }
        set<int> starters;
        set<int> indices;
        for (int i = 0; i < nums.size(); i++) {
            if (indices.find(nums[i] - k) != indices.end()) {
                starters.insert(nums[i] - k);
            }
            if (indices.find(nums[i] + k) != indices.end()) {
                starters.insert(nums[i]);
            }
            indices.insert(nums[i]);
        }
        
        return starters.size();
    }
};

---

Lonely Pixel I

Given a picture consisting of black and white pixels, find the number of black lonely pixels.

The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.

A black lonely pixel is character ‘B’ that located at a specific position where the same row and same column don’t have any other black pixels.

Example:

Input: 
[['W', 'W', 'B'],
 ['W', 'B', 'W'],
 ['B', 'W', 'W']]

Output: 3
Explanation: All the three 'B's are black lonely pixels.

Note

1. The range of width and height of the input 2D array is [1,500].

Code

class Solution {
public:

    /**
     * suppose matrix is m*n, there is at most min(m, n) lonely pixels, 
	 * because there could be no more than 1 in each row, or column;
     * therefore, if we record num of black pixel on each row and column, 
	 * we can easily tell whether each pixel is lonely or NO.
     * 
     */
    int findLonelyPixel(vector<vector<char>>& picture) {
        if (!picture.size() || !picture[0].size()) {
            return 0;
        }
        
        int m = picture.size();
        int n = picture[0].size();
        vector<int> rows = vector<int>(m, 0);
        vector<int> cols = vector<int>(n, 0);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                rows[i] += picture[i][j] == 'B';
                cols[j] += picture[i][j] == 'B';
            }
        }

        int lonely = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n && rows[i] > 0; j++) {
                lonely += picture[i][j] == 'B' && rows[i] == 1 && cols[j] == 1;
            }
        }

        return lonely;
    }
};

---

Lonely Pixel II

Given a picture consisting of black and white pixels, and a positive integer N, find the number of black pixels located at some specific row R and column C that align with all the following rules:

1. Row R and column C both contain exactly N black pixels.
2. For all rows that have a black pixel at column C, they should be exactly the same as row R

The picture is represented by a 2D char array consisting of ‘B’ and ‘W’, which means black and white pixels respectively.
Example:

Input:                                            
[['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'B', 'W', 'B', 'B', 'W'],    
 ['W', 'W', 'B', 'W', 'B', 'W']] 

N = 3
Output: 6
Explanation: All the bold 'B' are the black pixels we need (all 'B's at column 1 and 3).
        0    1    2    3    4    5         column index                                            
0    [['W', 'B', 'W', 'B', 'B', 'W'],    
1     ['W', 'B', 'W', 'B', 'B', 'W'],    
2     ['W', 'B', 'W', 'B', 'B', 'W'],    
3     ['W', 'W', 'B', 'W', 'B', 'W']]    
row index

Take 'B' at row R = 0 and column C = 1 as an example:
Rule 1, row R = 0 and column C = 1 both have exactly N = 3 black pixels. 
Rule 2, the rows have black pixel at column C = 1 are row 0, row 1 and row 2. They are exactly the same as row R = 0.

Note:

1. The range of width and height of the input 2D array is [1,200].

Code

/**
    * Analysis:
    * rule 1 can be easily achieved by create 2 vector<int> rows, cols; to record black pixel in each row & col;
    * for rule 2, you need to 1st, know the rows black on col[j], which can be achieved by using vector<set<int>> cols;
    * 2nd able to compare those rows as string or bitmap or simply vector<char>;
    * 
    * Steps:
    * 1. create map<int, set<int>> cols; map<int, set<int>> rows;
    * 2. for every pixel meet rule 1: pic[i][j] == 'B' && rows[i].size() == N && cols[j].size() == N
    *       rule2: for every row k in cols[j];  check that row[k] = row[i];
    */

class Solution {
public:
    int findBlackPixel(vector<vector<char>>& pic, int N) {
        if (!pic.size() || !pic[0].size()) {
            return 0;
        }
        
        int m = pic.size();
        int n = pic[0].size();
        unordered_map<int, set<int>> rows;
        unordered_map<int, set<int>> cols;

        /* 1. create map<int, set<int>> cols; map<int, set<int>> rows; */
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (pic[i][j] == 'B') {
                    rows[i].insert(j);
                    cols[j].insert(i);
                }
            }
        }

        /* 2. 2. for every pixel meet rule 1: pic[i][j] == 'B' && rows[i].size() == N && cols[j].size() == N */
        int lonelys = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n && rows.count(i); j++) {
                if (pic[i][j] == 'B' && rows[i].size() == N && cols[j].size() == N) {
                    /* rule2: for every row k in cols[j];  check that row[k] = row[i]; */
                    bool lonely = true;
                    for (int r : cols[j]) {
                        if (rows[r] != rows[i]) {
                            lonely = false; break;
                        }
                    }
                    lonelys += lonely;
                }
            }
        }

        return lonelys;
    }
};

---

Freedom Trail

In the video game Fallout 4, the quest “Road to Freedom” requires players to reach a metal dial called the “Freedom Trail Ring”, and use the dial to spell a specific keyword in order to open the door.

Given a string ring, which represents the code engraved on the outer ring and another string key, which represents the keyword needs to be spelled. You need to find the minimum number of steps in order to spell all the characters in the keyword.

Initially, the first character of the ring is aligned at 12:00 direction. You need to spell all the characters in the string key one by one by rotating the ring clockwise or anticlockwise to make each character of the string key aligned at 12:00 direction and then by pressing the center button.
At the stage of rotating the ring to spell the key character key[i]:

1. You can rotate the ring clockwise or anticlockwise one place, which counts as 1 step. The final purpose of the rotation is to align one of the string ring’s characters at the 12:00 direction, where this character must equal to the character key[i].
2. If the character key[i] has been aligned at the 12:00 direction, you need to press the center button to spell, which also counts as 1 step. After the pressing, you could begin to spell the next character in the key (next stage), otherwise, you’ve finished all the spelling.

Example:

Input: ring = "godding", key = "gd"
Output: 4
Explanation:
 For the first key character 'g', since it is already in place, we just need 1 step to spell this character. 
 For the second key character 'd', we need to rotate the ring "godding" anticlockwise by two steps to make it become "ddinggo".
 Also, we need 1 more step for spelling.
 So the final output is 4.

Note:

1. Length of both ring and key will be in range 1 to 100.
2. There are only lowercase letters in both strings and might be some duplcate characters in both strings.
3. It’s guaranteed that string key could always be spelled by rotating the string ring.

Code

public class Solution {
    public int findRotateSteps(String ring, String key) {
        int n = ring.length();
        int m = key.length();
        int[][] dp = new int[m + 1][n];
        
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = Integer.MAX_VALUE;
                for (int k = 0; k < n; k++) {
                    if (ring.charAt(k) == key.charAt(i)) {
                        int diff = Math.abs(j - k);
                        int step = Math.min(diff, n - diff);
                        dp[i][j] = Math.min(dp[i][j], step + dp[i + 1][k]);
                    }
                }
            }
        }
        
        return dp[0][0] + m;
    }
}