题目描述 给定一个代表游戏板的二维字符矩阵。 'M' 代表一个未挖出的地雷，'E' 代表一个未挖出的空方块，'B' 代表没有相邻（上，下，左，右，和所有4个对角线）地雷的已挖出的空白方块，数字（'1' 到 '8'）表示有多少地雷与这块已挖出的方块相邻，'X' 则表示一个已挖出的地雷。现在给出在所有未挖出的方块中（'M'或者'E'）的下一个点击位置（行和列索引），根据以下规则，返回相应位置被点击后对应的面板： 如果一个地雷（'M'）被挖出，游戏就结束了- 把它改为 'X'。 如果一个没有相邻地雷的空方块（'E'）被挖出，修改它为（'B'），并且所有和其相邻的未挖出方块都应该被递归地揭露。 如...

链表节点描述 记录面试中常见的链表经典题型 class ListNode{ int val; ListNode next; ListNode(int x){ val = x; next = null } } 单指针题型 双指针题型 1. 环形链表 题目描述： 力扣 141.环形链表给定一个链表，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中...

题目描述 请判断一个链表是否为回文链表。请采用 O(n) 的时间复杂度和 O(1) 的空间复杂度进行求解。 题目分析 如果是数组，很显然采用双指针，分别从前和后两段同时遍历即可但是链表面临着两个问题1、链表的长度2、单链表，没有从后向前遍历的方法那么需要解决这两个问题1、首先需要查找到链表的中间节点 (快慢双指针，快指针每次走两个节点，慢指针每次走一个节点)2、从中间节点到尾结点进行逆序 (头插法，辅助空间为 O(1) ) class Solution { //本质上是，将从中间节点之后节点反转，把中间节点作为两个头指针所指向链表的终点 public boolea...

在这里推荐一些，关于背包九讲，非常好的视频讲解和相关的博客学习背包九讲 —— yxc 直播回放   B站 大雪菜背包九讲 —— 全篇详细理解与代码实现   CSDN 良月澪二，博主提供了很多背包方面的题解。结合视频和博客的学习，这里提供一些 java 的实现版本，其实就是翻译一下，大佬们的 C++ 程序 。这些题都可以在 AcWing 题库第一页就能找到，是不是很方便。这里也只介绍了四类背包问题， 因为其他的类型，本人太菜了，还没学会 ( T—T ) ， 后期再慢慢加上。 01背包 传送门 import java.util.*; public class Main{ public...

题目描述 给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）: 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 输入: [1,2,3,0,2]输出: 3解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]来源 -> 力扣：最佳买卖股票时机含冷冻期 题目分析 1. 状态定义  我们用 f[i] 表示第 i 天结束之后的「累计最大收益」。根据题目描述，由于我们最多只能同时...

 最近在力扣上刷到最佳买卖股票时机系列的题型，主要采用动态规划的思想来解决此类问题。在这里从简单情况，慢慢过渡到相对复杂的情况分析。 题一、买卖股票的最佳时机 题目描述给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。注意：你不能在买入股票前卖出股票。输入: [7,1,5,3,6,4]输出: 5解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6 - 1 = 5 。注意利润不能是 7 - 1 = 6, 因为卖出价格需要...

题目描述 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。我们英勇的骑士（K）最初被安置在左上角的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数，则表示骑士将增加健康点数）。为了尽快到达公主，骑士决定每次只向右或向下移动一步。 编写一个函数来计算确保...

题目描述 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。输入:[ [0,0,0], [0,1,0], [0,0,0]]输出: 2解释:3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径：1： 向右 -> 向右 -> 向下 -> 向下2： 向下 -> 向下 -> 向右 -> ...

题目描述 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？输入1： m = 3 , n = 2输出1：3解释:从左上角开始，总共有 3 条路径可以到达右下角。1: 向右 -> 向右 -> 向下2: 向右 -> 向下 -> 向右3: 向下 -> 向右 -> 向右输入2：m = 7 , n = 2输出2：28来源：力扣 -- 不同路径 方案一 ：动态规划 1、 确定状态方程我们使用一个二维数组...

TreeMap TreeMap底层是根据红黑树的数据结构构建的，默认是根据key的自然排序来组织（比如integer的大小，String的字典排序），而没有提供根据value进行排序的方法，但又常常遇到需要对value进行排序的情况。在此，主要目的是记录TreeMap中的key和value的排序实现。TreeMap底层实现原理 Lambda表达式 在往下进行之前，先了解一个很强大的功能。自java8发布后，其中一个很重要的新特性 -- Lambda表达式它允许将行为传入函数中，但在这之前我们想要将行为传入函数时，仅有的选择是匿名内部类(内容相对麻烦些)。而Lambda表达式的应用，将...

节点表达方式 public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; } 1. 树的深度 递归求取左右字数的深度，返回两者中的较大者并加1，即为树的深度。 public class Solution { /** * * @param root TreeNode类 * @return int整型 */ public int maxDepth (TreeNode root) { // write c...

题目 可能很多人要吐槽为什么标题不是“救救blabla”了。怪人PM6喜欢数糖纸，不同的糖纸有不同的颜色，一共有 N 张糖纸，第 i 张糖纸颜色为 Ci ，它们的位置都是固定的。PM6喜欢五彩缤纷的糖纸，所以他不希望有重复的颜色。他有一次机会，可以收集任意一段连续区间内的糖纸。求出PM6最多能收集多少张糖纸。 输入描述 第一行一个正整数 N ，表示共有 N 张糖纸。第二行共有 N 个正整数，第 i 个正整数表示第 i 张糖纸的颜色 Ci对于20%的数据：1<=N<=100对于40%的数据：1<=N<=1000对于100%的数据：1<=N<=1e6，...

题目 给出长度为n的序列a，其中第i个元素为ai，定义区间(l,r)的价值为请计算出： 输入描述 第一行输入数据组数T对于每组数据，第一行为一个整数n，表示序列长度接下来一行有n个数，表示序列内的元素 思路：就是求所有子区间(区间长度大于1的子区间)的最大值减去最小值的和是多少。我们对原式子拆分一下可得:其中max(l,r)表示区间l到r的最大值，min(l,r)表示区间l到r的最小值。那么问题就转化为 求所有区间长度大于1的子区间的最大值之和/最小值之和。暴力的方法就是两个for枚举起点和终点去计算，会TLE考虑单调栈，单调栈维护什么？ 维护以a[i]为区间的最大值，往左右两边...

单调栈 单调栈就是栈里面存放的数据都是有序的，所以可以分为单调递增栈和单调递减栈两种。1.单调递增栈就是从栈底到栈顶是从大到小2.单调递减栈就是从栈底到栈顶是从小到大接下来通过例题进行介绍：博文学习来源 单调栈的经典题目（求最大子矩阵的大小） 给出一个矩形统计图，它的每个矩形的宽度都为1，高度是题目所给。要你求出这个矩形图中最大面积的长方形。矩形统计图的数据为 [4, 3, 2, 5, 6] 思路准备一个栈，栈低到栈顶是从小到大的。栈如图所示 第一个下标是0，值是4，栈为空，放入栈中。 第二个下标为1，值为3，比栈顶（此时是4）小，不符合栈低到栈顶从小到大，所以弹出栈顶（4）...