LeetCode [334] Increasing Triplet Subsequence

 334. Increasing Triplet Subsequence

Medium

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1]
Output: false

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

bool increasingTriplet(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); for(int i=1; i<n; ++i){ for(int j=0; j<i; ++j){ if(nums[i]>nums[j]){ dp[i] = max(dp[i], dp[j]+1); if(dp[i]>=3) return true; } } } return false; }

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

bool increasingTriplet1(vector<int>& nums) { vector<int> dp; for(auto n:nums){ if(dp.empty()||n>dp.back()){ dp.push_back(n); if(dp.size()>=3) return true; }else{ int l = 0, r = dp.size()-1; while(l<=r){ int m = (l+r)/2; if((m==0||n>dp[m-1])&&n<=dp[m]){ dp[m]=n; break; }else if(n>dp[m]){ l = m+1; }else{ r = m-1; } } } } return false; }

1 2 3 4 5 6 7 8 9

bool increasingTriplet2(vector<int>& nums) { int c1 = INT_MAX, c2 = INT_MAX; for(auto n:nums){ if(n<=c1) c1 = n; else if(n<=c2) c2 = n; else return true; } return false; }

MJ [54] Binary Index Tree

Ref
[1] http://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
[2] https://github.com/kellyualberta/Algorithms-Data-Structures/blob/master/GeeksforGeeks/binary_index_tree.cpp

LeetCode [333] Largest BST Subtree

Ref

[1] https://leetcode.com/problems/largest-bst-subtree/

LeetCode [332] Reconstruct Itinerary

332. Reconstruct Itinerary

Medium

Given a list of airline tickets represented by pairs of departure and arrival airports [from, to], reconstruct the itinerary in order. All of the tickets belong to a man who departs from JFK. Thus, the itinerary must begin with JFK.

Note:

1. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].
2. All airports are represented by three capital letters (IATA code).
3. You may assume all tickets form at least one valid itinerary.

Example 1:

Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
Output: ["JFK", "MUC", "LHR", "SFO", "SJC"]

Example 2:

Input: [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
Output: ["JFK","ATL","JFK","SFO","ATL","SFO"]
Explanation: Another possible reconstruction is ["JFK","SFO","ATL","JFK","ATL","SFO"].
             But it is larger in lexical order.

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

class Solution { Map<String, PriorityQueue<String>> targets = new HashMap<>(); List<String> route = new LinkedList(); public List<String> findItinerary(List<List<String>> tickets) { for (List<String> ticket : tickets) targets.computeIfAbsent(ticket.get(0), k -> new PriorityQueue()).add(ticket.get(1)); visit("JFK"); return route; } void visit(String airport) { while(targets.containsKey(airport) && !targets.get(airport).isEmpty()) visit(targets.get(airport).poll()); route.add(0, airport); } }

LeetCode [331] Verify Preorder Serialization of a Binary Tree

Ref
[1] https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree/
[2] https://leetcode.com/discuss/83824/7-lines-easy-java-solution
[3] https://leetcode.com/discuss/83825/simple-python-solution-using-stack-with-explanation

MJ [53] Tree S Expression

Question:

You are given a binary tree as a sequence of parent-child pairs. For example, the tree represented by the node pairs below:

(A,B) (A,C) (B,G) (C,H) (E,F) (B,D) (C,E). 鍥磋鎴戜滑@1point 3 acres

may be illustrated in many ways, with two possible representations below:

     A   /  \  B    C / \  / \G  D  E   H       \            F        A   /  \  B    C / \  / \D  G H   E        /       F

Below is the recursive definition for the S-expression of a tree:

S-exp(node) = ( node->val (S-exp(node->first_child))(S-exp(node->second_child))), if node != NULL
                         = "", node == NULL
   where, first_child->val < second_child->val (lexicographically smaller)
-google 1point3acres

This tree can be represented in a S-expression in multiple ways. The lexicographically smallest way of expressing this is as follows:

(A(B(D)(G))(C(E(F))(H)))

We need to translate the node-pair representation into an S-expression (lexicographically smallest one), and report any errors that do not conform to the definition of a binary tree.

The list of errors with their codes is as follows:

Error Code      Type of error
E1                 More than 2 children
E2                 Duplicate Edges
E3                 Cycle present.1point3acres缃�
E4                 Multiple roots
E5                 Any other error   

Input Format:
Input must be read from standard input.
Input will consist of on line of parent-child pairs. Each pair consists of two node names separated by a single comma and enclosed in parentheses. A single space separates the pairs.. 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
Output:. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
The function must write to standard output.
Output the given tree in the S-expression representation described above.

There should be no spaces in the output.. from: 1point3acres.com/bbs 

Constraints:

• There is no specific sequence in which the input (parent,child) pairs are represented.
• The name space is composed of upper case single letter (A-Z) so the maximum size is 26 nodes.
• Error cases are to be tagged in the order they appear on the list. For example, if one input pair raises both error cases 1 and 2, the output must be E1.

. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�. 

Sample Input #00

(B,D) (D,E) (A,B) (C,F) (E,G) (A,C)

Sample Output #00

(A(B(D(E(G))))(C(F)))

Sample Input #01

(A,B) (A,C) (B,D) (D,C). From 1point 3acres bbs

Sample Output #01

E3

Explanation

Node D is both a child of B and a parent of C, but C and B are both child nodes of A. Since D tries to attach itself as parent to a node already above it in the tree, this forms a cycle.

===============
Ref
[1] http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=165923&extra=page%3D2%26filter%3Dsortid%26sortid%3D311%26sortid%3D311

MJ [52] subsquence combinations

Question:
String s1 = "waeginsapnaabangpisebbasepgnccccapisdnfngaabndlrjngeuiogbbegbuoecccc"
String s2 = "a+b+c-";

s2的形式是一个字母加上一个符号，正号代表有两个前面的字符，负号代表有四个，也就是说s2其实是"aabbcccc"，不考虑invalid。
在s1中，找出连续或者不连续的s2，也就是说从s1中找出"aa....bb.....cccc"，abc顺序不能变，但是之间可以有零个或多个字符，返回共有多少个。在上面这个例子中，有四个。

MJ [51] Pair in BST

Question:
http://www.geeksforgeeks.org/find-a-pair-with-given-sum-in-bst/