## leetcode Self Crossing

You are given an array

xof`n`

positive numbers. You start at point`(0,0)`

and moves`x[0]`

metres to the north, then`x[1]`

metres to the west,`x[2]`

metres to the south,`x[3]`

metres to the east and so on. In other words, after each move your direction changes counter-clockwise.Write a one-pass algorithm with

`O(1)`

extra space to determine, if your path crosses itself, or not.

Example 1:

Givenx=`[2, 1, 1, 2]`

Return`true`

(self crossing)

Example 2:

Givenx=`[1, 2, 3, 4]`

Return`false`

(not self crossing)

Example 3:

Givenx=`[1, 1, 1, 1]`

Return`true`

(self crossing)

# Month: February 2016

## leetcode Increasing Triplet Subsequence

## leetcode Increasing Triplet Subsequence

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 thatarr[i]<arr[j]<arr[k]given 0 ≤i<j<k≤n-1 else return false.Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:

Given`[1, 2, 3, 4, 5]`

,

return`true`

.Given

`[5, 4, 3, 2, 1]`

,

return`false`

.

## leetcode Reconstruct Itinerary

## leetcode Reconstruct Itinerary

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:

- 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"]`

.- All airports are represented by three capital letters (IATA code).
- You may assume all tickets may form at least one valid itinerary.

Example 1:

`tickets`

=`[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]`

Return`["JFK", "MUC", "LHR", "SFO", "SJC"]`

.

Example 2:

`tickets`

=`[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]`

Return`["JFK","ATL","JFK","SFO","ATL","SFO"]`

.

Another possible reconstruction is`["JFK","SFO","ATL","JFK","ATL","SFO"]`

. But it is larger in lexical order.

## leetcode Verify Preorder Serialization of a Binary Tree

## leetcode Verify Preorder Serialization of a Binary Tree

One way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as

`#`

.

1234567 _9_/ \3 2/ \ / \4 1 # 6/ \ / \ / \# # # # # #For example, the above binary tree can be serialized to the string

`"9,3,4,#,#,1,#,#,2,#,6,#,#"`

, where`#`

represents a null node.Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.

Each comma separated value in the string must be either an integer or a character

`'#'`

representing`null`

pointer.You may assume that the input format is always valid, for example it could never contain two consecutive commas such as

`"1,,3"`

.