单点更新，区间查询 假设有一个数组，对他大量的修改和查询，修改的是数组中某一个元素的值，查询的是数组中任意一个区间的和。对于修改比较简单，时间复杂度是 O(1) ，而查询的时间复杂度是 O(n) 。有同学可能会说使用前缀和来优化，前缀和查询的时间复杂度确实是 O(1) ，但如果我们修改某一个元素的时候，前缀和后面的值也都要修改，时间复杂度是 O(n) 。那么我们综合一下，有没有一种方式可以让修改和查询时间复杂度降一个数量级呢？有的，那就是树状数组，他的修改和查询时间复杂度都是 O(logn) ，综合来看还是不错的。如下图所示，他就是一个树状数组，其中数组 a[] 是原始数组，数组 c[] 是...

链表（Linked list）是一种物理存储单元上非连续的数据结构、数据元素的逻辑顺序是通过链表中的指针实现的。由于不必按顺序存储，链表在插入的时候可以达到 O(1) 的复杂度，但链表查找的时候由于不能通过索引查找，所以查找的时间复杂度是 O(n) 。常见的链表有单向链表，双向链表，以及环形链表。 单向链表 单向链表是最简单的一种链表，一般只包含存储的数据和指针（这里的指针不是 C 语言中的地址指针，他是下一个节点的引用），每个指针指向下一个节点，最后一个节点指向空，如下图所示。为了方便在尾部添加节点，我们新增一个 tail 变量，指向链表的尾节点。 单向链表的节点类如下： private...

单点更新，区间查询 假设有一个数组，对他大量的修改和查询，修改的是数组中某一个元素的值，查询的是数组中任意一个区间的和。对于修改比较简单，时间复杂度是 O(1) ，而查询的时间复杂度是 O(n) 。有同学可能会说使用前缀和来优化，前缀和查询的时间复杂度确实是 O(1) ，但如果我们修改某一个元素的时候，前缀和后面的值也都要修改，时间复杂度是 O(n) 。那么我们综合一下，有没有一种方式可以让修改和查询时间复杂度降一个数量级呢？有的，那就是树状数组，他的修改和查询时间复杂度都是 O(logn) ，综合来看还是不错的。如下图所示，他就是一个树状数组，其中数组 a[] 是原始数组，数组 c[] 是...

假设给你一个数组 nums ，先对区间 [a,b] 中每个元素加 3 ，在对区间 [c,d] 每个元素减 5 …… ，这样非常频繁的区间修改，常规的做法可以一个个计算。 public void increment(int[] nums, int a, int b, int k) { for (int index = a; index <= b; index++) { nums[index] += k; } } 频繁对数组的一段区间进行增加或减去同一个值，如果一个个去操作，很明显效率很差，我们可以使用差分数组，差分数组就是原始数组相邻元素之间的差。定义...

解法一 如果到第i个台阶，我们可以从第i-1个台阶跳一步上来，也可以从第i-2个台阶跳两步上来。哪个花费少我们就选择从哪个跳上来。我们定义dp[i]表示到第i个台阶需要的最小花费，那么我们可以得出递推公式 dp[i] = Math.min(dp[i - 2] + cost[i - 2], dp[i - 1] + cost[i - 1]); 其中 dp[i - 2] + cost[i - 2]表示从第i-2个台阶跳到第i个台阶的最小花费 dp[i - 1] + cost[i - 1]表示从第i-1个台阶跳到第i个台阶的最小花费 有了递推公式，我们再来看下代码 import java.u...

解法一 这里的青蛙比前面两道题的青蛙更厉害一些，他一次可以跳1阶，2阶，3阶……。所以要想跳到第n个台阶，我们可以从第1个台阶跳上来，也可以从第2个台阶跳上来……，所以递推公式是 f(n)=f(n-1)+f(n-2)+……+f(2)+f(1); 同样如果我们想跳到第n-1个台阶，也可以列出下面这个公式 f(n-1)=f(n-2)+……+f(2)+f(1); 通过这两个公式我们可以得出 f(n)=2*f(n-1) 实际上他是个等比数列，base case当n等于1的时候结果为1，来看下代码 import java.util.Scanner; public class Main { ...

这题和前面 DP1 斐波那契数列基本上是一样的，不同的是，这里斐波那契数列的起始项是1,2,3,5,8，我们把它改一下即可 解法一 题中要求的是 空间复杂度 O(1) ，很明显使用递归是行不通的，我们先改成非递归的看一下（这种复杂度也是不行的，我们先看一下代码） import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num = in.nextInt()...

解法一 题中要求的是 空间复杂度 O(1) ，很明显使用递归是行不通的，我们先改成非递归的看一下（这种复杂度也是不行的，我们先看一下代码） import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int num = in.nextInt(); int[] dp = new int[num + 1]; dp[1] = 1; ...

欢迎大家一起来学习算法😀  数据结构和算法的博客_牛客博客 https://blog.nowcoder.net/sdwwld

四指针解决 在算法中双指针我们经常听过，但四指针还是比较少的，四指针顾名思义就是使用4个指针来解决。 这题是让把节点值小于x的节点都放到前面，最简单的一种解决方式就是把原链表的节点分隔为两个链表，其中一个链表节点的值都是小于x的，另一个链表节点的值都是大于或等于x的，最后再把这两个链表合并即可。这里要使用四个指针，其中两个指向小的链表，两个指向大的链表，原理如下图所示 最后我们再来看下代码 public ListNode partition(ListNode head, int x) { //小链表的头 ListNode smallHead = new ListNode(0...

先上下交换，在对角线交换 这题是让把矩阵顺时针旋转90度，最简单的一种方式就是先上下关于中心线翻转，然后再对角线翻转，具体看下图形分析 原理比较简单，来直接看下代码 public int[][] rotateMatrix(int[][] matrix, int n) { int length = matrix.length; //先上下交换 for (int i = 0; i < length / 2; i++) { int temp[] = matrix[i]; matrix[i...

递归解决 判断二叉树是否是对称，需要从子节点开始比较，两个子节点的值必须相同，并且左子节点的右子节点（如果有）必须等于右子节点的左子节点，左子节点的左子节点必须等于右子节点的右子节点。就像下面图中那样 public boolean isSymmetric (TreeNode root) { if (root == null) return true; //从两个子节点开始判断 return isSymmetricHelper(root.left, root.right); } public boolean isSymmetricHelper(Tr...

BFS打印 二叉树的的层次遍历就是一层一层的遍历，也就是我们俗称的BFS（宽度优先搜索算法（又称广度优先搜索））,之前在373，数据结构-6,树 中讲过树的宽度优先搜索，最简单的方式就是使用队列。但这题打印的时候多了一个条件，就是不能一直从一个方向打印，要先从左边打印然后再从右边打印……，就这样交替进行，所以这里要有个变量来判断是从左往右还是从右往左打印，代码比较简单，我们来看下。 import java.util.ArrayList; /* public class TreeNode { int val = 0; TreeNode left = null; Tree...