代码编织梦想

题目:

代码:已编译通过,并测试,如有问题,请在下面留言。

#include <stdio.h>
#include <stdlib.h>

int get_windows(int *array, int array_length, int window_len){
	int *assist_queue = NULL;	//辅助队列
	int head_pos, tail_pos;
	int queue_len;
	int i;
	
	if(window_len > array_length || array_length <= 0 || window_len <= 0 || !array){
		return -1;
	}

	//1. 初始化
	assist_queue = calloc(sizeof(int), array_length);
	if(!assist_queue) return -1;
	head_pos = 0;
	tail_pos = 0;
	queue_len = 0;
	
	//2. 查找
	printf("[");
	//i每加一次,窗口向前滑动一次
	for(i = 0; i < array_length; i++){
		if(queue_len > 0){
			//超出窗口范围,则删除
			if(assist_queue[head_pos] <= i - window_len){
				head_pos += 1;
				queue_len -= 1;
			}

			//从右向左删除列表中小于当前值的项
			while(array[assist_queue[tail_pos - 1]] <= array[i] && tail_pos > head_pos){
				tail_pos = tail_pos - 1;
				queue_len = queue_len - 1;
			}
		}

		//入队列
		assist_queue[tail_pos] = i;
		queue_len += 1;
		tail_pos += 1;

		//达到窗口大小,输出窗口内最大值(最左边)
		if(i + 1 >= window_len){
			printf("%d,", array[assist_queue[head_pos]]);
		}
	}

	printf("]\n");

	free(assist_queue);
	assist_queue = NULL;

	return 0;
}

int main(){
	int array[10] = {19,12,12,2,13,14,123,1212,122,211};
	int array_length = 10;
	int window_len = 4;

	get_windows(array, array_length, window_len);

	return 0;
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 本文链接: https://blog.csdn.net/stella_alash/article/details/110944755

LeetCode-860-爱代码爱编程

860. 柠檬水找零 在柠檬水摊上,每一杯柠檬水的售价为 5 美元。 顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。 每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。 注意,一开始你手头没有任何零钱。 如果你能给每位顾客正确找零,

荷兰国旗问题-爱代码爱编程

荷兰国旗问题 给定一个数组arr,和一个数num,请把小于num的数放在数组的左边,等于num的数放在数组的中间,大于num的数放在数组的右边。 要求额外空间复杂度O(1),时间复杂度O(N) 1.分析 使用less指针指向给定数组区间的左边的前一个位置 使用more指针指向此区间右侧的后一个位置 使用cur指针指向当前元素若cur的值小于

2020/12/9 栈队列堆(牛客网)-爱代码爱编程

数组与矩阵 栈的压入、弹出序列(牛客网) 栈的压入、弹出序列(牛客网) 题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出

【Lintcode】1732. Snakes and Ladders-爱代码爱编程

题目地址: https://www.lintcode.com/problem/snakes-and-ladders/description 给定一个 N × N

算法设计与分析(王晓东 教材解析-爱代码爱编程

算法 一、算法定义 算法的性质: 输入:有零个或多个由外部提供的量作为算法的输入输出:算法产生至少一个量作为输出确定性:组成算法的每条指令是清晰的,无歧义的有限性:算法中每条指令的执行次数是有限的,执行每条指令的时间也是有限的算法的复杂度分析 ​ 分为时间复杂度和空间复杂度 主定理证明 时间复杂度分析符号说明 Θ – 等于 f ( n

(最详细合理代码)C++实现图的深度优先遍历、广度优先遍历和拓扑排序算法-爱代码爱编程

图的邻接矩阵和邻接表矩阵 void createGraph(vector<vector<int>>& edge, vector<vector<int>>& edge1,int start, int end, vector<int> inDegree) { edge[start]

python力扣刷题记录——1480. 一维数组的动态和-爱代码爱编程

题目: 给你一个数组 nums 。数组「动态和」的计算公式为:runningSum[i] = sum(nums[0]…nums[i]) 。 请返回 nums 的动态和。 方法一: 执行用时: 44 ms 内存消耗: 13.5 MB class Solution: def runningSum(self, nums: List[int

2020/12/9 栈队列堆(牛客网)-爱代码爱编程

数组与矩阵 栈的压入、弹出序列(牛客网) 栈的压入、弹出序列(牛客网) 题目描述 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出

二叉树的实现、遍历及面试题-爱代码爱编程

树 树 如图就是一个树结构,最上边的叫「根节点」,最下边的叫「叶子节点」。根节点有多个子节点,叶子节点没有子节点。二叉树就是,每个节点最多有两个子节点的树。 树还有两种特殊类型,叫做「满二叉树」和「完全二叉树」。 满二叉树和完全二叉树 完全二叉树是指「最底层的叶子节点全都集中在左边,且其它层的节点数达到最大值」的树,当完全二叉树

(最详细合理代码)C++实现图的深度优先遍历、广度优先遍历和拓扑排序算法-爱代码爱编程

图的邻接矩阵和邻接表矩阵 void createGraph(vector<vector<int>>& edge, vector<vector<int>>& edge1,int start, int end, vector<int> inDegree) { edge[start]

Java语言程序设计与数据结构(基础篇)课后练习题 第十章(二)-爱代码爱编程

10.8 咳,这个代码太多,不推荐做了,想做的老铁照着以前的练习题8.12,按照题目改改就行,很简单。 10.9 import java.util.ArrayList; import java.util.List; public class dishizhang { public static void main(String[] args) {

Leetcode(Python3) 19. Remove Nth Node From End of List-爱代码爱编程

The question is :Given the head of a linked list, remove the nth node from the end of the list and return its head. A follow-up question: Could you do this in one pass? Example