力扣喜刷刷--day1

登录 · 发表于 2026-2-27 12:58:10

1.无重复字符的最宗子串

知识点：滑动窗口

根本概念

窗口：窗口是一个一连的子序列，可以是固定长度或可变长度。
滑动：窗口在数据序列上移动，可以是向左或向右。
界限：窗口的起始和竣事位置。

应用场景

字符串匹配：如KMP算法中的部分匹配表就是利用滑动窗口来优化字符串搜刮。
最大/最小子数组：比方Kadane算法，通过滑动窗口找到数组中的最大子数组和。
窗口内元素的统计：如统计窗口内元素的个数、总和、均匀值等。
数据流的实时处置处罚：在数据流中，滑动窗口可以用来处置处罚固定时间范围内的数据。
滑动窗口协议：在网络通讯中，滑动窗口用于流量控制和拥塞克制。

实现方式

固定窗口：窗口巨细稳定，通过移动窗口的起始或竣事位置来遍历整个数据序列。
可变窗口：窗口巨细可以根据必要厘革，通常用于处置处罚动态数据聚集。

示例代码（Python）

def max_subarray_sum(nums):
max_sum = float('-inf')
current_sum = 0
start = 0
for end in range(len(nums)):
current_sum += nums[end]
while current_sum > max_sum and start <= end:
max_sum = current_sum
current_sum -= nums[start]
start += 1
return max_sum if max_sum != float('-inf') else 0
# 使用示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_sum(nums)) # 输出应该是6，对应子数组[4, -1, 2, 1]

复制代码

代码：

#include <stdio.h>
#include <string.h>
int lengthOfLongestSubstring(char *s) {
int n = strlen(s);
int charIndex[128]; // ASCII 128字符的索引表
for (int i = 0; i < 128; i++) {
charIndex[i] = -1; // 初始化索引表为-1
}
int left = 0, maxLength = 0;
for (int right = 0; right < n; right++) {
char currentChar = s[right];
if (charIndex[currentChar] >= left) {
left = charIndex[currentChar] + 1; // 更新左边界
}
charIndex[currentChar] = right; // 更新当前字符的最新索引
int currentLength = right - left + 1;
if (currentLength > maxLength) {
maxLength = currentLength;
}
}
return maxLength;
}
int main() {
char s[] = "abcabcbb";
int length = lengthOfLongestSubstring(s);
printf("最长不重复子串长度是: %d\n", length);
return 0;
}

复制代码

代码表明

初始化：
- charIndex：一个数组，用于存储每个字符的最新出现位置。我们假定字符串只包罗ASCII字符（共128个）。
- 将charIndex数组初始化为-1，体现字符尚未出现。
滑动窗口：
- left：滑动窗口的左界限。
- maxLength：记载最宗子串的长度。
- 遍历字符串 s 的每个字符，right 体现滑动窗口的右界限。
- 如果当前字符 s[right] 在charIndex中的值大于即是 left，阐明遇到了重复字符，必要更新左界限 left。
- 将当前字符的索引更新到charIndex中。
- 盘算当前窗口的长度 right - left + 1，并更新 maxLength。
返回效果：
- 遍历完成后，maxLength即为最长不含重复字符的子串的长度。

提交效果

2.前k个高频元素

知识点：哈希表和快速排序算法

哈希表（Hash Table）

哈希表是一种数据结构，它提供了快速的数据插入和查找功能。以下是哈希表的一些关键点：

根本头脑：哈希表通过利用哈希函数将输入（比方字符串大概数字）映射到一个大数组的索引上，这个数组称为哈希表的“桶”。
哈希函数：哈希函数的计划对于哈希表的性能至关紧张，它应该可以或许匀称地分布元素，以淘汰辩说。
辩说办理：当两个差别的输入通过哈希函数映射到同一个索引时，称为“辩说”。办理辩说的常见方法包罗链地点法（每个桶包罗一个链表来存储具有类似哈希值的元素）和开放寻址法（探求空的数组位置来存储元素）。
动态扩容：随着元素的增长，哈希表大概必要扩容以保持利用的服从，扩容通常涉及到重新盘算现有元素的哈希值并将它们重新分配到新的更大的数组中。
时间复杂度：理想情况下，哈希表的插入和查找利用可以到达均匀时间复杂度O(1)，但在最坏情况下（比方，全部元素都映射到同一个桶中）大概退化到O(n)。

快速排序算法（Quick Sort）

快速排序是一种高效的排序算法，接纳分治法的计谋来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。以下是快速排序的一些关键点：

选择基准：算法起首选择一个元素作为“基准”（pivot），然后重新分列数组，使得全部比基准小的元素都在基准的左边，全部比基准大的元素都在基准的右边。
分区利用：通太过区利用，数组被分为两个部分，然后递归地对这两个部分举行快速排序。
递归：递归是快速排序的核心，它将标题分解为更小的子标题，直到子标题富足小，可以直接办理。
时间复杂度：在均匀情况下，快速排序的时间复杂度为O(n log n)，但在最坏情况下（比方，数组已经排序或全部元素相当）时间复杂度会退化到O(n^2)。
原地排序：快速排序是一种原地排序算法，它不必要额外的存储空间，除了递归调用的栈空间。
稳固性：快速排序不是稳固的排序算法，类似的元素在排序后大概会改变它们原来的序次。

代码表明

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int key;
int value;
struct Node* next;
} Node;
Node** createHashTable(int size) {
Node** hashTable = (Node**)malloc(sizeof(Node*) * size);
for (int i = 0; i < size; i++) {
hashTable[i] = NULL;
}
return hashTable;
}
int getHashValue(int key, int size) {
return abs(key % size);
}
void insert(Node** hashTable, int key, int size) {
int index = getHashValue(key, size);
Node* node = hashTable[index];
Node* prev = NULL;
while (node != NULL) {
if (node->key == key) {
node->value++;
return;
}
prev = node;
node = node->next;
}
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->key = key;
newNode->value = 1;
newNode->next = NULL;
if (prev == NULL) {
hashTable[index] = newNode;
} else {
prev->next = newNode;
}
}
int partition(Node** nums, int left, int right) {
int pivot = nums[right]->value;
int i = left - 1;
for (int j = left; j < right; j++) {
if (nums[j]->value >= pivot) {
i++;
Node* temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
Node* temp = nums[i+1];
nums[i+1] = nums[right];
nums[right] = temp;
return i + 1;
}
void quickSort(Node** nums, int left, int right) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
quickSort(nums, left, pivotIndex - 1);
quickSort(nums, pivotIndex + 1, right);
}
}
int* topKFrequent(int* nums, int numsSize, int k, int* returnSize) {
int hashSize = numsSize * 2;
Node** hashTable = createHashTable(hashSize);
for (int i = 0; i < numsSize; i++) {
insert(hashTable, nums[i], hashSize);
}
int uniqueNums = 0;
for (int i = 0; i < hashSize; i++) {
Node* node = hashTable[i];
while (node != NULL) {
uniqueNums++;
node = node->next;
}
}
Node** frequencyArray = (Node**)malloc(sizeof(Node*) * uniqueNums);
int index = 0;
for (int i = 0; i < hashSize; i++) {
Node* node = hashTable[i];
while (node != NULL) {
frequencyArray[index++] = node;
node = node->next;
}
}
quickSort(frequencyArray, 0, uniqueNums - 1);
*returnSize = k;
int* result = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; i++) {
result[i] = frequencyArray[i]->key;
}
return result;
}

复制代码

包罗尺度输入输出头文件stdio.h和尺度库头文件stdlib.h。
界说了一个结构体Node，包罗一个整数key，一个整数value和一个指向Node的指针next。
界说了一个函数createHashTable，它担当一个整数size作为参数，创建一个巨细为size的哈希表，并初始化全部元素为NULL。
界说了一个辅助函数getHashValue，它担当一个整数key和一个整数size，返回哈希表中对应的索引位置。
界说了一个insert函数，它担当一个哈希表指针、一个整数key和一个整数size，用于将键值对插入到哈希表中。如果键已经存在，则增长其值。
界说了一个partition函数，用于快速排序中的分区利用。
界说了一个quickSort函数，用于对节点数组举行快速排序。
界说了紧张的函数topKFrequent，它担当一个整数数组nums、数组的巨细numsSize、必要找出的前k个最频仍元素的数目以及一个指向整数的指针returnSize。这个函数起首创建一个哈希表，然后统计每个元素出现的次数，接着将统计效果放入一个数组中，对数组举行快速排序，末了返回出现次数最多的前k个元素。

提交效果

3.百马百担

100 匹马驮 100 担货，已知一匹大马驮 3 担，一匹中马驮 2 担，两匹小马驮 1 担。试编写步调盘算大、中、小马的全部大概组合数目。

#include <stdio.h>
int main() {
int count = 0;
for (int big = 0; big <= 100 / 3; big++) {
for (int medium = 0; medium <= 100 / 2; medium++) {
int small = 100 - big - medium;
if ((3 * big + 2 * medium + small) == 100) {
// Valid combination found
printf("大马：%d 匹，中马：%d 匹，小马：%d 匹\n", big, medium, small);
count++;
}
}
}
printf("共有 %d 种可能的组合。\n", count);
return 0;
}

复制代码

代码表明

界说了一个count变量，用于统计有效组合的数目。
外层循环变量big从0开始，到100 / 3竣事，由于每匹大马的重量是3单元，以是最多有33匹大马（100 / 3向上取整）。
内层循环变量medium从0开始，到100 / 2竣事，由于每匹中马的重量是2单元，以是最多有50匹中马。
盘算small的值，它是100减去big和medium的总和。
利用一个if语句查抄3 * big + 2 * medium + small是否即是100。如果即是，阐明找到了一个有效的组合，并打印出来。
每次找到有效组适时，count变量增长1。
循环竣过后，打印出全部有效组合的总数。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金

本帖子中包含更多资源

浏览过的版块