HOT100与剑指Offer

2025/2/22 2:13:38 来源：https://blog.csdn.net/qq_43264167/article/details/139515033 浏览: 次关键词：HOT100与剑指Offer

文章目录

前言
一、53. 最大子数组和（HOT100）
二、33. 链表中倒数第k个节点（剑指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;elsereturn NULL;}slow = pListHead;while (fast->next != NULL) {fast = fast->next;slow = slow->next;}return slow;}
};