Index
0%

Posted on Edited on

译自Spring Cloud Document

7.7 Feign的继承支持

Feign通过单继承接口支持模板apis。这样可以把常用操作通过接口进行分组。

UserService.java.
1
2
3
4
5
public interface UserService {

    @RequestMapping(method = RequestMethod.GET, value ="/users/{id}")
    User getUser(@PathVariable("id") long id);
}
UserResource.java.
1
2
3
4
@RestController
public class UserResource implements UserService {

}
UserClient.java.
1
2
3
4
5
6
package project.user;

@FeignClient("users")
public interface UserClient extends UserService {

}

通常不建议在服务器和客户端之间共享接口（Java Interface）。这是一种紧耦合，而且这样也无法使用Spring MVC（方法中的参数映射不会被继承）。

Posted on Edited on

简述

快速排序使用分治理念，将目标数组每次划分为左右两个区间分而治之。因而他也是一种不稳定排序算法，最坏情况下，每次选择的基准都是分区内最小或最大数，造成左/右分区为空，这种情况下，时间复杂度与冒泡排序相同，等于O(n^2)

Talk is cheap, show me the 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
42
43
44
45
46
47
48
49
50
51
52
53
public class QuickSort {

    /**
     * a[]   目标数组
     * low   低位
     * hight 高位
     **/ 
    public static void sort(int a[], int low, int hight) {
        int i, j, index;
        if (low > hight) {
            return;
        }
        //左分区起始位
        i = low;
        //右分区结束位
        j = hight;
        // 用子表的第一个记录做基准
        index = a[i];
        // 从表的两端交替向中间扫描
        while (i < j) { 
            //先从高位向低位扫描
            while (i < j && a[j] >= index)
                j--;
            if (i < j)
                //用比基准小的记录替换低位记录
                a[i++] = a[j];
            //再从低位向高位扫描
            while (i < j && a[i] < index)
                i++;
            if (i < j)
                // 用比基准大的记录替换高位记录
                a[j--] = a[i];
        }
        // 将基准数值替换回 a[i]
        a[i] = index;
        //继续分区
        sort(a, low, i - 1); // 对低子表进行递归排序
        sort(a, i + 1, hight); // 对高子表进行递归排序
 
    }
 
    public static void quickSort(int a[]) {
        sort(a, 0, a.length - 1);
    }
 
    public static void main(String[] args) {
 
        int a[] = { 48, 38, 69, 97, 76, 13, 37, 48 };
        quickSort(a);
        System.out.println(Arrays.toString(a));
        
    }
}

Posted on Edited on

最近在刷题的时候遇到了字典树，字典树又称单词查找树。顾名思义，主要应用于字符串存储和检索，可以便捷的使用公共前缀实现字符串快速检，所以经常被搜索引擎系统用于文本词频统计。其主要思想还是空间换时间。时间复杂度等于O(树高)。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

性质：

  • 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  • 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  • 每个节点的所有子节点包含的字符都不相同。

搜索过程：

  1. 从根结点开始一次搜索。
  2. 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索。
  3. 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
  4. 迭代过程…
  5. 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

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
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
//首先假设节点上的字符为a-z
public class Trie {
    private int SIZE=26;
    private TrieNode root;//字典树的根
 
    //初始化字典树
    Trie() {
        root = new TrieNode();
    }
 
    //字典树节点
    private class TrieNode {
        private int num;//有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
        private TrieNode[] son;//所有的子节点
        private boolean isEnd;//是不是最后一个节点
        private char val;//节点的值
 
        TrieNode() {
            num = 1;
            son = new TrieNode[SIZE];
            isEnd = false;
        }
    }
    
    //在字典树中插入一个单词
    public void insert(String str) {
        if(str==null||str.length()==0) {
            return;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(int i=0,len=str.length(); i<len; i++) {
            int pos=letters[i]-'a';
            if(node.son[pos]==null) {
                node.son[pos]=newTrieNode();
                node.son[pos].val=letters[i];
            } else {
                node.son[pos].num++;
            }
            node=node.son[pos];
        }
        node.isEnd=true;
    }
 
    //计算单词前缀的数量
    public int countPrefix(Stringprefix) {
        if(prefix==null||prefix.length()==0) {
            return-1;
        }
        TrieNode node=root;
        char[]letters=prefix.toCharArray();
        for(inti=0,len=prefix.length(); i<len; i++) {
            int pos=letters[i]-'a';
            if(node.son[pos]==null) {
                return 0;
            } else {
                node=node.son[pos];
            }
        }
        return node.num;
    }
    //打印指定前缀的单词
    public String hasPrefix(String prefix) {
        if (prefix == null || prefix.length() == 0) {
            return null;
        }
        TrieNode node = root;
        char[] letters = prefix.toCharArray();
        for (int i = 0, len = prefix.length(); i < len; i++) {
            int pos = letters[i] - 'a';
            if (node.son[pos] == null) {
                return null;
            } else {
                node = node.son[pos];
            }
        }
        preTraverse(node, prefix);
        return "";
    }
    // 遍历经过此节点的单词.
    public void preTraverse(TrieNode node, String prefix) {
        if (!node.isEnd) {
            for (TrieNode child : node.son) {
                if (child!=null) {
                    preTraverse(child, prefix+child.val);
                }
            }
            return;
        }
        System.out.println(prefix);
    }
 
 
    //在字典树中查找一个完全匹配的单词.
    public boolean has(Stringstr) {
        if(str==null||str.length()==0) {
            return false;
        }
        TrieNode node=root;
        char[]letters=str.toCharArray();
        for(inti=0,len=str.length(); i<len; i++) {
            intpos=letters[i]-'a';
            if(node.son[pos]!=null) {
                node=node.son[pos];
            } else {
                return false;
            }
        }
        return node.isEnd;
    }
 
    //前序遍历字典树.
    public void preTraverse(TrieNodenode) {
        if(node!=null){
            System.out.print(node.val+"-");
            for(TrieNodechild:node.son) {
                preTraverse(child);
            }
        }
    }
 
    public TrieNode getRoot() {
        return this.root;
    }
}