实现 itoa ???????????????

Merge N sorted array ??????????

Make a heap from the first element in each array.
Pop the head element from the heap, insert it into the result array, and then take the next element from the array the head of the heap came from, and insert that into the heap.
Repeat until you consume all of the arrays.

c++中，int, long的大小问题

                     int (in bytes)            long（in bytes)
16位机：          2                                   4

32位机：          4                                  4
64位机：          4                                  8 (windows系统还是4)   

Lowest Common Ancestor of a Binary Tree with parent pointer

Given a binary tree, find the lowest common ancestor of two given nodes in the tree. Each node contains a parent pointer which links to its parent.

Note:
This is Part II of Lowest Common Ancestor of a Binary Tree. If you need to find the lowest common ancestor without parent pointers, please read Lowest Common Ancestor of a Binary Tree Part I.

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

 An easy solution:   use HashSet

The best solution:

A little creativity is needed here. Since we have the parent pointer, we could easily get the distance (height) of both nodes from the root. Once we knew both heights, we could subtract from one another and get the height’s difference (dh). If you observe carefully from the previous solution, the node which is closer to the root is always dh steps ahead of the deeper node. We could eliminate the need of marking visited nodes altogether. Why?

The reason is simple, if we advance the deeper node dh steps above, both nodes would be at the same depth. Then, we advance both nodes one level at a time. They would then eventually intersect at one node, which is the LCA of both nodes. If not, one of the node would eventually reach NULL (root’s parent), which we conclude that both nodes are not in the same tree. However, that part of code shouldn’t be reached, since the problem statement assumed that both nodes are in the same tree.

int getHeight(Node *p) {
  int height = 0;
  while (p) {
    height++;
    p = p->parent;
  }
  return height;
}
 
// As root->parent is NULL, we don't need to pass root in.
Node *LCA(Node *p, Node *q) {
  int h1 = getHeight(p);
  int h2 = getHeight(q);
  // swap both nodes in case p is deeper than q.
  if (h1 > h2) {
    swap(h1, h2);
    swap(p, q);
  }
  // invariant: h1 <= h2.
  int dh = h2 - h1;
  for (int h = 0; h < dh; h++)
    q = q->parent;
  while (p && q) {
    if (p == q) return p;
    p = p->parent;
    q = q->parent;
  }
  return NULL;  // p and q are not in the same tree
}

Lowest Common Ancestor of a Binary Tree w/t parent pointer

Given a binary tree, find the lowest common ancestor of two given nodes in the tree.

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

If you are not so sure about the definition of lowest common ancestor (LCA), please refer to my previous post: Lowest Common Ancestor of a Binary Search Tree (BST) or the definition of LCA here. Using the tree above as an example, the LCA of nodes 5 and 1 is 3. Please note that LCA for nodes 5 and 4 is 5.


 A Top-Down Approach (Worst case O(n²) ):

// Return #nodes that matches P or Q in the subtree.
int countMatchesPQ(Node *root, Node *p, Node *q) {
  if (!root) return 0;
  int matches = countMatchesPQ(root->left, p, q) + countMatchesPQ(root->right, p, q);
  if (root == p || root == q)
    return 1 + matches;
  else
    return matches;
}
 
Node *LCA(Node *root, Node *p, Node *q) {
  if (!root || !p || !q) return NULL;
  if (root == p || root == q) return root;
  int totalMatches = countMatchesPQ(root->left, p, q);
  if (totalMatches == 1)
    return root;
  else if (totalMatches == 2)
    return LCA(root->left, p, q);
  else /* totalMatches == 0 */
    return LCA(root->right, p, q);
}

A Bottom-up Approach (Worst case O(n) ):

Node *LCA(Node *root, Node *p, Node *q) {
  if (!root) return NULL;
  if (root == p || root == q) return root;
  Node *L = LCA(root->left, p, q);
  Node *R = LCA(root->right, p, q);
  if (L && R) return root;  // if p and q are on both sides
  return L ? L : R;  // either one of p,q is on one side OR p,q is not in L&R subtrees
}

traval maximum unvisited cities each day.

Q:
 Input (arr, k )
Output:a list of ending cities till traversal.

背景描述：

Given n cities, indexed from 0 to n-1, we have an array arr, of size n, where A[i] =j, means that there is a direct road between city i and j. there are n-1 roads, all cities are connected.

 for example :  we have 7 cities

                           3                   5

                           |                   | 

                           |                   |

                           |                   |

0 ------------------1 -------------- 2 ----------------4 ----------6

array[ 0 ]  = 1

array[ 1]  = 2

array[ 2 ]  =4

array[ 3 ]  = 1

array[ 4 ]  =6

array[ 5 ]  =2

array[ 6 ]  = 4    

Starting from city  k , each day we visit maximum number of unvisited cities, , but we traval back on the same day.

Print the last city that you visited each day, (ending city) , untill all cities are marked visited.

For example:   k = 2, 

one day 1 , you can visit 3 unvisited cities,   2-1-0(ending city is 0),  or 2-1-3,  or 2 - 4- 6.

so, our final output could be :

0   6     5 3

also, it could be   0 6 3 5,   or  6 0 3 5   or  6 0 5 3,  or 3 6 1 5  or 3 6 5 1

O(n) space &  time

A:

一维数组，向左/右 循环移动k位

Q:

一维数组，向左/右  循环移动k位


A：
   先全部reverse， 再[0,k-1] 和 [k, end] 分别reverse

代码

 #!/usr/bin/python
  2 def reverse(arr,low,high):
  3     while(low<high):
  4         arr[low],arr[high] = arr[high],arr[low]
  5         low+=1
  6         high-=1
  7 
  8 lst = [n for n in range(0,14)]
  9 print(lst)
 10     
 11 k = int(input("enter right shift number k = "))%len(lst)
 12 reverse(lst,0,len(lst)-1)
 13 reverse(lst,0,k-1)
 14 reverse(lst,k,len(lst)-1)
 15 
 16 print(lst)