只有脚踩上去才知其远近和曲折

剑指offer

1、链表

删除结点时注意释放空间,防止内存泄漏

注意把next指向NULL,防止野指针

1.1 两个链表的第一个公共结点

剑指 Offer 52. 两个链表的第一个公共节点

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *node1 = headA;
        ListNode *node2 = headB;

        while (node1 != node2) {
            node1 = node1 != NULL ? node1->next : headB;
            node2 = node2 != NULL ? node2->next : headA;
        }
        return node1;
    }
};

1.2 复杂链表的复制

剑指 Offer 35. 复杂链表的复制

方法一 哈希

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/
class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return head;
        unordered_map<Node *, Node *> m;
        Node virhead(0, NULL, NULL);

        Node *p = &virhead, *q = head;
        while (q) {
            p->next = new Node(q->val, NULL, NULL);
            m.insert(make_pair(q, p->next));
            q = q->next;
            p = p->next;
        }

        p = &virhead, q = head;
        while (q) {
            p->next->random = m[q->random];
            q = q->next;
            p = p->next;
        }

        return virhead.next;
    }
};

方法二

  1. 复制每一个节点,使得复制后的节点都在当前节点的下一个节点
  2. 原生链表的节点的指向任意节点,使复制的节点也都指向某一任意节点
  3. 重新连接节点,把原生节点重新连接起来,把克隆后的节点连接起来

图示:

《剑指offer》

代码

//不需要额外空间
    public static Node copyListWithRand2(Node head){
        if (head == null ){
            return null;
        }
        Node curr = head;
        //拷贝链表,并且把链表连接起来
        while(curr != null){
            Node next = curr.next;
            Node copy = new Node(curr.val);
            curr.next = copy;
            copy.next = next;
            curr = next;
        }
        //指定随即指针
        curr = head;
        while(curr != null){
            Node next = curr.next.next;//原节点的下一个节点
            Node currCopy = curr.next;//当前的拷贝节点
            currCopy.random = curr.random!=null?curr.random.next:null;//指定随机指针节点
            curr = next;//当前节点指向下一个节点
        }
        //拆分链表
        curr = head;
        Node res = curr.next;//用于返回的拷贝头节点
        while (curr != null){
            Node next = curr.next.next;//原节点的下一个节点
            Node curCopy = curr.next;//拷贝节点
            curr.next = next;//将原节点指向下一个原节点
            curCopy.next = next!=null?next.next:null;//拷贝节点的下一个节点指向下一个原节点的下一个节点
            curr = next;//将当前节点指向下一个原节点
        }
        return res;
    }

2、二叉树

2.1 重建二叉树

剑指 Offer 07. 重建二叉树

  • 先序、中序建树
  • 中序、后序建树

先序、中序建树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> mino;

    TreeNode* _build(vector<int>& pre, int pl, int pr, vector<int>& ino, int il, int ir) {
        if (pl > pr || il > ir) return NULL;
        int imid = mino[pre[pl]], pmid = pl + imid - il;

        TreeNode *node = new TreeNode;
        node->val = pre[pl];
        node->left = _build(pre, pl + 1, pmid, ino, il, imid - 1);
        node->right = _build(pre, pmid + 1, pr, ino, imid + 1, ir);
        return node;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.size() <= 0 || inorder.size() <= 0) return NULL;
        for (int i = 0; i < inorder.size(); ++i) mino[inorder[i]] = i;
        return _build(preorder, 0, preorder.size() - 1, inorder, 0, inorder.size() - 1);
    }
};

2.2 树的子结构

剑指 Offer 26. 树的子结构

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode *a, TreeNode *b) {
        if (!b) return true;
        if (!a) return false;
        if (a->val != b->val) return false;
        return check(a->left, b->left) && check(a->right, b->right);
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        if (!A || !B) return false;
        if (A->val == B->val && check(A, B)) return true;
        if (isSubStructure(A->left, B) || isSubStructure(A->right, B)) return true;
        return false;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool check(TreeNode* a, TreeNode *b) {
        if (!b) return true;
        if (!a || a->val != b->val) return false;
        return check(a->left, b->left) && check(a->right, b->right);
    }

    bool isSubStructure(TreeNode* A, TreeNode* B) {
        return (A && B) && (check(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B));
    }
};

2.3 二叉树中和为某一值的路径

剑指 Offer 34. 二叉树中和为某一值的路径

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    void dfs(vector<vector<int>> &res, vector<int> &temp, TreeNode *root, int sum) {
        if (!root) return ;
        sum -= root->val;
        temp.push_back(root->val);
        if (!sum && !root->left && !root->right) res.push_back(temp);
        dfs(res, temp, root->left, sum);
        dfs(res, temp, root->right, sum);
        temp.pop_back();
        return ;
    }

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> temp;
        dfs(res, temp, root, sum);
        return res;
    }
};

2.4 二叉搜索树的第k大节点

剑指 Offer 54. 二叉搜索树的第k大节点

思路

中序遍历的结果是升序序列,倒着中序遍历便是降序,便可求得第k大

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool inorder(TreeNode *root, int &k, int &res) {
        if (!root) return false;
        if (inorder(root->right, k, res)) return true;
        if (--k == 0) {
            res = root->val;
            return true;
        }
        if (inorder(root->left, k, res)) return true;
        return false;
    }

    int kthLargest(TreeNode* root, int k) {
        int res = 0;
        inorder(root, k, res);
        return res;
    }
};

2.5 二叉搜索树的最近公共祖先

面试题68 – I. 二叉搜索树的最近公共祖先

代码——递归

最坏情况退化为链表

时间复杂度:O(n)

空间复杂度:O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (p->val < root->val && q->val < root->val) return lowestCommonAncestor(root->left, p, q);
        else if (p->val >root->val && q->val > root->val) return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};

代码——迭代

最坏情况退化为链表

时间复杂度:O(n)

空间复杂度:O(1)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        int pval = p->val, qval = q->val;
        while (root) {
            if (pval < root->val && qval < root->val) root = root->left;
            else if (pval > root->val && qval > root->val) root = root->right;
            else return root;
        }
        return root;
    }
};

2.6 二叉树的最近公共祖先

面试题68 – II. 二叉树的最近公共祖先

解题思路

根据 left 和 right ,可展开为四种情况;

  • 当 left 和 right 同时为空 :说明 root 的左 / 右子树中都不包含 p,q,返回 null;
  • 当 left 和 right 同时不为空 :说明 p, q 分列在 root 的 异侧 (分别在 左 / 右子树),因此 root 为最近公共祖先,返回 root ;
  • 当 left 为空 ,right 不为空 :p,q 都不在 root 的左子树中,直接返回 right 。具体可分为两种情况:
    • p,q 其中一个在 root 的 右子树 中,此时 right 指向 p(假设为 p );
    • p,q 两节点都在 root 的 右子树 中,此时的 right 指向 最近公共祖先节点 ;
  • 当 left 不为空 , right 为空 :与情况 3. 同理;

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root || p->val == root->val || q->val == root->val) return root;
        TreeNode *l = lowestCommonAncestor(root->left, p, q);
        TreeNode *r = lowestCommonAncestor(root->right, p, q);
        if (!l) return r;
        if (!r) return l;
        return root;
    }
};

2.7 二叉搜索树与双向链表

解题思路

利用中序遍历

代码

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if (!root) return root;
        _build(root);
        head->left = pre;
        pre->right = head;
        return head;
    }

    void _build(Node *node) {
        if (!node) return ;
        _build(node->left);
        if (!pre) head = node;
        else pre->right = node;
        node->left = pre;
        pre = node;
        _build(node->right);

        return ;
    }
private :
    Node *pre, *head;
};

剑指 Offer 36. 二叉搜索树与双向链表

3、贪心

3.1 剪绳子2

剑指 Offer 14- II. 剪绳子 II

尽量转换成 3^a^ * 2^b^ 的形式

class Solution {
public:
    long long quick_pow(long long a, long long b, long long c) {
        long long res = c, mod = 1e9 + 7;
        while (b) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res % mod;
    }
    int cuttingRope(int n) {
        if (n < 3) return 1;
        if (n == 3) return 2;
        int a = n % 3, b = n / 3;
        if (a == 0) return (int)quick_pow(3, b, 1);
        else if (a == 2) return (int)quick_pow(3, b, 2);
        else return (int)quick_pow(3, b - 1, 4);
    }
};

4、 二分

4.1 在排序数组中查找数字 I

剑指 Offer 53 – I. 在排序数组中查找数字 I

class Solution {
public:
    int _find(vector<int> &arr, int key) {
        int l = 0, r = arr.size() - 1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (arr[mid] <= key) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }
    int search(vector<int>& nums, int target) {
        return _find(nums, target) - _find(nums, target - 1); 
    }
};

4.2 0~n-1中缺失的数字

剑指 Offer 53 – II. 0~n-1中缺失的数字

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int l = 0, r = nums.size(), mid;
        while (l < r) {
            mid = (l + r) >> 1;
            if (nums[mid] == mid) l = mid + 1;
            else r = mid;
        }
        return l;
    }
};

5、动态规划

5.1 股票的最大利润

剑指 Offer 63. 股票的最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if (prices.size() <= 0) return 0;
        int cost = prices[0], res = 0;
        for (int i = 1; i < prices.size(); ++i) {
            res = (res > prices[i] - cost ? res : prices[i] - cost);
            cost = (cost < prices[i] ? cost : prices[i]);
        }
        return res;
    }
};

5.2 把数字翻译成字符串

46. 把数字翻译成字符串

class Solution {
public:
    int translateNum(int num) {
        int now = 1, last = 1;
        string s = to_string(num);
        for (int i = 2; i <= s.size(); ++i) {
            int temp = now;
            if (s[i - 2] != '0' && ((s[i - 2] - '0') * 10 + (s[i - 1] - '0') <= 25)) now += last;
            last = temp;
        }
        return now;
    }
};

5.3 n个骰子的点数

剑指 Offer 60. n个骰子的点数

思路

简单的dp问题

状态:dp(i, j) 表示 i 个骰子组成和 j 有多少种可能

状态转移方程:dp(i, j) = dp(i – 1, j – 1) + … +dp(i – 1, j – 6)

代码

class Solution {
public:
    vector<double> twoSum(int n) {
        int cnt = n * 6 - n + 1; // 求得有多少种可能点数和
        vector<double> res(cnt, 0);
        for (int i = 0; i < 6; ++i) res[i] = 1;
        // 滚动数组
        for (int i = 2; i <= n; ++i) {
            for (int j = i * 6 - i; j >= 0; --j) { // 采用滚动数组,所以倒着搜
                for (int l = 1; l < 6 && j - l >= 0; ++l) { 
                    // 当前的状态可以由n-1个骰子的 dp(n-1, j-1) + ... + dp(n-1, j-6),相加得到
                    // 因为当前增加了一个骰子,所以所有骰子最少和由n-1变为n,即res[j]的值就是dp(n-1, j-1)
                    res[j] += res[j - l];
                }
            }
        }

        for (int i = 0; i < cnt; ++i) {
            res[i] = res[i] * (1.0 / pow(6, n));
        }
        return res;
    }
};

6、位运算

6.1 不用乘除做加法

剑指 Offer 65. 不用加减乘除做加法

class Solution {
public:
    int add(int a, int b) {
        while (b != 0) {
            int c = (unsigned int)(a & b) << 1; // 计算二进制需要进位的地方
            a ^= b;
            b = c;
        }
        return a;
    }
};

6.2 二进制中1的个数

剑指 Offer 15. 二进制中1的个数

class Solution {
public:
    int hammingWeight(uint32_t n) {
        if (!n) return 0;
        int res = 0;
        while (n) {
            n = n & (n - 1);
            ++res;
        }
        return res;
    }
};

6.3 数组中数字出现的次数 I

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

思路

设a、b是数组中只出现一次的元素

  • 先将数组所有元素进行异或,可得到 a ^ b
  • 取 a ^ b 最后一个 1 的位置将数组进行划分(取任何一个 1 的位置划分都可以)
  • 再将被划分为两部分的数组分别异或,即可得到a、b

代码

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        vector<int> res(2, 0);
        int x = 0, y = 1;
        for (int i = 0; i < nums.size(); ++i) x ^= nums[i];
        while ((y & x) == 0) y <<= 1;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] & y) res[0] ^= nums[i];
            else res[1] ^= nums[i];
        } 
        return res;
    }
};

6.4 数组中数字出现的次数 II

剑指 Offer 56 – II. 数组中数字出现的次数 II

解题思路

因为每个数字出现的次数只有 1 和 3,所以当一个数字出现三次的时候就等同于出现 0 次

  • one 标记出现一次,two 标记出现两次
  • 一个数位出现一次时 one 为 1,two 为 0
  • 一个数位出现两次时 one 为 0,two 为 1
  • 一个数位出现三次和未出现过时时 one 为 0,two 为 0

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int one = 0, two = 0;
        for (int x : nums) {
            one = one ^ (x & ~two);
            two = two ^ (x & ~one);
        }
        return one;
    }
};

其他

1.矩阵螺旋输出

剑指 Offer 29. 顺时针打印矩阵

输出顺序:

  • 第一行
  • 最后一列(少第一行)
  • 最后一行(比第一行少首尾两列)
  • 第一列(少第一行)
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if (!matrix.size()) return res;
        int n = matrix.size(), m = matrix[0].size();
        int starti = 0, endi = n - 1, startj = 0, endj = m - 1;
        while (starti <= endi && startj <= endj) {
            for (int j = startj; j <= endj; ++j) res.push_back(matrix[starti][j]);
            for (int i = starti + 1; i <= endi; ++i) res.push_back(matrix[i][endj]);    
            if (starti < endi && startj < endj) { 
                for (int j = endj - 1; j > startj; --j) res.push_back(matrix[endi][j]);
                for (int i = endi; i > starti; --i) res.push_back(matrix[i][startj]);
            }
            ++starti, --endi, ++startj, --endj;
        }
        return res;
    }
};

1.2 数组中出现次数超过一半的数字

剑指 Offer 39. 数组中出现次数超过一半的数字

解题思路

本题常见解法如下:

哈希表统计法: 遍历数组 nums ,用 HashMap 统计各数字的数量,最终超过数组长度一半的数字则为众数。此方法时间和空间复杂度均为 O(N)。
数组排序法: 将数组 nums 排序,由于众数的数量超过数组长度一半,因此 数组中点的元素 一定为众数。此方法时间复杂度 O(N log N)。
摩尔投票法: 核心理念为 “正负抵消” ;时间和空间复杂度分别为 O(N) 和 O(1);是本题的最佳解法。

摩尔投票法:

  • 票数和: 由于众数出现的次数超过数组长度的一半;若记 众数 的票数为 +1,非众数 的票数为 -1 ,则一定有所有数字的 票数和 > 0。
  • 票数正负抵消: 设数组 nums 中的众数为 x,数组长度为 n。若 nums 的前 a 个数字的 票数和 = 0,则 数组后 (n-a)个数字的 票数和一定仍 >0 (即后 (n-a) 个数字的 众数仍为 x)。

《剑指offer》

算法原理:

  • 为构建正负抵消,假设数组首个元素 n~1~为众数,遍历统计票数,当发生正负抵消时,剩余数组的众数一定不变 ,这是因为(设真正的众数为 x):
    • 当 n~1~ = x: 抵消的所有数字中,有一半是众数 x。
    • 当 n~1~ != x: 抵消的所有数字中,少于或等于一半是众数 x。
  • 利用此特性,每轮假设都可以 **缩小剩余数组区间 **。当遍历完成时,最后一轮假设的数字即为众数(由于众数超过一半,最后一轮的票数和必为正数)。

算法流程:

  • 初始化: 票数统计 votes = 0, 众数 x;
  • 循环抵消: 遍历数组 nums 中的每个数字 num;
    • 当 票数 votes等于 0 ,则假设 当前数字 num 为 众数 x ;
    • 当 num = x时,票数 votes自增 1 ;否则,票数 votes 自减 1 。
  • 返回值: 返回 众数 x 即可。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int x = 0, cnt = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (cnt == 0) x = nums[i];
            cnt += (x == nums[i] ? 1 : -1);
        }
        return x;
    }
};

1.3 构建乘积数组

剑指 Offer 66. 构建乘积数组

解题思路

从前往后扫一遍,再从后往前扫一遍即可

class Solution {
public:
    vector<int> constructArr(vector<int>& a) {
        vector<int> res(a.size());
        res[0] = 1;
        for (int i = 1; i < res.size(); ++i) res[i]  = res[i - 1] * a[i - 1];
        int temp = 1;
        for (int i = res.size() - 2; i >= 0; --i) {
            temp *= a[i + 1];
            res[i] *= temp;
        }
        return res;
    }
};
点赞