题目：给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

思路：和二叉树的层序遍历相似，只需将每一层最右边的节点值加入到结果list周=中即可

二叉树的层序遍历使用bfs来完成，用一个变量q_count来记录当前Queue的size,遍历本层的所有节点，找出下一层放进Queue里，当index为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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> que = new LinkedList<>();
        // res.add(root);
        if(root == null) return res;
        que.add(root);
        
        while(!que.isEmpty()){
            int q_count = que.size();
            while(q_count > 0){
                if(q_count == 1){
                    res.add(que.peek().val);
                }
                TreeNode node = que.poll();
                if(node.left != null){
                    que.add(node.left);
                }
                if(node.right != null){
                    que.add(node.right);
                }
                q_count--;
                
            }
        }
        return res;
        
    }
}

题目：

编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。
如果 n 是快乐数就返回 True ；不是，则返回 False 。

思路： 检测重复使用hashset

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

class Solution {
    public boolean isHappy(int n) {
        HashSet<Integer> myset = new HashSet<>();
        myset.add(n);
        while(n!=1){
            // System.out.println(n);
            n = next(n);
            if(myset.contains(n)){
                return false;
            }
            myset.add(n);
        }
        return true;

    }

    public int next(int n){
        int res=0;
        while(n!=0){
            res += (n%10)*(n%10);
            n = n/10;
        }
        return res;
    }
}

合并k个长度为n的有序链表

方法一

依次合并k个链表，时间复杂度：O(k*k*n)

方法二

分治法

方法三

最小堆法

维护一个大小为k的最小堆，每次取对顶元素加入到结果链表后面，并将将元素的下一个点加入到最小堆中，当堆为空时返回结果。

* 注意：kava中使用PriorityQueue实现最小堆的功能，默认是最小堆，若要实现最大堆需重载compare方法，可使用匿名函数(o1,o2)->Integer.compare(o2,o1)*

回溯个人感觉和dfs加visited数组差不多，

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

public class Main{
    List<List<Integer>> res = new LinkedList<>();
    public List<List<Integer>> permute(int[] nums){
        LinkedList<Integer> track = new LinkedList<>();
        backTrack(track, nums);
        return res;
    }
    public void backTrack(LinkedList<Integer> track, int[] nums){
        if(track.size() == nums.length){
            res.add(new LinkedList(track));
            return;
        }

        for(int i=0; i<nums.length; ++i){
            if(track.contains(nums[i])) continue;
            track.add(nums[i]);
            backTrack(track, nums);
            track.removeLast();
        }
    }
    public static void main(String[] args) {
        Main m = new Main();
        m.test();


    }

    public void test(){
        permute(new int[]{1,2,3,4,5});
        for(List<Integer> list : res){
            for(Integer v : list){
                System.out.print(v+" ");
            }
            System.out.println();
        }
    }
}

用证书的公钥去解密证书的签名并将其与证书的MD5摘要进行对比查看是否一致

HTTPS工作原理

1. 首先HTTP请求服务端生成证书，客户端对证书的有效期、合法性、域名是否与请求的域名一致、证书的公钥（RSA加密）等进行校验；
2. 客户端如果校验通过后，就根据证书的公钥的有效， 生成随机数，随机数使用公钥进行加密（RSA加密）；
3. 消息体产生的后，对它的摘要进行MD5（或者SHA1）算法加密，此时就得到了RSA签名；
4. 发送给服务端，此时只有服务端（RSA私钥）能解密。
5. 解密得到的随机数，再用AES加密，作为密钥（此时的密钥只有客户端和服务端知道）。
   偷个图
   

首先来说一下URI 、URL、URN的区别

• URI是统一资源标识符（Uniform Resource Identifier）
• URL是统一资源定位符（Uniform Resource Locator）
• URN是统一资源命名（Uniform Resource Name）

URL和URN属于URI，也就是说URL和URN是URI的子集。打个比方，你的身份证号就是URN，可以唯一表示你这个人；URL是你的住址，可以通过住址找到你这个人；

网址http://www.baidu.com属于URL

Java 包(package)

为了更好地组织类，Java 提供了包机制，用于区别类名的命名空间。

包的作用

1. 把功能相似或相关的类或接口组织在同一个包中，方便类的查找和使用。

2. 如同文件夹一样，包也采用了树形目录的存储方式。同一个包中的类名字是不同的，不同的包中的类的名字是可以相同的，当同时调用两个不同包中相同类名的类时，应该加上包名加以区别。因此，包可以避免名字冲突。

3. 包也限定了访问权限，拥有包访问权限的类才能访问某个包中的类。

Java 使用包（package）这种机制是为了防止命名冲突，访问控制，提供搜索和定位类（class）、接口、枚举（enumerations）和注释（annotation）等。

默认包/缺省包（default package）

• 这里默认包的意思是指没有写package的java类文件所在的包。
• 因为默认包的类没有包名, 在被有包结构的类引用时，会被当成本包内的类。即编译器会在comm包下查找helloworld类，自然是找不到的。而由于没有包名，也无法使用import导入。
• 同一个包下的类文件之间不用写import语句也能成功调用。
• 不在同一个包下的类需要通过import导入后才能调用。

ClassLoder

JVM的机制是自上而下加载，自下而上检查

最开始是由BootStrap ClassLoader加载rt.jar下的文件，也就是java最最核心的部分；然后由Extension ClassLoader加载ext下的文件；再有App ClassLoader加载用户自己的文件。

由于BootStrap ClassLoader是用c++写的，所以在返回该ClassLoader时会返回null。显然，Class为java.lang.Class，是rt.jar中的，由BootStrap ClassLoader加载，所以返回null

类加载器也是Java类，因为Java类的类加载器本身也是要被类加载器加载的，显然必须有第一个类加载器不是Java类，这个正是BootStrap,使用C/C++代码写的，已经封装到JVM内核中了，而ExtClassLoader和AppClassLoader是Java类。

双亲委托机制的类加载方式

如果自己写一个java.lang.String类, 用AppClassLoader去加载的话，根据双亲委托机制，最终会加载到rt.jar里面的java.lang.String类，自己写的这个java.lang.String类根本不会被加载；如果自己写一个ClassLoader去特意加载自己写的java.lang.String类的话，也不会成功，因为AppClassLoader会拒绝加载java.开头的类，在preDefineClass中可以看到

if ((name != null) && name.startsWith("java.")) {
        throw new SecurityException
            ("Prohibited package name: " +
             name.substring(0, name.lastIndexOf('.')));
    }