HOT100与剑指Offer


前言

一个本硕双非的小菜鸡,备战24年秋招,计划刷完hot100和剑指Offer的刷题计划,加油!
根据要求,每一道题都要写出两种以上的解题技巧。

一、53. 最大子数组和(HOT100)

53. 最大子数组和
Note:贪心解题,从左向右迭代,一个个数字加过去
如果sum <0,重新开始找子序串

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        //类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值
        int result = INT_MIN;
        int numsSize = int(nums.size());
        int sum = 0;
        for (int i = 0; i < numsSize; i++)
        {
            sum += nums[i];
            result = max(result, sum);
            //如果sum < 0,重新开始找子序串
            if (sum < 0)
            {
                sum = 0;
            }
        }

        return result;
    }
};

Note:动态规划解题

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int size = nums.size();
        if (size <= 0) return 0;

        //1.确定dp数组
        //dp[i]:包括下标i(以nums[i]为结尾)的最大连续子序列和为dp[i]。
        vector<int> dp(size);

        //2.确定递推公式
        //dp[i] = max(nums[i], dp[i - 1] + nums[i]);

        //3.确定dp数组初始化
        dp[0] = nums[0];
        int res = dp[0];

        //4.确定遍历顺序
        for (int i = 1; i < nums.size(); i++) {
            dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            res = dp[i] > res ? dp[i] : res;
        }

        //5.确定推导结果
        return res;
    }
};

二、33. 链表中倒数第k个节点(剑指Offer)

链表中倒数第k个节点

Note:我们一共遍历两次:

第一次遍历得到链表总长度 n;
链表的倒数第 k 个节点,相当于正数第 n−k+1个节点。所以第二次遍历到第 n−k+1 个节点,就是我们要找的答案。
注意当 k>n 时要返回NULL。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, int k) {
        int size = 0;
        for (auto p = pListHead; p; p = p->next) size++;
        
        if (size < k) return NULL;
        
        auto p = pListHead;
        
        for (int i = 0; i < size - k; i++)
            p = p->next;
        
        return p;
    }
};

Note:双指针的经典应用,如果要找到倒数第n个节点,让fast移动n步,然后让fast和slow同时移动,直到fast指向链表末尾。此时返回slow所指向的节点就可以了。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL || k <= 0) return NULL;
        
        ListNode* fast = pListHead;
        ListNode* slow = NULL;
        
        for (unsigned int i = 0; i < k - 1; i++) {
            if (fast->next != NULL)
                fast = fast->next;
            else
                return NULL;
        }
        
        slow = pListHead;
        
        while (fast->next != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        
        return slow;
    }
};

总结

祝大家都能学有所成,找到一份好工作!

相关推荐

  1. HOT100Offer

    2024-06-11 04:16:01       8 阅读
  2. HOT100Offer

    2024-06-11 04:16:01       7 阅读
  3. HOT100Offer

    2024-06-11 04:16:01       11 阅读
  4. HOT100Offer

    2024-06-11 04:16:01       8 阅读
  5. HOT100Offer

    2024-06-11 04:16:01       10 阅读
  6. HOT100Offer

    2024-06-11 04:16:01       6 阅读
  7. offer A + B

    2024-06-11 04:16:01       32 阅读

最近更新

  1. svm 超参数

    2024-06-11 04:16:01       0 阅读
  2. shell判断语句练习

    2024-06-11 04:16:01       0 阅读
  3. MySQL周内训参照2、DDL与DML语句

    2024-06-11 04:16:01       0 阅读
  4. Scala学习笔记12: 高阶函数

    2024-06-11 04:16:01       0 阅读
  5. 详解 Flink CDC 的介绍和入门案例

    2024-06-11 04:16:01       0 阅读
  6. Nginx之Stream(TCP/UDP)负载均衡

    2024-06-11 04:16:01       0 阅读
  7. Sklearn简介、安装教程、入门学习

    2024-06-11 04:16:01       0 阅读

热门阅读

  1. 游戏心理学Day10

    2024-06-11 04:16:01       5 阅读
  2. 使用EFCore和Linq查询语句封装复杂的查询结果

    2024-06-11 04:16:01       3 阅读
  3. Python爬虫实现“自动重试”机制的方法(1)

    2024-06-11 04:16:01       3 阅读
  4. OpenAI 发布的 GPT-4o是什么,有什么功能?

    2024-06-11 04:16:01       3 阅读
  5. 算法训练营day52

    2024-06-11 04:16:01       3 阅读