位运算

右移 >> 和 >>>

  • >> 是带符号右移，用符号位补位
  • >>> 是不带符号右移，用0补位
1
2
3
4
5
6
7
8
9
//Integer.MIN_VALUE 的十进制和二进制
-2147483648
10000000000000000000000000000000
//Integer.MIN_VALUE >> 1 的十进制和二进制
-1073741824
11000000000000000000000000000000
//Integer.MIN_VALUE >>> 1 的十进制和二进制
1073741824
01000000000000000000000000000000

例1：打印一个数字的32位二进制形式：

1
2
3
for (int i = 31; i >= 0; i--) {
    System.out.print((n & (1 << i)) == 0 ? '0' : '1');
}

例2： Integer.MIN_VALUE，即 -2^31^，它的负数还是它自己。

二进制数的LowBit

X & -X ，即 X & (~X+1) 得到 二进制数的LowBit（其二进制最低位/最右侧的1，其余位均为0）：

-X的值，是在X的基础上进行按位取反之后再加1得到的，

  • 当X为偶数时，~X为奇数，奇数加上1会发生进位，最低位的连续的1都会变为0，所以X和 ~X的低位都为0，高位都相反，只有得到进位的那个位置都为1，即X的最右边的1相等，所以，当一个偶数与它的负值相与时， 结果是能整除这个偶数的最大的2的幂, 即： m = n & -n , 则 n % m = 0, 且 m = 2^k^
  • 当X为奇数时，因为奇数取反后为偶数，偶数加1并不会影响进位，所以此时 X & -X 结果一定为1（奇数最低位的1就在二进制数的末尾）

链表

k个一组翻转链表

leetcode25.

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

例：

1
2
输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

思路：这道题不涉及复杂的算法，但是实现过程中需要考虑的细节比较多，容易写出冗长的代码。主要考查面试者设计的能力。

image-20220609152053978

image-20220609152109809

image-20220609152128213

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
public static ListNode reverseKGroup(ListNode head, int k){
    ListNode start = head;
    ListNode end = getKGroupEnd(start, k);
    if (end == null){
        return head;
    }
    head = end;
    reverse(start, end);
    ListNode lastEnd = start;
    while (lastEnd.next != null){
        start = lastEnd.next;
        end = getKGroupEnd(start, k);
        if (end == null){
            return head;
        }
        reverse(start, end);
        lastEnd.next = end;
        lastEnd = start;
    }
    return head;
}
public static ListNode getKGroupEnd(ListNode start, int k){
    while (--k != 0 && start != null){
        start = start.next;
    }
    return start;
}
public static void reverse(ListNode start, ListNode end){
    end = end.next;
    ListNode pre = null;
    ListNode cur = start;
    ListNode next = null;
    while (cur != end){
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    start.next = end;
}

链表求和

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

1
2
输入：(7->1->6) + (5->9->2)，即617 + 295
输出：2->1->9，即912

假设这些数位是正向存放的，又该如何解决呢? （翻转链表，或使用栈，将数字压入栈中，再依次取出相加）

1
2
输入：(6->1->7) + (2->9->5)，即617 + 295
输出：9->1->2，即912

思路：同时遍历两个链表，逐位相加，并且加上上一位的进位，对于短的链表，可以认为其后是若干0。最后，如果遍历结束后进位不为0，还要再加一个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public ListNode addTwoNumber(ListNode head1,ListNode head2){
    ListNode head = null, tail = null;
    int carry = 0; //表示进位
    while (head1 != null || head2 != null){
        int n1 = head1 != null ? head1.val : 0;
        int n2 = head2 != null ? head2.val : 0;
        int sum = n1 + n2 + carry;  //每一位数都等于两个链表节点的值以及进位的和
        if (head == null){
            head = tail = new ListNode(sum % 10);
        }else{
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        carry = sum / 10;
        if (head1 != null) head1 = head1.next;
        if (head2 != null) head2 = head2.next;
    }
    //链表遍历结束后，如还有进位，则需要再加一个节点
    if (carry > 0) tail.next = new ListNode(carry);
    return head;
}

合并有序链表

合并两个有序链表

leetcode21.

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

1
2
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

思路1：迭代，谁小就指向谁

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode mergeTwoList(ListNode head1, ListNode head2){
    //先建立一个哨兵节点
    ListNode ans = new ListNode(-1);
    ListNode pre = ans;
    while (head1 != null && head2 != null){
        //谁小就指向谁
        if (head1.val <= head2.val){
            pre.next = head1;
            head1 = head1.next;
        }else{
            pre.next = head2;
            head2 = head2.next;
        }
        pre = pre.next;
    }
    //当有一方遍历完，且另一链表剩下部分是有序的，则pre可以直接指向剩下的部分
    pre.next = head1 != null ? head1 : head2;
    return ans.next;
}

思路2：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    } else if (l2 == null) {
        return l1;
    } else if (l1.val < l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

合并有序链表数组

leetcode 剑指offer II 078. 合并排序链表

树

morris遍历

morris遍历二叉树，时间复杂度O(N)，**空间复杂度O(1)**。

遍历过程

设cur为当前节点，一开始cur指向树的根节点，循环执行以下流程：

  1. 如果cur无左树，cur = cur.right；

  2. 如果cur有左树，找到左树最右的节点，记为mostright；

    1. 如果mostright的右指针指向null，使mostright.right = cur，cur = cur.left；

    2. 如果mostright的右指针指向cur，mostright.right = null，cur = cur.right （由于有2.1的操作，所以mostright的右指针可能是指向cur的）

当cur为null时，流程结束。

代码

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 static void morris(Node head) {
     if (head == null) {
         return;
     }
     Node cur = head;
     Node mostRight = null;
     while (cur != null) {
         //看cur是否有左树
         mostRight = cur.left;
         if (mostRight != null) {
             //找cur的左树的最右节点
             while (mostRight.right != null && mostRight.right != cur) {
                 mostRight = mostRight.right;
             }
             //情况2.1
             if (mostRight.right == null) {
                 mostRight.right = cur;
                 cur = cur.left;
             } else {
                 //情况2.2
                 mostRight.right = null;
                 cur = cur.right;
             }
         } else {
             //情况1
             cur = cur.right;
         }
     }
 }

前中后遍历

morris特点：有左树的节点会遍历两次，其他节点均只遍历一次。即符合2.1情况的节点是第一个遍历，符合2.2情况的节点是第二次遍历。

比如，递归遍历二叉树会经过节点三次，在不同的经过时机进行打印，就是前序、中序、后序遍历二叉树。

1
2
3
4
5
6
7
8
9
10
11
//树的x序遍历
void inorder(Node *node){
    if(node == NULL){
        return;
    }
    //前序遍历，即第一次经过
    inorder(node->left);
    //中序遍历，即第二次经过
    inorder(node->right);
    //后序遍历，即第三次经过
}

而morris的遍历时机：

  • 前序遍历：在第一次遍历节点时打印
  • 中序遍历：对于会遍历两次的节点，在其第二次遍历时打印，其他的照常打印。
  • 后序遍历：对于会遍历两次的节点，分别逆序打印其左树的右边界，最后在逆序打印整棵树的右边界(根节点的右边界)（右边界是指这个节点一直向右走下去的路径，包括它自己）
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
public static void morris(Node head) {
    if (head == null) {
        return;
    }
    Node cur = head;
    Node mostRight = null;
    while (cur != null) {
        mostRight = cur.left;
        if (mostRight != null) {
            while (mostRight.right != null && mostRight.right != cur) {
                mostRight = mostRight.right;
            }               
            //情况2.1
            if (mostRight.right == null) {
                //System.out.print(cur.val + " "); //先序遍历
                mostRight.right = cur;
                cur = cur.left;
            } else {
                //情况2.2
                mostRight.right = null;
                //System.out.print(cur.val + " "); //中序遍历
                //printEdge(cur.left);    //后序遍历，打印左树的右边界,
                //注：由于后序遍历是打印节点的右边界，应该在最右节点的右节点为null，不然它的右节点还会指向其他地方，致使多打印
                cur = cur.right;
            }
        } else {
            //情况1
            //System.out.print(cur.val + " "); //先序、中序遍历都要这个打印
            cur = cur.right;
        }
    }
    //printEdge(head);  //后序遍历，打印整个树的右边界(即根节点的右边界)
}
//后序遍历需要：逆序打印节点的右边界
public static void printEdge(Node head){
    Node tail = reverseEdge(head);  //翻转链表
    Node cur = tail;
    while (cur != null){
        System.out.print(cur.val + " ");
        cur = cur.right;
    }
    reverseEdge(tail); //再翻转回来
}
//后序遍历需要：翻转右边界(链表)
public static Node reverseEdge(Node from){
    Node pre = null;
    Node next = null;
    while (from != null){
        next = from.right;
        from.right = pre;
        pre = from;
        from = next;
    }
    return pre;
}

图

数据结构

由于图本身的数据结构表达多种多样，为了不用在和图有关的算法上使用不同种数据结构去实现。所以可以考虑只使用一种兼容性好的结构，用到的时候，将题目中的数据结构转换为常用的这个结构，就不用考虑多种结构的算法实现了。

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
//点
public class Node {
    public int value;
    public int in;  //入读
    public int out; //出度
    public ArrayList<Node> nexts; //点集：直接邻居，从自己出发能到达的第一个节点
    public ArrayList<Edge> edges; //边集：从自己出去的边的集合

    public Node(int value) {
        this.value = value;
        in = 0;
        out = 0;
        nexts = new ArrayList<>();
        edges = new ArrayList<>();
    }
}
//边
public class Edge {
    public int weight;	//权重
    public Node from;
    public Node to;

    public Edge(int weight, Node from, Node to) {
        this.weight = weight;
        this.from = from;
        this.to = to;
    }
}
//图
public class Graph {
    public HashMap<Integer, Node> nodes;
    public HashSet<Edge> edges;

    public Graph() {
        nodes = new HashMap<>();
        edges = new HashSet<>();
    }
}

假设有一个图的数据结构为 [weight，from，to]，则以下是结构的转换过程：

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 static Graph createGraph(Integer[][] matrix){
    Graph graph = new Graph();
    for (int i = 0; i < matrix.length; i++) {
        Integer weight = matrix[i][0];
        Integer from = matrix[i][1];
        Integer to = matrix[i][2];

        //如果点集中没有这个点，就新建一个加进去
        if (!graph.nodes.containsKey(from)){
            graph.nodes.put(from, new Node(from));
        }
        if (!graph.nodes.containsKey(to)){
            graph.nodes.put(from, new Node(to));
        }
        //得到from点和to点
        Node fromNode = graph.nodes.get(from);
        Node toNode = graph.nodes.get(to);
        //建边
        Edge newEdge = new Edge(weight, fromNode, toNode);
        //to点是from点的直接邻居
        fromNode.nexts.add(toNode);
        fromNode.out++;
        toNode.in++;
        //新边是from点的出边
        fromNode.edges.add(newEdge);
        graph.edges.add(newEdge);
    }
    return graph;
}

图的遍历

深度优先遍历DFS和广度优先遍历BFS

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
//从node出发，进行宽度优先遍历
public static void bfs(Node node){
    if (node == null){
        return;
    }
    Queue<Node> queue = new LinkedList<>();
    HashSet<Node> set = new HashSet<>();
    queue.add(node);
    set.add(node);
    while (!queue.isEmpty()){
        Node cur = queue.poll();
        //出队列时打印
        System.out.println(cur.value);
        //将所有没加入过的直接邻居 加入集合和队列中
        for (Node next : cur.nexts){
            if (!set.contains(next)){
                set.add(next);
                queue.add(next);
            }
        }
    }
}
//深度优先遍历
public static void dfs(Node node){
    if (node == null){
        return;
    }
    Stack<Node> stack = new Stack<>();
    HashSet<Node> set = new HashSet<>();
    stack.add(node);
    set.add(node);
    System.out.println(node.value);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        for (Node next : cur.nexts) {
            if (!set.contains(next)) {
                //先将当前元素入栈，再入栈直接邻居，然后beak
                //目的是为了保留元素，以便回来往其他方向深度搜索
                stack.push(cur);
                stack.push(next);
                set.add(next);
                //入栈时打印
                System.out.println(next.value);
                break;
            }
        }
    }
}

拓扑排序

AOV网（Activity On Vertex NetWork）：用顶点表示活动的网。每个AOV网都有一个或多个拓扑排序序列。

AOV网有且仅有一个入度为0的开始点，出度为0的结束点。

拓扑排序：在有向无环图中，找出做事的先后顺序。

规则：

  • 图中每个顶点只出现一次。
  • A在B前面，则不存在B在A前面的路径。(不能成环！！！！)
  • 顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！

使用拓扑排序时，一般是稀疏图，所以用邻接表，

代码思想为：

新建node类，包含节点数值和它的指向；

一个数组包含node(这里默认编号较集中)。初始化，添加每个节点指向的时候同时被指的节点入度+1！(A—>C)那么C的入度+1；
扫描一遍所有node。将所有入度为0的点加入一个栈(队列)。

当栈(队列)不空的时候，抛出其中任意一个node(栈就是尾，队就是头，顺序无所谓，上面分析了只要同时入度为零可以随便选择顺序)。将node输出，并且node指向的所有元素入度减一。如果某个点的入度被减为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
//拓扑排序
public static List<Node> sortedTopology(Graph graph) {
    //key为某个node，value为剩余的入度
    HashMap<Node, Integer> inMap = new HashMap<>();
    Queue<Node> zeroInQueue = new LinkedList<>();
    //记录每个点的入度，并将入度为0的点加入队列
    for (Node node : graph.nodes.values()) {
        inMap.put(node, node.in);
        if (node.in == 0){
            zeroInQueue.add(node);
        }
    }
    //result存放拓扑排序的结果
    List<Node> result = new ArrayList<>();
    while (!zeroInQueue.isEmpty()){
        Node cur = zeroInQueue.poll();
        result.add(cur);
        //遍历cur的直接邻居，使其入度-1，并将入度变为0的节点加入队列
        for (Node next: cur.nexts){
             inMap.put(next, inMap.get(next) - 1);
             if (inMap.get(next) == 0){
                 zeroInQueue.add(next);
             }
        }
    }
    return result;
}

最小生成树

普里姆(prim)算法

（从顶点 考虑）

  1. 选择初始点 把图中的顶点分成两个不同的顶点集S(生成树的顶点集)，V-S
  2. 在横跨两个不同顶点集的边中选择一条权值最小的边加入到生成树中
  3. 将该边的另一个顶点加入到顶点集S中，并从V-S中删除
  4. 重复步骤2，3，知道V-S为空集

image-20220610110015537

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
//prim最小生成树算法
public static Set<Edge> primMST(Graph graph) {
    //解锁的边进入小根堆
    PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new Comparator<Edge>() {
        @Override
        public int compare(Edge o1, Edge o2) {
            return o1.weight - o2.weight;
        }
    });
    HashSet<Node> set = new HashSet<>();
    HashSet<Edge> result = new HashSet<>();
    //外层for循环，是为了预防森林，没有森林的话可以去掉
    for (Node node : graph.nodes.values()) { //随便一个点开始
        //node是开始点
        if (!set.contains(node)) {
            set.add(node);
            priorityQueue.addAll(node.edges); //将开始点的所有边加入最小堆
            while (!priorityQueue.isEmpty()) {
                Edge edge = priorityQueue.poll(); //弹出现有的最小边
                Node toNode = edge.to;  //看to点是否在集合中，不在的话也将它的边加入最小堆
                if (!set.contains(toNode)) {
                    set.add(toNode);
                    result.add(edge);   //加入结果集
                    priorityQueue.addAll(toNode.edges);
                }
            }
        }
    }
    return result;
}

克鲁斯卡尔(kruskal)算法

（从边 考虑）

  1. 把图中的顶点看成n个不同的顶点集，每个顶点集都只含1个顶点
  2. 每次都在横跨不同顶点集的边中选择一条权值最小的边加入到最小生成树中
  3. 直到图中所有的顶点都在同一个顶点集为止

image-20220610110252139

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
public class Kruskal {
    //用并查集实现kruskal算法 
	public static Set<Edge> kruskalMST(Graph graph){
		UnionFind unionFind = new UnionFind();
		unionFind.makeSets(graph.nodes.values());
		// 从小的边到大的边，依次弹出，小根堆！
		PriorityQueue<Edge> priorityQueue = new PriorityQueue<>(new Comparator<Edge>() {
            public int compare(Edge o1, Edge o2) {
                return o1.weight - o2.weight;
            }
        });
		for (Edge edge : graph.edges) { // M 条边
			priorityQueue.add(edge);  // O(logM)
		}
		Set<Edge> result = new HashSet<>();
		while (!priorityQueue.isEmpty()) { // M 条边
			Edge edge = priorityQueue.poll(); // O(logM)
			if (!unionFind.isSameSet(edge.from, edge.to)) { // O(1)
				result.add(edge);
				unionFind.union(edge.from, edge.to);
			}
		}
		return result;
	}
	
	// Union-Find Set，并查集
	public static class UnionFind {
		// key 某一个节点， value key节点往上的节点
		private HashMap<Node, Node> fatherMap;
		// key 某一个集合的代表节点, value key所在集合的节点个数
		private HashMap<Node, Integer> sizeMap;

		public UnionFind() {
			fatherMap = new HashMap<Node, Node>();
			sizeMap = new HashMap<Node, Integer>();
		}
		
		public void makeSets(Collection<Node> nodes) {
			fatherMap.clear();
			sizeMap.clear();
			for (Node node : nodes) {
				fatherMap.put(node, node);
				sizeMap.put(node, 1);
			}
		}
		//找到这个集合的代表
		private Node findFather(Node n) {
			Stack<Node> path = new Stack<>();
			while(n != fatherMap.get(n)) {
				path.add(n);
				n = fatherMap.get(n);
			}
			while(!path.isEmpty()) {
				fatherMap.put(path.pop(), n);
			}
			return n;
		}
		
		//判断两个点是否在同一个集合中
		public boolean isSameSet(Node a, Node b) {
			return findFather(a) == findFather(b);
		}
		
		//将两个点并入同一个集合
		public void union(Node a, Node b) {
			if (a == null || b == null) {
				return;
			}
			Node aDai = findFather(a);
			Node bDai = findFather(b);
			if (aDai != bDai) {
				int aSetSize = sizeMap.get(aDai);
				int bSetSize = sizeMap.get(bDai);
				if (aSetSize <= bSetSize) {
					fatherMap.put(aDai, bDai);
					sizeMap.put(bDai, aSetSize + bSetSize);
					sizeMap.remove(aDai);
				} else {
					fatherMap.put(bDai, aDai);
					sizeMap.put(aDai, aSetSize + bSetSize);
					sizeMap.remove(bDai);
				}
			}
		}
	}
    
}

堆

比较器

1
2
3
4
5
6
new Comparator<T>() {
    @Override
    public int compare(T o1, T o2) {
        return o1.xx - o2.xx;
    }
});

一般会这样规定：

  • 升序：前减后，即 o1 - o2
  • 降序：后减前，即 o2 - o1

或者：

  • 返回负数时，o1排在前；
  • 返回正数时，o2排在前；
  • 返回0时，二者相等；

动态规划

尝试模式(暴力递归)

暴力递归-从左往右的尝试

尝试就是接解题的步骤，也可以说尝试就是暴力递归。

从左往右，就是坐标逐步往后移动，解决问题。

字符串的全部子序列

打印一个字符串的全部子序列

1
2
3
4
5
6
7
8
9
10
11
//例1：打印一个字符串的全部子序列
public static void process1(char[] str, int index, List<String> ans, String path) {
	if (index == str.length) {
		ans.add(path);
		return;
	}
	String no = path;
	process1(str,  index + 1, ans, no);
	String yes = path + String.valueOf(str[index]);
	process1(str, index + 1, ans, yes);
}

字符串的全排列

打印一个字符串的全排列。

1
2
3
4
5
6
7
8
9
10
11
public static void process2(char[] str, int i, ArrayList<String> res) {
       //在终止位置加入
	if (i == str.length) {
		res.add(String.valueOf(str));
	}
	for (int j = i; j < str.length; j++) {
		swap(str, i, j);
		process2(str, i+1,res);
		swap(str, i, j);
	}
}

打印一个字符串的全排列，要求不要出现重复的排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void process3(char[] str, int i, ArrayList<String> res) {
	if (i == str.length) {
		res.add(String.valueOf(str));
	}
       //用于判断本次循环中是否出现了重复字母，即这个字母的情况已经罗列过了，可以剪枝掉
	boolean[] visit = new boolean[26];
	for (int j = i; j < str.length; j++) {
		if (!visit[str[i] - 'a']) {
			visit[str[i] - 'a'] = true;
			swap(str, i, j);
			process2(str, i+1,res);
			swap(str, i, j);
		}
	}
}

数字转化字母

（facebook面试题）

规定1和A对应、2和B对应、3和C对应……那么一个数字字符串比如”111”就可以转化为： “AAA”、”KA”和”AK”；
给定一个只有数字字符组成的字符串str, 返回有多少转化结果；

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
//di'gui
	//i之前的位置，如何转化已经做过决定，不用再关心
	public static int process4(char[] str, int i) {
		if (i == str.length) {
			return 1;
		}
		if (str[i] == '0') {	//单独的‘0’是无效的，0只能和10和20在一起才有效
			return 0;
		}
		//字母最多到26，所以要考虑十几和二十几的情况
		if (str[i] == '1') {
			int res = process4(str,  i + 1);  //i自己作为单独的数，后续有多少种方案
			if (i + 1 < str.length) {
				res += process4(str, i + 2);  //i和i+1作为一个二位数，后续有多少种方案
			}
			return res;
		}
		if (str[i] == '2') {
			int res = process4(str,  i + 1);	//i自己作为单独的数，后续有多少种方案
			//i和i+1这个数，不能超过26
			if (i + 1 < str.length && (str[i+1] >= '0' && str[i+1] <= '6')) {
				res += process4(str, i + 2); //i和i+1作为一个二位数，后续有多少种方案
			}
			return res;
		}
		//str[i] == '3' ~ '9'
		return process4(str, i + 1);
	}

拿纸牌

给定一个整型数组ar,代表数值不同的纸牌排成一条线，玩家A和玩家B依次拿走每张纸牌，规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或最右的纸牌，玩家A和玩家B都绝顶聪明。

请返回最后获胜者的分数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//拿牌比最后总大小
public static int win1(int[] arr) {
	if (arr== null || arr.length == 0) {
		return 0;
	}
	return Math.max(f(arr, 0, arr.length-1), s(arr, 0, arr.length - 1));
}
//拿牌
public static int f(int[] arr, int l, int r) {
	if (l == r) {
		return arr[l];
	}
	return Math.max(arr[l] + s(arr, l+1, r), arr[r] + s(arr, l, r-1));
}
//s是对方给自己的后续牌堆，一定是后续总共能拿到的最小值
public static int s(int[] arr, int i, int j) {
	if (i == j) {
		return 0;
	}
	return Math.min(f(arr, i+1, j), f(arr, i, j-1));
	
}

n皇后

N皇后问题是指在N*N的棋盘上要摆N个皇后，要求任何两个皇后不同行、不同列，也不在同一条斜线上。

给定一个整数n，返回n皇后的摆法有多少种。

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
//n皇后问题
//摆放第i行的皇后，一共有n行
public static int nQueen(int i, int[] record, int n) {
	if (i == n) {
		return 1;
	}
	int res = 0;
	for (int j = 0; j < n; j++) {
		if (isValid(record,i, j)) {
			record[i] = j;
			res += nQueen(i+1, record, n);
		}
	}
	return res;	
}
//返回皇后能不能放在第i行，j列
public static boolean isValid(int[] record, int i, int j) {
	for (int k = 0; k < i; k++) {
		//record[k]指之前皇后所摆的列数，
		//设两点(a,b)和(c,d)，如果两点共斜线，则满足|b-d|==|a-c|
		if (j == record[k] || Math.abs(record[k] - j) ==  Math.abs(i - k)) {
			return false;
		}
	}
	return true;
}

n皇后的位运算优化，优化常数操作

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
//使用一个n位的二进制数表示n皇后，但不要超过32皇后问题
public static int nQueen2(int n) {
	if (n < 1 || n > 32) {
		return 0;
	}
	//假如是9皇后, limit最右9个1, 其他都是0
	int limit = n == 32 ? -1 : (1 << n) - 1;
	return nq2(limit, 0, 0, 0);
}
//limit是问题的规模，即n皇后，值固定
//colLim是列限制，规定那一列不能放皇后。1不能放，0能放
//leftDiaLim是左斜线限制
//rightDiaLim是右斜线限制
public static int nq2(
		int limit, int colLim, 
		int leftDiaLim, int rightDiaLim) {
	if(colLim == limit) {	//base case
		return 1;
	}
	//所有候选皇后的位置，都在pos上，1能放皇后
	//先"或"运算得到总限制，取反，则1能放皇后，最后和limit进行"与"运算，剔除超出棋盘范围的1
	int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
	int mostRightOne = 0;
	int res = 0;
	while (pos != 0) {
		//取pos最右侧的1，其余是0
		mostRightOne = pos & (~pos + 1);
		//将取过的1减掉，即变为0
		pos = pos - mostRightOne;
		res += nq2(limit, 
				//列限制"或"上当前放皇后位置的1，即新的列限制
				colLim | mostRightOne, 
				//左斜线限制"或"上当前放皇后位置的1，再左移1位，即新的左斜线限制
				(leftDiaLim | mostRightOne) << 1,
				(rightDiaLim | mostRightOne) >>> 1);
	}
	return res;
}

//比较使用位运算优化前后的耗时
public static void main(String[] args) {
	int n = 13;
       
	//普通暴力递归 耗时
	int[] record1 = new int[n];
	long start = System.currentTimeMillis();
	System.out.println(nQueen(0, record1, n));
	long end = System.currentTimeMillis();
	System.out.println("cost time： " + (end -start) + "ms");
	//位运算优化常数操作 耗时
	int[] record2 = new int[n];
	long start2 = System.currentTimeMillis();
	System.out.println(nQueen2(n));
	long end2 = System.currentTimeMillis();
	System.out.println("cost time： " + (end2 -start2) + "ms");
}

范围上的尝试

多样本位置全对应的尝试

寻找业务限制的尝试

动态规划

例1：

假设有排成一行的N个位置，记为1 ~ N, N一定大于或等于2；

开始时机器人在其中的M位置上(M一定是1 ~ N中的一个)；机器人可以在 1 ~ N 范围内行动；规定机器人必须走K步，最终能来到P位置(P也是1~N中的一个) 的方法有多少种？ 给定四个参数N、M、K、P, 返回方法数。

JAVA方法

Math.random

Math.random会等概率地返回Double类型的 [0, 1) 的随机数，应用：

  • 随机返回 [0, k) 的数： Math.random() * k

  • 随机返回 [0, k] 的整数： (int) Math.random() * (k+1)

  • 设x属于 [0, 1) ，原本 x 在[0, x) 上出现的概率是 x，如果要将出现的概率改为 x^2^ ： 

    1
    Math.max(Math.random(), Math.random())

1-5随机到1-7随机

例1：设有一个方法f1()，它等概率返回 [1,5]，现要求将其改成等概率返回 [1,7] 的方法：

思路：先将f1改成 01等概率方法f2，则f2可以表示一位二进制位，已知三个二进制位可表示 [0,7]，所以利用位运算可以得到一个等概率的3位二进制数，再将等于0的机会均分给其他的数即可。

改造成01等概率，有奇数个则将某个数的概率均分给其他数，有偶数个直接平分即可。

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
    //f1()功能：随机返回 [1,5]
    public static int f1() {
        return (int) (Math.random() * 5) + 1;
    }

    //f2()功能：将f1()改造成随机返回 0、1
    public static int f2() {
        int ans;
        do {
            ans = f1();
        } while (ans == 3);
        //将等于3的概率均分给1245
        //当f()为12时返回0， 为45时返回1
        return ans < 3 ? 0 : 1;
    }

    //f3()功能：将f2的结果作为一个二进制位，三位即可返回[0,7]，再将等于0的概率均分给其他数，即可等概率得到[1，7]
    public static int f3() {
        int ans;
        do {
            ans = (f2() << 2) + (f2() << 1) + f2();
        } while (ans == 0);
        return ans;
    }
//f3也可以先等到[0,6]，再+1

01不等概率到01等概率

例2：设方法f1()返回0的概率是p，返回1的概率是1- p，只使用f1()，写出能等概率返回01的方法。

思路：调用俩次f1，组成一个二位的二进制数，则01和10的概率均为 p(1- p)，而00概率p^2^，11概率(1- p)^2^。所以取01和10作为 0和1返回，00和11直接舍去。

1
2
3
4
5
6
7
8
9
10
11
12
13
//01不等概率
   public static int f1(){
       return Math.random() > 0.7 ? 1 : 0;
   }
   //01等概率
   public static int f2(){
       int ans;
       do{
           ans = f1();
       }while (ans == f1());
       //f1调用两次，当第一次等于第二次时，重新选值。
       return ans;
   }

对数器

对数器：有一个能随机生成符合要求的数组的方法，一个用于复制的方法，一个验证正误的方法；

在比赛中，一般只会给出一两道简单的例子，不能验证算法是否正确，所以就可以用对数器进行大量例子验证。

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
//返回一个值和长度都随机的数组
   public static int[] lenAndValueRandom(int maxLen, int maxValue) {
       int len = (int) (Math.random() + maxLen);  //长度随机，范围在[0, maxLen-1]
       int[] ans = new int[len];
       for (int i = 0; i < len; i++) {
           ans[i] = (int) (Math.random() * maxValue);  //值随机，范围在[0,maxValue-1]
       }
       return ans;
   }

   //复制一份，用于出错后比较
   public static int[] copy(int[] arr) {
       int[] ans = new int[arr.length];
       for (int i = 0; i < arr.length; i++) {
           ans[i] = arr[i];
       }
       return ans;
   }

   //判断使用了算法的数组是否达到预期要求
   public static boolean judge(int[] arr){
       //具体内容根据题目要求而定
       return true;
   }

   //写出来的算法，需要验证
   public static void algorithm1(int[] arr){

   }

   public static void main(String[] args) {
       int maxLen = 5;
       int maxValue = 1000;
       int testTime = 10000; //测试次数
       for (int i = 0; i < testTime; i++) {
           int[] arr1 = lenAndValueRandom(maxLen, maxValue);
           int[] arr2 = copy(arr1);
           //当算法不符合要求时，根据情况进行打印，可以方便分析
           if (!judge(arr1)){
               System.out.println("算法出错了");
               for (int k : arr2) {
                   System.out.print(k + " ");
               }
               for (int k : arr1) {
                   System.out.print(k + " ");
               }
           }
       }
   }

动态数组

动态数组每次容量不够时，ArrayList会扩容至1.5倍，而Vector容量会扩至2倍，并将旧数据拷贝进去；不管是ArrayList还是Vector，多次扩容的时间代价是一个等比数列，所以扩容的时间复杂度是O(N)，当每一步扩容均摊到算法计算过程中，可以当作常数操作，所以使用动态数组不影响时间复杂度。