首页 💻 数据结构,📝 算法学习

写在前面: 听dalao们说去搬砖之前要刷剑指Offer, 所以就有了本篇文章, 题目代码默认语言为C++, 如有使用其他语言会在题目上标注出来的

leetcode传送门

https://leetcode-cn.com/problemset/lcof/


一、数组中重复的数字

展开查看详情

题目传送门

https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/

题意

给定一个数组, 找到其中任意一个重复出现的数字并返回

思路

额外开一个数组记录一下前面出现过的数字, 遍历数组, 如果该数字在前面出现过直接返回

代码

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int a[100005]; memset(a, 0, sizeof(a));
        for(auto it : nums){
            if(a[it] != 0) return it;
            else a[it]++;
        }
        return 0;
    }
};

二、二维数组中的查找

展开查看详情

题目传送门

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/

题意

给定一个有序的二维数组, 查找其中是否存在某个元素, 是返回 true , 否返回 false

思路

纵向遍历二维数组, 横向采用二分查找, 碰到则返回, 时间复杂度 $O(nlogm)$

代码

class Solution {
public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
        for(int i = 0; i < matrix.size(); i++){
            int k = lower_bound(matrix[i].begin(), matrix[i].end(), target) - matrix[i].begin();
            if(k >= 0 && k < matrix[i].size() && matrix[i][k] == target) return true;
        }
        return false;
    }
};

三、替换空格

展开查看详情

题目传送门

https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/

题意

给定一个字符串, 将其中所有空格替换为 "%20"

思路

另声明一个空字符串, 遇到空格则拼接 "%20" , 其他直接拼接原来的即可

代码

class Solution {
public:
    string replaceSpace(string s) {
        string t = "";
        for(auto it : s){
            if(it != ' ') t += it;
            else t += "%20";
        }
        return t;
    }
};

四、从尾到头打印链表

展开查看详情

题目传送门

https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

题意

输入一个链表的头节点, 从尾到头反过来返回每个节点的值(用数组返回)

思路

遍历链表存到数组, 执行 reverse 操作并返回

代码

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        vector<int> v; v.clear();
        while(head != NULL){
            v.push_back(head -> val);
            head = head -> next;
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

五、重建二叉树

展开查看详情

题目传送门

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/

题意

给定一颗二叉树的前序和中序遍历, 重建该二叉树

思路

给定前序序列的第一个数字是当前根节点, 而在中序序列中该数字左边的数是左子树, 右边的数是右子树, 按照这个思路递归建树即可

代码

class Solution {
private:
    unordered_map<int, int> mp;

public:
    void dfs(vector<int>& preorder, vector<int>& inorder, int l, int r, int k, TreeNode* fa) {
        fa -> val = preorder[k];
        fa -> left = (TreeNode*)malloc(sizeof(TreeNode));
        fa -> right = (TreeNode*)malloc(sizeof(TreeNode));
        if(l <= mp[preorder[k]] - 1)
            dfs(preorder, inorder, l, mp[preorder[k]] - 1, k + 1, fa -> left);
        else
            fa -> left = NULL;
        if(mp[preorder[k]] + 1 <= r)
            dfs(preorder, inorder, mp[preorder[k]] + 1, r, k + mp[preorder[k]] - l + 1, fa -> right);
        else
            fa -> right = NULL;
    }

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if(preorder.size() == 0 || inorder.size() == 0) return NULL;
        mp.clear(); for(int i = 0; i < inorder.size(); i++) mp[inorder[i]] = i;
        TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
        dfs(preorder, inorder, 0, preorder.size() - 1, 0, root);
        return root;
    }
};

六、用两个栈实现队列

展开查看详情

题目传送门

https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

题意

实现队列 push 和 pop 操作

思路

用数组模拟队列实现即可

代码

class CQueue {
private:
    int q[20005], s, e;

public:
    CQueue() {
        s = 0, e = 0;
    }
    
    void appendTail(int value) {
        q[s++] = value;
    }
    
    int deleteHead() {
        if(s == e) return -1;
        return q[e++];
    }
};

七、斐波那契数列

展开查看详情

题目传送门

https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/

题意

求斐波那契数列第 $n$ 项

思路

循环遍历

代码

class Solution {
private:
    const int mod = 1000000007;

public:
    int fib(int n) {
        if(n == 0 || n == 1) return n;
        int t, a = 0, b = 1;
        for(int i = 2; i <= n; i++){
            t = b;
            b = (a + b) % mod;
            a = t;
        }
        return b;
    }
};

八、青蛙跳台阶

展开查看详情

题目传送门

https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

题意

青蛙一次可以跳一节台阶或两节台阶, 问跳到第 $n$ 节台阶有多少种方案

思路

简单dp, 既然每次可以跳1或2, 那么第 $n$ 节台阶就是 $n - 1$ 和 $n - 2$ 节台阶转移过来的, 转移方程 $dp_i = dp_{i-1} + dp_{i-2}$

代码

class Solution {
private:
    const int mod = 1000000007;

public:
    int numWays(int n) {
        if(n <= 1) return 1;
        if(n == 2) return 2;
        int t, a = 1, b = 2;
        for(int i = 3; i <= n; i++){
            t = b;
            b = (a + b) % mod;
            a = t;
        }
        return b;
    }
};

九、旋转数组的最小数字

展开查看详情

题目传送门

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

题意

找出给定数组中的最小值

思路

遍历数组找最小值

代码

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int ans = 0x7f7f7f7f;
        for(auto it : numbers) ans = min(ans, it);
        return ans;
    }
};

十、矩阵中的路径

展开查看详情

题目传送门

https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof/

题意

给定一个矩阵和一个单词, 问其中相连的路径能否组成该单词

思路

dfs+剪枝

代码

class Solution {
private:
    bool flag; int l, r;
    int mv[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

public:
    void dfs(vector<vector<char>>& board, string word, int step, int x, int y) {
        if(flag) return;
        if(step == word.size()){flag = true; return;}
        for(int i = 0; i < 4; i++){
            int dx = x + mv[i][0], dy = y + mv[i][1];
            if(dx >= 0 && dx < l && dy >= 0 && dy < r && board[dx][dy] == word[step]){
                board[dx][dy] = '\0';
                dfs(board, word, step + 1, dx, dy);
                board[dx][dy] = word[step];
            }
        }
    }

    bool exist(vector<vector<char>>& board, string word) {
        if(word == "") return false;
        l = board.size(), r = board[0].size();
        for(int i = 0; i < l; i++){
            for(int j = 0; j < r; j++){
                flag = false;
                if(board[i][j] == word[0]){
                    if(word.size() == 1) return true;
                    board[i][j] = '\0';
                    dfs(board, word, 1, i, j);
                    board[i][j] = word[0];
                    if(flag) return true;;
                }
            }
        }
        return false;
    }
};

十一、机器人的运动范围

展开查看详情

题目传送门

https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/

题意

给定一个 $m * n$ 的矩阵, 机器人从 (0, 0) 点出发, 可以向上下左右走, 但是所到达的坐标数位和不能超过 $k$, 问机器人能走多少个格子

思路

bfs统计经历过的格子

代码

class Solution {
private:
    bool vis[105][105];
    int mv[4][2] = {1, 0, -1, 0, 0, 1, 0, -1};

    bool check(int x, int y, int k){
        int ans = 0;
        while(x){
            ans += (x % 10);
            x /= 10;
        }
        while(y){
            ans += (y % 10);
            y /= 10;
        }
        return ans <= k;
    }

public:
    int movingCount(int m, int n, int k) {
        int ans = 0;
        queue<pair<int, int> > q;
        q.push({0, 0}); vis[0][0] = true;
        while(!q.empty()){
            auto head = q.front();
            q.pop();
            for(int i = 0; i < 4; i++){
                int dx = head.first + mv[i][0];
                int dy = head.second + mv[i][1];
                if(dx >= 0 && dx < m && dy >= 0 && dy < n && !vis[dx][dy] && check(dx, dy, k)){
                    vis[dx][dy] = true;
                    q.push({dx, dy});
                }
            }
        }
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(vis[i][j]) ans++;
        return ans;
    }
};

十二、剪绳子

展开查看详情

题目传送门

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

题意

给定一段长度为 $n$ 的绳子, 分成若干段, 要使这些段绳子的乘积最大, 问这个最大的乘积

思路

$dp_i$ 表示长度为 $i$ 的绳子的答案, 则将比当前绳子短的绳子遍历一遍转移过来就行了, 转移方程 $dp_i = max(dp_i, max(dp_j * (i - j), j * (i - j)))$

代码

class Solution {
public:
    int cuttingRope(int n) {
        int dp[59] = {1, 1, 1};
        for(int i = 3; i <= n; i++)
            for(int j = 2; j < i; j++)
                dp[i] = max(dp[i], max(dp[j] * (i - j), j * (i - j)));
        return dp[n];
    }
};

十三、剪绳子Ⅱ

展开查看详情

题目传送门

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

题意

给定一段长度为 $n$ 的绳子, 分成若干段, 要使这些段绳子的乘积最大, 问这个最大的乘积, 答案对1000000007取模

思路

这个题的数据范围是1000, $dp$ 的时间复杂度是 $O(n^2)$ , 刚刚好可以卡过去, 看到官方题解是用数学证明了一下, 尽可能地把绳子分为长度为3的小段, 当然我看不懂那个证明 tnl , 贪心的时间复杂度是 $O(n)$
PS: Python

代码

class Solution:
    def cuttingRope(self, n: int) -> int:
        dp = [1] * 1005
        for i in range(3, n + 1):
            for j in range(2, i):
                dp[i] = max(dp[i], max(dp[j] * (i - j), j * (i - j)))
        return dp[n] % 1000000007

十四、二进制中1的个数

展开查看详情

题目传送门

https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/

题意

给定一个数, 求其二进制中1的个数

思路

lowbit
PS: Java

代码

public class Solution {
    // you need to treat n as an unsigned value
    public int lowbit(int x){
        return x & -x;
    }

    public int hammingWeight(int n) {
        int ans = 0;
        while(lowbit(n) != 0){n -= lowbit(n); ans++;}
        return ans;
    }
}

十五、数值的整数次方

展开查看详情

题目传送门

https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof/

题意

实现一个计算 $x^n$ 的函数

思路

快速幂

代码

class Solution {
public:
    double myPow(double x, int n) {
        long long b = n;
        if(b < 0) x = 1.0 / x, b = -b;
        double ans = 1.0;
        while(b){
            if(b & 1) ans *= x;
            x *= x;
            b >>= 1;
        }
        return ans;
    }
};

十六、打印从1到最大的n位数

展开查看详情

题目传送门

https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/

题意

给定 $n$, 打印从一开始到最大的 $n$ 位数

思路

没有思路

代码

class Solution {
public:
    int work(int n) {
        int res = 0;
        while(n--) res = res * 10 + 9;
        return res;
    }

    vector<int> printNumbers(int n) {
        vector<int> v;
        int maxx = work(n);
        for(int i = 1; i <= maxx; i++) v.push_back(i);
        return v;
    }
};

十七、删除链表的节点

展开查看详情

题目传送门

https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/

题意

删除单链表中的一个节点

思路

没有思路

代码

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head->val == val) return head->next;
        ListNode *pre = head, *cur = head->next;
        while(cur != nullptr && cur->val != val) {
            pre = cur;
            cur = cur->next;
        }
        if(cur != nullptr) pre->next = cur->next;
        return head;
    }
};

十八、正则表达式匹配

十九、表示数值的字符串

二十、调整数组顺序使奇数位于偶数前面

展开查看详情

题目传送门

https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

题意

给定一个数组, 要求调整位置让奇数在前半部分偶数在后半部分

思路

没有思路

代码

class Solution {
    public:
    vector<int> exchange(vector<int>& nums) {
        vector<int> v;
        for(auto it : nums) if(it & 1) v.push_back(it);
        for(auto it : nums) if(!(it & 1)) v.push_back(it);
        return v;
    }
};

二十一、链表中倒数第k个节点

展开查看详情

题目传送门

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

题意

找到链表中的倒数第 $k$ 个节点

思路

没有思路

代码

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        struct ListNode *p=head; int l;
        int num_node=0;
        while(p){
            p=p->next;
            num_node++;
        }
        l=num_node+1-k;
        while(--l){
            head=head->next;
        }
        return head;
    }
};

二十二、反转链表

展开查看详情

题目传送门

https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/

题意

反转链表

思路

没有思路

代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL || head->next==NULL) return head;
        ListNode* p = head;
        ListNode* q = p->next;
        p->next=NULL;
        while(q){
            ListNode* temp=q->next;
            q->next=p;
            p=q;
            q=temp;
        }
        return p;
    }
};

二十三、合并两个排序的链表

展开查看详情

题目传送门

https://leetcode-cn.com/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/

题意

合并两个链表

思路

没有思路

代码

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1) cur->next = l1;
        else cur->next = l2;
        return head->next;
    }
};




文章评论