Day 111, ##, Contains Duplicate II, Contains Duplicate III, Maximal Square

Contains Duplicate II
Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between iand j is at most k. ------------------------------------------------
this is one of the onsite interview questiona at fb, and I failed

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int,int> dic;
        for (int i = 0; i < nums.size(); i++) {
            if (dic.find(nums[i]) != dic.end()) {
                return true;
            }
            dic[nums[i]] = i;
            
            // save space
            if (i - k >= 0) {
                dic.erase(nums[i - k]);
            }
        }
        return false;
    }
};

Contains Duplicate III
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
------------------------------------------------------------
方法1，bucket sort，O(n)，如果每个bucket里出现2个元素，则可直接返回true。所以确保了在程序运行过程中每个bucket只可能存在1个或者0个元素
casting的问题
k < 1 或 t < 0 直接返回false

(long long)t + 1, + 1是为了防止当t 为0

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        if (k <= 0 || t < 0) return false;
        unordered_map<long long,int> bucket;
        
        for (int i = 0; i < nums.size(); i++) {
            long long inter = nums[i] + 2147483648;
            long long curBucket = inter / ((long long)t + 1);
            if (bucket.find(curBucket) != bucket.end() 
                || (bucket.find(curBucket - 1) != bucket.end() && abs((long long)nums[i] - bucket[curBucket - 1]) <= t)
                || (bucket.find(curBucket + 1) != bucket.end() && abs((long long)nums[i] - bucket[curBucket + 1]) <= t)) {
                return true;
            }
            
            bucket[curBucket] = (long long)nums[i];
            if (i - k >= 0) {
                long long oldBucket = (nums[i - k] + 2147483648) / ((long long)t + 1);
                bucket.erase(oldBucket);
            }
        }
        
        return false;
    }
};

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.
-------------------------------------------------------------
看了提示tag
O(m * n) 空间, dp[i][j] 代表以i，j为右下角的正方形边长

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<vector<int> > dp(m,vector<int>(n,0));
        int maxSquare = 0;
        
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                dp[i][0] = 1;
                maxSquare = 1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (matrix[0][i] == '1') {
                dp[0][i] = 1;
                maxSquare = 1;
            }
        }
        
        
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    dp[i][j] = 1 + min(dp[i - 1][j - 1],min(dp[i - 1][j],dp[i][j - 1]));
                    maxSquare = max(maxSquare,dp[i][j]);
                }
            }
        }
        
        return maxSquare * maxSquare;
    }
};

O(n)空间优化，注意 else 语句将 dp[j] 清0

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        if (m == 0) return 0;
        int n = matrix[0].size();
        vector<int> dp(n + 1, 0);
        int maxSquare = 0, pre = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n + 1; j++) {
                int temp = dp[j];
                if (matrix[i][j - 1] == '1') {
                    dp[j] = 1 + min(dp[j - 1],min(pre,dp[j]));
                    maxSquare = max(maxSquare,dp[j]);
                }else {
                    dp[j] = 0;
                }
                
                pre = temp;
            }
        }
        
        return maxSquare * maxSquare;
    }
};