当前位置：网站首页>【无标题】2022-7-24

【无标题】2022-7-24

2022-08-03 03:27:00 【骑驴_找马】

先正序计算每个位置左max

倒序计算每个位置右max

当前水位 = min（左max，右max）- 当前高度

蓄水量为各个位置蓄水量求和

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int trap(int* height, int heightSize){
	int out=0,max=0;
	int *tl=(int*)malloc(sizeof(int)*heightSize);
	memset(tl,0,heightSize);
	for(int i=1;i<heightSize;i++){
		max=max<height[i-1]?height[i-1]:max; 
		tl[i]=max;

	}
	max=0;
	for(int i=heightSize-2;i>0;i--){
		max=max<height[i+1]?height[i+1]:max; 
		int t=max<tl[i]?max:tl[i];
		t=t-height[i];
		if(t>0){
			out+=t;

		}
	}
	return out;
}

如果喜欢栈顶的甜点的学生存在，那么不管他们在队伍的哪个位置，必定会遍历到他。否则，一定无法继续拿掉栈顶甜点。

int countStudents(int* students, int studentsSize, int* sandwiches, int sandwichesSize){
    int arr[2];
    memset(arr, 0, sizeof(arr));
    for (int i=0; i<studentsSize; ++i) {
        ++arr[students[i]];
    }
    for (int i=0; i<sandwichesSize; ++i) {
        if (arr[sandwiches[i]] == 0) break;
        --arr[sandwiches[i]];
    }
    return arr[0] + arr[1];
}

先使用快慢指针找中点

反转后半部分链表

交叉合并两个链表



void reorderList(struct ListNode* head){

    struct ListNode *tmp = head;
    int ListLen = 1;
    while (tmp->next != NULL) {
        ListLen++;
        tmp = tmp->next;
    }

    struct ListNode **ListArry = malloc(sizeof(struct ListNode*) * ListLen);

    tmp = head;
    int i = 0;
    while (tmp->next != NULL) {
        ListArry[i] = tmp;
        i++;
        tmp = tmp->next;
    }
    ListArry[i] = tmp;

    tmp = head;
    struct ListNode *tmp2 = NULL;
    for (int i = 0; i < ListLen / 2; i++) {
        tmp2 = tmp->next;
        tmp->next = ListArry[ListLen - 1 - i];
        tmp = tmp->next;
        tmp->next = tmp2;
        tmp = tmp->next;
    }

    tmp->next = NULL;
}

typedef struct minstack{
    int val;
    int size;
    struct minstack *next;
    struct minstack *top;

} MinStack;

/** initialize your data structure here. */


MinStack* minStackCreate() {
    MinStack *root = (MinStack *)malloc(sizeof(MinStack));
    root->next = NULL;
    root->size = 0;
    root->top = NULL;
    return root;
}


void minStackPush(MinStack* obj, int x) {//入栈
    MinStack *node = minStackCreate();
    node->val = x;
    node->next = obj->top;
    obj->top = node;
    obj->size++;
}


void minStackPop(MinStack* obj) {//出栈
    if(obj->size == 0) return;
    MinStack *cur = obj->top;
    obj->top = obj->top->next;
    obj->size--;
    free(cur);
}


int minStackTop(MinStack* obj) {//获取栈顶的值
    if(obj->size == 0) return 0;
    return obj->top->val;
}


int minStackGetMin(MinStack* obj) {
    MinStack *cur = obj;  
    MinStack *top = obj->top; 
    if(cur->size == 0) return 0;
    int minret = cur->top->val;
    int size = cur->size;
    while(size--)
    {
        int temp = cur->top->val;
        minret = minret < temp ? minret : temp;
        cur->top = cur->top->next; 

    }

    cur->top = top; 
    return minret;
}

void minStackFree(MinStack* obj) {
    if(obj->size == 0)
    {
        return;
    }

    while(obj->size > 0)
    {
        MinStack *temp = obj->top;
        obj->top = obj->top->next;
        free(temp);
        obj->size--;
    }
}

用两个栈实现队列的入队、出队
一个栈只进行入栈，相当于入队
另一个栈只进行出栈，相当于出队

typedef struct {
    int top1; //栈1的栈顶指针
    int top2; //栈2的栈顶指针
    int size; //栈的大小
    int count; //队列中的元素个数
    int *S1; //栈1
    int *S2; //栈2
} MyQueue;

/** Initialize your data structure here. */
//初始化两个栈
MyQueue* myQueueCreate() {
    MyQueue* queue = (MyQueue*)malloc(sizeof(MyQueue));
    queue->top1 = -1;
    queue->top2 = -1;
    queue->size = 100;
    queue->count = 0;  //队列中当前元素个数0
    queue->S1 = (int*)malloc(queue->size * sizeof(int));
    queue->S2 = (int*)malloc(queue->size * sizeof(int));

    return queue;
}


void myQueuePush(MyQueue* obj, int x) {
    if(obj->top1 == -1)
    {
        while(obj->top2 != -1)
        {
            obj->S1[++obj->top1] = obj->S2[obj->top2--]; //将栈2中的所有元素保存到栈1
        }
    }
    obj->S1[++obj->top1] = x; //新元素入栈相当于入队
    
    obj->count++; //队列元素个数加一
}

int myQueuePop(MyQueue* obj) {
    if(obj->top2 == -1)
    {
        while(obj->top1 != -1)
        {
            obj->S2[++obj->top2] = obj->S1[obj->top1--]; //将栈1中的元素保存到栈2中
        }
    }
    obj->count--;
    return obj->S2[obj->top2--];

}

/*查看队头元素，即查看栈2的栈顶元素*/
int myQueuePeek(MyQueue* obj) {
    if(obj->top2 == -1)
    {
        while(obj->top1 != -1)
        {
            obj->S2[++obj->top2] = obj->S1[obj->top1--];
        }
    }
    return obj->S2[obj->top2];
}

/*队列为空返回true，否则返回false */
bool myQueueEmpty(MyQueue* obj) {
    if(obj->count == 0)
        return true;
    else
        return false;
}

void myQueueFree(MyQueue* obj) {
    free(obj->S1);
    free(obj->S2);
    free(obj);
}