Kiddyup-CSDN博客

原创 LC 剑指 Offer II 011. 0 和 1 个数相同的子数组

题目：给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。示例：输入: nums = [0,1]输出: 2说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。思路前缀和+哈希前缀和的作用：可以快速的求出一个序列中某一段的和在此题中，我们可以把所有的0替换为-1，这样的好处在于：当我们在计算这个二进制数组的前缀和时，当中间有一段子数组的01个数相同时，在这段子数组前后的前缀和的值是不变的（相当于加了0），比如我们以：

2022-05-05 14:40:05 227

原创剑指 Offer II 092. 翻转字符

剑指 Offer II 092. 翻转字符题目：如果一个由 ‘0’ 和 ‘1’ 组成的字符串，是以一些 ‘0’（可能没有 ‘0’）后面跟着一些 ‘1’（也可能没有 ‘1’）的形式组成的，那么该字符串是单调递增的。我们给出一个由字符 ‘0’ 和 ‘1’ 组成的字符串 s，我们可以将任何 ‘0’ 翻转为 ‘1’ 或者将 ‘1’ 翻转为 ‘0’。返回使 s 单调递增的最小翻转次数。示例:输入：s = "00110"输出：1解释：我们翻转最后一位得到 00111.思路：动态规划，设dp方

2022-04-25 22:48:14 303

原创 LC 剑指 Offer 60. n个骰子的点数

剑指 Offer 60. n个骰子的点数题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。示例：输入: 1输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]分析：当n=1，即只有一个骰子时，对应的点数只有 1、2、3、4、5、6当n = 2时，有两个骰子时，对应的点数有，

2022-04-25 00:26:41 269

原创 LC 516 最长回文子序列

LC 516 最长回文子序列题目:给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。输入：s = "bbbab"输出：4解释：一个可能的最长回文子序列为 "bbbb" 。分析：首先我们可以很清楚地知道，一个回文字符串去掉头和尾之后依然是一个回文字符串。那么一个回文字符s1，假设头尾下标为i,j，那么s1的长度就会等于s1[i-1…j+1]+2。由此可以想到用动态规划解决。思路：我们

2022-04-22 20:40:50 220

原创 JWT基础（一）

1、JWT的作用什么是JWTjwt 简称 JSON Web Token ，也就是以Json的形式作为web中的令牌。在数据传输过程中还可以完成数据加密、签名等操作。主要的作用：授权这是使用JWT的最常见方案。一旦用户登录，每个后续请求将包括JWT，从而允许用户访问该令牌允许的路由，服务和资源。单点登录是当今广泛使用JWT的一项功能，因为它的开销很小并且可以在不同的域中轻松使用。2.信息交换JSON Web Token是在各方之间安全地传输信息的好方法。因为可以对JWT进行签名

2022-04-16 00:43:17 2937

原创 ThreadLocal作用、原理以及问题

ThreadLocal1、ThreadLocal的作用在多线程访问共享资源时会采取一定的线程同步方式（如：加锁）来解决带来的并发问题。（如图）使用ThreadLocal对共享资源的访问也可以解决并发问题作用：ThreadLocal提供了线程的本地变量，即当创建一个变量后，每个线程对其进行访问的时候访问的是自己线程的变量。这里的本地内存并不是线程的工作内存，而是Thread类中的一个变量，而不是放在不是存放在ThreadLocal实例里面这样做的好处：线程安全，可以避免多线程访问同

2022-03-31 12:59:02 3698

原创 lowbit操作

lowbit操作应用求得二进制的最后一个1证明假设x为_ _ _ _ _ 1 0 0 0 0则：~x(x取反）为_ _ _ _ _ 0 1 1 1 1~x+1为_ _ _ _ _ 1 0 0 0 0那么可以通过x&~x+1获得最后一个1（注意：在编程中-x即为~x+1）所以x&-x与x&~x+1等价模板int lowbit (int x){ return x & -x;}...

2021-06-06 00:08:05 156

原创数据结构：单调栈

单调栈应用场景给定一个序列求序列中的每个元素的离它左边最近且比这个数小的数。同理（以下均适用）：给定一个序列求序列中的每个元素的离它左边最近且比这个数大的数。给定一个序列求序列中的每个元素的离它右边最近且比这个数小的数。给定一个序列求序列中的每个元素的离它右边最近且比这个数大的数。证明栈是单调的以（给定一个序列求序列中的每个元素的离它左边最近且比这个数小的数。）为例给定一个序列a假设：下标x<i 且 x+2<i如果：a[x]>=a[x+2]那么a[x]一定可以被a[

2021-06-05 23:53:27 116

原创最小生成树（prim以及kruskal）

最小生成树概念：一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。构造方法：普里姆（prim）和克鲁斯卡尔（kruskal）普里姆(Prim)时间复杂度(O(n2))基本思路及过程：在一个加权连通图中，创建两个集合：顶点集V和边集E，另外还需访问标志数组visit。在所有点中任意选出一个点作为初始点，并将该点的visit标记为true，接着计算所有与该点相连接的点的距离，找到与之距离最短的点，标记visit为tru

2020-09-11 09:45:04 180

原创实现二叉树的基本操作

具体实现的算法：（1）构建二叉树（2）前序、中序、后序遍历二叉树（3）层次遍历二叉树（4）求二叉树的最大宽度（5）求二叉树的叶子结点个数（6）交换每个结点的左右子树（7）求二叉树的深度代码：#include <iostream>#include <algorithm>#include <cstring>#include <queue>using namespace std;typedef struct BiTNode {

2020-09-09 23:01:22 1387

原创哈夫曼（Huffman）树的基本概念，构造算法以及哈夫曼编码

哈夫曼树的基本概念哈夫曼树：假设有m个权值{w1,w2,···,wm}，可以构造一棵含n个叶子结点的二叉树，每个叶子结点的权为wi，则其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。WPL（树的带权路径长度）：所有叶子结点的权乘上到根节点的距离的总和。例子：四个叶子结点a b c d,分别带权 6 3 4 2，则构建哈夫曼树如图： &nb

2020-09-08 18:51:34 2004 1

原创三种常用排序代码模板（含时间复杂度）

冒泡排序时间复杂度：O(n2)代码：#include <iostream>#include <algorithm>#include <cstring>using namespace std;const int N = 1010;void bubble_sort(int a[],int len) //核心代码{ for(int i = 0;i < len - 1;i++) for(int j = 0;j < len -

2020-09-02 21:59:48 235

原创前缀和&差分（一维与二维）

前缀和概念：用一个数组存储已知序列从第1位到第i（i ：1~n）位的值。作用：解决问题的一种预处理方法，可以快速的求出序列中某一段的和。一维前缀和基本操作：（1）计算前缀和：s[i] = s[i-1] + a[i]（s[i]表示前缀和，a[i]表示原序列）（2）计算中间的一段值：ans = s[r] - s[l-1]代码 for(int i = 1;i <= n;i++) // 计算前缀和 { cin >> a[i]; s[i] =

2020-08-30 23:41:29 271

原创洛谷：P1122 最大子树和（题解）树形dp

题目描述题目描述小明对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。于是当日课后，小明就向老师提出了这个问题：一株奇怪的花卉，上面共连有N朵花，共有N−1条枝干将花儿连在一起，并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的，说明这朵花看着都让人恶心。所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一

2020-08-17 19:11:04 300

Kiddyup的博客