LIKE CODING

Wednesday, June 12, 2019

LeetCode [413] Arithmetic Slices

A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, these are arithmetic sequence:

1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9

The following sequence is not arithmetic.

1, 1, 2, 5, 7

A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.

A slice (P, Q) of array A is called arithmetic if the sequence:
A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.

The function should return the number of arithmetic slices in the array A.

Example:

A = [1, 2, 3, 4]

return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.

 class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        int ret = 0;
        vector<int> dp(n, 0);//dp[i] is the number of slices ending at i
        for(int i=2; i<n; ++i){
            if(A[i]-A[i-1]==A[i-1]-A[i-2]){
                dp[i] = dp[i-1]+1;
                ret += dp[i];
            }
        }
        return ret;
    }
};

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& A) {
        int n = A.size();
        int ret = 0;
        int slices0 = 0;
        for(int i=2; i<n; ++i){
            if(A[i]-A[i-1]==A[i-1]-A[i-2]){
                int slices1 = slices0+1;
                ret += slices1;
                slices0 = slices1;
            }else{
                slices0 = 0;
            }
        }
        return ret;
    }
};

Tuesday, June 11, 2019

LeetCode [635] Design Log Storage System

You are given several logs that each log contains a unique id and timestamp. Timestamp is a string that has the following format: Year:Month:Day:Hour:Minute:Second, for example, 2017:01:01:23:59:59. All domains are zero-padded decimal numbers.

Design a log storage system to implement the following functions:

void Put(int id, string timestamp): Given a log's unique id and timestamp, store the log in your storage system.

int[] Retrieve(String start, String end, String granularity): Return the id of logs whose timestamps are within the range from start to end. Start and end all have the same format as timestamp. However, granularity means the time level for consideration. For example, start = "2017:01:01:23:59:59", end = "2017:01:02:23:59:59", granularity = "Day", it means that we need to find the logs within the range from Jan. 1st 2017 to Jan. 2nd 2017.

Example 1:

put(1, "2017:01:01:23:59:59");
put(2, "2017:01:01:22:59:59");
put(3, "2016:01:01:00:00:00");
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Year"); // return [1,2,3], because you need to return all logs within 2016 and 2017.
retrieve("2016:01:01:01:01:01","2017:01:01:23:00:00","Hour"); // return [1,2], because you need to return all logs start from 2016:01:01:01 to 2017:01:01:23, where log 3 is left outside the range.

Note:

There will be at most 300 operations of Put or Retrieve.
Year ranges from [2000,2017]. Hour ranges from [00,23].
Output for Retrieve has no order required.

class LogSystem {
    map<string, vector<int>> mp;//time, id
    map<string, int> unit;
public:
    LogSystem() {
        unit["Year"] = 0;
        unit["Month"] = 1;
        unit["Day"] = 2;
        unit["Hour"] = 3;
        unit["Minute"] = 4;
        unit["Second"] = 5;
    }
    
    //t1>t2: 1; t1==t2 0; t1<t2 -1
    int comp(string t1, string t2, string gra){
        stringstream s1(t1), s2(t2);
        for(int i=0; i<=unit[gra]; ++i){
            string v1, v2;
            getline(s1, v1 ,':');
            getline(s2, v2 ,':');
            if(v1>v2) return 1;
            if(v1<v2) return -1;
        }
        return 0;
    }

    void put(int id, string timestamp) {
        mp[timestamp].push_back(id);
    }
    
    vector<int> retrieve(string s, string e, string gra) {
        vector<pair<string, vector<int>>> vec;
        for(auto m:mp){
            vec.push_back(make_pair(m.first, m.second));
        }
        sort(vec.begin(), vec.end());
        vector<int> ret;
        for(auto v:vec){
            if(comp(v.first, s, gra)>=0 && comp(v.first, e, gra)<=0){
                ret.insert(ret.end(), v.second.begin(), v.second.end());
            }
        }
        return ret;
    }
};

class LogSystem {
    TreeMap<String, Integer> tMap;
    public int compare(String s1, String s2){
        String[] ss1 = s1.split(":");
        String[] ss2 = s2.split(":");
        for(int i=0; i<6; ++i){
            if(ss1[i].compareTo(ss2[i])!=0) return ss1[i].compareTo(ss2[i]);
        }
        return 0;
    }
    public LogSystem() {
        tMap = new TreeMap<String, Integer>((a, b) ->  compare(a,b));
    }
    
    public void put(int id, String timestamp) {
        tMap.put(timestamp, id);
    }
    
    String processTime(String str, String granularity, boolean isStart){
        int index = -1;
        if(granularity.equals("Year")) index = 0;
        if(granularity.equals("Month")) index = 1;
        if(granularity.equals("Day")) index = 2;
        if(granularity.equals("Hour")) index = 3;
        if(granularity.equals("Minute")) index = 4;
        if(granularity.equals("Second")) index = 5;
        String[] strs = str.split(":");
        for(int i=index+1; i<6; ++i) strs[i] = isStart?"00":"59";
        StringBuilder sb = new StringBuilder();
        for(String s : strs){
            if(sb.length()>0) sb.append(":");
            sb.append(s);
        }
        return sb.toString();
    }

    public List<Integer> retrieve(String start, String end, String granularity) {
        
        List<Integer> list = new ArrayList<>();
        if(compare(start, end)>0) return list;
        String l = tMap.ceilingKey(processTime(start, granularity, true));
        String r = tMap.floorKey(processTime(end, granularity, false));
        if(l==null || r==null || compare(l, r)>0) return list;
        for(int id : tMap.subMap(l, true, r, true).values()){
            list.add(id);
        }
        return list;
    }
}

Monday, June 10, 2019

LeetCode [408] Valid Word Abbreviation

Given a non-empty string s and an abbreviation abbr, return whether the string matches with the given abbreviation.

A string such as "word" contains only the following valid abbreviations:

["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]

Notice that only the above abbreviations are valid abbreviations of the string "word". Any other string is not a valid abbreviation of "word".

Note:
Assume s contains only lowercase letters and abbr contains only lowercase letters and digits.

Example 1:

Given s = "internationalization", abbr = "i12iz4n":

Return true.

Example 2:

Given s = "apple", abbr = "a2e":

Return false.

class Solution {
public:
    bool validWordAbbreviation(string word, string abbr) {
        int i = 0, j = 0, sw = word.size(), sa = abbr.size();
        while(i<sw && j<sa){
            if(word[i]==abbr[j])
            {
                i++; j++;
            }
            else{
                if(!isdigit(abbr[j])||abbr[j]=='0') return false;
                int k = j;
                while(k<sa && isdigit(abbr[k])) k++;
                int cnt = stoi(abbr.substr(j, k-j));
                j = k;
                i += cnt;
            }
        }
        
        return (i==sw && j==sa);
    }
};

LeetCode [416] Partition Equal Subset Sum

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.

class Solution { public: bool canPartition(vector& nums) { bitset<10001> bits(1); int sum = accumulate(nums.begin(), nums.end(), 0); for (auto n : nums) bits |= bits << n; return !(sum & 1) && bits[sum >> 1]; } };

Sunday, June 9, 2019

LeetCode [477] Total Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

Elements of the given array are in the range of 0 to 10^9
Length of the array will not exceed 10^4.

https://leetcode.com/problems/total-hamming-distance/discuss/96226/Java-O(n)-time-O(1)-Space

//"For each bit position 1-32 in a 32-bit integer, we count the number of integers in the array which have that bit set. Then, if there are n integers in the array and k of them have a particular bit set and (n-k) do not, then that bit contributes k*(n-k) hamming distance to the total."
class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int total = 0, n = nums.size();
        for (int j=0;j<32;j++) {
            int bitCount = 0;
            for (int i=0;i<n;i++) 
                bitCount += (nums[i] >> j) & 1;
            total += bitCount*(n - bitCount);
        }
        return total;        
    }
};

Saturday, June 8, 2019

LeetCode [461] Hamming Distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

class Solution {
public:
    int hammingDistance(int x, int y) {
        int z = x^y;
        int ret = 0;
        while(z){
            ret += (z%2);
            z >>= 1;
        }
        return ret;
    }
};

Friday, June 7, 2019

LeetCode [805] Split Array With Same Average

In a given integer array A, we must move every element of A to either list B or list C. (B and C initially start empty.)

Return true if and only if after such a move, it is possible that the average value of B is equal to the average value of C, and B and C are both non-empty.

Example :
Input: 
[1,2,3,4,5,6,7,8]
Output: true
Explanation: We can split the array into [1,4,5,8] and [2,3,6,7], and both of them have the average of 4.5.

Note:

The length of A will be in the range [1, 30].
A[i] will be in the range of [0, 10000].

class Solution
{
public:
    bool splitArraySameAverage(vector<int> &A)
    {
        int sz = A.size();
        int szb = sz / 2; //size of the smaller array
        int sum = 0;
        for (auto n : A)
            sum += n;
        bool possible = false;
        for (int k = 1; k <= szb; ++k)
        {
            if (sum * k % sz == 0)
            {
                possible = true;
                break;
            }
        }
        if (!possible)
            return false;

        vector<unordered_set<int>> dp(szb+1);
        dp[0].insert(0);
        for(int i=0; i<sz; ++i){
            vector<unordered_set<int>> dp0 = dp;
            for(int j=1; j<=min(szb,i+1); ++j){
                for(auto s:dp0[j-1]){
                    dp[j].insert(s+A[i]);
                }
            }
        }

        for(int k=1; k<=szb; ++k){
            if(sum*k%sz==0 && dp[k].count(sum*k/sz)!=0) return true;
        }

        return false;
    }
};