LIKE CODING: September 2019

Tuesday, September 17, 2019

LeetCode [397] Integer Replacement

397. Integer Replacement

Medium

Given a positive integer n and you can do operations as follow:

If n is even, replace n with n/2.
If n is odd, you can replace n with either n + 1 or n - 1.

What is the minimum number of replacements needed for n to become 1?

Example 1:

Input:
8

Output:
3

Explanation:
8 -> 4 -> 2 -> 1

Example 2:

Input:
7

Output:
4

Explanation:
7 -> 8 -> 4 -> 2 -> 1
or
7 -> 6 -> 3 -> 2 -> 1

typedef long long ll;
class Solution {
    int countBit(ll n){
        int cnt = 0;
        while(n){
            cnt += (0x1 & n);
            n = n>>1;
        }
        return cnt;
    }
public:
    int integerReplacement(int n) {
        int step = 0;
        ll m = n;
        while(m!=1){
            if(m%2==0){
                m = m>>1;
            }else if (m==3){
                m--;
            }else if (countBit(m-1)<countBit(m+1)){
                m--;
            }else{
                m++;
            }
            step++;
        }
        return step;
    }
};

class Solution {
public:
    int integerReplacement(int n) {
        vector<int> dp(n+1, INT_MAX);
        dp[1] = 0;
        for(int i=2; i<=n; ++i){
            if(i%2==0){
                dp[i] = min(dp[i], dp[i/2]+1);
            }else{
                dp[i] = min(dp[i], min(1+dp[i-1], 2+dp[i/2+1]));//(i+1)/2==i/2+1, avoid overflow
            }
        }
        return dp[n];
    }
};

typedef long long ll;
class Solution {
public:
    int integerReplacement(int n) {
        return dfs(n);
    }
    
    int dfs(ll m){
        if(m==1) return 0;
        if(m%2==0) return 1+dfs(m/2);
        return min(dfs(m+1), dfs(m-1))+1;        
    }
};

https://leetcode.com/problems/integer-replacement/discuss/87920/A-couple-of-Java-solutions-with-explanations

Saturday, September 14, 2019

All Palindrome Subsequence

#include "misc.h"

class Solution{
public:
    vector<string> getPalindromes(string s){
        int n = s.size();
        vector<vector<set<string>>> dp(n, vector<set<string>>(n));
        for(int i=0; i<n; ++i){
            dp[i][i].insert(s.substr(i, 1));
            if(i+1<n && s[i]==s[i+1]){
                dp[i][i+1].insert(s.substr(i, 2));
            }
        }

        for(int i=n-1; i>=0; --i){
            for(int j=i+2; j<n; ++j){
                if(s[i]==s[j]){
                    dp[i][j].insert(s.substr(i,1)+s.substr(j,1));
                    for(int i0=i+1; i0<=j-1; ++i0){
                        for(int j0=i0; j0<=j-1; ++j0){
                            for(auto p:dp[i0][j0]){
                                p = s[i] + p + s[j];
                                cout<<p<<endl;
                                dp[i][j].insert(p);
                            }
                        }
                    }
                }
            }
        }

        set<string> st;
        for(int i=0; i<n; ++i){
            for(int j=i; j<n; ++j){
                st.insert(dp[i][j].begin(), dp[i][j].end());
            }
        }

        return vector<string>{st.begin(), st.end()};
    }
};

int main(){
    Solution sol;
    vector<string> ret = sol.getPalindromes("abacedecba");
    for(auto x:ret) cout<<x<<" ";
    cout<<endl;
    return 0;
}

Thursday, September 12, 2019

Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to k pieces of the same length len are cut. What is the longest len you can get?

比如五根木头长度分别为1,2,3,4,5，
要切出5段，最大长度是2
要切7段，最大长度是1
要切16段，切不了

#include "misc.h"

class Solution{
public:
    int getMaxLen(vector<int> woods, int k){
        int l = *min_element(woods.begin(), woods.end());
        int r = *max_element(woods.begin(), woods.end());
        int maxLen = 0;
        while(l<=r){
            int m = (l+r)/2;
            int cnt = 0;
            for(auto w:woods){
                cnt += w/m;
            }
            if(cnt>=k){
                maxLen = max(maxLen, m);
                l = m+1;
            }else{
                r = m-1;
            }
        }
        return maxLen;
    }
};

int main(){
    Solution sol;
    vector<int> woods{1,2,3,4,5};
    cout<<sol.getMaxLen(woods, 16)<<endl;
    return 0;
}

https://likemyblogger.blogspot.com/2019/09/leetcode-875-koko-eating-bananas.html

LeetCode [875] Koko Eating Bananas

875. Koko Eating Bananas

Medium

Koko loves to eat bananas. There are N piles of bananas, the i-th pile has piles[i] bananas. The guards have gone and will come back in H hours.

Koko can decide her bananas-per-hour eating speed of K. Each hour, she chooses some pile of bananas, and eats K bananas from that pile. If the pile has less than K bananas, she eats all of them instead, and won't eat any more bananas during this hour.

Koko likes to eat slowly, but still wants to finish eating all the bananas before the guards come back.

Return the minimum integer K such that she can eat all the bananas within H hours.

Example 1:

Input: piles = [3,6,7,11], H = 8
Output: 4

Example 2:

Input: piles = [30,11,23,4,20], H = 5
Output: 30

Example 3:

Input: piles = [30,11,23,4,20], H = 6
Output: 23

Note:

1 <= piles.length <= 10^4
piles.length <= H <= 10^9
1 <= piles[i] <= 10^9

class Solution {
    public int minEatingSpeed(int[] piles, int H) {
        int l = 1, r = (int)1e9;
        while(l<r){
            int mid = l + (r-l)/2;
            if(valid(piles, H, mid)){
                r = mid;
            }else{
                l = mid+1;
            }
        }
        return l;
    }
    
    boolean valid(int[] piles, int H, int target)
    {
        int count = 0;
        for(int p : piles){
            count += (int)Math.ceil(p/(double)target);
            if(count>H) return false;
        }
        return true;
    }
}

LeetCode [498] Diagonal Traverse

498. Diagonal Traverse

Medium

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

Output:  [1,2,4,7,5,3,6,8,9]

Explanation:

Note:

The total number of elements of the given matrix will not exceed 10,000.

class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        int m = matrix.size();
        if(m==0) return ret;
        int n = matrix[0].size();
        if(n==0) return ret;
        
        for(int s=0; s<=m+n-2; ++s){
            vector<int> line;
            for(int j = max(0, s - (m-1)); j < n; ++j){
                int i = s-j;    
                if(i<0) break;
                line.push_back(matrix[i][j]);
            }
            if(s%2==1) reverse(line.begin(), line.end());
            ret.insert(ret.end(), line.begin(), line.end());
        }
        return ret;
    }
};

class Solution {
    public int[] findDiagonalOrder(int[][] matrix) {
        int m = matrix.length;
        if(m==0) return new int[0];
        int n = matrix[0].length;
        if(n==0) return new int[0];
        int[] ret = new int[m*n];
        
        int r = 0, c = 0;
        for(int i=0; i<m*n; ++i){
            ret[i] = matrix[r][c];
            if((r+c)%2 == 0){//moving up
                if(c==n-1) r++;
                else if(r == 0) c++;
                else {r--; c++;}
            }else{//moving down
                if(r==m-1) c++;
                else if(c==0) r++;
                else {r++; c--;}
            }
        }
        
        return ret;
    }
}

Wednesday, September 11, 2019

LeetCode [731] My Calendar II

731. My Calendar II

Medium

Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A triple booking happens when threeevents have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triplebooking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar();MyCalendar.book(start, end)

Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
Explanation: 
The first two events can be booked.  The third event can be double booked.
The fourth event (5, 15) can't be booked, because it would result in a triple booking.
The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.
The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;
the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.
In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

class MyCalendarTwo {
    map<int, int> overlaps;//end, start
    vector<pair<int, int>> events;
public:
    MyCalendarTwo() {
    }
    
    bool updateOverlaps(int start, int end, bool bookit = false) {
        auto nxt = overlaps.upper_bound(start);
        if(nxt!=overlaps.end() && nxt->second<end) return false;
        if(bookit) overlaps[end] = start;
        return true;
    }
    
    bool book(int start, int end) {
        if(!updateOverlaps(start, end)) return false;
        for(auto& p:events){
            int l = max(start, p.first);
            int r = min(end, p.second);
            if(l<r) updateOverlaps(l, r, true);
        }
        events.emplace_back(start, end);
        return true;
    }
};

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo* obj = new MyCalendarTwo();
 * bool param_1 = obj->book(start,end);
 */

class MyCalendarTwo {
    List<int[]> meetings;

    public MyCalendarTwo() {
        meetings = new ArrayList<>();
    }
    
    public boolean book(int start, int end) {
        MyCalendar overlaps = new MyCalendar();
        for(int[] m : meetings){
            int a = Math.max(m[0], start);
            int b = Math.min(m[1], end);
            if(a<b){
                if(!overlaps.book(a, b)) return false;
            }
        }
        meetings.add(new int[] {start, end});
        return true;
    }

    private class MyCalendar {
        List<int[]> meetings = new ArrayList<>();
        boolean book(int s, int e)
        {
            for(int[] m : meetings){
                int a = Math.max(m[0], s);
                int b = Math.min(m[1], e);
                if(a<b) return false;
            }
            meetings.add(new int[] {s, e});
            return true;
        }
    }
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 = obj.book(start,end);
 */

LeetCode [729] My Calendar I

729. My Calendar I

Medium

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar();MyCalendar.book(start, end)

Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: 
The first event can be booked.  The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.
In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

class MyCalendar {
    map<int, int> mp;//end, start
public:
    MyCalendar() {
        
    }
    
    bool book(int start, int end) {
        auto nxt = mp.upper_bound(start);
        if(nxt!=mp.end() && nxt->second<end) return false;
        mp[end] = start;
        return true;
    }
};

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar* obj = new MyCalendar();
 * bool param_1 = obj->book(start,end);
 */

class MyCalendar {
    List<int[]> list;

    public  MyCalendar() {
        list = new ArrayList<>();
    }
    
    public boolean book(int start, int end) {
        for(int[] b : list){
            if (Math.max(b[0], start)<Math.min(b[1], end)){
                return false;
            }
        }

        list.add(new int[] {start, end});
        return true;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

class MyCalendar {
    TreeMap<Integer, Integer> meetings = new TreeMap<>();
    public MyCalendar() {
        
    }
    
    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> last = meetings.floorEntry(end-1);
        if(last!=null && last.getValue()>start) return false;
        meetings.put(start, end);
        return true;
    }
}

SpiralArray

n=3
1 2 3
8 9 4
7 6 5

n=4
1 2 3 4
12 13 14 5
11 16 15 6
10 9 8 7

#include "misc.h"

class SpiralArray{
public:
    vector<vector<int>> getMatrix(int n){
        if(n==0) return vector<vector<int>>();
        vector<vector<int>> ret(n, vector<int>(n, 0));
        int L = n/2;
        int t = 0;

        for(int l=0; l<L; ++l){
            //top
            int i = l;
            for(int j=l; j<n-1-l; ++j) ret[i][j] = ++t;

            //right
            int j = n-1-l;
            for(int i=l; i<n-1-l; ++i) ret[i][j] = ++t;

            //bottom
            i = n-1-l;
            for(int j=n-1-l; j>l; --j) ret[i][j] = ++t;

            //left
            j = l;
            for(int i=n-1-l; i>l; --i) ret[i][j] = ++t;
        }
        if(n%2==1) ret[n/2][n/2] = ++t;
        return ret;
    }
};

int main(){
    SpiralArray sa;
    vector<vector<int>> ret = sa.getMatrix(4);

    for(auto r:ret){
        for(auto c:r) cout<<c<<" ";
        cout<<endl;
    }
    return 0;
}