Category Archives: Algorithm

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.

List is most simple data structure we could start with.

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

the definition of list_head

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);
}

append something into tail is to add entry between head and tail(head and tail are linked together)

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);
}

delete from one list and add as another’s 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);
	}
}

move head->next to head and tail.

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

Question URL is https://code.google.com/codejam/contest/4224486/dashboard

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]

binarySideView

[/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;
}