7 liweiwei1419

尚未进行身份认证

我要认证

著名歌唱家,嘻嘻嘻嘻。

等级
TA的排名 1k+

「力扣」第 96 题:不同的二叉搜索树

题目链接方法一:动态规划这里 j 表示左子树的元素个数,最小是 0 ,最大是 i - 1。注意:这里 000 个结点构成的子树的个数为 111,这个值是我们需要的,因此需要多开 111 个空间。Java 代码:public class Solution { public int numTrees(int n) { int[] dp = new int[n + 1]; // 想清楚这个值很关键 dp[0] = 1; dp.

2020-07-15 09:38:42

「力扣」第 162 题:寻找峰值(中等)

题目链接说明:数组可能包含多个峰值,在这种情况下,返回任何一个峰值所在位置即可。Java 代码:public class Solution { public int findPeakElement(int[] nums) { int len = nums.length; int left = 0; int right = len - 1; // [left, right] while (left < r.

2020-07-15 04:38:24

「力扣」第 350 题:两个数组的交集 II (简单)

题目链接Java 代码:import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Solution { public int[] intersect(int[] nums1, int[] nums2) { Arrays.sort(nums1); Arrays.sort(nums2); int i = 0; .

2020-07-15 04:02:44

「力扣」第 120 题: 三角形最小路径和(中等)

「力扣」第 120 题: 三角形最小路径和(中等)掌握如何定义「状态」和写出「状态转移方程」。链接给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如,给定三角形:[ [2], [3,4],[6,5,7],[4,1,8,3]]自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。说明:如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。思路分析:关键的地方在于三角

2020-07-14 10:18:20

「力扣」第 30 场双周赛代码(前 3 题)

第 1 题:转变日期格式Java 代码:import java.util.HashMap;import java.util.Map;public class Solution { public String reformatDate(String date) { String[] split = date.split(" "); StringBuilder stringBuilder = new StringBuilder(); stri

2020-07-12 09:52:11

「力扣」第 195 场周赛代码(前 2 题)

比赛时间:北京时间 2020 年 6 月 28 日早 10:30再接再厉!第 1 题:判断路径是否相交Java 代码:import java.util.HashMap;import java.util.HashSet;import java.util.Map;import java.util.Objects;import java.util.Set;public class Solution { public boolean isPathCrossing(String path

2020-06-28 16:32:56

「力扣」第 29 场双周赛代码(前 3 题)

比赛时间:北京时间 2020 年 6 月 27 日晚 10:30再接再厉!第 1 题:https://leetcode-cn.com/problems/average-salary-excluding-the-minimum-and-maximum-salary/Java 代码:public class Solution { public double average(int[] salary) { int len = salary.length; dou

2020-06-28 16:28:58

「线段树」第 4 节:区间更新(单点更新)

区间更新(单点更新)想一想更新的步骤,根据画图分析。从树的根开始更新,先把数据更新了,再更新 tree。set方法 的设计与实现,其实是程式化的,这个过程熟悉了以后写起来,就会比较自然。最后不要忘记 merge 一下,从叶子结点开始,父辈结点,祖辈结点,直到根结点都要更新。Java 代码:public void set(int dataIndex, E val) { if (dataIndex < 0 || dataIndex >= data.length) { t

2020-06-26 04:39:56

「线段树」第 3 节:创建线段树与区间查询

根据原始数组创建线段树这一节的目标是:我们把员工的信息输入一棵线段树,让这棵线段树组织出领导架构。即已知 data 数组,要把 tree 数组构建出来。分析递归结构,重点体会:二叉树每做一次分支都是「一分为二」进行的,因此线段树是一棵二叉树;递归到底的时候,这个区间只有 111 个元素。设计私有函数,我们需要考虑:我们要创建的线段树的根结点的下标,这个下标是线段树的下标;对于线段树结点所要表示的 data 数组的区间的左端点是什么;对于线段树结点所要表示的 data 数组的区间的右端点是

2020-06-26 04:33:25

「线段树」第 2 节:写出预处理数组的结构

由于「线段树」是平衡二叉树,因此可以使用数组表示以前我们学习过「堆」,知道「堆」是一棵「完全二叉树」,因此「堆」可以用数组表示。基于此,我们很自然地想到可以用数组表示「线段树」;完全二叉树的定义:除了最后一层以外,其余各层的结点数达到最大,并且最后一层所有的结点都连续地、集中地存储在最左边;线段树虽然不是完全二叉树,但线段树是平衡二叉树,依然也可以用数组表示。如何构建线段树、如何实现区间查询、如何实现区间更新「自顶向下」递归构建线段树首先看看「线段树」长什么样;线段树是一种二叉树结构,不

2020-06-26 04:12:52

「线段树」第 1 节:线段树是原始数组的一个预处理数组

线段树(segment tree)又称「区间树」,是一个高级数据结构,应用的对象是「数组」;线段树是一种实现了高效的「区间查询」与「区间更新」的数据结构。前置知识:理解「前缀和」数组preSum[i] 表示 nums[0..i - 1] 里全部元素的和(一个数代表了原始数组的一个前缀区间的和);前缀和数组,就是一堆前缀和,可以用于:快速计算区间和(查询区间和 );区间 [i..j] 的和: preSum[j + 1] - preSum[i]。「前缀和数组」与「线段树」都是原始.

2020-06-26 03:49:52

「树状数组」第 4 节: 相关例题

其实下面这两个问题本质上是一个问题。例 1:《剑指 Offer 》第 51 题:逆序数的计算剑指 Offer 51. 数组中的逆序对。在数组中的两个数字如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数。样例输入:[1,2,3,4,5,6,0]输出:6分析:这道题最经典的思路是使用分治法计算,不过使用树状数组语义更清晰一些。Python 代码:class Solution(object): def inversePa

2020-06-26 03:00:29

「树状数组」第 3 节:理解 lowbit 操作

下面我们介绍一种很酷的操作,叫做 lowbit ,它可以高效地计算 2k2^k2k,即我们要证明:lowbit(i)=2k{\rm lowbit}(i) = 2^klowbit(i)=2k其中 kkk 是将 iii 表示成二进制以后,从右向左数,遇到 111 则停止时,数出的 000 的个数。通过 lowbit 高效计算 2k2^k2klowbit(i) = i & (-i)理解这行伪代码需要一些二进制和位运算的知识作为铺垫。首先,我们知道负数的二进制表示为:相应正数的二进制表示的

2020-06-26 02:53:59

「树状数组」第 2 节:理解预处理数组 C

「树状数组」第 2 节:理解预处理数组 C我们看看树状数组长什么样。树状数组的样子例 5我们以一个有 8 个元素的数组 A 为例(如上图),在数组 A 之上建立一个数组 C,使得数组 C 的形成如上的一个多叉树形状,数组 C 就形成了一个树状数组的结构。以下是两点说明:树状数组要建成动态的树形结构吗?不用。学习过堆、线段树的朋友一定知道,使用数组就能方便地索引左右孩子结点、双亲结点(因为规律特别容易找到),这样的树就不必创建成结点、指针那样的动态树形结构。如何解释「前缀和」查询和

2020-06-26 02:37:41

「树状数组」第 1 节:树状数组能解决的问题

关键词:位运算、前缀和的查询与更新。第 1 节 树状数组能解决的问题![image.png](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9jZG4ubmxhcmsuY29tL3l1cXVlLzAvMjAyMC9wbmcvMTM1NDE3Mi8xNTkzMTA4MDAzNjYyLTU5MzkwNTdhLWFkY2ItNDNlYi04ZjVjLWIzN2QxYjQwMjEyNi5wbmc?x-oss-process=image/format,png#align=left

2020-06-26 02:10:47

「力扣」第 787 题:K 站中转内最便宜的航班(深度优先遍历、广度优先遍历)

方法一:深度优先遍历(回溯算法)说明:航班没有重复,且不存在环路;每个航班的价格范围是 [1, 10000]。Java 代码:public class Solution { public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) { // 构建邻接矩阵 int[][] graph = new int[n][n]; for (int[] f

2020-06-15 14:13:04

「力扣」第 193 场周赛前 3 题代码(照例不做第 4 题)

说明:第 4 题不做是因为超纲不会做,本人非科班,没有时间去研究第 4 题。第 193 场周赛地址:https://leetcode-cn.com/contest/weekly-contest-193/第 1 题:一维数组的动态和一句话题解:其实就是求前缀和,注意有 1 个位置的下标偏移。题目链接:https://leetcode-cn.com/problems/running-sum-of-1d-array/Java 代码:import java.util.Arrays;pu

2020-06-14 13:45:02

「力扣」第 380 题:常数时间插入、删除和获取随机元素(哈希表、动态数组)

Java 代码:import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class RandomizedSet { /** * 动态数组 */ List<Integer> nums; /** * 用来建立每个数字和其在数组中的位置之间的对应关系 * key :真正插入的数

2020-06-12 17:01:11

「力扣」第 127 题:单词接龙(BFS)

Java 代码:import java.util.ArrayList;import java.util.Collections;import java.util.HashSet;import java.util.LinkedList;import java.util.List;import java.util.Queue;import java.util.Set;public class Solution { // 非标准 BFS 的写法 public int

2020-06-01 16:36:08

「力扣」第 1465 题:切割后面积最大的蛋糕(区间和)

说明:标签是乱起的。中文地址:https://leetcode-cn.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/英文地址:https://leetcode.com/problems/maximum-area-of-a-piece-of-cake-after-horizontal-and-vertical-cuts/思路:找出最长的「长」和「宽」即可,注意边界条件和调试。

2020-05-31 16:23:35

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取