堆-优先队列进阶:TopK-3D接雨水-C-Js-Rust语言描述

2022-05-09
阅读 7 分钟
2.1k
在之前的文章里,我分享了Js版的堆实现和C语言版的堆实现, 理解的话,堆的实现其实并不难,以大顶堆为例,简单归纳就是插入时候,比节点小,就不断向下沉,让更大的上浮,直到最大的上浮到根节点。

数据结构与算法: 堆 优先队列 JavaScript语言描述

2022-05-09
阅读 3 分钟
664
C语言可能受众小些,且略微不太好理解,今天就用JavaScript描述一个最小堆,其实是基于最小堆的优先队列,不过两者基本上么有什么太大的区别,无非堆是存最基础的数字,优先队列则储存的是一个结构体或者对象,有自己的key/value,有自己的属性。

双指针进阶-接雨水-Rust语言描述

2022-05-09
阅读 1 分钟
724
之前讲过,只要逐个找出每个点左右的最大值,即可得到可以接的雨水;维护左右两个指针,以及left_max, right_max,这篇文章是看到论坛里有个同学用Rust求解该题,结果花了144ms......

单调栈进阶-接雨水-最大矩形

2022-05-09
阅读 4 分钟
2.3k
1 前言在前阵子的一篇分享里,简单提到了单调栈这个数据结构,文章如下↓↓↓分享一个简单但挺有意思的算法题2-贪心-单调栈-动态规划当时只是用单调栈解决了股票问题,是最基础的入门示例,算是easy或者勉强medium级别,今天用单调栈来解决一些hard题目2 示例-接雨水42. 接雨水这是一道经典的面试题,解法有三种,一是正反遍...

分享一个简单但挺有意思的算法题2-贪心-单调栈-动态规划

2022-04-23
阅读 3 分钟
1.5k
*输入:prices = [7,1,5,3,6,4]输出:7解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。*

LeetCode PHP题解 4. 寻找两个正序数组的中位数

2020-11-04
阅读 2 分钟
1.6k
题目链接4. 寻找两个正序数组的中位数 难度:hard有点类似TopK问题,只是这里是有有序的,且是两个数组中寻找,二分找到中位数即可。解法1.合并排序暴力解法,略过不提2.二分求中位数将两个数组切割,假设A数组长度为m,切割位置为i,B数组长度为n,切割位置为j,则有: {代码...} 复杂度分析时间复杂度:O(min(m,n)),其...

LeetCode PHP题解 3. 无重复字符的最长子串

2020-10-30
阅读 2 分钟
1.7k
用一个数组做滑动窗口,每次right向右移动时候,判断该字符串是否在窗口内存在,若不存在则继续右移,记录当前窗口长度;若存在则将左边界置为窗口中该字符的右边。

LeetCode 题解与知识点 2. 两数相加 Add-Two-Numbers

2020-10-26
阅读 2 分钟
2.2k
题目链接2. Add-Two-Numbers 难度:$\color{#00965e}{medium}$知识点1.数据结构单链表数据结构基础,此处不赘述2.链表尾插法C 单链表头插法/尾插法/删除指定值结点解法简单累加留心进位用head记录头结点,head->next即题解需要的头结点复杂度分析时间复杂度:O(max(m,n)),其中 m,nm,n 为两个链表的长度。我们要遍历...

LeetCode 题解与知识点 1. 两数之和 Two Sum

2020-10-14
阅读 2 分钟
2.4k
题目链接1. Two Sum 难度:$\color{#00965e}{easy}$知识点1.哈希(散列)函数经典散列函数Times33应用非常广泛,核心算法如下: {代码...} laruence大佬有一篇文章讲过:PHP中的Hash算法 - 风雪之隅2.哈希碰撞处理方法2.1链地址法(拉链法)(广泛使用)即使用单向链表来处理哈希冲突的key;php,java都是使用该方法优点:处...