parlindrome partition

leetCode 131 a sample code :

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

void dfs(int depth, string s){
  if(depth == s.size()){
    v.push_back(v1);
  }
  if(depth<s.size()){
    for(int i=depth; i<s.size(); i++){
      //left substring 
      if(palindrome(s.substr(depth, i-depth+1))){
        v1.push_back(s.substr(depth, i-depth+1));
        dfs(i+1, s);
        v1.pop_back();  
      }
    }
  }  
}

1) each col in the table is one way to partition the string.e.g. aab. col_1 , left string a is palindrome, v1=[a]; feed right string ab to dfs(i+1, s)(depth=0, i=depth)

1.1) col1_1, left string a is palindrome, v1=[a, a];
feed right string b into dfs(i+1, s) (depth=1, i=depth)

1.1.1) b will push into v1, make v1=[a, a, b], feed into dfs(i+1, s) (depth=2, i=depth), which will return since depth==s.size().

the above dfs()(depth=2, i=depth) returned, the immediate next step is b pop out from v1; also now is the finished of dfs()(depth=1, i=depth), so the immediate next step is the second a pop out.

1.1.2) so now go to (depth=1, i=depth+1), push ab into v1, making v1=[a, ab] . but ab is not palindrome, return immediately, then pop out ab.

1.2) at this time, the very outside dfs()(depth=0, i=depth) is all done, so pop the first a in v1; and go to (depth=0, i=depth+1); then (depth=0, i=depth+2)…

recursive of DFS

another example of recursive dfs. leetcode 129 sum root of leaf numbers

dfs is used to find all the solutions, in a way to go through each branch in the same level first, then go into the next level.

to traverse all solutions(branches), also need to mark traversing/traversed branches. so usually need:

to push ->  current traversing element
to pop -> traversed element 

and a container to hold all solutions.

if design recursive with returned value, consider the critical condition. e.g. what suppose to return when the last element, and usually design the returned value as local variable in each recursive function, rather than a global variable.

one more thing is about the traversing direction, from left to right end, then when coding make sure the direction is consistent at all times.

BFS to find mini cuts

DFS is used to solve the kind of problem: traversal all possible solutions; leetcode 132 askes for the mini cuts, once find out the mini-cuts solution, done, no traverse all possibilities.

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

// define done, cut as class member variable 
void bfs(string s, bool& done){
  int len = s.length();
  string left, right;
  int i =0;
  while(!done && i<len){
    left = s.substr(0, len-i); //starting from the longest left string
    right = s.substr(len-i, i);
    if(palindrome(left)){
        cut++;
        if(palindrome(right))
        {
          done = true ;
        }else {
            bfs(right, done);
        }
    }
    i++;
  }
}

leetCode130, like go game.

how to design the solution, at first it is naive to traverse with two for loops, then there will be too many if statement to specify, and not clear to seperate these if statements.

three ideas behind a sample solution.

using addtional status variable

in lower space the problem is difficult to analysis, then from a higher space, the problem is clear and easy. e.g. trakcing the O in the board, how to mark them ? keep O will not tell the marked ones and the original ones. so using M to mark these already traversed, it make the situation much more clear

starting from the critial domain

at first, no idea where is a good start point, but the trick point is at the boundary, only the cells at boundary with O will keep O; all the O not on the boundary either connect to the boundary Os or they will be Xs.

traversing with queue

if not queue, to detect these O cells need two for loops, then deal with these O cells again need another two for loops.

for loop is a global handling, while queue list is a local way, no need to take all cells in consideration, but only the cells in queue.

queue should be a good way to traverse whenever the operation is not deal with all the elements.

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

//extending from the boundary 'O', any extened will keep same statue
void process(int i, int j, vector<vector<char>>& board){
  int height = board.size();
  int width = board[0].size();
  std::pair<int, int> p;
  queue<std::pair<int, int>> Q ;
  Q.push(p(i,j));
  board[i][j] = 'm';
  while(!Q.empty()){
      p tmp = Q.front(); Q.pop();
      i=tmp.first;
      j=tmp.second;
      if(i!=0 && board[i-1][j] == 'O'){
        board[i-1][j] = 'm';
        Q.push(p[i-1][j]);
      }
      if(i!= width-1 && board[i+1][j]=='O')
      {
        board[i+1][j] = 'm';
        Q.push(p[i+1][j]);
      }
      if(j!=0 && board[i][j-1]=='0')
      {
        board[i][j-1]='m';
        Q.push(p[i][j-1]);
      }
      if(j!=height-1 && board[i][j+1]=='O')
      {
        board[i][j+1] = 'm';
        Q.push(p[i][j+1]);
      }
  }
}
void sol(vector<vector<char>>& board){
  int height = board.size();
  int width = board[0].size();
//tracking the boundary 'o' and mark them as 'm'
  for(int i=0; i<width; i++){
    if(board[i][0] == 'O'){ //bottom boundary
      board[i][0] = 'm' ;
      process(i, 0, board);
    }
    if(board[i][height-1] == 'O')
    {
        board[i][height-1] = 'm' ;
        process(i, height-1, board);
      }
  }
  for(int j=0; j<height; j++){
    if(board[0][j] == 'O'){
      board[0][j] = 'm';
      process(0, j, board);
    }
     if(board[width-1][j] == 'O')
    {
        board[width-1][j] = 'm' ;
        process(width-1, j, board);
      }
  }
  for(int i=0; i<width; i++)
    for(int j=0; j<height; j++){
      if(board[i][j] == 'O')
        board[i][j] = 'X';
      if(board[i][j] == 'm')
        board[i][j] = 'O';
    }
  }
}

the ideas behind hashtable is: 1) input the key to hash function, output the bucket index; 2) adding the element to the bucket[idx]. usually design the bucket[idx] as a linked list, allowing mulitply keys in the same bucket, which is called “collesion chaining”. 3) hashtable has three basic operators: insert/put, search/get, and remove.

the memory usage of hashtable is continuous bucket array, then each bucket is a linked list. when first thought about the “continue array”, really is a vector, then why need hash function. That’s the point, hashtable allows the benefits of both vector and linked list.

a few interesting topics about hash.

1)why prime numbers? the fundamental mathematical operations with prime numbers generally result in numbers who’s bit biases are close to random. in other word, when multiply or add a set of randome numbers by a prime number, the resulting numbers when as a group, statistically analyzed at their bit levels should show no bias towards being one state or another. in comupter science, pseudo random number generator has bit bias.

2) string hash/scattering,
basically the hash functions should deal with each chracter in the input string, so no information about this string will be missed, and the information entropy after hashing operator suppose increase.

3) Blizzard hash function. not all hash function deal collision conflict with linked list, here is the example.

4) hash map benchmark performance review

one feeling at this moment, so many brilliant and deep-focusing guys there, stay foolish and stay humble.

std::unordered_map

there is map vs unordered_map :

map      |     unordered_map

Ordering        | increasing  order   | no ordering
                | (by default)        |

Implementation  | Self balancing BST  | Hash Table

search time     | log(n)    | O(1) ->Average 
                |           | O(n) -> Worst 

Insertion time  | log(n) + Rebalance  | Same as search

Deletion time   | log(n) + Rebalance  | Same as search

basically map works for traversal, pre/post element access; unordered_map is quick in once search,insertion, deletion. here is a dictionary demo

example

word ladder, hash table is used to find a special word from dictionary. the benefit of unorder_set is O(1) find. so design a unorder_set to store the dict.

in the following example, each character position in the word requires 25 times search of the dict. also every marked word from the dict, should not be searched second time.

another variable is used to track the list of one_character_diff from current word, it’s like BFS. so design as a queue, which only need take care the neighbor two layers.

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

int sol(string start, string end, vector<string>& wordList)
{
	int length = 2 ; 
	unordered_set<string> dict ;
	foreach word in wordList:
		dict.insert(word)
	
	queue<string> one_diff_list; 
	// initial by pushing start 
	one_diff_list.push(start);
	while(!one_diff_list.empty()){
		int size = one_diff_list.size();	
		for(int i=0; i<size; i++){
			string word=one_diff_list.front();
			one_diff_list.pop();
			for(int i=0; i<start.length(); i++){
				char oldChar = word[i];
				for(char c='a'; c<='z'; c++){
					if(c == oldChar) continue ;
					word[i] = c ; 
					if(dict.find(word) != dict.end()){
						if(word == end) 
						{ //find the match
						  return length;
						}
						one_diff_list.push(word);
						dict.erase(word);
					}
				}
				word[i] = oldChar;
			}
		}
		length++;
		}
		return 0;
	}

reinforcement learning from David Silver. In autonomous vehicle training, more and more practices dependent on simulator training e.g. carla RF
an open source architecture used often is OpenAI GYM

each agent has state, observation, action, which can be defined in state_space, observation_space, action_space.

background

1) infinite or finite :

in real case, state, observation space are easily to be infinite, e.g. in every frame, the agent has a different environment,
which means a different state. the elements in action_space may be limited, e.g. turn left, turn right, accelerate, brake. etc.

2) continuous or discrete :

when driving a car, the control is continuous, namely, a continuous function a time t. on the other hand, like play GO game,
the action is not time related, each action is discrete to another.

3) locally or globally perception

for a grid world game, the agent knows the whole world; but when a car running in a city, it can only percept the environment locally.
this has a big difference when make decision

the following talks about on-line policy RL, which means the agent will follow some policy(high-level). e.g the velocity limit, no collision with another car etc to training agent know how to drive, often need define environment reward, used to update the policy(detail-level), e.g. when the agent in stateA, policyI will be used. but keep in mind, neither the human nor the agent know exactly at first, which is the best(detail-level) value for the chosen policy, and the input (state, policy/action) is not even accurate so the learning process is actually to iterate in each episode to update the table (state, action), in which the policy is updated hidden, and which is usually called Q-value. after training, the (state, action) is better to handle the simulation environement.

so the high-level computing flow:

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

 
 s0 = env.step(agent)
 a0 = agent.follow_policy(s0)
 while not is_done: 
s1, r1, is_done, info = agent.act(a0) 
old_q_value = env.get_Q(s0, a0)
cur_q_value = env.get_Q(s1, a1) 
measure = r1 + gamma * cur_q_value 
new_q_value = old_q_value + alpha * (measure - old_q_value) 
env.set_Q(s0, a0, new_q_value) 
s0, a0 = s1, a1

real case

while loop is basically update policy, so next time in a certain state, the agent will performance better. but there is a problem, most real problem don’t have a Q-table, since the state space is infinite.

1) linear space approximator

the real state space is high-dimension even infinite-dimension, mathmatically it’s OK to use a linear space to be as close as possible to the real space (Hilbert space). e.g. in elastic mechanics, the finite element space can approximate any accuracy to the continuous elastic space.

so the idea is to construct the linear space base vector based on existing sample state, then all state can be descriped as a linear combination of the base vector.

2） neuro-network aproximator

for nonlinear fitted application, to construct a neuro-network to describe the state space. how to train the network and how to make sure it is robost and convergence is another topic

Pick python up from a link for new position:

type

1
2

type(123)
isinstance(instance_name, class_name)

@property

transfer get()method in a class to a decorator

define function

1
2
3

def my_abs(x):
    if not isinstance(x, (int, float)):
        raise TypeError('bad operand type')

fun decorator

1
2

@decorator
def fun()

filter

1
2
3
4

def is_odd(n):
	return n%2 == 1 
	
list(filter(is_odd, [1, 2, 3, 4])

lambda

1

list(map(lambda x: x*2, [1, 2, 3, 4]))

slice

1
2

L = [1, 2, 3, 4, 5]
L[-2:]  #[4, 5]

list generation

1

[x*2 for x in range(1, 5)]

class & instance

1
2
3
4
5
6
7
8
9

class s(object):
	def \__init__(self, name):
		self.name = name
	
	def print_s(self):
		print('%s:' %(self.name))
		
s1 = s("john")
s1.print_s()

customized class

dynamic language, so the instance of any class can be added any other attributes.

1
2
3
4
5
6
7
8
9

class s(object):
	def \__init__(self, name):
			self._name = name
	def \__str__(self):
		return 's object(name: %s)' % self._name
	
	def \__getattr__(self, attr):
		if attr == 'attr1':
			return lambda: attr1.value

raise & except

1
2
3
4
5
6
7
8
9
10
11

import logging
try:
	print('try...')
	r = 10/0 
	print('result: ', r)
except ZeroDiisionError as e:
	print('except', e)
	logging.exception(e)
finally:
	print('finally..')

IO stream

1
2
3
4
5
6
7
8
9
10
11

f = open('test.log', 'r')
print(f.read(size))
f.close() 
#or 
with open('test.log', 'r') as f:
	printf(f.read(size)) 
	for line in f.readlines():
		print(line.strip())

pickling

serializaion/marshalling/flattening and reverse

1
2
3
4
5
6

import pickle
import json
d = dic(name='zj', age='18')
pickle.dumps(d)
json.dumps(d)

go ahead

1
2
3
4
5
6
7
8

<table cellspacing="0" style="border: 1px solid #333333; margin: 10px;"><tr><td colspan="2" style="border: none; font: bold 16px sans-serif; background: #ffddbb; color: #000000; padding: 5px; margin: 0px; text-align: center;">This Is My Life, Rated</td></tr><tr><td style="width: 85px; padding: 5px; font: bold 18px sans-serif; text-align: left; border: 1px solid #333333; border-left: none; background-image: none; background: #ffffcc; color: #000000;">Life:
</td><td style="width: 240px; padding: 5px; padding-left: 0px; font: bold 18px sans-serif; text-align: left; border: 1px solid #333333; border-left: none; border-right: none; vertical-align: middle; background-image: none; background: #ffffff; color: #000000;"><img src="http://www.monkeyquiz.com/img/grebar.gif" height="12" width="124" style="border: 1px solid #000000; border-left: none; vertical-align: middle; padding: 0px; margin: 0px;"> 6.2</td></tr><tr><td style="width: 85px; padding: 5px; font: bold 12px sans-serif; text-align: left; border: none; border-right: 1px solid #333333; background-image: none; background: #ffffcc; color: #000000;">Mind:
</td><td style="width: 240px; padding: 5px; padding-left: 0px; font: bold 12px sans-serif; text-align: left; border: none; vertical-align: middle; background-image: none; background: #ffffff; color: #000000;"><img src="http://www.monkeyquiz.com/img/greblubar.gif" height="12" width="134" style="border: 1px solid #000000; border-left: none; vertical-align: middle; padding: 0px; margin: 0px;"> 6.7</td></tr><tr><td style="width: 85px; padding: 5px; font: bold 12px sans-serif; text-align: left; border: none; border-right: 1px solid #333333; background-image: none; background: #ffffcc; color: #000000;">Body:
</td><td style="width: 240px; padding: 5px; padding-left: 0px; font: bold 12px sans-serif; text-align: left; border: none; vertical-align: middle; background-image: none; background: #ffffff; color: #000000;"><img src="http://www.monkeyquiz.com/img/blubar.gif" height="12" width="156" style="border: 1px solid #000000; border-left: none; vertical-align: middle; padding: 0px; margin: 0px;"> 7.8</td></tr><tr><td style="width: 85px; padding: 5px; font: bold 12px sans-serif; text-align: left; border: none; border-right: 1px solid #333333; background-image: none; background: #ffffcc; color: #000000;">Spirit:
</td><td style="width: 240px; padding: 5px; padding-left: 0px; font: bold 12px sans-serif; text-align: left; border: none; vertical-align: middle; background-image: none; background: #ffffff; color: #000000;"><img src="http://www.monkeyquiz.com/img/blupurbar.gif" height="12" width="176" style="border: 1px solid #000000; border-left: none; vertical-align: middle; padding: 0px; margin: 0px;"> 8.8</td></tr><tr><td style="width: 85px; padding: 5px; font: bold 12px sans-serif; text-align: left; border: none; border-right: 1px solid #333333; background-image: none; background: #ffffcc; color: #000000;">Friends/Family:
</td><td style="width: 240px; padding: 5px; padding-left: 0px; font: bold 12px sans-serif; text-align: left; border: none; vertical-align: middle; background-image: none; background: #ffffff; color: #000000;"><img src="http://www.monkeyquiz.com/img/orbar.gif" height="12" width="46" style="border: 1px solid #000000; border-left: none; vertical-align: middle; padding: 0px; margin: 0px;"> 2.3</td></tr><tr><td style="width: 85px; padding: 5px; font: bold 12px sans-serif; text-align: left; border: none; border-right: 1px solid #333333; background-image: none; background: #ffffcc; color: #000000;">Love:
</td><td style="width: 240px; padding: 5px; padding-left: 0px; font: bold 12px sans-serif; text-align: left; border: none; vertical-align: middle; background-image: none; background: #ffffff; color: #000000;"><img src="http://www.monkeyquiz.com/img/redbar.gif" height="12" width="16" style="border: 1px solid #000000; border-left: none; vertical-align: middle; padding: 0px; margin: 0px;"> 0.8</td></tr><tr><td style="width: 85px; padding: 5px; font: bold 12px sans-serif; text-align: left; border: none; border-right: 1px solid #333333; background-image: none; background: #ffffcc; color: #000000;">Finance:
</td><td style="width: 240px; padding: 5px; padding-left: 0px; font: bold 12px sans-serif; text-align: left; border: none; vertical-align: middle; background-image: none; background: #ffffff; color: #000000;"><img src="http://www.monkeyquiz.com/img/greblubar.gif" height="12" width="142" style="border: 1px solid #000000; border-left: none; vertical-align: middle; padding: 0px; margin: 0px;"> 7.1</td></tr><tr><td colspan="2" style="border: none; border-top: 1px solid #333333; font: bold 14px sans-serif; background: #ffeedd; padding: 5px; margin: 0px; text-align: center;"><a href="http://www.monkeyquiz.com/life/rate_my_life.html" style="color: #0000ff;">Take the Rate My Life Quiz</a></td></tr></table>

I am not a socialized man, period

leetCode 124. the first idea is recursive from root to bottom leaf, and return the max from left or right at each node.

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

int subsum(TreeNode* node)
{
	int max_left = 0, max_right =0;
	if(node->left)
		max_left = subsum(node->left);
	else
		return std::max(node->val, subsum(node->right));
	if(node->right)
		max_right = subsum(node->right);
	else
		return std::max(node->val, subsum(node->left));
	sum += node->val + std::max(max_left, max_right); 
	return sum;
}

this will get the max sum branch from top to bottom, but can’t consider the other branch, and there is case when the max sum branch is actually smaller than a subtree sum. so here needs to consider the subtree sum as well, since the root tree can be consider as a subtree, so after implmenting subtree sum, actually no need to consider the other branch sum.

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

int subsum(TreeNode*  node, std::priority_queue<int, vector<int>, greater<int> >& s)
{
 if(node==nullptr)
	 return 0;
 
 int max_left=0, max_right=0;
 int sum=0; 
 int subtree_sum = 0; 
 if(node->left){
	 max_left = subsum(node->left, s); 
	 subtree_sum += max_left;  
 }else
 {
	 subtree_sum += node->val; 
	 return std::max(node->val,  subsum(node->right, s)); 
 }
	 
 if(node->right){
	 max_right = subsum(node->right, s);
	 subtree_sum += max_right;  
 }else{
	 subtree_sum += node->val; 
	 return std::max(node->val, subsum(node->left, s)); 
 }
 
 sum += node->val + std::max(max_left, max_right);
 if(node->right != nullptr  || node->left != nullptr)
	subtree_sum += node->val; 
 else
	 subtree_sum -= node->val; 
 
 if(subtree_sum > sum){
	 s.push(subtree_sum); 
	 cout << "s.top= " << s.top() << "\n" << endl; 
	 while( sum > s.top())
	 {
		 s.pop();
	 }
 }
 return sum; 
}

passing priority_queue s as reference, so if subtree\_sum is bigger than the top-bottom branch sum, then it will be pushed into s; but pop out the elements smaller than current branch sum in each recrusive routing.

finally, compare the largest elemnet in s with top-bottom branch sum.

leetCode 115: given a string S and a string T, count the number of distinct subsequences of S which equals T.

Input: S = "babgbag", T = "bag"
Output: 5
Explanation:
As shown below, there are 5 ways you can generate "bag" from S.
(The caret symbol ^ means the chosen letters)

babgbag
^^ ^
babgbag
^^    ^
babgbag
^    ^^
babgbag
   ^  ^^
babgbag
     ^^^

first thought

for each alpha in T, traversing S, find a match, return; then move forward for next alpha in T and traversing S again,

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

int sol(string& s1,  string& s2)
{
 string::iterator sit1, sit2, nait; 
 string notagain; 
 int count=0;	 
for(nait = s2.begin(); nait != s2.end(); nait++)
{
	notagain.push_back(*nait);
	sit1 =  s1.begin(); 
	sit1_last = s1.begin(); 
	
	while( sit1 != s1.end())
	{	 
		for(sit2=s2.begin(); sit2 != s2.end(), sit1 != s1.end(); sit1++)
		{
			if(*sit1 == *sit2)
			{
				tmp.push_back(*sit2);
				sit2++; 
			}
		 
			if(tmp.compare(s2) == 0)
			{
				count++;
				break;
			}
		}
		
		sit1 = st1_last++;
	}	
}
}

this is a failed trail. Since this kind of problem really can’t be solved by purely nested for-loop. think about, at the last level (traverse S to get g), there needs one for-loop, then the previous level or the level above (traverse S to get a) needs another loop. and each “a” needs one for-loop to traverse all possible “g” in S again. and the top level (travers S to get “b”) is another for-loop, and each “b” need another for-loop to traverse “a”. and this is only three levels (b->a->g)

basically if implementing tree traversing with for-loop, since tree structure has many branches to the end, since even each sub-branch needs a for-loop, there will be exponent disaster of for-loop to cover all branches.

second thoughts

what’s the different mindset? recursive. when dealing with many-branches-travsersing (e.g. a tree strucutre), recursive is nature to think. since recursive only consider the neighbor two level branches.

for this example, inside each recursive need a for-loop to catch all possible positions of the satisfied character, and stack is need to, when visiting a new character from T need poush, and when find out a T, then need to pop out the last character.

during breadth traversing tree, either using a pure recursive or using stack with a while-loop. but here it needs a for-loop and stack inside each recursive. (a little complex)

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

void rec(string& S, string& T, string::iterator tc, std::stack<char> ss,  int& nums )
{
	if(tc == T.end())
		return ;
	
	for(int i= 0; i<S.size(); i++)
	{
		if(S[i] == *tc)
		{
			ss.push(*tc);
			if(ss.size() != T.size())
			{
				string cur_s = S.substr(i+1); 
				rec(cur_s, T,  ++tc,  ss, nums);
				--tc; 
				ss.pop();
			}else
			{
				cout << "found one\n" ; 
				nums++; 
				ss.pop(); 
			}
		}
	}
}
int sol(string& S,  string& T)
{
	string::iterator tit = T.begin();
	std::stack<char>  ss ;
	int nums =0; 
	rec(S, T, tit, ss, nums); 
	
	return nums; 
}

TODO: there suppose be a general pattern for this kind of problem.

third thoughts

if the problem is too complex to handle at first, more memory always make it looks simple, using containers to split the content. with 2 for-loops to create #num of buckets to store positions of each alphaet in T

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

int sol(string& s1,  string& s2)
{
	int length =  s2.size(); 
	std::map<char, vector<int>>  smap; 
	std::vector<int> pos; 
	string::iterator sit; 
	char alpha ; 
	for(i=0; i<s2.size(); i++)
	{
		alpha = s2[i]; 
		int i=0; 
		pos.clear(); 
		for(sit = s1.begin(); sit != s1.end(); sit++)
		{
			if( alpha == *sit)
			{
				pos.push_back(i++);
			}
		}
		smap.insert(std::pair<char, vector<int>>(alpha, pos);
	}

b 0, 2, 4
a 1, 5
g 3, 6

after get the map, then play the combinations games. that’s actually still a recursive problem.

Btree traversal is obvious to implement in recursion. here are non-recursion implementation, which needs std::stack or std::queue data structure to store the next level nodes in both deep-first-search idea and breadth-first-search idea, link. these are good examples of using stack, queue.

usage in leetCode114, flatten a BTree to a linked list

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92

void preorder_print(TreeNode* leaf)
{
	if(leaf == nullptr)
		return; 
	
	std::stack<int> s; 
	TreeNode* tmp ; 
	s.clear();  //
	s.push(leaf);
	while(!s.empty())
	{
		tmp = s.pop(); 
		cout << tmp->value  << ', ' ;
		if(leaf->right != nullptr)
			s.push(leaf->right);
		if(leaf->left != nullptr)
			s.push(leaf->left);
	}
		
}
void inorder_print(TreeNode* leaf)
{
	std::stack<int> s ; 
	s.clear(); 
	TreeNode *tmp; 
	
	while( !s.empty() || leaf!=nullptr)
	{
		if(leaf != nullptr)
		{
			s.push(leaf);
			leaf = leaf->left;
		}else
		{
			tmp = s.top();
			s.pop(); 
			cout << tmp->value << ', ' ;
			leaf = leaf->right;
		}
	}
}
void postorder_print(TreeNode* leaf)
{
	std::stack<int> s ;
	s.clear();
	
	TreeNode *lastNodeVisited = nullptr ; 
	TreeNode *peekNode = nullptr; 
	
	while( !s.empty() || leaf != nullptr)
	{
		if(leaf != nullptr)
		{
			s.push(leaf);
			leaf = leaf->left;
		}else
		{
			peekNode = s.top();
			if(peekNode->right != nullptr && lastNodeVisited != peekNode->right)
				leaf = peekNode->right;
			else
			{
				cout << peekNode->value << ', ';
				lastNodeVisited = s.top();
				s.pop();
			}
		}
	}
}
void bfs_print(TreeNode* leaf)
{
	std::queue<int> q ;
	q.clear();
	q.push(leaf);
	TreeNode *node; 
	while( ! q.empty())
	{
		node = q.front(); 
		q.pop();
		cout << node->vaue << ', ';
		
		if(node->left != nullptr)
			q.push(node->left);
		
		if(node->right != nullptr)
			q.push(node->right)
	}
}

leetCode 109 construct a height-balanced Binary Search tree from input array(sorted or not).

a self-balanced BStree, which means the left and right kid of each node have no more than 1 height difference, also named as AVL tree. There are three basic routines in implementation of AVL tree: right tree rotate, left tree rotate, and insert. and each TreeNode requires an additionly height value.

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
46
47
48
49
50
51
52
53
54
55
56

TreeNode*  rightRotate(TreeNode* leaf)
{
	if(leaf==nullptr)
		return leaf;
	
	TreeNode*  root_left =  leaf->left ;
	TreeNode*  left_right = root_left->right ;
	root_left->right = leaf;
	leaf->left = left_right;
	
	return root_left; 
}
TreeNode* leftRotate(TreeNode* leaf)
{
	if(leaf==nullptr)
		return leaf;
	
	TreeNode* root_right = leaf->right; 
	TreeNode* right_left = root_right->left; 
	root_right->left = leaf;
	leaf->right =  right_left;
	
	return root_right;
}
TreeNode* insert(TreeNode* root, int key)
{
	if(root==nullptr)
		return (new TreeNode(key));
	
	if(key > root->val)
		root->right = insert(root->right, key);
	
	else if(key < root->val)
			root->left = insert(root->left, key);
	else
		return root; 
	
	root->height = std::max(height(root->left), height(root->right)) + 1 ; 
	int balance = height_dif(root); 
	if(balance > 1 && key < root->val )  //new key inserted in left sub 
	{
		return rightRotate(root); 
	}
	
	/* keep in mind,    -1 <= last_balance <= 1 
	   only  key < root->val, will it possible that current_balance > 1 */
	if(balance < -1 && key > root->val )
	{	
		return leftRotate(root);
	}
	
	return root; 
}

at the very first coding I natively pass node pointer by reference:

TreeNode* insert(TreeNode* &root, int key)
root->right = insert(root->right, key);

since assigned insert() back to the same node pointer again, if passing by reference, each insert will clear the memory-write the same memory all the time, and can’t generate. what actually happen in insert is creating a new object.

the structure pointer inside structure definition is the trick here. when define root node, both leftand right nodes are nullptr, so argument root->right is nullptr, but the returning root->right is actually pointing to a node structure memory.

also nullptr can’t be dereferring, basically since nullptr doesn’t point to any meaningful object, to dereference a null pointer will cause runtime or immediate crash.