Wednesday, June 26, 2019

LeetCode [904] Fruit Into Baskets

In a row of trees, the i-th tree produces fruit with type tree[i].
You start at any tree of your choice, then repeatedly perform the following steps:
  1. Add one piece of fruit from this tree to your baskets.  If you cannot, stop.
  2. Move to the next tree to the right of the current tree.  If there is no tree to the right, stop.
Note that you do not have any choice after the initial choice of starting tree: you must perform step 1, then step 2, then back to step 1, then step 2, and so on until you stop.
You have two baskets, and each basket can carry any quantity of fruit, but you want each basket to only carry one type of fruit each.
What is the total amount of fruit you can collect with this procedure?

Example 1:
Input: [1,2,1]
Output: 3
Explanation: We can collect [1,2,1].
Example 2:
Input: [0,1,2,2]
Output: 3
Explanation: We can collect [1,2,2].
If we started at the first tree, we would only collect [0, 1].
Example 3:
Input: [1,2,3,2,2]
Output: 4
Explanation: We can collect [2,3,2,2].
If we started at the first tree, we would only collect [1, 2].
Example 4:
Input: [3,3,3,1,2,1,1,2,3,3,4]
Output: 5
Explanation: We can collect [1,2,1,1,2].
If we started at the first tree or the eighth tree, we would only collect 4 fruits.

Note:
  1. 1 <= tree.length <= 40000
  2. 0 <= tree[i] < tree.length
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
]class Solution {
public:
    int totalFruit(vector<int>& tree) {
        int ret = 0, n = tree.size(), l = 0, r = 0;
        map<int, int> mp;
        while(r<n){
            mp[tree[r]]++;
            while(mp.size()>2){
                int v = tree[l++];
                if(--mp[v]==0) mp.erase(v);
            }
            if(ret<r-l+1) ret = r-l+1;
            r++;
        }
        return ret;
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int totalFruit(int[] tree) {
        int n = tree.length;
        int i = 0, j = 0, types = 0, maxCnt = 0;
        Map<Integer, Integer> map = new HashMap<>();
        while(j<n){
            int type = tree[j++];
            if(map.getOrDefault(type, 0)==0) types++;
            map.put(type, map.getOrDefault(type, 0)+1);
            while(types>2){
                int last = tree[i++];
                map.put(last, map.get(last)-1);
                if(map.get(last)==0) types--;
            }
            maxCnt = Math.max(maxCnt, j-i);
        }
        return maxCnt;
    }
}
Posted by at No comments:

LeetCode [844] Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.
Example 1:
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
Example 2:
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".
Example 3:
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
Example 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
Note:
  1. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. S and T only contain lowercase letters and '#' characters.
Follow up:
  • Can you solve it in O(N) time and O(1) space?
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    void moveToLastValidChar(string S, int &index){
        int cnt = 0;//number of '#'
        while(index>=0){
            if(S[index] == '#'){
                index--;
                cnt++;
            }else if(cnt>0){
                index--;
                cnt--;
            }else{
                break;
            }
        }
    }
public:
    bool backspaceCompare(string S, string T) {
        int ns = S.size(), nt = T.size(), i = ns-1, j = nt-1;
        while(i>=0 || j>=0){
            moveToLastValidChar(S, i);
            moveToLastValidChar(T, j);
            if(i>=0 && j>=0 && S[i]!=T[j]) return false;
            if((i<0 && j>=0)||(j<0 && i>=0)) return false;
            i--; j--;
        }
        return true;
    }
};
Posted by at No comments:

Tuesday, June 25, 2019

LeetCode [524] Longest Word in Dictionary through Deleting

524. Longest Word in Dictionary through Deleting
Medium

Given a string and a string dictionary, find the longest string in the dictionary that can be formed by deleting some characters of the given string. If there are more than one possible results, return the longest word with the smallest lexicographical order. If there is no possible result, return the empty string.

Example 1:

Input:
s = "abpcplea", d = ["ale","apple","monkey","plea"]

Output: 
"apple"

Example 2:

Input:
s = "abpcplea", d = ["a","b","c"]

Output: 
"a"

Note:

  1. All the strings in the input will only contain lower-case letters.
  2. The size of the dictionary won't exceed 1,000.
  3. The length of all the strings in the input won't exceed 1,000.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    struct comp{
        bool operator()(const string &s1, const string &s2){
            if(s1.size()==s2.size()){
                return s1 < s2;
            }else{
                return s1.size()>s2.size();
            }
        }
    };
    comp c;
public:
    string findLongestWord(string s, vector<string>& d) {
        sort(d.begin(), d.end(), c);
        for(auto w:d){
            int i = 0, j = 0;
            while(i<s.size() && j<w.size()){
                if(s[i]!=w[j]) i++;
                else{i++; j++;}
            }
            if(j == w.size()) return w;
        }
        return "";
    }
};


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
//Java
class Solution {
    public String findLongestWord(String s, List<String> d) {
        String ret = "";
        for(String w : d){
            int i=0, j=0;
            while(i<s.length() && j<w.length()){
                if(s.charAt(i)==w.charAt(j)) j++;
                i++;
            }
            if(j==w.length() && w.length()>=ret.length()){
                if(w.length()>ret.length() || w.compareTo(ret)<0) ret = w;
            }
        }
        return ret;
    }
}
Posted by at No comments:

LeetCode [457] Circular Array Loop

You are given a circular array nums of positive and negative integers. If a number kat an index is positive, then move forward k steps. Conversely, if it's negative (-k), move backward k steps. Since the array is circular, you may assume that the last element's next element is the first element, and the first element's previous element is the last element.
Determine if there is a loop (or a cycle) in nums. A cycle must start and end at the same index and the cycle's length > 1. Furthermore, movements in a cycle must all follow a single direction. In other words, a cycle must not consist of both forward and backward movements.

Example 1:
Input: [2,-1,1,2,2]
Output: true
Explanation: There is a cycle, from index 0 -> 2 -> 3 -> 0. The cycle's length is 3.
Example 2:
Input: [-1,2]
Output: false
Explanation: The movement from index 1 -> 1 -> 1 ... is not a cycle, because the cycle's length is 1. By definition the cycle's length must be greater than 1.
Example 3:
Input: [-2,1,-1,-2,-2]
Output: false
Explanation: The movement from index 1 -> 2 -> 1 -> ... is not a cycle, because movement from index 1 -> 2 is a forward movement, but movement from index 2 -> 1 is a backward movement. All movements in a cycle must follow a single direction.

Note:
  1. -1000 ≤ nums[i] ≤ 1000
  2. nums[i] ≠ 0
  3. 1 ≤ nums.length ≤ 5000

Follow up:
Could you solve it in O(n) time complexity and O(1) extra space complexity?
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    int mod(int x, int y){
        if(x%y>=0) return x%y;
        else return x%y+y;
    }
public:
    bool circularArrayLoop(vector<int>& nums) {
        int n = nums.size();
        if(n==0) return false; 

        for(int i=0; i<n; ++i)
        {
            int p1 = i, p2 = i;
            int length = 0;//cycle length;
            while(true){
                length++;
                p1 = mod(p1+nums[p1], n);
                int step1 = nums[p2];
                int step2 = nums[mod(p2+step1, n)];
                p2 = mod(p2+step1+step2, n);
                if(nums[p1]*nums[i]<=0 || nums[p2]*nums[i]<=0 ) break;//wrong direction
                if(p1==p2) break; //because nums has limited length and is circular, there must be a cycle. 
            }
            if(p1==i && length>1) return true; // found a cycle with length greater than 1 starting from i
        }

        return false;
    }
};
Posted by at No comments:

Sunday, June 16, 2019

LeetCode_Summary [Two Pointers]

LeetCode [283] Move Zeroes






  1. maintain "start_index" and "end_index"
  2. the two indices go towards each other

  1. maintain two indices on two vectors
  2. both indices go backwards from the end

  1. fast and slow indices
  2. both go towards the same direction

LeetCode [141] Linked List Cycle


Posted by at No comments:

Saturday, June 15, 2019

LeetCode [977] Squares of a Sorted Array

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:
Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]
Example 2:
Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:
  1. 1 <= A.length <= 10000
  2. -10000 <= A[i] <= 10000
  3. A is sorted in non-decreasing order.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> sortedSquares(vector<int>& A) {
        int n = A.size();
        vector<int> ret(n);
        int l = 0, r = n-1, i = n-1;
        while(l<=r){
            if(abs(A[l])>=abs(A[r])){
                ret[i] = A[l]*A[l];
                l++;
            }else{
                ret[i] = A[r]*A[r];
                r--;
            }
            i--;
        }
        return ret;
    }
};
Posted by at No comments:

LeetCode [935] Knight Dialer

A chess knight can move as indicated in the chess diagram below:
 .           

This time, we place our chess knight on any numbered key of a phone pad (indicated above), and the knight makes N-1 hops.  Each hop must be from one key to another numbered key.
Each time it lands on a key (including the initial placement of the knight), it presses the number of that key, pressing N digits total.
How many distinct numbers can you dial in this manner?
Since the answer may be large, output the answer modulo 10^9 + 7.

    Example 1:
    Input: 1
Output: 10
    Example 2:
    Input: 2
Output: 20
    Example 3:
    Input: 3
Output: 46

    Note:
    • 1 <= N <= 5000
     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
    /*
68   79   48
039      017
26   13   24
     46
*/

typedef long long ll;
class Solution {
    const int X = 1000000007;
public:
    int knightDialer(int N) {
        if (N==1) return 10;
        vector<vector<ll>> dp(N+1, vector<ll>(10, 1));//dp[i][j] is the i-length #number ends at j
        for(int i = 2; i<=N; ++i){
                dp[i][0] = (dp[i-1][4] + dp[i-1][6])%X;
                dp[i][1] = (dp[i-1][6] + dp[i-1][8])%X;
                dp[i][2] = (dp[i-1][7] + dp[i-1][9])%X;
                dp[i][3] = (dp[i-1][4] + dp[i-1][8])%X;
                dp[i][4] = (dp[i-1][3] + dp[i-1][9] + dp[i-1][0])%X;
                dp[i][6] = (dp[i-1][1] + dp[i-1][7] + dp[i-1][0])%X;
                dp[i][7] = (dp[i-1][2] + dp[i-1][6])%X;
                dp[i][8] = (dp[i-1][1] + dp[i-1][3])%X;
                dp[i][9] = (dp[i-1][2] + dp[i-1][4])%X;
        }

        int ret = 0;
        for(int j=0; j<=9; ++j){
            if (j!=5) ret = (ret + dp[N][j])%X;
        }
        return ret%X;
    }
};
    Posted by at No comments:

    LeetCode [463] Island Perimeter

    You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water.
    Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells).
    The island doesn't have "lakes" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island.

    Example:
    Input:
[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Output: 16

Explanation: The perimeter is the 16 yellow stripes in the image below:



     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
    class Solution {
public:
    int islandPerimeter(vector<vector<int>>& grid) {
        int islands = 0, neighbors = 0;
        int m = grid.size(), n = grid[0].size();
        for(int i=0; i<m; ++i)
        {
            for(int j=0; j<n; ++j)
            {
                if(grid[i][j]) {
                    islands++;
                    if(i+1<m && grid[i+1][j]) neighbors++;
                    if(j+1<n && grid[i][j+1]) neighbors++;
                }
            }
        }
        
        return islands*4 - neighbors*2;
    }
};


     1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    class Solution {
    public int islandPerimeter(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        int ret = 0;
        for(int i=0; i<rows; ++i)
        {
            for(int j=0; j<cols; ++j)
            {
                if(grid[i][j] == 1)
                {
                    ret += 4;
                    if(i-1>=0 && grid[i-1][j]==1) ret--;
                    if(i+1<rows && grid[i+1][j]==1) ret--;
                    if(j-1>=0 && grid[i][j-1]==1) ret--;
                    if(j+1<cols && grid[i][j+1]==1) ret--;
                }
            }
        }
        return ret;
    }
}
    Posted by at No comments:
    Subscribe to: Posts (Atom)