发表于   |   分类于   |  

有关C++ STL的set和unordered_set翻译了:

http://www.cplusplus.com/reference/set/set/

http://www.cplusplus.com/reference/unordered_set/unordered_set/?kw=unordered_set　　　　

　　

Set

　　set内部元素总是排好序的，依据一种内部的排序对象Compare的严格的弱序化规则排序。有关weak ordering的更多解释看这里：https://en.wikipedia.org/wiki/Weak_ordering

set内部元素总是排好序的，依据一种内部的排序对象Compare的严格的弱序化规则排序。有关weak ordering的更多解释看这里：https://en.wikipedia.org/wiki/Weak_ordering

　　set容器根据key获取元素的时间效率上不如unordered_set,but they allow the direct iteration on subsets based on their order.

　　set的通常实现是二叉查找树。

unordered_set

　　unordered_set存储无序的，不重复元素的容器。

　　在unordered_set中，元素value跟key相同，能够唯一标识一个元素。key是不可变的，因此元素是不能变的，但是它们可以被插入或者删除。

　　unordered_set内部的值不是排好序的，而是根据哈希值被组织到buckets中，这样做可以根据它们你的值快速获取单个元素，平均时间复杂度是O(1)的。

　　unordered_set比set通过key获取元素更快，尽管要通过元素的子集进行范围迭代不是很高效。

　　unordered_set的迭代器模式至少是forward iterators，有关forward iterators http://www.cplusplus.com/reference/iterator/ForwardIterator/

发表于   |   分类于   |  

题目大意

　　http://www.lintcode.com/problem/sort-integers

　　整数排序，这里用堆排序实现。

题目分析

　　使用最大堆，堆排序的思路是按照算法导论中的思路。写了三个方法，第一个是heapify方法，作用是堆化，调用这个方法的前提是，节点i的左右子树都是堆。第二个方法是构建最大堆，从最后一个不是叶子节点开始往前遍历，逐步堆化，最后整棵树就是堆了。第三个方法就是堆排序了。首先先构建最大堆，构建完之后，树根一定是最大的元素，将树根与最后一个元素交换，然后堆的大小减一（最后一个元素不考虑了），然后调用堆化方法，这样树根又成了最大元素，之后再与最后一个元素交换，如此反复。

代码

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
public class Solution {
    
    private void heapify(int[] A, int i, int len) {
    	int left = 2 * i + 1;
    	int right = 2 * i + 2;
    	int largest = i;
    	if(left < len && A[i] < A[left]) {
    		largest = left;
    	}
    	if(right < len && A[largest] < A[right]) {
    		largest = right;
    	}
    	if(largest != i) {
    		int temp = A[i];
    		A[i] = A[largest];
    		A[largest] = temp;
    		heapify(A, largest, len);
    	}
    }
    
    private void buildMaxHeap(int[] A, int len) {
    	for(int i = len / 2; i >= 0; i--) {
    		heapify(A, i, len);
    	}
    }
    
    private void heapSort(int[] A) {
    	int len = A.length;
    	buildMaxHeap(A, len);
    	for(int i = len - 1; i >= 1; i--) {
    		int temp = A[0];
    		A[0] = A[i];
    		A[i] = temp;
    		heapify(A, 0, i);
    	}
    }
    
    public void sortIntegers(int[] A) {
    	heapSort(A);
    }
}

时间复杂度O(n*logn)

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/kth-smallest-element-in-a-bst/

　　给你一棵二叉查找树，输出第k小的元素

题目分析

　　中序遍历输出第k个元素即可。但这个题目还有扩展，当二叉树节点频繁增加删除时，还用这一思路复杂度高。因此如果可以更改数据结构的话，加个域，代表左边子树的节点个数，这样就可以在遍历每个节点时，就可以按照k和左边子树节点个数关系进行分路，复杂度会降到O(height of 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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    
    private static int num = 0;
    private static int res;
    
    private void inOrder(TreeNode root, int k) {
        if(root == null) {
            return ;
        }
        if(num >= k) {
            return ;
        }
        inOrder(root.left, k);
        num++;
        if(num == k) {
            res = root.val;
            return ;
        }
        inOrder(root.right, k);
    }
    
    public int kthSmallest(TreeNode root, int k) {
        num = 0;
        inOrder(root, k);
        return res;
    }
}

发表于   |  

纯粹自己写着玩儿的。。。记性不好，怕以后忘了

随时不断补充……………………………………..

用\转义

1
1986\. What a great season.

\1986. What a great season.

直接 1986. 会被Markdown认为是列表

代码样式（直接tab或者4个空格）

1
2
3
4
int main(){
    printf("Hello,World\n");
    return 0;
}

行内代码直接用反撇号``包起来，如：

Use the printf() function.

效果：Use the printf() function.

链接标题

1
This is [an example](http://example.com/ "Title") inline link.

This is an example inline link.

参考式链接

1
2
3
4
5
6
I get 10 times more traffic from [Google] [1] than from
[Yahoo] [2] or [MSN] [3].
  [1]: http://google.com/        "Google"
  [2]: http://search.yahoo.com/  "Yahoo Search"
  [3]: http://search.msn.com/    "MSN Search"

I get 10 times more traffic from Google than from
Yahoo or MSN.

1
2
[Google][]  省略的写法
[Google]: https://www.google.com.hk/

Google

如果链接文字跟链接相同，还可以这样：

1
<http://example.com/>

效果： http://example.com/