Monday, July 25, 2016

LeetCode [350] Intersection of Two Arrays II

350. Intersection of Two Arrays II
Easy

Given two arrays, write a function to compute their intersection.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?
  • What if nums1's size is small compared to nums2's size? Which algorithm is better?
  • What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> mp;//number, count
        for(auto n:nums1) mp[n]++;
        vector<int> ret;
        for(auto n:nums2){
            if(mp.count(n) && mp[n]>0){
                mp[n]--;
                ret.push_back(n);
            }
        }
        return ret;
    }
};
at No comments:

LeetCode [349] Intersection of Two Arrays

  Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Note:
  • Each element in the result must be unique.
  • The result can be in any order.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> st(nums1.begin(), nums1.end());
        set<int> st1;
        for(auto n:nums2){
            if(st.count(n)) st1.insert(n);
        }
        vector<int> ret(st1.begin(), st1.end());
        return ret;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> ret;
        int i=0, j = 0, n1 = nums1.size(), n2 = nums2.size();
        while(i<n1 && j<n2){
            if(nums1[i]<nums2[j]) i++;
            else if(nums1[i]>nums2[j]) j++;
            else{
                if(ret.empty() || ret.back()!=nums1[i]){
                    ret.push_back(nums1[i]);
                }
                i++;
                j++;
            }
        }
        return ret;
    }
};
at No comments:

LeetCode [348] Design Tic-Tac-Toe

Design a Tic-tac-toe game that is played between two players on a n x n grid.
You may assume the following rules:
  1. A move is guaranteed to be valid and is placed on an empty block.
  2. Once a winning condition is reached, no more moves is allowed.
  3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Example:
Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|
Follow up:
Could you do better than O(n2) per move() operation?
 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
34
35
36
37
38
39
class TicTacToe {
public:
  vector<int> cols, rows;
  int diagonal, antiDiagonal;

  /** Initialize your data structure here. */
  TicTacToe(int n) : diagonal(0), antiDiagonal(0) {
    cols = vector<int>(n);
    rows = vector<int>(n);
  } 
    
  /** Player {player} makes a move at ({row}, {col}).
      @param row The row of the board.
      @param col The column of the board.
      @param player The player, can be either 1 or 2.
      @return The current winning condition, can be either:
              0: No one wins.
              1: Player 1 wins.
              2: Player 2 wins. */
  int move(int row, int col, int player) {
    int toAdd = player == 1 ? 1 : -1;
    rows[row] += toAdd;
    cols[col] += toAdd;
    if (row == col) {
      diagonal += toAdd;
    }
    int len = rows.size();
    if (row == len-col-1) {
      antiDiagonal += toAdd;
    }
    if (abs(rows[row]) == len ||
        abs(cols[col]) == len ||
        abs(diagonal) == len ||
        abs(antiDiagonal) == len) {
      return player;
    }
    return 0;
  }
};
at No comments:

LeetCode [347] Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Note:
  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
//quick sort: average complexity from O(n log n) to O(n), with a worst case of O(n2)
class Solution {
    Map<Integer, Integer> map = new HashMap<>();
    int[][] pairs;
    
    void printPairs(){
        for(int[] p : pairs){
            System.out.print(p[0]+ ":" + p[1] + "  ");
        }
        System.out.println();
    }
    
    void swapPairs(int i, int j){
        int[] t = pairs[i];
        pairs[i] = pairs[j];
        pairs[j] = t;
    }
    
    public int[] topKFrequent(int[] nums, int k) {
        for(int i : nums){
            map.put(i, map.getOrDefault(i, 0)+1);
        }
        pairs = new int[map.size()][2];
        int i = 0;
        for(Map.Entry<Integer, Integer> e : map.entrySet()){
            pairs[i++] = new int[]{e.getKey(), e.getValue()};
        }
        selectPairs(0, map.size()-1, k);
        
        int[] ret = new int[k];
        for(int j=0; j<k; ++j){
            ret[j] = pairs[j][0];
        }
        return ret;
    }
    
    int partitionPairs(int l, int r){
 //       System.out.println("Before Sort");
 //       printPairs();
        int[] pivot = pairs[r];
        int i = l;
        for(int j=l; j<r; ++j){
            if(pairs[j][1]>=pivot[1]){
                swapPairs(i, j);
                i++;
            }
        }
        swapPairs(i, r);
        
 //       System.out.println("sort from " + l + "->" + i);
   //     printPairs();
        return i;
    }
    
    void selectPairs(int l, int r, int k){
        if(l>=r) return;
        int p = partitionPairs(l, r);
        if(p<k){
            selectPairs(p+1, r, k);
        }else{
            selectPairs(l, p-1, k);
        }
    }
}


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
//minHeap: nlog(k)
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int i : nums) map.put(i, map.getOrDefault(i, 0) + 1);
        
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>((a,b) -> Integer.compare(a.getValue(), b.getValue()));
        
        for(Map.Entry<Integer, Integer> e : map.entrySet()){
            minHeap.add(e);
            if(minHeap.size()>k) minHeap.poll();
        }
        
        int[] ret = new int[k];
        for(int i=0; i<k; ++i){
            ret[i] = minHeap.poll().getKey();
        }
        
        return ret;
    }
}


    class Solution {
        public int[] topKFrequent(int[] nums, int k) {
            Map<Integer, Integer> freq = new HashMap<>();//value, freq
            int n = nums.length;
            List<Integer>[] buckets = new List[n+1];
            for(int i:nums){
                freq.put(i, freq.getOrDefault(i, 0)+1);
            }
            for(Map.Entry<Integer, Integer> e : freq.entrySet()){
                if(buckets[e.getValue()] == null){
                    buckets[e.getValue()] = new ArrayList<>();
                }
                buckets[e.getValue()].add(e.getKey());
            }

            List<Integer> ret = new ArrayList<>();
            for(int i=n; i>0; --i){
                if(buckets[i]!=null) ret.addAll(buckets[i]);
                if(ret.size()>=k) break;
            }

            return ret.subList(0, k).stream().mapToInt(i->i).toArray();
        }
    }
at No comments:

LeetCode [346] Moving Average from Data Stream

 346. Moving Average from Data Stream

Easy

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3
 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 MovingAverage {
    Deque<Integer> que = new ArrayDeque<>();
    int w, s;

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        w = size;
        s = 0;
    }
    
    public double next(int val) {
        if(que.size()==w){
            s -= que.pollFirst();
        }
        que.addLast(val);
        s += val;
        return (double)s/que.size();
    }
}

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage obj = new MovingAverage(size);
 * double param_1 = obj.next(val);
 */
at No comments:

LeetCode [345] Reverse Vowels of a String

 345. Reverse Vowels of a String

Easy

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:

Input: "hello"
Output: "holle"

Example 2:

Input: "leetcode"
Output: "leotcede"

Note:
The vowels does not include the letter "y".


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    boolean isVowel(char c){
        return c=='a'||c=='e'||c=='i'||c=='o'||c=='u'||c=='A'||c=='E'||c=='I'||c=='O'||c=='U';
    }
    public String reverseVowels(String s) {
        StringBuilder sb = new StringBuilder(s);
        int l = 0, r = s.length()-1;
        while(l<r){
            if(!isVowel(sb.charAt(l))) l++;
            else if(!isVowel(sb.charAt(r))) r--;
            else{
                char t = sb.charAt(l);
                sb.setCharAt(l, sb.charAt(r));
                sb.setCharAt(r, t);
                l++;
                r--;
            }
        }
        return sb.toString();
    }
}
at No comments:

LeetCode [344] Reverse String

Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.

Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Example 2:
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void reverseString(vector<char>& s) {
        int i = 0, j = s.size()-1;
        while (i < j) {
            swap(s[i++], s[j--]);
        }
    }
};
at No comments:

LeetCode [343] Integer Break

 343. Integer Break

Medium

Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.

Example 1:

Input: 2
Output: 1
Explanation: 2 = 1 + 1, 1 × 1 = 1.

Example 2:

Input: 10
Output: 36
Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36.

Note: You may assume that n is not less than 2 and not larger than 58.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
public:
  int integerBreak(int n) {
    vector<int> dp(n+1);
    dp[0] = 1;
    for (int i = 2; i <= n; i++) {
      for (int j = 1; j < i; j++) {
        dp[i] = max(dp[i], max(j, dp[j]) * max(i-j, dp[i-j]));
      }
    }
    return dp[n];
  }
};
at No comments:

LeetCode [342] Power of Four

at No comments:

LeetCode [341] Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.
Each element is either an integer, or a list -- whose elements may also be integers or other lists.
Example 1:
Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,1,2,1,1].
Example 2:
Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false, 
             the order of elements returned by next should be: [1,4,6].
 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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */
class NestedIterator {
    stack<vector<NestedInteger>::iterator> its, ends;
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        its.push(nestedList.begin());
        ends.push(nestedList.end());
    }

    int next() {
        auto it = its.top();
        int v = it->getInteger();
        its.top()++;
        return v;
    }

    bool hasNext() {
        while(!its.empty())
        {
            if(its.top() == ends.top())
            {
                its.pop();
                ends.pop();
            }
            else
            {
                auto it = its.top();
                if(it->isInteger()) return true;
                its.top()++;//current "it" is a list, and the list to stack and move to the next
                its.push(it->getList().begin());
                ends.push(it->getList().end());
            }
        }
        return false;
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */
at No comments: