2022-11-15

字数统计: 4k字 | 阅读时长: 19分

剑指offer-3

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

class Solution {
public:
    unordered_map <char, int> map;
    char firstUniqChar(string s) {
        for(int i = 0; i < s.size(); i++) {
            map[s[i]]++;
        }
        for(int i = 0; i < s.size(); i++) {
            if(map[s[i]] == 1) {
                return s[i];
            }
        }
        return ' ';
    }
};

剑指 Offer 51. 数组中的逆序对 - 力扣（LeetCode）

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

常规的思想：使用两重循环，但是会超时。

使用归并排序的思想，

时间复杂度 O(N \log N)，不会超时

//归并排序
class Solution {
public:
    int reversePairs(vector<int>& nums) {
        vector<int> tmp(nums.size());
        return mergeSort(0, nums.size() - 1, nums, tmp);
    }
private:
    int mergeSort(int l, int r, vector<int>& nums, vector<int>& tmp) {
        // 终止条件
        if (l >= r) return 0;
        // 递归划分
        int m = (l + r) / 2;
        int res = mergeSort(l, m, nums, tmp) + mergeSort(m + 1, r, nums, tmp);
        // 合并阶段
        int i = l, j = m + 1;
        for (int k = l; k <= r; k++)
            tmp[k] = nums[k];   //全部暂存到tmp
        for (int k = l; k <= r; k++) {
            if (i == m + 1)
                nums[k] = tmp[j++]; //代表左子数组已合并完，因此添加右子数组当前元素 tmp[j]tmp[j]
            else if (j == r + 1 || tmp[i] <= tmp[j])
                nums[k] = tmp[i++]; // j == r + 1代表右子数组已合并完；tmp[i] <= tmp[j]代表添加左子数组当前元素 tmp[i]
            else {
                nums[k] = tmp[j++];
                res += m - i + 1; // 统计逆序对，第i个元素大于第j个元素，则i到m之间的元素都大于i，也就大于j，因此加m - i + 1个逆序对
            }
        }
        return res;
    }
};

剑指 Offer 52. 两个链表的第一个公共节点 - 力扣（LeetCode）

输入两个链表，找出它们的第一个公共节点。思路就是A指针先遍历A链表，遍历完再遍历B。B指针先遍历B链表，再遍历A链表，两者相遇的节点即为相交节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* A = headA;
        ListNode* B = headB;
        while(A != B) {
            if(A != NULL) {
                A = A->next;
            }
            else {
                A = headB;
            }
            if(B != NULL) {
                B = B->next;
            }
            else {
                B = headA;
            }
        }
        return A;
    }
};

剑指 Offer 43. 1～n 整数中 1 出现的次数 - 力扣（LeetCode）

输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。

例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。

class Solution {
public:
    long countDigitOne(long n) {
        long digit = 1, res = 0;
        long high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res = res + high * digit;
            else if(cur == 1) res = res + high * digit + low + 1;
            else res = res + (high + 1) * digit;
            low = low + cur * digit;
            cur = high % 10;
            high = high / 10;
            digit = digit * 10;
        }
        return res;
    }
};

剑指 Offer 44. 数字序列中某一位的数字 - 力扣（LeetCode）

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。

请写一个函数，求任意第n位对应的数字。

class Solution {
public:
    int findNthDigit(int n) {
        int digit = 1;	//digit代表个位，十位
        long start = 1;	//start代表digit位数最开始的一个数字
        long count = 9;	//count代表由1到digit位组成的数一共多少位
        while(n > count) {
            n = n - count;
            digit = digit + 1;
            start = start * 10;
            count = 9 * start * digit;
        }
        long num = start + (n - 1) / digit;     //找到对应的数字
        string s = to_string(num);
        return s[(n - 1) % digit]  - '0';
    }
};

剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode）

给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

动态规划的思想：如果前面的两个数在10到25之间，就有dp[i - 1] + dp[i - 2]中翻译方法，否则就有dp[i - 1] 中翻译方法。

class Solution {
public:
    int translateNum(int num) {
        string str = to_string(num);
        int size = str.size();
        vector <int> dp(size + 1);
        dp[0] = 1;
        dp[1] = 1;
        if(size < 2) {
            return size;
        }
        for(int i = 2; i <= size; i++) {
            if(str[i - 2] == '1' || (str[i - 2] == '2' && str[i - 1] <= '5')) {
                dp[i] = dp[i - 1] + dp[i - 2];
            }
            else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[size];
    }
};

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode）

统计一个数字在排序数组中出现的次数。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        unordered_map <int, int> map;
        for(int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        return map[target]; 
    }
};

剑指 Offer 47. 礼物的最大价值 - 力扣（LeetCode）

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

动态规划经典题型了。

class Solution {
public:
    int maxValue(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int> (n, 0));
        dp[0][0] = grid[0][0];
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 && j == 0) {
                    continue;
                }
                else if(i == 0 && j > 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                }
                else if(j == 0 && i > 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                }
                else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
};

剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode）

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //双指针法
        unordered_set <char> set;
        int slow = 0;
        int fast = 0;
        int result = 0;
        for(int slow = 0; slow  < s.size(); slow ++) {      //双指针的算法
            if(slow == 0) {
                while(fast < s.size() && !set.count(s[fast])) {
                    set.insert(s[fast]);
                    fast++;
                }
                result = fast - slow;
            }
            else {
                set.erase(s[slow - 1]);
                while(fast < s.size() && !set.count(s[fast])) {
                    set.insert(s[fast]);
                    fast++;
                }
                result = max(result, fast - slow);
            }
        }
        return result;
    }
};

剑指 Offer 49. 丑数 - 力扣（LeetCode）

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

//丑数应该是1*2, 1*3, 1*5, 2*2, 2*3, 2*5, 3*2, 3*3, 3*5, ... , n1 *2, n1 * 3, n1 * 5, n2 * 2, n3* 3, n2 * 5排序后得到
class Solution {
public:
    int nthUglyNumber(int n) {
        vector <int> dp(n, 0);
        dp[0] = 1;
        int a = 0, b = 0, c = 0;
        for(int i = 1; i < n; i++) {
            int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
            dp[i] = min(min(n2, n3), n5);
            if(dp[i] == n2) {
                a++;    // 第a个数已经通过乘2得到了一个新的丑数，那下个需要通过乘2得到一个新的丑数的数应该是第(a+1)个数
            }
            if(dp[i] == n3) {
                b++;
            }
            if(dp[i] == n5) {
                c++;
            }
        }
        return dp[n - 1];
    }
};

剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode）

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i = 0;
        for(i = 0; i < nums.size(); i++) {
            if(nums[i] != i) {
                return i;
            }
        }
        return i;
    }
};

剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode）

给定一棵二叉搜索树，请找出其中第 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 {
private:
    int res;
public:
    int kthLargest(TreeNode* root, int k) {
        DFS(root, k);
        return res;
    }
    void DFS(TreeNode* node, int& k) {
        if(node->right != NULL) {
            DFS(node->right, k);
        }
        if(--k == 0) {
            res = node->val;
            return;
        }
        if(node->left != NULL) {
            DFS(node->left, k);
        }
    }
};

剑指 Offer 55 - I. 二叉树的深度 - 力扣（LeetCode）

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

例如：

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

/**
 * 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:
    int maxDepth(TreeNode* root) {
        if(root == NULL) return 0;
        int depth = 0;
        queue <TreeNode*> que;
        if(root != NULL) que.push(root);
        while(!que.empty())
        {
            depth++;
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
                TreeNode* node = que.front();
                que.pop();
                if(node->left != NULL) que.push(node->left);
                if(node->right != NULL) que.push(node->right);
            }
        }
        return depth;
    }
};

剑指 Offer 55 - II. 平衡二叉树 - 力扣（LeetCode）

输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
// -1 表示已经不是平衡二叉树了，否则返回值是以该节点为根节点树的高度
class Solution {
public:
    int getHeight(TreeNode* node)
    {
        if(node == NULL)    return 0;   //终止条件
        int leftHeight = getHeight(node->left);
        if(leftHeight == -1)    return -1;
        int rightHeight = getHeight(node->right);
        if(rightHeight == -1)   return -1;
        return abs(leftHeight - rightHeight) > 1? -1 : 1 + max(leftHeight, rightHeight);	//叶子节点leftHeight和rightHeight都是0，因此返回1
    }
    bool isBalanced(TreeNode* root) {
        if(getHeight(root) == -1)
        return false;
        else
        return true; 
    }
};

剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣（LeetCode）

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

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        unordered_map <int, int> map;
        vector <int> result;
        for(int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(map[nums[i]] == 1) {
                result.push_back(nums[i]);
            }
        }
        return result;
    }
};

还有一种异或的方法，效率更高：

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int x = 0, y = 0, n = 0, m = 1;
        for(int num : nums)         // 1. 遍历异或
            n ^= num;
        while((n & m) == 0)         // 2. 循环左移，计算 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. 返回出现一次的数字
    }
};

剑指 Offer 56 - II. 数组中数字出现的次数 II - 力扣（LeetCode）

上一题稍微修改一下就行了。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map <int, int> map;
        int result;
        for(int i = 0; i < nums.size(); i++) {
            map[nums[i]]++;
        }
        for(int i = 0; i < nums.size(); i++) {
            if(map[nums[i]] == 1) {
                result = nums[i];
                break;
            }
        }
        return result;
    }
};

剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode）

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_set <int> set;
        vector <int> result;
        for(int i = 0; i < nums.size(); i++) {
            if(set.count(target - nums[i]) != 0) {
                result.push_back(target - nums[i]);
                result.push_back(nums[i]);
                break;
            }
            else {
                set.insert(nums[i]);
            }
        }
        return result;
    }
};

剑指 Offer 57 - II. 和为s的连续正数序列 - 力扣（LeetCode）

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。

序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

双指针法，求和计算

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int i = 1, j = 2, s = 3;
        vector<vector<int>> res;
        while(i < j) {  //i < j确保最少有两个元素
            if(s == target) {
                vector<int> ans;
                for(int k = i; k <= j; k++)
                    ans.push_back(k);
                res.push_back(ans);
            }
            if(s >= target) {
                s -= i;
                i++;
            } else {
                j++;
                s += j;
            }
        }
        return res;
    }
};

剑指 Offer 58 - I. 翻转单词顺序 - 力扣（LeetCode）

输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。

class Solution {
public:
    void reverse(string& s, int start, int end) {
        for(int i = start, j = end; i < j; i++, j--) {      //双指针
            swap(s[i], s[j]);
        }
    }

    void removespace(string &s) {   //将多余的空格全部删除
        int slow = 0;
        for(int i = 0; i < s.size(); i++) {
            if(s[i] != ' ') {   //s[i]不是空格才处理
                if(slow != 0) s[slow++] = ' '; //不是第一个单词，就加上一个空格
                while(s[i] != ' ' && i < s.size()) {
                    s[slow++] = s[i++];     //注意这里是while，也就是要将整个单词都copy过来
                }
            }
        }
        s.resize(slow);
    }
    string reverseWords(string s) {
        removespace(s);
        reverse(s, 0, s.size() - 1);    //全局反转一次
        int start = 0;
       for(int i = 0; i <= s.size(); i++) {
           if(s[i] == ' ' || i == s.size()) {
                reverse(s, start, i - 1);   //对单词反转一次
                start = i + 1;
            }
        }
        return s;
    }
};

剑指 Offer 59 - I. 滑动窗口的最大值 - 力扣（LeetCode）

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

单调队列的思想，可以自己实现一个单调队列，队列从大到小排列，队列的front应该对应滑动窗口中的最大值。

//单调队列的思想, 始终保持队列的front对应的是滑动窗口内的最大值
class Solution {
private:
    class MyQueue{
        public:
        deque <int> que;
        void pop(int value)
        {
            if(!que.empty() && value == que.front())    //如果要移除的元素正好是队列的最大值，才会pop，也就是[3 -1 -3]时才pop
            que.pop_front();
        }
        void push(int value)
        {
            while(!que.empty() && value > que.back())   //push的时候保证单调队列，也就是队列从front到end是递减的
            {
                que.pop_back();
            }
            que.push_back(value);
        }
        int front()
        {
            return que.front(); //返回最大的
        }
    };
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        MyQueue que;
        vector <int> result;
        for(int i = 0; i < k; i++)
        {
            que.push(nums[i]);
        }
        result.push_back(que.front());
        for(int i = k; i < nums.size(); i++)
        {
            que.pop(nums[i - k]);   //移动窗口，只有要移除的元素正好是队列的最大值，才会pop
            que.push(nums[i]);
            result.push_back(que.front());
        }
        return result;
    }

};