MJ [46] Find Maximal Selection in 3n Numbers

Question:
Given 3n numbers placed in a circle, you and two of your friends are playing a game. Each time you pick a number first, then the two neighboring numbers of the one you picked are picked by your friends. All the picked numbers are removed from the circle and the left numbers compose a new circle. This game terminates when all the numbers are removed.
Write a program to find the maximum sum of the numbers you picked.

Eg, if nums = {1,2,3}, it returns 3
       if nums = {1,2,3,4,5,6}, the first run you choose 6 and your friends choose 5 and 1. then nums = {2,3,4}. The 2nd run you choose 4. Thus, it returns 4+6=10;

Problem: How to write a DP solution?

Ref
[1] http://www.mitbbs.com/article_t1/JobHunting/32961687_0_1.html

MJ [45] Minimum Difference String

Question:
Given two strings s1 and s2. Switch two elements of s2 to maximally decrease the difference of s1 and s2.

Eg., s1 = "abc",
       s2 = "cba".
The difference of s1 and s2 are 2 because s1[0]!=s2[0] and s1[2]!=s2[2]. By switching s2[0] and s2[2], s2 becomes "abc". Then the difference between s1 and s2 is 0. Thus return [0, 2].

If s1 = "abc" and s2 = "cbe", it should also return [0, 2] because after switch s2[0] and s2[2] s2 becomes "ebc" and the difference between s1 and s2 is decreased by 1.

Ref
[1] http://www.mitbbs.com/article_t1/JobHunting/32961687_0_1.html

LeetCode [296] Best Meeting Point

 296. Best Meeting Point

Hard

A group of two or more people wants to meet and minimize the total travel distance. You are given a 2D grid of values 0 or 1, where each 1 marks the home of someone in the group. The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example:

Input: 

1 - 0 - 0 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

Output: 6 

Explanation: Given three people living at (0,0), (0,4), and (2,2):
             The point (0,2) is an ideal meeting point, as the total travel distance 
             of 2+2+2=6 is minimal. So return 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

class Solution { public boolean canTransform(String start, String end) { if (!start.replace("X", "").equals(end.replace("X", ""))) return false; int p1 = 0; int p2 = 0; while(p1 < start.length() && p2 < end.length()){ // get the non-X positions of 2 strings while(p1 < start.length() && start.charAt(p1) == 'X'){ p1++; } while(p2 < end.length() && end.charAt(p2) == 'X'){ p2++; } //if both of the pointers reach the end the strings are transformable if(p1 == start.length() && p2 == end.length()){ return true; } // if only one of the pointer reach the end they are not transformable if(p1 == start.length() || p2 == end.length()){ return false; } if(start.charAt(p1) != end.charAt(p2)){ return false; } // if the character is 'L', it can only be moved to the left. p1 should be greater or equal to p2. if(start.charAt(p1) == 'L' && p2 > p1){ return false; } // if the character is 'R', it can only be moved to the right. p2 should be greater or equal to p1. if(start.charAt(p1) == 'R' && p1 > p2){ return false; } p1++; p2++; } return true; } }

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 { public int minTotalDistance(int[][] grid) { List<Integer> iList = new ArrayList<>(); List<Integer> jList = new ArrayList<>(); for(int i=0; i<grid.length; ++i){ for(int j=0; j<grid[0].length; ++j){ if(grid[i][j]==1){ iList.add(i); jList.add(j); } } } return getMin(iList) + getMin(jList); } int getMin(List<Integer> list){ Collections.sort(list); int n = list.size(), i = 0, j = n-1, r = 0; while(i<j){ r += (list.get(j--))-list.get(i++); } return r; } }

MJ [44] Find the Longest Substring

Question:
Give a dictionary "dict" and a string "S", find the longest valid word in dict which is a substring of "S".
Eg. dict = {"abc", "defgh", "ef"}
       S = "adbecfgh".
It should return "defgh".

Ref
[1] http://www.mitbbs.com/article_t/JobHunting/32960525.html

MJ [42] Find area code

Question:
+1 North America
...
+1950 Northern Cal
….1point3acres缃�
+44 UK. 1point 3acres 璁哄潧
+4420 London-google 1point3acres
+447 UK Mobile
+44750 Vodafoned. From 1point 3acres bbs
…

and we have a phone number, for instance
+447507439854795-google 1point3acres
+44989045454
. from: 1point3acres.com/bbs 
return where the number is from

Ref
[1] http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=101580&ctid=92

LeetCode [295] Find Median from Data Stream

295. Find Median from Data Stream

Hard

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example,

[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Design a data structure that supports the following two operations:

• void addNum(int num) - Add a integer number from the data stream to the data structure.
• double findMedian() - Return the median of all elements so far.

 

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

 

Follow up:

1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?
2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?

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

class MedianFinder { priority_queue<int> q1; priority_queue<int, vector<int>, greater<int>> q2; public: // Adds a number into the data structure. void addNum(int num) { if(q1.size()>q2.size()){ if(num>=q1.top()) q2.push(num); else{ q2.push(q1.top()); q1.pop(); q1.push(num); } }else{ if(!q2.empty()&&num>=q2.top()){ q1.push(q2.top()); q2.pop(); q2.push(num); }else q1.push(num); } } // Returns the median of current data stream double findMedian() { if(q1.size()>q2.size()){ return q1.top(); }else{ return (q1.top()+q2.top())/2.0; } } };

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

class MedianFinder { PriorityQueue<Integer> pq1 = new PriorityQueue<>((a,b)-> b-a); PriorityQueue<Integer> pq2 = new PriorityQueue<Integer>(); /** initialize your data structure here. */ public MedianFinder() { } public void addNum(int num) { if(!pq2.isEmpty() && num>=pq2.peek()){ pq2.add(num); }else{ pq1.add(num); } if(pq1.size()-1>pq2.size()) pq2.add(pq1.poll()); if(pq2.size()-1>pq1.size()) pq1.add(pq2.poll()); } public double findMedian() { if(pq1.size()==pq2.size()){ return (double)(pq1.peek()+pq2.peek())/2.0; }else if(pq1.size()>pq2.size()) return pq1.peek(); else return pq2.peek(); } } /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder obj = new MedianFinder(); * obj.addNum(num); * double param_2 = obj.findMedian(); */

LeetCode [294] Flip Game II

You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move and therefore the other person will be the winner.

Write a function to determine if the starting player can guarantee a win.

Example:

Input: s = "++++"
Output: true 
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

Follow up:
Derive your algorithm's runtime complexity.

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

class Solution { public: bool canWin(string s) { int n = s.size(); for(int i=0; i<n-1; ++i){ if(s.substr(i,2)=="++"){ string tmp = s; tmp[i] = '-'; tmp[i+1] = '-'; if (!canWin(tmp)) return true; } } return false; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14

//Java class Solution { public boolean canWin(String s) { int n = s.length(); for(int i=0; i<n-1; ++i){ StringBuilder sb = new StringBuilder(s); if(sb.substring(i, i+2).equals("++")){ sb.replace(i, i+2, "--"); if(!canWin(sb.toString())) return true; } } return false; } }