LIKE CODING

Saturday, June 15, 2019

LeetCode [415] Add Strings

Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

class Solution {
public:
    string addStrings(string num1, string num2) {
        int i = num1.size()-1, j = num2.size()-1;
        string ret = "";
        int c = 0;
        while(i>=0 && j>=0){
            int s = (num1[i--]-'0') + (num2[j--]-'0') + c;
            ret = to_string(s%10) + ret;
            c = s/10;
        }
        
        while(i>=0){
            int s = (num1[i--]-'0') + c;
            ret = to_string(s%10) + ret;
            c = s/10;
        }       
        
        while(j>=0){
            int s = (num2[j--]-'0') + c;
            ret = to_string(s%10) + ret;
            c = s/10;
        }  
        
        if(c) ret = to_string(c) + ret;
        return ret;
    }
};

Friday, June 14, 2019

LeetCode [825] Friends Of Appropriate Ages

Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.

Person A will NOT friend request person B (B != A) if any of the following conditions are true:

age[B] <= 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 && age[A] < 100

Otherwise, A will friend request B.

Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.

How many total friend requests are made?

Example 1:

Input: [16,16]
Output: 2
Explanation: 2 people friend request each other.

Example 2:

Input: [16,17,18]
Output: 2
Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: [20,30,100,110,120]
Output: 
Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Notes:

1 <= ages.length <= 20000.
1 <= ages[i] <= 120.

class Solution { public: int numFriendRequests(vector& ages) { int res = 0; int numInAge[121] = {0}; int sumInAge[121] = {0}; for(int i : ages) numInAge[i] ++; for(int i = 1; i <= 120; ++i) sumInAge[i] = numInAge[i] + sumInAge[i - 1]; for(int i = 15; i <= 120; ++i) { if(numInAge[i] == 0) continue; int count = sumInAge[i] - sumInAge[i / 2 + 7]; res += count * numInAge[i] - numInAge[i]; //people will not friend request themselves, so - numInAge[i] } return res; } };

LeetCode [824] Goat Latin

A sentence S is given, composed of words separated by spaces. Each word consists of lowercase and uppercase letters only.

We would like to convert the sentence to "Goat Latin" (a made-up language similar to Pig Latin.)

The rules of Goat Latin are as follows:

If a word begins with a vowel (a, e, i, o, or u), append "ma" to the end of the word.
For example, the word 'apple' becomes 'applema'.
If a word begins with a consonant (i.e. not a vowel), remove the first letter and append it to the end, then add "ma".
For example, the word "goat" becomes "oatgma".
Add one letter 'a' to the end of each word per its word index in the sentence, starting with 1.
For example, the first word gets "a" added to the end, the second word gets "aa" added to the end and so on.

Return the final sentence representing the conversion from S to Goat Latin.

Example 1:

Input: "I speak Goat Latin"
Output: "Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

Example 2:

Input: "The quick brown fox jumped over the lazy dog"
Output: "heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

Notes:

S contains only uppercase, lowercase and spaces. Exactly one space between each word.
1 <= S.length <= 150.

class Solution {
public:
    string toGoatLatin(string S) {
        set<char> vowels{'a','e','i','o','u','A','E','I','O','U'};
        string r, t;
        stringstream ss(S);
        int i = 0;
        while(ss>>t){
            if(vowels.count(t[0])) t += "ma";
            else{
                t = t.substr(1, t.size()-1) + t[0] + "ma";
            }
            t.append(++i, 'a');
            r += t + " ";
        }
        
        return r.substr(0, r.size()-1);
    }
};

LeetCode [885] Spiral Matrix III

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Note:

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

class Solution {
public:
    vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
        vector<vector<int>> dir{{0,1}, {1,0}, {0,-1}, {-1, 0}};
        vector<vector<int>> ret{{r0, c0}};
        int count = R*C;
        
        //11223344....
        int step = 1;
        int turns = 0;
        while(ret.size()<count){
            for(auto d:dir){
                for(int l = 0; l<step; ++l){
                    r0 += d[0]; c0 += d[1];
                    if(r0>=0 && r0<R && c0>=0 && c0<C)
                        ret.push_back(vector<int>{r0, c0});
                }
                if((++turns)%2==0) step++;
            }
        }
        
        return ret;
    }
};

Thursday, June 13, 2019

LeetCode [622] Design Circular Queue

Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called "Ring Buffer".

One of the benefits of the circular queue is that we can make use of the spaces in front of the queue. In a normal queue, once the queue becomes full, we cannot insert the next element even if there is a space in front of the queue. But using the circular queue, we can use the space to store new values.

Your implementation should support following operations:

MyCircularQueue(k): Constructor, set the size of the queue to be k.
Front: Get the front item from the queue. If the queue is empty, return -1.
Rear: Get the last item from the queue. If the queue is empty, return -1.
enQueue(value): Insert an element into the circular queue. Return true if the operation is successful.
deQueue(): Delete an element from the circular queue. Return true if the operation is successful.
isEmpty(): Checks whether the circular queue is empty or not.
isFull(): Checks whether the circular queue is full or not.

Example:

MyCircularQueue circularQueue = new MyCircularQueue(3); // set the size to be 3
circularQueue.enQueue(1);  // return true
circularQueue.enQueue(2);  // return true
circularQueue.enQueue(3);  // return true
circularQueue.enQueue(4);  // return false, the queue is full
circularQueue.Rear();  // return 3
circularQueue.isFull();  // return true
circularQueue.deQueue();  // return true
circularQueue.enQueue(4);  // return true
circularQueue.Rear();  // return 4

Note:

All values will be in the range of [0, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in Queue library.

class MyCircularQueue {
    vector<int> vec;
    int size;
    int count;
    int start, end;
public:
    /** Initialize your data structure here. Set the size of the queue to be k. */
    MyCircularQueue(int k) {
        size = k;
        vec.resize(k);
        count = 0;
        start = end = 0;
    }
    
    /** Insert an element into the circular queue. Return true if the operation is successful. */
    bool enQueue(int value) {
        if(count==size) return false;
        count++;
        vec[end] = value;
        if(end==size-1) end = 0;
        else end++;
        return true;
    }
    
    /** Delete an element from the circular queue. Return true if the operation is successful. */
    bool deQueue() {
        if(count == 0) return false;
        count--;
        if(start==size-1) start = 0;
        else start++;
        return true;
    }
    
    /** Get the front item from the queue. */
    int Front() {
        if(count == 0) return -1;
        return vec[start];
    }
    
    /** Get the last item from the queue. */
    int Rear() {
        if(count==0) return -1;
        if(end==0) return vec[size-1];
        else return vec[end-1];
    }
    
    /** Checks whether the circular queue is empty or not. */
    bool isEmpty() {
        return count==0;
    }
    
    /** Checks whether the circular queue is full or not. */
    bool isFull() {
        return count==size;
    }
};

/**
 * Your MyCircularQueue object will be instantiated and called as such:
 * MyCircularQueue* obj = new MyCircularQueue(k);
 * bool param_1 = obj->enQueue(value);
 * bool param_2 = obj->deQueue();
 * int param_3 = obj->Front();
 * int param_4 = obj->Rear();
 * bool param_5 = obj->isEmpty();
 * bool param_6 = obj->isFull();
 */

Wednesday, June 12, 2019

LeetCode [446] Arithmetic Slices II - Subsequence

A sequence of numbers 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 sequences:

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 subsequence slice of that array is any sequence of integers (P0, P1, ..., Pk) such that 0 ≤ P0 < P1 < ... < Pk< N.

A subsequence slice (P0, P1, ..., Pk) of array A is called arithmetic if the sequence A[P0], A[P1], ..., A[Pk-1], A[Pk] is arithmetic. In particular, this means that k ≥ 2.

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

The input contains N integers. Every integer is in the range of -231 and 231-1 and 0 ≤ N ≤ 1000. The output is guaranteed to be less than 231-1.

Example:

Input: [2, 4, 6, 8, 10]

Output: 7

Explanation:
All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

class Solution {
public:
int numberOfArithmeticSlices(vector<int>& A) {
    if(A.empty()) return 0;
    vector<unordered_map<int,int>> dp(A.size());//[index, [difference, count]]
    //dp[i][dif] is the count of sequences in which i is the last to second number. 
    
    int res = 0;
    for(int i = 0; i < A.size(); ++i){
        for(int j = 0; j < i; ++j){
            if((long)A[i] - (long)A[j] > INT_MAX || (long)A[i] - (long)A[j] < INT_MIN) continue;// do not ignore this step, it will help you save time & space to pass OJ.
            int dif = A[i] - A[j];
            dp[i][dif] += 1;
            if(dp[j].find(dif) != dp[j].end()){
                dp[i][dif] += dp[j][dif];
                res += dp[j][dif];
            }
        }
    }
    return res;
}
};

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;
    }
};