当前位置：首页 > news >正文

HOT100与剑指Offer

news 来源：原创 2024/9/29 5:34:54

文章目录

前言
一、560. 和为 K 的子数组（HOT100）
二、17. 从1到n整数中1出现的次数（剑指Offer）
总结

前言

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

一、560. 和为 K 的子数组（HOT100）

560. 和为 K 的子数组
Note：枚举
可以枚举 [0…i]里所有的下标 j 来判断是否符合条件

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int count = 0;for (int start = 0; start < nums.size(); ++start) {int sum = 0;for (int end = start; end >= 0; --end) {sum += nums[end];if (sum == k) {count++;}}}return count;}
};

Note：前缀和 + 哈希表优化
对于[j…i] 这个子数组和为 k，可以转化为：
pre[j- 1]== pre[i] - k
我们建立哈希表，以和为键，出现次数为对应的值，记录 pre[i] 出现的次数，从左往右边更新哈希表边计算答案，那么以 i 结尾的答案即可在 O(1)时间内得到。最后的答案即为所有下标结尾的和为 k 的子数组个数之和。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {int res = 0;int pre = 0;unordered_map<int, int> umap;umap[0] = 1;for (int i = 0; i < nums.size(); i++) {pre += nums[i];if (umap.find(pre - k) != umap.end())res += umap[pre - k];umap[pre]++;}return res;}
};

二、17. 从1到n整数中1出现的次数（剑指Offer）

这题没在acwing中找到

Note：剑指offer的题目
使用字符串来表达大数，并采用第一个字符发生进位来查看是否到达最大值，最后使用碰到第一个非0的字符之后才开始打印。

class Solution {
public:bool Increment(char* num) {bool Index = false;int nOffset = 0;int nLength = strlen(num);for (int i = nLength - 1; i >= 0; i--) {int nSum = num[i] - '0' + nOffset;if (i == nLength - 1)nSum++;if (nSum >= 10) {if (i == 0)Index = true;else {nSum -= 10;nOffset = 1;num[i] = '0' + nSum;}}else {num[i] = '0' + nSum;break;}}return Index;}void printNum(char* num) {bool Index = true;int nLength = strlen(num);for (int i = 0; i < nLength; i++) {if (Index && num[i] != '0')Index = false;if (!Index)printf("%c", num[i]);}printf("\t");}int numberOf1Between1AndN_Solution(int n) {if (n <= 0) return -1;char *num = new char[n + 1];memset(num, '0', n);num[n] = '\0';while (!Increment(num)) {printNum(num);}delete[] num;}
};

Note：翻转数组

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