# Backtrace – leetcode 17 – Letter Combinations of a Phone Number

this is a very classic backtrace problem.

Idea is simple, use ‘call stack’ to store string “a…z”

stack n – z
.
.
stack 1 – a

if stack.length == targetLenth
loop though stack to get char array to string.

```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   package com.dw.leetcode;   import java.util.*;   public class Letter_Combinations_of_a_Phone_Number_17 { static final char[][] number = { { 'a', 'b', 'c' }, { 'd', 'e', 'f' }, { 'g', 'h', 'i' }, { 'j', 'k', 'l' }, { 'm', 'n', 'o' }, { 'p', 'q', 'r', 's' }, { 't', 'u', 'v' }, { 'w', 'x', 'y', 'z' } };   public List<String> letterCombinations(String digits) { List<String> result = new ArrayList<String>(); if(digits.length() == 0){ return new ArrayList<>(); }   foo(digits, 0, 0, digits.length(), new ArrayList<Character>(), result); return result; }   public void foo(String digits, int index, int total, int len, List<Character> temp, List<String> result) { if(total == len) { StringBuilder stringBuilder = new StringBuilder(); for(Character c: temp) { stringBuilder.append(c); } result.add(stringBuilder.toString()); return; }   int numberIndex = Integer.parseInt(Character.toString(digits.charAt(index)));   for(char c: number[numberIndex - 2]) { temp.add(c); foo(digits, index+1, total+1, len, temp, result); temp.remove(temp.size() - 1); } }   public static void main(String[] args) { // TODO Auto-generated method stub Letter_Combinations_of_a_Phone_Number_17 s = new Letter_Combinations_of_a_Phone_Number_17(); System.out.println(s.letterCombinations("234")); }   }```

# Linux Kernel – Data structure List in include/linux/list.h

Linux Kernel has lots of data structure such as list (including linked list, double linked lists), red-black tree, B Tree , Interval tree, Heap, Radix tree, spin locks and so on.
I will put some articles for these interesting data structures.

Even for such simple data structure, Linux Kernel still has some operation which User-Space data structure didn’t use.

```1 2 3 struct list_head { struct list_head *next, *prev; };```

It is a double linked list.

```1 2 3 4 5 static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list->prev = list; }```
```1 2 3 4 5 6 7 8 9 static inline void __list_add(struct list_head *entry, struct list_head *prev, struct list_head *next) { next->prev = entry; entry->next = next; entry->prev = prev; prev->next = entry; }```

what this function todo is put entry between next and prev.

prev –> entry <--- next

```1 2 3 4 static inline void list_add_tail(struct list_head *new, struct list_head *head) { __list_add(new, head->prev, head); }```

```1 2 3 4 5 static inline void __list_del(struct list_head * prev, struct list_head * next) { next->prev = prev; prev->next = next; }```

del is to delete all items between prev and next. therefore, set next’s prev to prev node.
and prev node’s next to be next node.

```1 2 3 4 5 6 7 8 9 static inline void list_replace(struct list_head *old, struct list_head *new) { new->next = old->next; new->next->prev = new; new->prev = old->prev; new->prev->next = new; } INIT_LIST_HEAD(old); // let old's all pointer pointed to itself.```

delete old one and linked new one to old one’s postion.

```1 2 3 4 5 static inline void list_move(struct list_head *list, struct list_head *head) { __list_del_entry(list); list_add(list, head); }```

```1 2 3 4 5 6 7 8 9 static inline void list_rotate_left(struct list_head *head) { struct list_head *first;   if (!list_empty(head)) { first = head->next; list_move_tail(first, head); } }```

some other functions such as list_cut_position is to split list into two.
and list_splice is to join two lists

```1 2 3 4 #define list_for_each_prev_safe(pos, n, head) \ for (pos = (head)->prev, n = pos->prev; \ pos != (head); \ pos = n, n = pos->prev)```

some macro are defined in such format, there for developer don’t have to write “for” every time

# Google CodeJam – Mushroom Monster

This question could be become two sub question.
1. less mushroom to eat.
for array 10 5 15 5, what is the sum of decreased numbers?
10 is decreased to 5, the decreased number is (10-5).
5 raises to 15, it will be ignored.
15 is decreased to 5, the decreased number is (15-5)

the sum of all decreased numbers that is (10-5)+(15-5) will be the answer.

2. eating mushroom in static speed.

find the max gap of decreased numbers. (15-5) is the max speed in 10 seconds.
there for, if mushroom number on the dish is greater than (15-5), Kaylin only eats(15-5).

if mushroom number on the dish is less that (15-5), Kaylin will finish all of them and waiting for next refill.

Here is Clang code.

```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 int N; int L; int i,j,k; int array[MAXSIZE]; int sum1 = 0; int sum2 = 0;   scanf("%d\n",&N);   for(i=0;i<N;i++) { scanf("%d",&L); memset(array,0,sizeof(int)*MAXSIZE); sum1 = 0; sum2 = 0; for(j = 0;j<L;j++){ scanf("%d",&array[j]); }   //start for(j = 0;j<L - 1;j++){ if(array[j]>array[j + 1]) sum1 += (array[j] - array[j + 1]); }   int max = 0;   for(j = 0;j<L - 1;j++){ if(array[j]>array[j + 1]){ if(max<(array[j] - array[j + 1])){ max = array[j] - array[j + 1]; } } }   for(j = 0;j<L - 1;j++){ sum2 += (array[j]>max?max:array[j]); }   printf("Case #%d: %d %d\n",(i + 1),sum1,sum2); }```

# Leetcode – Count of Smaller Numbers After Self

Here is leetcode’s new hard level question:

https://leetcode.com/problems/count-of-smaller-numbers-after-self/

The basic idea is using two for to loop though to counter smaller number on its left.
Solution1:

```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public List<Integer> countSmaller(int[] nums) { List<Integer> result = new ArrayList<>();   result.add(0);   for(int i = nums.length - 2;i>=0;i--) { int target = nums[i]; int count = 0; for(int j=i+1;j<=nums.length-1;j++) { if(nums[j]<=target) count++; } result.add(count); }   Collections.reverse(result);   return result; }```

Solution 2:

Solution 1 is using two loops to go though to compare.

This solution is faster the second loop using tree.

```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   package leetcodetest;   import java.util.ArrayList; import java.util.Collections; import java.util.List;   /** * * @author wudi */ public class CountSmaller2 {   public class xTreenode { public xTreenode left = null; public xTreenode right = null; int count = 1;   int val;   public xTreenode(int x) { val = x; }   }   public int add(xTreenode root,int x) { int count = 0;   while(true) { if(x <= root.val) { root.count++;   if(root.left == null){ root.left = new xTreenode(x); break; }   root = root.left; } else { count += root.count; if(root.right == null) { root.right = new xTreenode(x); break; } root = root.right; } }   return count; }   public List<Integer> countSmaller(int[] nums) { List<Integer> result = new ArrayList<>(); if(nums == null || nums.length == 0) return result; xTreenode root = new xTreenode(nums[nums.length - 1]); result.add(0);   for(int i=nums.length - 2;i>=0;i--) { int count = add(root,nums[i]); result.add(count); }   Collections.reverse(result);   return result; } public static void main(String[] args) { int[] nums = {2,0,1};   CountSmaller2 c = new CountSmaller2(); System.out.println(c.countSmaller(nums)); } }```

# 199 Binary Tree Right Side View

Total Accepted: 2068 Total Submissions: 7422

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

```   1            <---
/   \
2     3         <---
\     \
5     4       <---
```

You should return `[1, 3, 4]`.

[code] [/code]

# LeetCode OJ: Length of Last Word

### Length of Last Word

Total Accepted: 29154 Total Submissions: 100944

Given a string s consists of upper/lower-case alphabets and empty space characters `' '`, return the length of last word in the string.

If the last word does not exist, return 0.

Note: A word is defined as a character sequence consists of non-space characters only.

For example,
Given s = `"Hello World"`,
return `5`.

https://oj.leetcode.com/problems/length-of-last-word/

Solution: see the comment in the code , writed in Java

```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   public static int lengthOfLastWord(String s) { if(s.length() == 0) return 0; // input may be ""   int result = -1;   int skipEmpty = 0; // skip empty string at the end of input string s for(int i= s.length() - 1;i>=0;i--) { if(s.charAt(i) == ' ') continue; else { skipEmpty = i; break; } } //Start to Calculate for(int i= skipEmpty;i>=0;i--) { if(s.charAt(i) != ' ') continue; else { result = i; break; }   }   return skipEmpty - result; }```