Noob
0%

发表于 更新于 分类于 ，

Follow up for “Unique Paths”:

Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.

[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2.

Note: m and n will be at most 100.
https://leetcode.com/problems/unique-paths-ii/

1
2
3
4
5
6
7
8
9
10
11
12
public int uniquePathsWithObstacles(int[][] ob) {
    if(ob == null || ob.length == 0 || ob[0].length == 0) return 0;
    int m = ob.length, n = ob[0].length;
    int[] dp = new int[n + 1];
    dp[1] = 1;
    for(int i = 0; i < m; ++i) {
        for(int j = 1; j <= n; ++j) {
            dp[j] = ob[i][j - 1] == 1 ? 0 : dp[j] + dp[j - 1];
        }
    }
    return dp[n];
}
阅读全文 »

发表于 更新于 分类于 ，

Wait() 和 sleep()的比较

wait() 和 sleep()都可以使线程阻塞，它们的区别如下：

  1. wait是Object的方法，而sleep是Thread类的静态方法
  2. sleep使线程阻塞指定时间，这段时间当前线程让出CPU时间，时间结束后继续执行，该过程不释放线程持有的对象锁；wait方法被调用后线程释放持有的锁并进入该锁的等待队列，当收到持有锁的其它线程释放notify或notifyAll信号后，wait方法返回。所以，一般wait方法放在检查某个变量的循环中。

notify和notifyAll的区别

notify随机唤醒一个等待锁的线程，notifyAll唤醒所有等待锁的线程

什么是Daemon线程

Daemon线程（守护线程，后台线程）是值程序运行时在后台提供一种通用服务的线程，并且这种线程不是程序中不可或缺的部分（例如垃圾回收线程就是一种后台线程）。所有非后台线程结束时会杀死所有的后台线程。只要有非后台线程没结束，程序就不会结束。

  1. 可以通过Thread的setDaemon方法将线程设置为Daemon线程，该方法必须在线程启动之前调用
  2. Daemon线程创建的线程也是Daemon线程
  3. Daemon不应该访问数据库、文件等资源，因为它随时有可能被中断（甚至无法执行finall中的语句）
阅读全文 »

发表于 更新于 分类于 ，

Trie树的实现

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
class TrieNode {
    // Initialize your data structure here.
    boolean isLeaf;
    TrieNode[] nodes;
    public TrieNode() {
        isLeaf = false;
        nodes = new TrieNode[26];
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); ++i) {
            int index = word.charAt(i) - 'a';
            /***错误的写法，node信息丢失 
            * node = node.nodes[index];
            * if(node == null)
            *     node = new TrieNode();
            ***/
            if(node.nodes[index] == null)
                node.nodes[index] = new TrieNode();
            node = node.nodes[index];
            if(i == word.length() - 1)
                node.isLeaf = true;
        }
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); ++i) {
            int index = word.charAt(i) - 'a';
            node = node.nodes[index];
            if(node == null)
                return false;
            if(i == word.length() - 1 && node.isLeaf)
                return true;
        }
        return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); ++i) {
            int index = word.charAt(i) - 'a';
            node = node.nodes[index];
            if(node == null)
                return false;
        }
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");

Word Search II

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = [“oath”,”pea”,”eat”,”rain”] and board =

[
[‘o’,’a’,’a’,’n’],
[‘e’,’t’,’a’,’e’],
[‘i’,’h’,’k’,’r’],
[‘i’,’f’,’l’,’v’]
]
Return [“eat”,”oath”].
Note:
You may assume that all inputs are consist of lowercase letters a-z.
https://leetcode.com/problems/word-search-ii/

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
class Trie {
    private class TrieNode {
        boolean isLeaf;
        TrieNode[] nodes;
        public TrieNode() {
            isLeaf = false;
            nodes = new TrieNode[26];
        }
    }
    
    private TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String word) {
        if(word == null || word.length() == 0) return;
        TrieNode node = root;
        for(int i = 0; i < word.length(); ++i) {
            char ch = word.charAt(i);
            if(node.nodes[ch - 'a'] == null)
                node.nodes[ch - 'a'] = new TrieNode();
            node = node.nodes[ch - 'a'];
            if(i == word.length() - 1)
                node.isLeaf = true;
        }
    }
    
    public boolean search(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); ++i) {
            int index = word.charAt(i) - 'a';
            if(node.nodes[index] == null)
                return false;
            node = node.nodes[index];
            if(i == word.length() - 1 &&  node.isLeaf)
                return true;
        }
        return false;
    }
    
    public boolean startWith(String word) {
        TrieNode node = root;
        for(int i = 0; i < word.length(); ++i) {
            int index = word.charAt(i) - 'a';
            if(node.nodes[index] == null)
                return false;
            node = node.nodes[index];
        }
        return true;
    }
}

public class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> result = new ArrayList<String>();
        if(board == null || board.length == 0 || words == null) return result;
        Trie dict = new Trie();
        for(String word : words)
            dict.insert(word);
        for(int i = 0; i < board.length; ++i) {
            for(int j = 0; j < board[0].length; ++j) {
                dfs(board, i, j, dict, result, new StringBuilder());       
            }
        }
        return result;
    }
    
    private void dfs(char[][] board, int x, int y, Trie dict, List<String> result, StringBuilder s) {
        if(x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] == '#') return;
        if(!dict.startWith(s.toString())) return;
        char tmp = board[x][y];
        s.append(tmp);
        String cur = s.toString();
        if(dict.search(cur) && !result.contains(cur))
            result.add(cur);
        board[x][y] = '#';
        dfs(board, x + 1, y, dict, result, s);
        dfs(board, x - 1, y, dict, result, s);
        dfs(board, x, y - 1, dict, result, s);
        dfs(board, x, y + 1, dict, result, s);
        board[x][y] = tmp;
        s.deleteCharAt(s.length() - 1);
    }
}
阅读全文 »

发表于 更新于 分类于 ，

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
https://leetcode.com/problems/merge-intervals/

Remenber Collections.sort(List list, Comparator<? super T> c) and the way to implement Comparator.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<Interval> merge(List<Interval> intervals) {
    if(intervals == null || intervals.size() <= 1) return intervals;
    List<Interval> result = new ArrayList<Interval>();
    Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                if(a.start < b.start) return -1;
                else if(a.start > b.start) return 1;
                else return 0;
            }
        });
    Interval t = intervals.get(0);
    for(int i = 1; i < intervals.size(); ++i) {
        Interval cur = intervals.get(i);
        if(cur.start > t.end) {
            result.add(t);
            t = cur;
        } else if(cur.end > t.end)
            t.end = cur.end;
    }
    result.add(t);
    return result;
}
阅读全文 »

发表于 更新于 分类于 ，

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library’s sort function for this problem.

https://leetcode.com/problems/sort-colors/

阅读全文 »

发表于 更新于 分类于 ，

The Java platfrom is designed from ground up to support concurrent. There are two units of excution: Processes and Threads. A system normally has multipul processes and threads, even if there is only single excution core, because processing time can be shared among threads and processes through time clicing.

阅读全文 »

发表于 更新于 分类于 ，

插入排序

基本思想：维护一个已排好序的序列，每次从未排好序的序列中选择一个元素插入排好序的序列中。具体来说，初始已排序序列为第一个元素，从第二个元素开始，每次选择一个未排序元素，将已排序序列中所有大于该元素的元素向后移动一位，然后把该未排序元素放到排序序列的正确位置。该算法平均时间复杂度O(n^2),在元素已排好序的情况下，时间复杂度为O(n),空间复杂度O(1),是一种稳定排序算法。

1
2
3
4
5
6
7
8
void insert_sort(int a[], int n) {
    int i, j, t;
    for (i = 1; i < n; ++i) {
        for (j = i - 1, t = a[i]; j >= 0 && a[j] > t; --j)
            a[j + 1] = a[j];
        a[j + 1] = t;
    }
}
阅读全文 »

发表于 更新于 分类于 ，

今天中午听《心理FM》，有一篇关于努力的文章让我倍受震撼，我不由得反思自己的一些问题。
几乎可以确切的说，我是“努力”的，花费在“学习”、“创业”这些正能量方面的时间不可谓不多。我没有时间经常性的运动，无论是我怕喜欢的篮球、乒乓球还是感兴趣想要提高的游泳，我都没能抽出足够的时间去做；无论是吉他、还是唱歌、画画，我都没有时间去玩，更不要说旅游、打游戏……

但是，我真的“努力”吗，还是像这篇文章指出的一样只是“有的人因为自身无能，所以要折腾出很多的事情让自己去忙碌，用来增加自己那可怜的自我价值感，同时得以忘记和逃避自己的无能！”

从学习和创业取得的成果来看，答案不言而喻。现在把这篇文章贴在这里自我反思。不断调整自我心态，努力到点子上！

阅读全文 »

发表于 更新于 分类于 ，

Best Time to Buy and Sell stock (Simple DP)

Giving an array of values, say the ith value is the price of stock of the ith day. If you can perform at most one transaction (ie. Buy one and sell one share of stock), find the maximum profit.

Keep tracing the minimum price before the ith day and calculating the maximum profit during scanning.

1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int result = 0, min = prices[0];
    for(int i = 1; i < prices.length; ++i) {
        result = Math.max(result, prices[i] - min);
        min = Math.min(min, prices[i]);
    }
    return result;
}

Best Time to Buy and Sell stock(Greed)

Giving an array of values, say the ith value is the price of stock of the ith day. If you can perform as many transactions (ie. Buy one and sell one share of stock) as you like, find the maximum profit.

Using greed algorithm, perform the transaction only if there is profit to make between two continuous days.

1
2
3
4
5
6
7
8
9
public int maxProfit(int[] prices) {
    if(prices == null || prices.length <= 1) return 0;
    int result = 0;
    for(int i = 1; i < prices.length; ++i) {
        if(prices[i] > prices[i - 1])
            result += prices[i] - prices[i - 1];
    }
    return result;
}

Best Time to Buy and Sell stock(Devide and Conquer & DP)

Giving an array of values, say the ith value is the price of stock of the ith day. If you can perform at most two transactions (ie. Buy one and sell one share of stock), find the maximum profit.

阅读全文 »

发表于 更新于 分类于 ，

综述

Spring框架的基本思想就是，通过XML配置来驱动Java代码，这样就可以把原来由Java代码管理的耦合关系，提取到XML配置文件中管理。通过这种方式实现系统中各组件的解耦，有利于系统的维护和升级。

依赖注入

Spring提供了两种注入方式：构造注入和设值注入，构造注入通过<constructor-arg.../>调用对应含参构造器；设值注入通过<property.../>调用对应的setter方法。Bean注入的成员变量可以分为四种。

  • 普通成员变量。 通过指定property的value属性实现。<property name="intField" value="1"/>,<property name="double" value="2.3"/>
  • 引用成员变量。通过指定property的ref属性实现<property name="axe" ref="steelAxe"/>。也可以通过配置autowrite属性让Spring自动装配Bean的引用成员变量，但在大型应用中自动装配会降低依赖关系的清晰度和透明度。如果被引用的Bean不需要被Spring容器访问，可以考虑使用嵌套Bean。
  • 数组和集合变量。通过在<property></property>中嵌入对应的数组和集合元素实现注入，其中，数组和list都使用实现注入。
  • 组合成员变量。Spring允许直接为Bean成员变量的属性赋值，<bean id="exam" class="com.jeff.Exam"><property name="foo.bar.x.y" value="12"/></bean>相当于执行exam.getFoo().getBar().getX.setY(12)
阅读全文 »