发表于   |   分类于   |  

参考了Core Java卷一的第十三章 - 集合

一些常用的集合接口和类

Collection

　　集合类的基本接口就是Collection接口，有两个基本方法

1
2
3
4
5
public interface Collection<E> {
  boolean add(E element);
  Iterator<E> iterator();
  .....
}

　　iterator接口返回一个实现Iteator接口的对象，也就是一个迭代器，Iterator接口，注意没有add方法

1
2
3
4
5
public interface Iterator<E> {
  E next();
  boolean hasNext();
  void remove();
}

　　for each循环可以与任何实现Iterable接口的对象一起工作，Iterable接口：

1
2
3
public interface Iterable<E> {
  Iterator<E> iterator();
}

　　因此Collection接口拓展了Iterable接口，关于Iterator和Iterable的区别可以看看 stackoverflow上的一个回答

　　Iterator的remove方法将删除上次调用next方法返回的元素，例如：

1
2
3
Iterator<String> it = c.iterator();
String element = it.next();
it.remove();//删除了element

　　remove方法调用之前没有next方法调用被认为是不合法的。

阅读全文 »

发表于   |   分类于   |  

参考 http://kubernetes.io/docs/api-reference/extensions/v1beta1/definitions/#_v1beta1_labelselector

　　Deployment LabelSelector分为两种，matchLabels和matchExpressions

matchLabels

　　一组{key,pair}的map形式，如

1
2
3
matchLabels:
  a: b
  c: d

　　就是代表有两个标签，a和c，值分别是b和d

matchExpressions

　　一组label selector，如

1
2
matchExpressions:
  - {key: a, operator: In, values: [b]}

　　代表标签为a，值为b，操作符是In代表“或”运算，operator共有四种In,NotIn（不属于）, Exists （存在一个条件）andDoesNotExist（不存在）.

　　值得注意的是，在deployment的yaml文件中，matchLabels和matchExpressions可以同时存在，并且是AND的关系

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/wiggle-subsequence/

　　给你一个数组，让你找出一个满足这样性质的最长子序列，子序列中元素总是相邻元素高地起伏，画成曲线呈现严格锯齿状。

题目分析

　　本题将数组化成直方图以后，实际上是找每个局部的极值点，根据数学知识，离散的局部极值点是左右差值异号的，比如a，b，c三点，b是局部极值点，那么(a - b) * (b - c) < 0，但一些特殊情况要考虑，比如最开始是平的，突然上升或者下降

阅读全文 »

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/house-robber-iii/

　　一个强盗可以对一棵树上从根节点至下对每个节点进行rob，要求相邻两个节点不能rob。

题目分析

　　这个题接续house robber i和house robber ii。但更为复杂的是，这次是一棵树，实质上还是进行先搜索，再进行记忆化，搜索就是基于穷举法，每次遇到一个节点，选择是留还是弃。留的话，那么下次的搜索只能从当前结点的儿子节点的儿子节点开始搜索。弃的话，下次搜索的起点是儿子节点。在此基础上，加上记录，但这次记录的不是数字了，而是TreeNode节点，可以利用Map<TreeNode, Integer>存储。

代码

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    private Map<TreeNode, Integer> cache;
    private int search(TreeNode cur) {
        if(cur == null) {
            return 0;
        }
        if(cache.containsKey(cur)) {
            return cache.get(cur);
        }
        //留当前结点
        int v1 = 0, v2 = 0, v3 = 0, v4 = 0;
        if(cur.left != null) {
            v1 = search(cur.left.left);
            v2 = search(cur.left.right);
        }
        if(cur.right != null) {
            v3 = search(cur.right.left);
            v4 = search(cur.right.right);
        }
        int max = cur.val + v1 + v2 + v3 + v4;
        //弃当前结点
        int v5 = 0, v6 = 0;
        v5 = search(cur.left);
        v6 = search(cur.right);
        max = Math.max(max, v5 + v6);
        cache.put(cur, new Integer(max));
        return max;
    }
    
    public int rob(TreeNode root) {
        cache = new HashMap<TreeNode, Integer>();
        return search(root);
    }
}

　　时间复杂度就是树的节点数。