承德网站建设方案,怎么做淘宝返利网站吗,网站建设套餐是什么意思,wordpress底部不显示1.无重复字符的最长子串 知识点#xff1a;滑动窗口
基本概念
窗口#xff1a;窗口是一个连续的子序列#xff0c;可以是固定长度或可变长度。滑动#xff1a;窗口在数据序列上移动#xff0c;可以是向左或向右。边界#xff1a;窗口的起始和结束位置。
应用场景
字符…1.无重复字符的最长子串 知识点滑动窗口
基本概念
窗口窗口是一个连续的子序列可以是固定长度或可变长度。滑动窗口在数据序列上移动可以是向左或向右。边界窗口的起始和结束位置。
应用场景
字符串匹配如KMP算法中的部分匹配表就是利用滑动窗口来优化字符串搜索。最大/最小子数组例如Kadane算法通过滑动窗口找到数组中的最大子数组和。窗口内元素的统计如统计窗口内元素的个数、总和、平均值等。数据流的实时处理在数据流中滑动窗口可以用来处理固定时间范围内的数据。滑动窗口协议在网络通信中滑动窗口用于流量控制和拥塞避免。
实现方式
固定窗口窗口大小不变通过移动窗口的起始或结束位置来遍历整个数据序列。可变窗口窗口大小可以根据需要变化通常用于处理动态数据集合。
示例代码Python
def max_subarray_sum(nums):max_sum float(-inf)current_sum 0start 0for end in range(len(nums)):current_sum nums[end]while current_sum max_sum and start end:max_sum current_sumcurrent_sum - nums[start]start 1return 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.hint 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.htypedef 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[i1];nums[i1] 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.hint 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 foundprintf(大马%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。 循环结束后打印出所有有效组合的总数。
