Noob
0%

发表于 更新于 分类于 ，

拓扑排序

拓扑排序（Topological Order）：将一个有向无环图（Directed Acyclic Graph, DAG）进行排序以得到一个有序线性序列，使得如果图中存在一条从A到B的路径，那么该序列中A出现在B的前面。

基于BFS的拓扑排序（入度）

在构建图的过程中统计每个节点的入度，维护一个入度为0的队列，每次选择一个入度为0的节点，将它指向的节点入度减1，重复该过程，直到没有入度为0的节点。

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 int[] findOrder(int num, int[][] pre) {
    if(num <= 0 || pre == null) return null;
    int[] indegree = new int[num];
    Deque<Integer> que = new ArrayDeque<Integer>();
    List<List> graph = new ArrayList<>();
    for(int i = 0; i < num; ++i)
        graph.add(new ArrayList<Integer>());
    for(int i = 0; i < pre.length; ++i) {
        graph.get(pre[i][1]).add(pre[i][0]);
        indegree[pre[i][0]]++;
    }
    for(int i = 0; i < num; ++i)
        if(indegree[i] == 0)
            que.add(i);
    int[] result = new int[num];
    int i = 0;
    while(!que.isEmpty()) {
        int zero = que.remove();
        result[i++] = zero;
        for(int j = 0; j < graph.get(zero).size(); ++j) {
            int nei = (int)graph.get(zero).get(j);
            indegree[nei]--;
            if(indegree[nei] == 0)
                que.add(nei);
        }
    }
    if(i == num) return result;
    else return new int[0];
}
阅读全文 »

发表于 更新于 分类于 ，

To set the default to UTF-8, you want to add the following to my.cnf

[client]
default-character-set=utf8

[mysql]
default-character-set=utf8

[mysqld]
collation-server = utf8_unicode_ci
init-connect=’SET NAMES utf8’
character-set-server = utf8

Works fine with MacOS Yosemite/MySQL 5.6.25

参考资料

http://stackoverflow.com/questions/3513773/change-mysql-default-character-set-to-utf-8-in-my-cnf

阅读全文 »

发表于 更新于 分类于 ，

Hibernate综述

Hibernate框架用于实现对数据库的操作，为应用程序构建一个持久层。Hibernate是对JDBC的封装，通过JDBC的DataBaseMetaData类和ResultSetMetaData类获取数据库表的字段名、类型、大小等相关信息。再结合Java的反射机制建立Java类与数据库表以Java对象与数据表中记录之间的关系。

Hibernate定义了以下对象状态（参考http://wiki.jikexueyuan.com/project/ssh-noob-learning/three-states.html）。

  • Transient - an object is transient if it has just been instantiated using the new operator, and it is not associated with a Hibernate Session. It has no persistent representation in the database and no identifier value has been assigned. Transient instances will be destroyed by the garbage collector if the application does not hold a reference anymore. Use the Hibernate Session to make an object persistent (and let Hibernate take care of the SQL statements that need to be executed for this transition).
  • Persistent - a persistent instance has a representation in the database and an identifier value. It might just have been saved or loaded, however, it is by definition in the scope of a Session. Hibernate will detect any changes made to an object in persistent state and synchronize the state with the database when the unit of work completes. Developers do not execute manual UPDATE statements, or DELETE statements when an object should be made transient.
  • Detached - a detached instance is an object that has been persistent, but its Session has been closed. The reference to the object is still valid, of course, and the detached instance might even be modified in this state. A detached instance can be reattached to a new Session at a later point in time, making it (and all the modifications) persistent again. This feature enables a programming model for long running units of work that require user think-time. We call them application transactions, i.e., a unit of work from the point of view of the user.

瞬态、持久态和游离态中，只有持久态态既与Session关联又存在于数据库中，瞬态是Hibernate新建后对象所处的状态，如果使瞬态对象与Session关联并调用save方法，则瞬态对象转化为持久态对象。当Session对象close或者evict某个对象时，该对象从持久态转化为瞬态。

阅读全文 »

发表于 更新于 分类于 ，

方法1：结合快排和二分的思想

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int findKthLargest(int[] nums, int k) {
    if(nums == null || k < 1 || k > nums.length) return -1;
    return kthElement(nums, k, 0, nums.length - 1);
}

private int kthElement(int[] nums, int k, int beg, int end) {
    int t = partation(nums, beg, end);
    if(t + 1 == k) return nums[t];
    if(t + 1 < k) return kthElement(nums, k, t + 1, end);
    else return kthElement(nums, k, beg, t - 1);
}

private int partation(int[] nums, int beg, int end) {
    int tmp = nums[beg];
    int i = beg, j = end;
    while(i < j) {
        while(j > i && nums[j] <= tmp) --j;
        nums[i] = nums[j];
        while(i < j && nums[i] > tmp) ++i;
        nums[j] = nums[i];
    }
    nums[i] = tmp;
    return i;
}

方法2：最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> que = new PriorityQueue<>();
    for(int i : nums) {
        if(que.size() < k)
            que.add(i);
        else {
            if(que.peek() < i) {
                que.poll();
                que.add(i);
            }
        }
    }
    return que.poll();
}
阅读全文 »

发表于 更新于 分类于 ，

Android

  1. References to resources are always scoped by the resource type (such as id or string), so using the same name does not cause collisions.
  2. Setting the width to zero improves layout performance because using “wrap_content” as the width requires the system to calculate a width that is ultimately irrelevant because the weight value requires another width calculation to fill the remaining space.
阅读全文 »

发表于 更新于 分类于 ，

求最长公共子序列

使用DP算法，i, j分别表示,s1和s2的下标，转移方程为:

  • dp[i][j] = 0; if(i == 0 || j == 0)
  • dp[i][j] = dp[i - 1][j - 1] + 1; if(s1[i] == s2[j])
  • dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); if(s1[i] != s2[j])

求最长公共子序列的方法是，在遍历过程中标记当前值从哪里来的（斜对角，上面还是下面），再从从后到前递归即可：

阅读全文 »

发表于 更新于 分类于 ，

字符串匹配（简版）

https://leetcode.com/problems/wildcard-matching/
“?”代表一个任意的字符，”*“ 代表0个或多个字符

有限状态机（DFA）

记录下不匹配的位置，然后依次回溯

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
public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    
    int i = 0, j = 0;
    int ti = -1, tj = -1;
    while(i < s.length()) {
        if(i < s.length() && j < p.length() && (p.charAt(j) == '?' || p.charAt(j) == s.charAt(i))) {
            ++i;
            ++j;
        }else if(j < p.length() && p.charAt(j) == '*') {
            while(j < p.length() && p.charAt(j) == '*') ++j;
            if(j == p.length()) return true;
            ti = i;
            tj = j;
        }else if(tj != -1 && (j == p.length() || p.charAt(j) != s.charAt(i))) {
            i = ++ti;
            j = tj;
        } else
            return false;
    }
    while(j < p.length()) {
        if(p.charAt(j) != '*')
            return false;
        else
            ++j;
    }
    return true;
}

二维DP

用一个二维数组dp[p.length() + 1][s.length() + 1]记录字符串s和模式串p的匹配情况，其中dp[i][j]表示s[0j]是否与p[0i]匹配，如果匹配dp[i][j]=true，否则dp[i][j]=false.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    
    boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
    dp[0][0] = true;
    for(int i = 0; i < p.length(); ++i) {
        //如果p[i]=='*'，dp[i+1][0]=dp[i][0]，因为此时的转移方程dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j]需要用到dp[i + 1][j]的值，而dp[i + 1][0]初始应该是dp[i][0]
        if(p.charAt(i) == '*') dp[i + 1][0] = dp[i][0];
        for(int j = 0; j < s.length(); ++j) {
            if(p.charAt(i) == '*')
                //设计和分析转移方程时有一个技巧：不看固定不变的量，只把注意力放在变化的量上。例如dp[i + 1][j + 1]与dp[i][j + 1]只看i -> i + 1，即p从第i个字符状态转移到第i+ 1个字符状态的过程（忽略相同的s的第j+1个字符位置）。
                dp[i + 1][j + 1] = dp[i][j + 1] || dp[i + 1][j] ;
            else
                dp[i + 1][j + 1] = dp[i][j] && (p.charAt(i) == '?' || s.charAt(j) == p.charAt(i));
        }
    }
    return dp[p.length()][s.length()];
}

一维DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isMatch(String s, String p) {
    if(s == null || p == null) return false;
    
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;
    for(int i = 0; i < p.length(); ++i) {
        if(p.charAt(i) == '*') {
            for(int j = 0; j < s.length(); ++j)
                dp[j + 1] = dp[j] || dp[j + 1];
        } else {
            for(int j = s.length() - 1; j >= 0; --j)
                dp[j + 1] = dp[j] && (p.charAt(i) == '?' || p.charAt(i) == s.charAt(j));
            dp[0] = false;
        }
    }
    return dp[s.length()];
}
阅读全文 »

发表于 更新于 分类于 ，

最大公约数

思路：使用欧几里得算法（辗转相除法），循环取除数和余数，直到余数为零。

1
2
3
4
5
6
7
8
9
int gcd(int a, int b) {
    int tmp = 0;
    while(b != 0 ) {
        tmp = a % b;
        a = b;
        b = tmp;
    }
    return a;
}

最小公倍数

思路： 两数的最小公倍数等于两数的积与两数的最大公约数的商

1
2
3
int lcd(int a, int b) {
    return (a * b) / gcd(a, b);
}
阅读全文 »

发表于 更新于 分类于 ，

Brute Force

暴力方法依次遍历原字符串，每次从当前位置开始与待查找字符串比较，如果对应字符串不相等，那么原字符串向后移动一位继续与待查找字符串比较。如果待查找字符串一直到结尾都相等，那么返回原字符串开始比较的位置即可。最坏情况下，每次待查找字符串都便利到最后一个字符时失配，这种情况下时间复杂度为O（n*m）。 

1
2
3
4
5
6
7
8
9
10
11
12
13
public int indexOf(String str, String needle) {
    if(str == null || needle == null)
        return -1;
    for(int i = 0; i < str.length(); ++i) {
        for(int j = 0; i + j < str.length() && j < needle.length(); ++j) {
            if(str.charAt(i) != needle.length())
                break;
        }
        if(j == needle.length())
            return i - j;
    }
    return -1;
}

注意防止原字符串越界

KMP

KMP算法是对暴力求解算法的改进，主要思想为：充分利用之前比较的结果，例如原字符串为”ABCDABCDABD”，待查找字符串为”ABCDABD”，当待查找字符串的最后一个D与原字符串的第二个C失配时，可以利用失配的D前面的AB与原字符串中的AB已经比较过，并且待查找字符串是以AB起始这一事实，直接比较原字符串中的C和待查找字符串中的C，避免再次比较AB。

算法步骤：

  1. 计算待查找字符串的next数组，该数组保存了待查找字符串的前缀信息，数组中的数字表示待查找字符串对应下标发生失配时下一次开始比较的位置。
  2. 和Brute force类似的流程比较
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
public int strStr(String haystack, String needle) {
    if(haystack == null || needle == null) return -1;
    if(needle.length() == 0) return 0;
    int[] next = calNext(needle);
    
    int i = 0;
    int j = 0;
    while(i < haystack.length()) {
        if(j == -1 || haystack.charAt(i) == needle.charAt(j)) {
            ++i;
            ++j;
        } else
            j = next[j];
        if(j == needle.length())
            return i - j;
    }
    return -1;
}

private int[] calNext(String s) {
    int[] next = new int[s.length()];
    int i = 0;
    int j = -1;
    next[0] = -1;
    
    while(i < s.length() - 1) {
        if(j == -1 || s.charAt(j) == s.charAt(i)) {
            ++j;
            ++i;
            next[i] = j;
        } else
            j = next[j];
    }
    return next;
}

Boyer-Moore

阅读全文 »

发表于 更新于 分类于 ，

Java Immutable

Java中Immutable对象表示这个对象一旦创建就不能被更改，常用的String、Integer等都是Immutable的，Immutable对象创建后存放在JVM方法区的常量池里，需要用到时只需要一个引用指向它即可，因此Immutable对象具有效率高的优点；同时，Immutable对象可以在多线程环境中保持一致的状态，这一特性可以大大减小并发编程的复杂度。其它线程需要修改这一对象时，只能copy它的副本，新建对象的性能消耗可以被同步机制的简化抵消（与mutable对象上加锁、解锁相比）。

阅读全文 »