## leetcode Counting Bits

Given a non negative integer number

num. For every numbersiin the range0 ≤ i ≤ numcalculate the number of 1’s in their binary representation and return them as an array.

Example:

For`num = 5`

you should return`[0,1,1,2,1,2]`

.

Follow up:

- It is very easy to come up with a solution with run time
O(n*sizeof(integer)). But can you do it in linear timeO(n)/possibly in a single pass?- Space complexity should be
O(n).- Can you do it like a boss? Do it without using any builtin function like
__builtin_popcountin c++ or in any other language.

# python

## leetcode House Robber III

## leetcode House Robber III

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

12345 3/ \2 3\ \3 1Maximum amount of money the thief can rob = 3 + 3 + 1 =

7.

Example 2:

12345 3/ \4 5/ \ \1 3 1Maximum amount of money the thief can rob = 4 + 5 =

9.

## leetcode Self Crossing

## 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)

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

.

## leetcode Patching Array

## leetcode Patching Array

Given a sorted positive integer array

numsand an integern, add/patch elements to the array such that any number in range`[1, n]`

inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

Example 1:

nums=`[1, 3]`

,n=`6`

Return`1`

.Combinations of

numsare`[1], [3], [1,3]`

, which form possible sums of:`1, 3, 4`

.

Now if we add/patch`2`

tonums, the combinations are:`[1], [2], [3], [1,3], [2,3], [1,2,3]`

.

Possible sums are`1, 2, 3, 4, 5, 6`

, which now covers the range`[1, 6]`

.

So we only need`1`

patch.

## leetcode Longest Increasing Path in a Matrix

## leetcode Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:nums = [

[9,9,4],

[6,6,8],

[2,1,1]

]

Return

`4`

The longest increasing path is`[1, 2, 6, 9]`

.

## leetcode Odd Even Linked List

## leetcode Odd Even Linked List

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:

Given`1->2->3->4->5->NULL`

,

return`1->3->5->2->4->NULL`

.

Note:

The relative order inside both the even and odd groups should remain as it was in the input.

The first node is considered odd, the second node even and so on …

## leetcode Count of Range Sum

## leetcode Count of Range Sum

Given an integer array

`nums`

, return the number of range sums that lie in`[lower, upper]`

inclusive.

Range sum`S(i, j)`

is defined as the sum of the elements in`nums`

between indices`i`

and`j`

(`i`

≤`j`

), inclusive.

Note:

A naive algorithm ofO(n^{2}) is trivial. You MUST do better than that.

Example:

Givennums=`[-2, 5, -1]`

,lower=`-2`

,upper=`2`

,

Return`3`

.

The three ranges are :`[0, 0]`

,`[2, 2]`

,`[0, 2]`

and their respective sums are:`-2, -1, 2`

.