剑指Offer总结

最近快要面试了，再刷一遍剑指Offer，看大家分享刷LeetCode和剑指Offer的时候都是有模板的，如果按照随机顺序刷，很容易忘记而且不容易总结刷题思路。所以常常把一类题放到一块一起刷。

《剑指Offer》有如下优点：

很可能在面试中出现原题（至少在微软面试经常能遇到原题）
题量少，但是涵盖的内容较全，性价比较高
能培养一个良好的刷题习惯

缺点是：

题目较少，刷着容易过拟合
动态规划的题比较少，因此需要在力扣上专项训练。

数据结构类题目

LinkedList

面试题06-从尾到头打印链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

第一反应还是利用栈，但是感觉这道题目考验的还是递归。

参考代码：

class Solution {
private:
    void reversePrintCore(ListNode* head, vector<int> &res) {
        if(head == NULL)
            return;
        reversePrintCore(head->next, res);
        res.push_back(head->val);
    }
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> res;
        reversePrintCore(head, res);
        return res;
    }
};

递归法复杂度分析：

时间复杂度 O(N)： 遍历链表，递归 N 次。
空间复杂度 O(N)： 系统递归需要使用 O(N) 的栈空间。

辅助栈复杂度分析：

时间复杂度 O(N)： 入栈和出栈共使用 O(N) 时间。
空间复杂度 O(N)： 辅助栈 stack 和数组 res 共使用 O(N) 的额外空间。

面试题18-删除链表的节点：双指针，头结点处理时可以使用哑点或者特殊处理

面试题22-链表中倒数第k个结点：双指针（没想起思路）

面试题24-反转链表：三个指针。注意pre指针的初始化，另外最终返回的是pre指针

面试题25-合并两个排序的链表：双指针，哑点的使用（要注意基于递归的写法，建议练习）

面试题35-复杂链表的复制：（想到并写出了利用map的方法，但是没想到节省空间的方法）

面试题52-两个链表的第一个公共节点（想到并写出了利用栈的方法，但是没想到双指针法）

链表测试用例：

特殊输入测试（输入的链表头结点指针为NULL）
普通链表（输入的链表有多个节点；输入的链表只有一个节点）

套路：

哑点的使用
双指针、三指针等用法

Tree

面试题07-重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
与主站105. 从前序与中序遍历序列构造二叉树重复。

前序遍历：节点按照 [ 根节点 | 左子树 | 右子树 ] 排序；中序遍历：节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。

根据以上性质，可得出以下推论：

前序遍历的首元素为树的根节点 node 的值。
在中序遍历中搜索根节点 node 的索引，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ] 。
根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ]（这个没想到）。

参考代码，注意这个代码比较重要的是边界的处理、递归函数返回值的处理：

class Solution {
private:
    int findRootIndex(vector<int> &inorder, int s2, int e2, int root_val) {
        int root_index = -1;
        for(int i=s2; i<=e2; i++) {
            if(inorder[i] == root_val) {
                root_index = i;
                break;
            }
        }
        return root_index;
    }

    TreeNode* buildTreeCore(vector<int>& preorder, int s1, int e1, vector<int>& inorder, int s2, int e2) {
        if(s1 > e1)
            return NULL;
        int index = findRootIndex(inorder, s2, e2, preorder[s1]);
        TreeNode* node = new TreeNode(preorder[s1]);
        node->left = buildTreeCore(preorder, s1+1, s1+(index-s2), inorder, s2, index-1);  // 递归左子树
        node->right = buildTreeCore(preorder, s1+(index-s2)+1, e1, inorder, index+1, e2);  // 递归右子树
        return node;
    }

public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return buildTreeCore(preorder, 0, preorder.size()-1, inorder, 0, inorder.size()-1);
    }
};

递归（想到递归，终止判断条件和递归时子函数传参有误，根源在于对于迭代器和重建二叉树过程理解不到位）

面试题26-树的子结构：两个递归（有大概思路，但是代码没想到是两个递归，需注意递归终止条件）

面试题27-二叉树的镜像：递归（掌握，建议练习）

面试题32-1 -从上往下打印二叉树：队列（掌握）

面试题32-2 -从上往下打印二叉树 2：队列（掌握）

面试题32-3 -从上往下打印二叉树 3：两个栈（想到了使用<algorithm>中reverse方法，但是没想到使用两个栈或者双边队列）

面试题33-二叉搜索树的后序遍历序列：后序遍历特点（未想起思路，代码需要这是一个递归过程）

面试题34-二叉树中和为某一值的路径：深度优先遍历，前序、中序、后序，这里用到了前序（想到了思路，但是不会写代码）

面试题36-二叉搜索树与双向链表：递归（没想到思路，第二遍仍然没有写出来代码，建议练习）

面试题55-1-二叉树的深度：递归（写的代码比较复杂）

面试题55-2-平衡二叉树：后序遍历（只想到了递归的方法，莫名其妙写成了后序遍历，建议练习）

面试题28-对称的二叉树：递归（有大致思路，但写不出具体代码）

面试题37-序列化二叉树：递归（有大致思路，但写不出具体代码，第二遍对于str库还不是很了解）

面试题54-二叉搜索树的第k大节点：中序遍历，右根左（掌握）

面试题68 - I-二叉搜索树的最近公共祖先：遍历（没有想到简单思路，第二遍代码写的复杂了，可以使用非递归的形式）

面试题68 - II-二叉树的最近公共祖先：遍历（没有想到思路，第二遍仍然没有想到简单思路）

二叉树测试用例：

普通二叉树（完全二叉树、非完全二叉树）
特殊二叉树（所有节点都没有右子节点的二叉树、所有节点都没有左子节点的二叉树、只有一个节点的二叉树）
特殊输入测试（二叉树的根节点指针为NULL；输入不满足题意）

看到二叉搜索树，就要想到前序、中序、后序遍历方式。其中中序遍历是按照从小到大的顺序排列的。

套路：

尝试将递归语句放到if条件中，可以

参考

剑指 Offer 07. 重建二叉树（分治算法，清晰图解）

Stack & Queue

面试题09-用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

这道题目较为简单，可以直接说下思路，假设两个栈分别是s1和s2。

加入队尾：将数值value放入到s1即可。

删除队头：

若s1和s2都为空，则return -1；
若s2为空，则将s1中的元素全部转移到s2，实现元素逆序，并返回栈顶元素。
若s2不为空，则返回栈顶元素。

class CQueue {
public:
    stack<int> s1, s2;
    CQueue() { 
    }
    
    void appendTail(int value) {
        s1.push(value);
    }
    
    int deleteHead() {
        if(s1.empty() && s2.empty())
            return -1;
        if(s2.empty()) {
            // int s1_len = s1.size();  // 不推荐这种写法, 容易出错
            // for(int i=0; i<s1_len; i++) {
            while(!s1.empty()) {
                int top_value = s1.top();
                s2.push(top_value);
                s1.pop();
            }
        }
        int res = s2.top();
        s2.pop();
        return res;
    }
};

面试题30-包含min函数的栈：辅助栈（push函数有点小问题）

面试题31-栈的压入、弹出序列：辅助栈（没有想到思路，第二遍仍没有写出来最优解，建议练习）

面试题58-1-翻转单词顺序：istringstream的使用（没有想到最优解，第二遍仍然不会用这个库，建议记忆）

面试题59-1-滑动窗口的最大值：双边队列（没有想到，第二遍仍然没有想到）

Heap

面试题40-最小的K个数：最小堆，priority_queue的使用（没有想起来思路，第二遍对于该库还不是很熟悉）

面试题41-数据流中的中位数：最大堆最小堆（没有想到思路，第二遍对库还不是很熟悉）

Hash Table

面试题50-第一个只出现一次的字符：哈希表（想到了思路，但不会写代码。第二遍没有想出来是两遍遍历）

图

面试题12-矩阵中的路径(BFS)：回溯（能想到思路，代码不是很熟，第二遍代码仍然有问题，建议练习）

面试题13-机器人的运动范围(DFS)：回溯（代码不是很熟练）

具体算法类题目

斐波那契数列

面试题10-1-斐波拉契数列

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
1
2
3
> F(0) = 0,   F(1) = 1
> F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
>

斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

这道题主要考察动态规划+数字溢出。数字溢出比较难想到。

但是拿到这个题目，第一反应是递归，它代码好写，但是会超时。

class Solution {
public:
    int fib(int n) {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        
        return (fib(n-1) + fib(n-2)) %1000000007;
    }
};

然后，说下动态规划的思路。

状态定义：设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列第 i 个数字。
转移方程： dp[i+1]=dp[i]+dp[i−1]，即对应数列定义 f(n+1)=f(n)+f(n−1)；可以发现dp列表的第i项只与第i-1和第i-2项有关，可以优化存储空间。
初始状态： dp[0]=0，dp[1]=1，即初始化前两个数字；
返回值： dp[n]，即斐波那契数列的第 n 个数字。

class Solution {
public:
    int fib(int n) {
        vector<int> cache = {0, 1};
        if(n <= 1)
            return cache[n];

        for(int i=2; i<=n; i++) {
            int tmp = (cache[0] + cache[1])%1000000007;
            cache[0] = cache[1];
            cache[1] = tmp;
        }
        return cache[1];
    }
};

面试题10-2-青蛙跳台阶问题

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

这道题的思想与上一道题是一致的，只是初始状态不同而已。

青蛙跳台阶问题： f(0)=1，f(1)=1，f(2)=2；
斐波那契数列问题： f(0)=0，f(1)=1，f(2)=1。

参考代码如下：

class Solution {
public:
    int numWays(int n) {
        vector<int> cache = {1, 2};
        if(n <= 1)
            return cache[0];
        if(n == 2)
            return cache[1];

        for(int i=3; i<=n; i++) {
            int tmp = (cache[0] + cache[1])%1000000007;
            cache[0] = cache[1];
            cache[1] = tmp;
        }
        return cache[1];
    }
};

搜索算法

面试题04-二维数组中的查找：右上角开始（能想到思路，但是代码不太会写）

面试题11-旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在重复元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

这道题考验的还是二分查找算法，容易出错的地方是边界值的处理。

二分查找相比较于遍历，好处在于可以缩减搜索的范围。分析旋转数组可以得到这是两个单调递增的序列，并且第一个序列的最小元素大于等于第二个序列的最大元素。如下图所示：

那么根据这个图可知，根据中值和前后值的大小关系只能得到它是否处于单调递增序列中的，但是无法判断处于哪一个单调递增序列。这个时候就需要拿中值和最后一个值比较大小。

若中值>最后值，则说明在第一个单调递增序列，下次遍历的范围是[mid+1,end]。
若中值=最后值，则无法判断，下次遍历的范围是[start,end-1]。（这种情况，我一开始全部遍历处理了）
若中值<最后值，则说明在第二个单调递增序列，下次遍历的范围是[start,mid]

参考代码如下：

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int length = numbers.size();
        if(length <= 0)
            return -1;
        
        int begin = 0;
        int end = length - 1;
        while(begin < end) {
            int mid = begin + (end-begin)/2;  //这样写是防止int溢出
            if(numbers[mid] < numbers[end])
                end = mid;
            else if(numbers[mid] > numbers[end])
                begin = mid + 1;
            else 
                end--;
        }
        return numbers[begin];  // 返回numbers[end];也可以
    }
};

面试题53-1-在排序数组中查找数字 I：二分查找（能想到思路，建议练习，注意）

面试题53-II-0～n-1中缺失的数字：二分查找（能想到思路，但是没有注意到缺失数字在数组末尾的情况，第二遍仍然没有注意到，建议练习）

全排列

面试题38-字符串的排列：递归（能想到思路，建议练习）

动态规划

面试题42-连续子数组的最大和：DP（掌握，但不知道方法是DP）

面试题19-正则表达式匹配：递归（未想到思路，第二遍思路仍然不清晰，建议练习）

面试题47-礼物的最大价值：DP（没写出来递推公式）

面试题48-最长不含重复字符的子字符串：DP（有思路但没想到转换为公式）

面试题60-n个骰子的点数：DP（没想出来状态表达式，且代码容易写错）

贪婪算法

面试题14-I-剪绳子

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

贪婪算法（没有想到思路）

面试题14-II-剪绳子：贪婪算法（没有想到思路，第二遍不会解决大数问题，建议练习）

回溯

面试题12-矩阵中的路径(BFS)

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

这道题是典型的回溯算法题目。核心的逻辑是看当前位置是否是匹配上了，如果匹配上了，则看上下左右能否继续匹配上（这也是递归的核心逻辑，一开始误将当前匹配的逻辑写在了递归外面）。在这个过程中，需要注意题目中的同一个单元格内的字母不能被重复使用，因此需要用一个矩阵来标示是否访问过。

详细代码如下：

class Solution {
private:
    bool existCore(vector<vector<char>>& board, int row, int col, string& word, int c_idx, vector<vector<int>>& flag) {
        if(c_idx == word.size())  //完全匹配上了
            return true;
        bool res = false;
        if(row >=0 && row<board.size() && col>=0 && col<board[0].size() && flag[row][col]!=1) {
            if(board[row][col] == word[c_idx]) {  // 判断当前是否匹配上了
                flag[row][col] = 1;
                res = existCore(board, row-1, col, word, c_idx+1, flag) ||
                        existCore(board, row+1, col, word, c_idx+1, flag) ||
                        existCore(board, row, col-1, word, c_idx+1, flag) ||
                        existCore(board, row, col+1, word, c_idx+1, flag);  // 看上下左右是否继续匹配上
                if(!res)
                    flag[row][col] = 0;  // 若无法匹配下一个元素，则终止递归，并重置flag
            }
        }
        return res;
    }
public:
    bool exist(vector<vector<char>>& board, string word) {
        if(board.empty() || word.empty())
            return false;
        int m = board.size();
        int n = board[0].size();
        bool res = false;
        vector<vector<int>> flag(m, vector<int>(n, 0));
        for(int i=0; i<m; i++) {
            for(int j=0; j<n; j++) {
                if(existCore(board, i, j, word, 0, flag))  // 注意若break在后面统一return, 则break时只会跳出第一层循环
                    return true;
            }
        }
        return res;
    }
};

面试题13-机器人的运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0]的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

与上一道题一样，也主要是回溯算法。不同的是，这里的visited记录矩阵，并不需要还原回去，因为这里只能从(0,0)出发，主要是记录是否访问过行了，只要是访问过的，那么从这个节点出发的所有情况都会回溯。

参考代码如下：

class Solution {
private:
    // 这个写法很值得借鉴
    int getDigitSum(int number) {
        int sum = 0;
        while(number > 0) {
            sum += number%10;
            number /= 10;
        }
        return sum;
    }
    // i,j 表示当前访问的元素，count表示当前元素之和，k表示不能超过的元素，后面visited必须传引用或者指针，否则结果不对
    int movingCountCore(int rows, int cols, int i, int j, int k, vector<vector<bool>>& visited) {
        int count = 0;
        int sum = getDigitSum(i) + getDigitSum(j);
        if(i>=0 && i<rows && j>=0 && j<cols && sum<=k && !visited[i][j]) {
            visited[i][j] = true;
        
            count = 1 + movingCountCore(rows, cols, i-1, j, k, visited)
                      + movingCountCore(rows, cols, i+1, j, k, visited)
                      + movingCountCore(rows, cols, i, j-1, k, visited)
                      + movingCountCore(rows, cols, i, j+1, k, visited);

        }
        return count;
    }

public:
    int movingCount(int m, int n, int k) {
        if(k < 0) 
            return 0;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        return movingCountCore(m, n, 0, 0, k, visited);
    }
};

排序

面试题51-数组中的逆序对：归并排序（只想到了暴力求解的方法，经典建议练习）

面试题53-I-在排序数组中查找数字 I：二分查找

面试题40-最小的K个数：最小堆（没有想起来思路）

位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作。

面试题15-二进制中1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量).）。

这道题考察的是位运算。

方法一：逐位判断

根据与运算定义，设二进制数字 n ，则有：

若 n&1=0，则 n 二进制最右一位为 0 ；
若 n&1=1，则 n 二进制最右一位为 1 。

根据以上特点，考虑以下循环判断：

判断 n 最右一位是否为 1，根据结果计数。
将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用无符号右移操作）

参考代码如下：

class Solution {
public:
    int hammingWeight(uint32_t n) {  // typedef unsigned int: uint32_t
        int res = 0;
        while(n){
            if(n&1) res++;
            n >>= 1;  // 右移
        }
        return res;
    }
};

方法二：巧用 n&(n−1)

(n−1) 解析：二进制数字 n 最右边的 1 变成 0，此 1 右边的 0 都变成 1 。
n&(n−1) 解析：二进制数字 n 最右边的 1 变成 0，其余不变。

算法流程：

初始化数量统计变量 ret 。
循环消去最右边的 1：当 n=0 时跳出。

res += 1 ：统计变量加 1；
n &= n - 1 ：消去数字 n 最右边的 1（也就是从右往左数，第一个1，不一定是从右数第一个元素）。
返回统计数量 ret。

参考代码：

class Solution {
public:
    int hammingWeight(uint32_t n) {  // typedef unsigned int: uint32_t
        int ret = 0;
        while (n) {  // 当n=0的时候退出
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

这里补充一下，在C++中如何Convert binary string to integer

#include <iostream>
#include <string>
using namespace std;

int main()
{
	string bin_string = "10101010";
	int number =0;

	number = stoi(bin_string, 0, 2);
	cout<<"bin_string: "<<bin_string<<endl;
	cout<<"number: "<<number<<endl;

	bin_string = "111100001100111010";
	number = stoi(bin_string, 0, 2);
	cout<<"bin_string: "<<bin_string<<endl;
	cout<<"number: "<<number<<endl;

	return 0;
}

Output

bin_string: 10101010
number: 170
bin_string: 111100001100111010
number: 246586

面试题16-数值的整数次方

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。
注意：本题与主站 50 题相同：https://leetcode-cn.com/problems/powx-n/

这道题想要做出来，首先还是得对这个公式有所了解。当指数 n 为负数时，我们可以计算 $x^{−n}$ 再取倒数得到结果，因此我们只需要考虑 n 为自然数的情况。

另外，本题主要考察的是快速幂的思想。若不采用快速幂的方法，会出现AddressSanitizer: stack-overflow这样的错误。

方法一：快速幂+递归

「快速幂算法」的本质是分治算法。举个例子，如果我们要计算$x^{64}$，我们可以按照下列顺序进行计算。

当我们要计算 $x^{77}$，我们可以按照下面顺序进行计算。

我们从右往左看，分治的思想就十分明显了：

当我们要计算 $ x^{n} $ 时，我们可以先递归地计算出 $ y=x^{\lfloor n / 2\rfloor} $，其中 $ \lfloor a\rfloor $ 表示对 $ a $ 进行下取整;
根据递归计算的结果，如果 $ n $ 为偶数, 那么 $ x^{n}=y^{2} $；如果 $ n $ 为奇数, 那么 $ x^{n}=y^{2} \times $ $ x $
递归的边界为 $ n=0 $，任意数的 0 次方均为 1 。

从这个公式中可以看出来，有$n/2$以及判断奇偶性，这就可以采用位运算来加快速度。

需要注意的是，-2^31 <= n <= 2^31-1，所以当-2^31变成正数时，会溢出，所以需要更改 n 的类型。

参考代码如下所示：

class Solution {
private:
    double myPowPos(double x, long n) {
        if(n == 0)
            return 1.0;
        double res = myPowPos(x, n>>1);
        if(n&1)
            return res * res * x;
        else
            return res * res; 
    }
public:
    double myPow(double x, int n) {
        long N = n;
        if(x == 0)
            return 0;
        if(n > 0)
            return myPowPos(x, N);
        else
            return 1/myPowPos(x, -N);
    }
};

方法二：快速幂+循环

由于递归需要使用额外的栈空间，我们试着将递归转写为迭代。我们从另外一个角度来理解快速幂。

比如要求 $ x^{11} $, 正常的乘积需要循环乘 11 次, 时间复杂度为 $ 0(n) $。

快速幂的思想就是将指数11 可以转成二进制数 1011, 则原来的式子可以转化成$ x^{11}=x^{2^{3}+2^{1}+2^{0}}=x^{2^{3}} \times x^{2^{1}} \times x^{2^{0}} $, 此时只运算了3次乘积, 时间复杂度降至 $ 0(\log n) $。

下方代码中的 $ \mathrm{x} =\mathrm{x} $ 是一个累乘的过程, 得到四位二进制数, 对应的四个权重, $ x, x =x $ $ , x^{2} =x^{2}, x^{4} =x^{4} $。

1011二进制数, 从右至左分别为 1101 , 只有在1的位置上, 才有相应的权重, 这也就是为什么需要通过与运算: $ (b \& 1)==1 $ 判断最后一位是否为 1 。

$x--->x^{2^{0}}---> 1 \\ x^{2}--->x^{2^{1}} ---> 1 \\ x^{4}--->x^{2^{2}} ---> 0 \\ x^{8}--->x^{2^{3}} ---> 1$

最终的结果就是将每一位的1 所对应的权重相乘即可： $ x^{2^{0}} \times x^{2^{1}} \times x^{2^{3}} $。

参考代码如下：

class Solution {
private:
    double myPowCore(double x, long n) {
        double res = 1;
        while(n) {
            if(n&1)
                res = res * x;
            x *= x;
            n >>= 1;
        }
        return res;
    }
public:
    double myPow(double x, int n) {
        long N = n;
        if(n >= 0)
            return myPowCore(x, N);
        else
            return 1/myPowCore(x, -N);
    }
};

面试题56-1-数组中数字出现的次数

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

注意这题对时间和空间复杂度做了要求，肯定不能采用暴力方法和哈希表了。

我们先简化问题，一个整型数组 nums 里除1个数字x之外，其他数字都出现了两次。我们知道异或有两个性质。

$a \oplus a = 0$
满足交换律

因此，若将 nums 中所有数字执行异或运算，留下的结果则为出现一次的数字 x。

但是这道题比较难， nums 中有两个不同的数字。

设两个只出现一次的数字为 $ x, y $，由于 $ x \neq y $，则 $ x $ 和 $ y $ 二进制至少有一位不同 (即分别为 0 和 1 )，根据此位可以将 nums 拆分为分别包含 $ x $ 和 $ y $ 的两个子数组。

易知两子数组都满足「除一个数字之外，其他数字都出现了两次」。因此, 仿照以上简化问题的思路，分别对两子数组遍历执行异或操作, 即可得到两个只出现一次的数字 $ x, y $ 。

参考代码如下：

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x = 0, y = 0, n = 0, m = 1;
        // 得到结果是 x^y
        for(int num : nums)         // 1. 遍历异或
            n ^= num;               
        // 找到x⊕y某为1的二进制位m, 用于将nums分组
        while((n & m) == 0)         // 2. 循环左移，计算 m, 要记住 n&m 要加上括号
            m <<= 1;
        for(int num : nums) {       // 3. 遍历 nums 分组
            if(num & m) x ^= num;   // 4. 当 num & m != 0
            else y ^= num;          // 4. 当 num & m == 0
        }
        return vector<int> {x, y};  // 5. 返回出现一次的数字
    }
};

面试题56-2-数组中数字出现的次数 II

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

如果一个数字出现3次，它的二进制每一位也出现的3次。如果把所有的出现三次的数字的二进制表示的每一位都分别加起来，那么每一位都能被3整除。我们把数组中所有的数字的二进制表示的每一位都加起来。如果某一位能被3整除，那么这一位对只出现一次的那个数的这一肯定为0。如果某一位不能被3整除，那么只出现一次的那个数字的该位置一定为1。

面试题65-不用加减乘除做加法：位运算（没有想到思路，且没有考虑到负数的情况，第二遍仍然没有考虑到）