剑指offer题目总结

Posted on | In ,

本文将针对剑指offer题目按照章节进行讲解。

题目表

题号 是否掌握 题号 是否掌握 题号 是否掌握
3 * 27 50 *
4 * 28 51
5 29 52 *
6 * 30 53-1
7 31 53-2
8 32-1 * 54
9 55-1 *
10-1 32-3 55-2
10-2 33 * 56-1
11 34 56-2
12 35 - 57
13 36 57-2
14-1 37 58-1
14-2 38 58-2
15 39 59-1
16 40 59-2
17 41 60
18 42 61
19 43 62
20 44 63
21 45 64
22 46 65
24 47 66 *
25 48 67
26 49 68-1

第二章

数组中重复的数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int findRepeatNumber(vector<int>& nums) {
    int length = nums.size();
    if(length == 0 || length == 1) return 0;
    for(int i=0;i<length;++i){
        if(nums[i] < 0 || nums[i] >= length) return 0;
    }
    for(int i=0;i<length;++i){
        while(nums[i] != i){
            
            if(nums[i] == nums[nums[i]]) return nums[i];
            
            int temp = nums[i];
            nums[i] = nums[nums[i]];
            nums[temp] = temp;
        }
    }
    return 0;
}

二维数组中的查找

1
2
3
4
5
6
7
8
9
10
11
12
13
bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    if(matrix.size() == 0 || matrix[0].size()==0) return false;
    int rows = matrix.size();
    int cols = matrix[0].size();
    int row  = rows-1;
    int col  = 0;
    while(row >= 0 && col < cols){
        if(matrix[row][col] == target) return true;
        else if(matrix[row][col] < target) col++;
        else row--;
    } 
    return false;
}

替换空格

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
string replaceSpace(string s) {
    if(s.empty()) return s;
    int ori_length = s.size();
    int space_num  = 0;
    for(int i=0;i<ori_length;++i){
        if(s[i]==' ') ++space_num;
    }

    for(int i=0;i<space_num;++i){
        s.push_back(' ');
        s.push_back(' ');
    }
    int new_length = ori_length + space_num*2;
    int ptr1 = ori_length-1;
    int ptr2 = new_length-1;
    while(ptr1>=0 && ptr2 >= ptr1){
        if(s[ptr1] == ' '){
            s[ptr2--] = '0';
            s[ptr2--] = '2';
            s[ptr2--] = '%';
        }
        else{
            s[ptr2--] = s[ptr1];
        }
        ptr1--;
    }
    return s;

}

从尾到头打印链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> reversePrint(ListNode* head) {
    if(head == nullptr) return vector<int>{};
    stack<ListNode*> node_stack{};
    while(head!=nullptr){
        node_stack.push(head);
        head = head->next;
    }

    vector<int> ans{};
    while(!node_stack.empty()){
        ans.push_back(node_stack.top()->val);
        node_stack.pop();
    }
    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
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if(preorder.empty() || inorder.empty() || preorder.size() != inorder.size()) return nullptr;
    return buildTree(preorder, inorder, 0, preorder.size()-1, 0, preorder.size()-1);
}

TreeNode* buildTree(vector<int>& preorder,
                    vector<int>& inorder,
                    int pre_left, 
                    int pre_right,
                    int in_left,
                    int in_right){
    if(pre_left > pre_right || in_left>in_right) return nullptr;

    //1. 创建根节点
    TreeNode* root = new TreeNode(preorder[pre_left]);
    root->left  = nullptr;
    root->right = nullptr;

    //2. 寻找根节点在中序遍历中的位置
    if(pre_left == pre_right && in_left == in_right && preorder[pre_left] == inorder[in_left]) return root;
    int root_index = -1;
    for(int i=in_left;i<=in_right;++i){
        if(inorder[i] == root->val){
            root_index = i;
            break;
        }
    }
    if(root_index == -1) return nullptr;

    //3. 计算左右子树长度
    int left_length  = root_index - in_left;
    int right_length = in_right - in_left - left_length;

    //4. 遍历左右子树
    root->left  = buildTree(preorder, inorder, pre_left+1, pre_left+left_length, in_left, in_left+left_length-1);
    root->right = buildTree(preorder, inorder, pre_left+left_length+1, pre_right, in_left+left_length+1, in_right);
    return root;
}

用两个栈实现队列

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
class CQueue {
private:
    stack<int> first{};
    stack<int> second{};
public:
    CQueue() {

    }
    void appendTail(int value) {
        first.push(value);
    }
    
    int deleteHead() {
        int ans = 0;
        if(second.empty()){
            while(!first.empty()){
                second.push(first.top());
                first.pop();
            }
        }
        if(second.empty()) return -1;
        ans = second.top();
        second.pop();
        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
int minArray(vector<int>& numbers) {
    if(numbers.empty()) return 0;
    int index1 = 0;
    int index2 = numbers.size()-1;
    int mid    = 0;
    while(numbers[index1] >= numbers[index2]){
        if(index2 - index1 == 1) {
            return numbers[index2];
        }
        mid = index1 + (index2 - index1)/2;
        if(numbers[index1] == numbers[index2] && numbers[index1] == numbers[mid]) 
            return minInOrder(numbers);

        if(numbers[mid] >= numbers[index1]) index1 = mid;
        else if(numbers[mid] <= numbers[index2]) index2 = mid;
    }
    return numbers[mid];

}
int minInOrder(vector<int>& numbers){
    int result = numbers[0];
    for(int i=0;i<numbers.size();i++){
        if(numbers[i] < result) result = numbers[i];
    }
    return result;
}

矩阵中的路径

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
bool exist(vector<vector<char>>& board, string word) {
    if(board.empty())    return false;
    else if(word.empty()) return true;

    int rows = board.size();
    int cols = board[0].size();

    vector<vector<int>> visited(rows, vector<int>(cols,0));

    for(int i=0;i<rows;++i){
        for(int j=0;j<cols;++j){
            if(dfs(board, word, i,j,0,visited)) return true;
        }
    }
    return false;
}
bool dfs(vector<vector<char>>& board, string& word, int row, int col, int length, vector<vector<int>>& visited){
    if(length == word.size()) return true;
    bool hasPath = false;
    if(row >= 0 && row < board.size() && col >=0 && col < board[0].size() && word[length] == board[row][col] && !visited[row][col]){
        ++length;
        visited[row][col]= true;

        hasPath = dfs(board, word, row+1,col,   length,visited) ||
            dfs(board, word, row-1,col,   length,visited) ||
            dfs(board, word, row,  col+1, length,visited) ||
            dfs(board, word, row,  col-1, length,visited);

        if(hasPath == false){
            length--;
            visited[row][col] = false;
        }
    }
    return hasPath;
}

剪绳子

1
2


数值的整数次方

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
double myPow(double x, int n) {
    if(x - 0 <= 1e-6 && x-0 >= -1e-6){
        if(n == 0) return 1;
        else if(n < 0) return -1;
        else return 0;
    }

    unsigned int absN = 0;
    if(n>0) absN = n;
    else{
        if(n == INT_MIN) absN = 2147483648;
        else absN = -n;
    }

    double result = absPow(x, absN);
    return n > 0 ? result : 1/result;
}
double absPow(double x, unsigned int n){
    if(n == 0) return 1;
    double result = absPow(x, n>>1);
    result*=result;
    if((n & 1) == 1) result*=x;
    return result;

}

删除链表的结点

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
void DeleteNode(ListNode** head, ListNode* toBeDeleted){
    if(head == nullptr || *head == nullptr || toBeDeleted == nullptr) return;
    
    if(toBeDeleted->next != nullptr){
        ListNode* next = toBeDeleted->next;
        toBeDeleted->value = next->value;
        toBeDeleted->next  = next->next;
        
        delete next;
        next = nullptr;
    }
    
    else if(*head == toBeDeleted){
        delete toBeDeleted;
        toBeDeleted = nullptr;
        
        *head = nullptr;
    }
    
    else{
        ListNode* cur = *head;
        while(cur->next != toBeDeleted){
            cur = cur->next;
        }
        cur->next = nullptr;
        delete toBeDeleted;     //删除指针指向内存
        toBeDeleted = nullptr;  //将指针接地
    }
}

链表倒数第K个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
ListNode* getKthFromEnd(ListNode* head, int k) {
    if(head == nullptr) return head;

    ListNode* fast = head;
    ListNode* slow = head;
    for(int i=0;i<k-1;i++){
        if(fast->next == nullptr) return nullptr;
        fast = fast->next;
    }
    while(fast->next!=nullptr){
        fast= fast->next;
        slow= slow->next;
    }
    return slow;
}

环的入口节点

1
2


反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
ListNode* reverseList(ListNode* head) {
    ListNode* pre = nullptr;
    ListNode* cur = head;
    while(cur != nullptr){
        ListNode* next = cur->next;
        cur->next = pre;
        if(next == nullptr){
            break;
        }
        pre = cur;
        cur = next;
    }
    return cur;
}

不使用+-*/实现加法

1
2
3
4
5
6
7
8
int add(int a, int b) {
    while(b!=0){
        int plus = a ^ b;
        b = ((unsigned int)(a&b) << 1);
        a = plus;
    }
    return a;
}

第四章

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void dfs(vector<vector<int>>& ans,
         int sum,
         TreeNode* root,
         vector<int>& temp){
    if(root == nullptr) return;
    temp.push_back(root->val);
    sum -= root->val;

    if(sum == 0 && root->left == nullptr && root->right == nullptr) ans.push_back(temp);

    dfs(ans, sum, root->left, temp);
    dfs(ans, sum, root->right, temp);

    temp.pop_back();

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

复杂链表的复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    map<Node*, Node*> visited;
public:
    Node* copyRandomList(Node* head) {
        if(head == nullptr) return head;
        else if( visited[head] != nullptr) return visited[head];
        
        Node* copy = new Node(head->val);
        visited[head] = copy;
        copy -> next = copyRandomList(head->next);
        copy -> random = copyRandomList(head->random);
        return copy;

    }
};c

第五章

把数组排成最小的数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
static bool cmp(string a, string b)
{
    return a+b < b+a;
}

string minNumber(vector<int>& nums)
{
    vector<string> str_num;
    for(int i: nums)
        str_num.push_back(to_string(i));

    sort(str_num.begin(), str_num.end(), cmp);

    string rec = "";
    for(string i: str_num)
        rec += i;

    return rec;
}

最长不含重复字符的子字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size() == 0) return 0;
        int max_str = 0;
        int left = 0;          //队列左侧
        unordered_set<int> lookup{};   //用无序set作为队列
        for(int i=0;i<s.size(); ++i){  //遍历s
            while(lookup.find(s[i]) != lookup.end()){   //右侧元素已经出现在字符串中
                lookup.erase(s[left]);         //弹出队列左侧元素，直到右侧元素不在当前字符串中
                left++;                        //窗口左侧右移
            }
            max_str = max(max_str, i-left+1);
            lookup.insert(s[i]);              //添加右侧元素
        }
        return max_str;
    }
};

二叉树类题目

对称二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

解答

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
//解法一：递归
bool isSymmetric(TreeNode* left, TreeNode* right){
    if(left == nullptr && right == nullptr) return true;
    if(left == nullptr || right == nullptr || left->val != right->val) return false;
    return isSymmetric(left->left,right->right)&&isSymmetric(left->right,right->left);
}
bool isSymmetric(TreeNode* root) {
    if(root == nullptr) return true;
    return isSymmetric(root->left,root->right);
}

//解法二：迭代
bool isSymmetric(TreeNode* root) {
    if(root == nullptr) return true;
    queue<TreeNode*> node_queue{};
    node_queue.push(root->left);
    node_queue.push(root->right);
    while(!node_queue.empty()){
        TreeNode* left = node_queue.front();
        node_queue.pop();
        TreeNode* right = node_queue.front();
        node_queue.pop();

        if(left == nullptr && right == nullptr) continue;
        else if(left == nullptr || right == nullptr || left->val != right->val) return false;

        node_queue.push(left->left);
        node_queue.push(right->right);
        node_queue.push(left->right);
        node_queue.push(right->left);
    }
    return true;
}

二叉树的深度

题目描述

输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。

例如：

给定二叉树 [3,9,20,null,null,15,7]，

  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

解答

  1. 递归法
  1. 迭代法

数学

不使用+-×/实现加法

解答

13二进制为：1101，9二进制为：1001。

十进制是遇到大于等于10就保留余数，然后进位1。
那对应到二进制，就是遇到2就保留余数0，然后进位1。（二进制位之和不可能大于2）

计算二进制1101+1001：
1.计算不进位的和。从左到右，第1位为0，第2位为1，第3位为0，第4位为0，结果为0100；
2.计算进位。从左到右，第1位进位1，第2、3位没有进位，第4位进位1，结果为1001。不对，进位右边要补0，正确结果是10010。

计算二进制0100+10010：
1.计算不进位的和：10110；
2.计算进位：无。

因此结果为10110=22。

1）分析上面对二进制的计算过程，不难发现：
1.计算不进位的和，相当于对两个数进制异或：1101^1001=0100；
2.计算进位，第1位相当于对两个数求与：1101&1001=1001，然后再对其进行左移1位：1001<<1=10010。
然后再重复以上两个步骤。这里再异或一次就得到结果了，没进位：0100^10010=10110=22。

2）计算a+b，等价于(a^b)+((a&b)<<1)。 由于公式中又出现了+号，因此要再重复2）这个等价的计算过程。 结束条件是：没有进位了1</sup>。

1
2
3
4
5
6
7
8
int add(int a, int b) {
    while(b!=0){                        //没有进位了
        int plus = a ^ b;               //不考虑进位的加法，即异或
        b = ((unsigned int)(a&b) << 1); //考虑进位，按位与后左移一位
        a = plus;
    }
    return a;
}

快速幂

1
2
3
4
5
6
7
8
9
10
11
int fast_pow(long long base,int index){  
    int ans = 1;
    while(index>0){
        if(index%2==1){
            ans*=base; //指数为计数，x^(2n+1)可以写为x*x^2n
        }
        index/=2;      //指数为偶数，那么可以将指数减半，底翻倍
        base*=base;    //可能溢出
    }
    return ans;
}

快速幂本质是通过二分法对幂指数进行求解，上面是快速幂的模板，需要牢记

参考文献

0%