剑指 Offer 56 - I. 数组中数字出现的次数

题目　　

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

输入：nums = [1,2,10,4,1,4,3,3] 输出：[2,10] 或 [10,2]

思路：

其他数字出现两次，只有两个数字出现一次，很自然地想到两个相同的数字异或为0，记两个数字为a和b，可以通过这个方法抵消两个相同数字，整个数组全部异或的结果就是两个只出现一次的数字异或的结果a^b，我们需要分别列出a和b，那么显然还缺乏一个信息。官方题解的思路是分组异或，理解后确实觉得很妙。
首先我们找到a^b最后一个1，也a和b最低位不同的数字。之后我们将这一位不同的数字单独异或，两组答案就分别是a和b了（相同的数字必在同一组）。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int ret = 0;
        for(int num:nums){
            ret^=num;
        }
        ret = ret^(ret&(ret-1));    //得到最后一位1的数
        int a = 0, b = 0;
        for(int num:nums){
            if(ret&num){
                a^=num;
            }else{
                b^=num;
            }
        }
        return {a,b};
    }
};

133. 克隆图

题目　　

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

思路：

方法一：DFS

对于本题而言，我们需要明确图的深拷贝是在做什么，对于一张图而言，它的深拷贝即构建一张与原图结构，值均一样的图，但是其中的节点不再是原来图节点的引用。因此，为了深拷贝出整张图，我们需要知道整张图的结构以及对应节点的值。　　 由于题目只给了我们一个节点的引用，因此为了知道整张图的结构以及对应节点的值，我们需要从给定的节点出发，进行图的遍历，并在遍历的过程中完成图的深拷贝。

为了防止多次遍历同一个节点，陷入死循环，我们需要用一种数据结构记录已经被克隆过的节点。
从给定节点开始遍历图。如果某个节点已经被访问过，则返回其克隆图中的对应节点。

如果当前访问的节点不在哈希表中，则创建它的克隆节点并存储在哈希表中。注意：在进入递归之前，必须先创建克隆节点并保存在哈希表中。如果不保证这种顺序，可能会在递归中再次遇到同一个节点，再次遍历该节点时，陷入死循环。

class Solution {
public:
    unordered_map<Node*, Node*> visited;
    Node* cloneGraph(Node* node) {
        if (node == nullptr) {
            return node;
        }

        // 如果该节点已经被访问过了，则直接从哈希表中取出对应的克隆节点返回
        if (visited.find(node) != visited.end()) {
            return visited[node];
        }

        // 克隆节点，注意到为了深拷贝我们不会克隆它的邻居的列表
        Node* cloneNode = new Node(node->val);
        // 哈希表存储
        visited[node] = cloneNode;

        // 遍历该节点的邻居并更新克隆节点的邻居列表
        for (auto& neighbor: node->neighbors) {
            cloneNode->neighbors.emplace_back(cloneGraph(neighbor));
        }
        return cloneNode;
    }
};

方法二：BFS

要使用BFS，需要使用一个队列，保存接下来需要访问的节点，注意队列中每次取出的节点一定会给他加上所有的邻居（访问过的直接加入，没有的递归加入）。

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (node == nullptr) {
            return node;
        }

        unordered_map<Node*, Node*> visited;

        // 将题目给定的节点添加到队列
        queue<Node*> Q;
        Q.push(node);
        // 克隆第一个节点并存储到哈希表中
        visited[node] = new Node(node->val);

        // 广度优先搜索
        while (!Q.empty()) {
            // 取出队列的头节点
            auto n = Q.front();
            Q.pop();
            // 遍历该节点的邻居
            for (auto& neighbor: n->neighbors) {
                if (visited.find(neighbor) == visited.end()) {
                    // 如果没有被访问过，就克隆并存储在哈希表中
                    visited[neighbor] = new Node(neighbor->val);
                    // 将邻居节点加入队列中
                    Q.push(neighbor);
                }
                // 更新当前节点的邻居列表
                visited[n]->neighbors.emplace_back(visited[neighbor]);
            }
        }

        return visited[node];
    }
};

102. 二叉树的层序遍历

题目　　

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例： 二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

思路：

这个题如果不要求层序，直接使用一个队列输出即可，但是他要求按照层序组织成不同数组，那么我们需要保存每一层的数量，最初我的想法是保存当前层和下一层的数量，当前层每有一个孩子，下一层数量加一，当前层数量减为零时，开始遍历下一层，下一层数量作为当前层数量，下一层数量清零。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(!root) return {};
        int currNum=1, nextNum=0;
        queue<TreeNode*> que;
        que.push(root);
        vector<vector<int>> res;
        vector<int> once;
        while(!que.empty()||once.size()){
            if(currNum--){
                TreeNode* cur = que.front();
                que.pop();
                once.push_back(cur->val);
                if(cur->left){
                    nextNum++;
                    que.push(cur->left);
                }
                if(cur->right){
                    nextNum++;
                    que.push(cur->right);
                }
            }else{
                res.push_back(once);
                once.clear();
                currNum=nextNum;
                nextNum = 0;
            }
        }
        return res;
    }
};

看官方题解意识到其实每一层遍历结束时队列中剩余的节点数量，就是下一层的数量，只需要维护一个当前层的数量即可。

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector <vector <int>> ret;
        if (!root) {
            return ret;
        }

        queue <TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            int currentLevelSize = q.size();    //遍历完一层时队列剩余的数量就是下一层的数量
            ret.push_back(vector <int> ());
            for (int i = 1; i <= currentLevelSize; ++i) {
                auto node = q.front(); q.pop();
                ret.back().push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
        }
        
        return ret;
    }
};

105. 从前序与中序遍历序列构造二叉树

题目　　

给定一棵树的前序遍历 preorder 与中序遍历 inorder。请构造二叉树并返回其根节点。

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

思路

可以使用分治的思想，把问题分解。其实这种问题自己手做的方法也就是类似一个分解的过程，分治也就是模拟了手做这种题目的过程。非常容易出错的十是各种各样的边界问题，一不小心就容易写错、越界。

class Solution {
public:
	TreeNode* my_buildTree(vector<int>& preorder, vector<int>& inorder, int pre_s, int pre_e, int in_s, int in_e) {
		if (pre_e - pre_s < 0) return nullptr;
		if (pre_e - pre_s == 0) return new TreeNode(preorder[pre_s]);
		int root_num = preorder[pre_s];
		int index = find(inorder.begin() + in_s, inorder.begin() + in_e, root_num) - inorder.begin();
		int left_size = index - in_s;
		int right_size = in_e - index;
		TreeNode * left = my_buildTree(preorder, inorder, pre_s + 1, pre_s + left_size, in_s, in_s + left_size - 1);
		TreeNode * right = my_buildTree(preorder, inorder, pre_s + left_size + 1, pre_e, index + 1, in_e);
		return new TreeNode(root_num, left, right);
	}
	TreeNode * buildTree(vector<int> & preorder, vector<int> & inorder) {
		return my_buildTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
	}
};

761. 特殊的二进制序列

题目

特殊的二进制序列是具有以下两个性质的二进制序列：

• 0 的数量与 1 的数量相等。
• 二进制序列的每一个前缀码中 1 的数量要大于等于 0 的数量。

给定一个特殊的二进制序列 S，以字符串形式表示。定义一个 操作 为首先选择 S 的两个连续且非空的特殊的子串，然后将它们交换。（两个子串为连续的当且仅当第一个子串的最后一个字符恰好为第二个子串的第一个字符的前一个字符。)

在任意次数的操作之后，交换后的字符串按照字典序排列的最大的结果是什么？

示例 1:
输入: S = "11011000"
输出: "11100100"
解释:
将子串 "10" （在S[1]出现） 和 "1100" （在S[3]出现）进行交换。 这是在进行若干次操作后按字典序排列最大的结果。

说明:

1. S 的长度不超过 50。
2. S 保证为一个满足上述定义的特殊 的二进制序列。

题解来自力扣官方题解

思路：分治

前言

对于本题而言，将 $1$ 看成左括号 ‘(’，$0$ 看成右括号 ‘)’，那么一个特殊的二进制序列就可以看成一个合法的括号序列。（这样就很好理解）这种「映射」有助于理解题目中的操作，即交换两个相邻且非空的合法括号序列。但为了与题目保持一致，下面的部分仍然使用 1/0 进行叙述。

这个题目关键的是抓住特殊序列的性质：对于一个特殊的二进制序列，其

• 要么不能拆分，作为一个完整的特殊序列，要么可以拆分成几段连续的特殊序列；
• 它一定以 1 开始，以 0 结束。

如果题目给定的字符串是一个不可再拆分的特殊序列，也就是说，它无法完整地拆分成多个特殊序列，那么它的首位 1 和末位 0 是不可能在任何交换操作中出现的。证明见官方题解。 因此，我们可以将开头的 1 和结尾的 0 拆去后考虑中间的部分（不可拆分的序列任意前缀一定 1 的数量多于 0 的数量，去头去尾后中间的部分一定也是一个特殊序列，我们递归考虑这个去头去尾的子字符串可以拆分与不可拆分两种情况即可递归完成整个字符串的拆分）。
如果给定的是一个可拆分的特殊序列，那么整个序列都可拆分为极端连续的特殊序列，将其拆分为多端子序列。

对于拆分出的子序列，我们利用字典序将其排序，排序后拼接即是交换后可得到的最大序列结果。

class Solution {
    public static String makeLargestSpecial(String s) {
        // 对于一个特殊二进制序列，要么整体是二进制特殊序列，要么可以拆分为多个最小二进制特殊序列
        if(s.length()<=2) return s;

        List<String> subs = new ArrayList<>();
        int count = 0, left = 0;
        for(int i = 0; i<s.length();i++){
            if(s.charAt(i)=='1'){
                count++;
            }else{
                count--;
                if(count==0){   // 碰到一个特殊前缀
                    // 去掉1和0将问题转化为子问题
                    subs.add("1"+makeLargestSpecial(s.substring(left+1, i))+"0");
                    left=i+1;
                }
            }
        }
        subs.sort((a, b)->{
            return b.compareTo(a);
        });
        StringBuilder builder = new StringBuilder();
        for(String sub: subs){
            builder.append(sub);
        }
        return builder.toString();
    }

}

827. 最大人工岛

题目

给你一个大小为 $n \times n$ 二进制矩阵 grid 。最多只能将一格 0 变成 1 。

返回执行此操作后，grid 中最大的岛屿面积是多少？

岛屿 由一组上、下、左、右四个方向相连的 1 形成。

思路

容易想到利用「并查集」来维护不同的连接分量，我们将二维数组展平来利用并查集，首先完成并查集的基本操作：初始化、查询、合并，注意可以用一个 size 数组来维护不同分量的面积大小（只有访问帮助节点才有意义）。
在遍历过整个 grid 后，已经将同一个连通分量维护起来了，接着我们需要再次遍历 grid，将其中潜在的翻转点（值为0）上下左右四个位置的连通分量面积和加起来（如果多个方向上是同一个连通分量只计算一次，可以用set实现），记录遍历过程的最大值即是答案。

class Solution {
    int n;
    int[] p;
    int[] size;
    int[][] dirs = new int[][]{{0,1}, {0,-1}, {-1,0}, {1,0}};

    private int find(int a){
        if(p[a] == a) return a;
        return p[a] = find(p[a]);    // 压缩路径
    }
    private void merge(int a, int b){
        int pa = find(a); int pb = find(b);
        if(pa == pb) return;
        if(size[pa] <= size[pb]){
            p[pa] = pb;
            size[pb] += size[pa];
        }else{
            merge(b, a);
        }
    }

    public int largestIsland(int[][] grid) {
        this.n = grid.length;
        // init 
        p = new int[n*n];   size = new int[n*n];
        for(int i = 0; i < n*n; i++){
            p[i] = i;
        }
        Arrays.fill(size,1);
        
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                // 遍历
                if(grid[i][j]==1){
                    for(int[] dir: dirs){ // 四个方向
                        int x = i+dir[0]; int y = j+ dir[1];
                        if(x<0 || x==n || y<0 || y==n || grid[x][y]==0) continue;
                        merge(x*n + y, i*n + j);
                    }
                }
            }
        }
        
        int res = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j]==1){
                    res = Math.max(res, size[find(i*n + j)]);
                }else{
                    // 候选翻转点
                    int area = 1;
                    Set<Integer> seen = new HashSet<>();
                    for(int[] dir: dirs){ // 四个方向
                        int x = i + dir[0]; int y = j + dir[1];
                        if(x<0 || x==n || y<0 || y==n || grid[x][y]==0) continue;
                        int root = find(x*n + y);
                        if(seen.contains(root)) continue;
                        seen.add(root);
                        area += size[root];
                    }
                    res = Math.max(res, area);
                }
            }
        }
        return res;
    }
}

750. Pow(x, n)

题目

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，$x^n$ ）

思路

直接使用 $O(n)$ 的暴力算法会超时，考虑降低时间复杂度，最直接的思路就是找到 $O(logn)$ 的算法，自然就想到了二分。

我们将幂运算化解成两个子幂相乘，如：

对于负数次幂，只需要将运算结果放在分母上，将 n 转化为 -n 即可。

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
    }

    public double quickMul(double x, long N) {
        // 注意题目中 n 为 int，这里用 N 接收，防止 Integer.MIN_VALUE乘-1后向上溢出
        if (N == 0) {
            return 1.0;
        }
        double y = quickMul(x, N / 2);
        return N % 2 == 0 ? y * y : y * y * x;
    }
}