zhangxiaojiakele的博客

原创 漫谈密码学

漫谈密码学密码学就在我们身边”密码学“，当你听到这三个词的时候，脑海里是否会联想到一些高深、神秘的画面呢？例如谍战电影中秘密发送电报的场景？事实上，在当今社会，密码学离我们一点都不遥远。随着万物互联的进一步普及，人类社会信息传输量正急剧膨胀，与之伴随的是我们对于传输消息中所涉及隐私、安全等问题的持续关注。不知道你在使用浏览器访问网站的过程中，是否注意到有些地址栏的域名左侧带有一个🔒的符号。事实上，如果有这个锁，便意味着你与这个网站的通信过程是被安全加密的，也就是说，你发送给对方网站的消息不是原始的明文，

原创 程序员的38堂成长课

《程序员的38堂成长课》第一课 心系代码1. 你是否关注代码？你的关注在工作中是如何体现出来的？2. 作为一个程序员，你需要提升自己吗？哪些领域是你提升的重点？3. 你认为“优秀的程序员能写出好的代码，平庸的程序员则不能”这句话正确吗？有没有可能好的程序员也会写出糟糕的代码？在什么情况下会这样？第二课 保持外观整洁1. 你是否应该调整遗留代码的排版方式，使之符合公司的编码规范？或者是保持原有的排版风格？为什么？2. 你认为代码自动格式化工具有价值吗？这类工具在多大程度上依赖于你所用的编程语言？3. 整

原创 设计模式:装饰器模式

1. 类的功能扩展面向对象设计中, 可扩展通常是类设计中的一项重要考量. 在不改变原有类的情况下, 对当前类进行扩展的最直接方法是继承当前类, 并在子类中扩展其功能. 然而, 如果我们对当前类的扩展并不是专属与该类的, 例如对其他类也可能需要进行该功能的扩展, 则如果使用继承模式, 我们需要对每一个待扩展类分别继承, 并在子类中添加相同的扩展功能代码. 在良好的代码设计中, 通常应该考虑消除重复代码. 借助装饰器模式, 我们可以消除在每一个待扩展类上重复编写扩展功能代码.2. 装饰器模式适用场景对功

原创 对B树/B+树的理解

1. B树/B+树的应用场景对于大规模数据,受计算机主存限制,通常无法一次性将全部数据加载进主存当中,只能分批加载. 目前,辅存(外部存储)通常有两种设备,固态硬盘与机械硬盘.其中固态硬盘与主存类似,可以实现数据的随机存取,而机械硬盘无法实现数据的随机存取,为了获取特定位置的数据,机械磁盘的磁头需要先移动到起始位置,然后才开始读取数据.为了提高机械硬盘读取数据的效率,通常每一次读取一个分页大小的数据,来均摊掉磁头移动所需时间.目前,大数据存储中,机械硬盘仍是主要的存储设施,因此需要设计合适的数据结构,能

原创 设计模式之:简单工程模式+策略模式

1. 简单工厂模式1.1要点对于一组相关的策略类:使用接口+多个实现类使用简单工厂创建策略类, 将具体类对客户代码封装1.2 代码public interface IStrategy{ public void run();} public class StrategyA implements IStrategy{ public void run(){ //具体策略 }}public class StrategyB implements IStrategy{ public

原创 TCP/IP:传输层多路复用与多路分解图示

原创 死锁检测与恢复

注:本文主要参考自<<现代操作系统>>6.3,6.4节在死锁一文中,我们提到死锁问题有四种解决方案.本文将主要介绍第二种方法:死锁检测与恢复.此处简要提及一下第一种方法,忽略死锁.如果程序员可以推断死锁发生的概率非常小,且发生死锁后不会造成严重后果.则可以考虑忽略死锁,毕竟解决死锁问题不仅需要编写额外代码,死锁解决方案本身也会对程序性能造成影响.例如我们即将介绍的死锁检测与恢复方法中.需要持续判断当前是否发生了死锁,这是一个不小的开销.死锁检测与恢复使用这种技术,我们并不试图

原创 系统为什么会死锁?

注:本文主要参考<<现代操作系统>>6.1,6.2节何为死锁先给大家讲一个关于死锁的笑话：某天张三去面试，面试官问他你知道什么是死锁吗？张三说：你先给我offer我就告诉你．面试官说你先告诉我，我再给你offer．张三说：不行，你先给我offer，我再高速你．面试官说：不行，你先告诉我，我再给你offer．于是这场面试持续进行…哈哈哈！在计算机系统中，某些资源在同一时刻最多只能被一个进程使用，例如打印机．如果两个进程在同一时刻使用打印机，那打印出的一份文档上可能交叉打印出两

原创 基于管程的多线程程序

注：本文主要参考自<<现代操作系统>>2.3.7节在互斥量与条件变量一文中，我们使用互斥量与条件变量解决了多线程生产者与消费者问题．其中互斥量主要用于确保生产者与消费者不会同时访问缓冲区，条件变量则用于确保线程仅在其执行必要条件满足时才会执行．本文，我们将介绍一种与该方法一脉相承的另一种技术：管程．管程首先，应当说明，管程属于编程语言的范畴．是为了方便程序员编程，而为编程语言添加的新特性．因此，并不是所有的编程语言都支持管程这一特性．为了支持管程，编程语言的编译器需要做一些额外

原创 互斥量，条件变量

注：本文主要参考<<现代操作系统>>2.3.6节在进程唤醒与睡眠一文中，针对多进程的生产者－消费者问题，我们提出了基于信号量的解决方案．该方案避免了进程在等待其要求的下一步执行条件时进入忙等待状态．我们使用了三个信号量，信号量mutex用于保证生产者进程与消费者进程不会同时访问缓冲区．信号量empty用于保证当缓冲区满是生产者被阻塞进入休眠状态，当缓冲区不满时其能够被再次唤醒．信号量full用于保证当缓冲区空时消费者被阻塞进入休眠状态，当缓冲区不空时其将被生产者进程唤醒．信号量可

原创 进程唤醒与睡眠

注：本文主要参考自<<现代操作系统>>2.3节进程唤醒与睡眠使用睡眠与唤醒避免忙等待在前一节如何避免多进程(线程）因竞争条件引发的错误？，我们提出了集中能保证多个进程互斥访问临界区，我们所提出的解决方案均使用忙等待策略，即在进程等待进入临界区时，其持续检查，直到能够进入临界区为止．我们能否在进程未满足下一步工作条件时进入休眠状态，当进程满足下一步工作条件时，由其他进程唤醒该进程呢？如果可以实现这种方法，则我们可以避免进程的忙等待，从而节省CPU资源．操作系统提供的sleep系

原创 如何避免多进程(线程）因竞争条件引发的错误？

注：本文主要参考自<<现代操作系统>>第２章如果避免多进程（线程）因竞争条件引发执行错误？多进程程序竞争条件对于多进程或多线程协作程序，如果多个执行程序间需要访问共享内存区域，则程序编写人员一定要仔细判断程序执行逻辑，确保多个程序对共享内存区域的访问不会出现逻辑错误．对于多个进程协作可能因竞争条件引发的执行错误，在多线程编程中同样存在，其解决方法也同样适用于多线程问题，因此后文均以多进程来说明问题．多进程协作间因竞争条件引发错误的根本问题在于程序并未按照开发者设想的逻辑顺序正

原创 leetcode:由斜杠划分区域

题目来源:力扣题目描述：在由 1 x 1 方格组成的 N x N 网格 grid 中，每个 1 x 1 方块由 /、\ 或空格构成。这些字符会将方块划分为一些共边的区域。（请注意，反斜杠字符是转义的，因此 \ 用 “\” 表示。）。返回区域的数目。=============================================示例 1：输入：[" /",“/ "]...

原创 leetcode:不邻接植花

题目来源:力扣题目介绍:有 N 个花园，按从 1 到 N 标记。在每个花园中，你打算种下四种花之一。paths[i] = [x, y] 描述了花园 x 到花园 y 的双向路径。另外，没有花园有 3 条以上的路径可以进入或者离开。你需要为每个花园选择一种花，使得通过路径相连的任何两个花园中的花的种类互不相同。以数组形式返回选择的方案作为答案 answer，其中 answer[i] 为在...

原创 leetcode:二叉搜索树转化为双向循环链表

题目来源:力扣题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。审题：题目要求我们将一棵二叉搜索树转化为双向循环链表．由于二叉搜索树的中序遍历结果递增有序，因此我们可以考虑中序处理每一个节点，相当于我们从头构建双向循环链表．我们可以先构建一个双向链表，然后在将链表的首尾节点相连，构成双向循环链表．为了构建双向...

原创 leetcode:为运算表达式设计优先级

题目来源:力扣题目描述给定一个含有数字和运算符的字符串，为表达式添加括号，改变其运算优先级以求出不同的结果。你需要给出所有可能的组合的结果。有效的运算符号包含 +, - 以及 * 。============================================================示例 1:输入: “2-1-1”输出: [0, 2]解释:((2-1)-1) =...

原创 leetcode:剪绳子

题目来源：力扣题目介绍给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]…k[m] 。请问 k[0]k[1]…*k[m] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。==============================...

原创 leetcode: 最低票价

题目来源:力扣题目介绍:在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。火车票有三种不同的销售方式：一张为期一天的通行证售价为 costs[0] 美元；一张为期七天的通行证售价为 costs[1] 美元；一张为期三十天的通行证售价为 costs[2] 美元。通行证...

原创 leetcode:二进制中1的个数

题目来源:力扣题目描述:请实现一个函数，输入一个整数，输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。============================================================示例 1：输入：00000000000000000000000000001011输...

原创 leetcode:叶值的最小代价生成树

题目来源:力扣题目介绍:给你一个正整数数组 arr，考虑所有满足以下条件的二叉树：每个节点都有 0 个或是 2 个子节点。数组 arr 中的值与树的中序遍历中每个叶节点的值一一对应。（知识回顾：如果一个节点有 0 个子节点，那么该节点为叶节点。）每个非叶节点的值等于其左子树和右子树中叶节点的最大值的乘积。在所有这样的二叉树中，返回每个非叶节点的值的最小可能总和。这个和的值是一个 32...

原创 leetcode:等差数列划分

题目来源:力扣题目介绍如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。========================================================示例:A = [1, 2, 3, 4]返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。=======...

原创 leetcode:回文子串

题目来源:力扣题目介绍:给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。=============================================================示例 1:输入: “abc”输出: 3解释: 三个回文子串: “a”, “b”, “c”.示...

原创 leetcode:使用最小花费爬楼梯

题目来源:力扣题目介绍:数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。================================================...

原创 leetcode:我能赢吗

题目来源:力扣题目介绍:在 “100 game” 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和达到 100 的玩家，即为胜者。如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。给定一个整数 maxChoosableInteger ...

原创 leetcode:买卖股票最佳时机含手续费

题目来源:力扣题目介绍:给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。示例 1:输入: prices = [1, 3, 2, 8, 4, 9], fee = 2输出:...

原创 leetcode:三角形最小路径和

题目来源:力扣题目描述:给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。例如，给定三角形：[[2],[3,4],[6,5,7],[4,1,8,3]]自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。说明：如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。审题:对...

原创 leetcode:不同的二叉搜索树

题目来源：力扣题目介绍：给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？示例:输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树.审题：考虑对于从iii到jjj的节点序列，我们可以选择iii到jjj的任意一个值作为二叉搜索树根节点，假设选择kkk作为根节点，则此时左子树的有节点序列iii到k−1k-1k−1构成，右子树由节点k...

原创 leetcode:礼物的最大价值

题目来源:力扣题目描述:在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？=============================================示例 1:输入:[[1,3...

原创 leetcode:石子游戏II

题目来源:力扣题目介绍:亚历克斯和李继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。亚历克斯和李轮流进行，亚历克斯先开始。最初，M = 1。在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。游戏一直持续到所有石子都被拿走。...

原创 leetcode:石子游戏

题目来源:力扣题目介绍:亚历克斯和李用几堆石子在做游戏。偶数堆石子排成一行，每堆都有正整数颗石子 piles[i] 。游戏以谁手中的石子最多来决出胜负。石子的总数是奇数，所以没有平局。亚历克斯和李轮流进行，亚历克斯先开始。 每回合，玩家从行的开始或结束处取走整堆石头。 这种情况一直持续到没有更多的石子堆为止，此时手中石子最多的玩家获胜。假设亚历克斯和李都发挥出最佳水平，当亚历克斯赢得比...

原创 leetcode:比特位计数

题目来源:力扣题目描述：给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。================================================示例 1:输入: 2输出: [0,1,1]示例 2:输入: 5输出: [0,1,1,2,1,2]===============...

原创 leetcode:按摩师

题目来源:力扣题目介绍:一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，替按摩师找到最优的预约集合（总预约时间最长），返回总的分钟数。注意：本题相对原题稍作改动=============================================================示例...

原创 leetcode: 连续子数组的最大和

题目来源：力扣题目描述：输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。=============================================示例1:输入: nums = [-2,1,-3,4,-1,2,1,-5,4]输出: 6解释: 连续子数组 [4,-1,2,1] 的和最...

原创 leetcode:除数博弈

题目来源:力扣这是我做的第一道动态规划题目,今天看了一上午算法导论动态规划那一章,下午准备检验一下自己的理解.虽然这道题难度为简单级别,但在自己独立思考下做出来了,感觉美滋滋!题目描述:爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：选出任一 x，满足 0 < x < N 且 N % x == 0...

原创 leetcode:距离原点最近的Ｋ个点

题目来源：力扣题目描述：我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。（这里，平面上两点之间的距离是欧几里德距离。）你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。审题：该题属于典型的TopK问题，我们在之前已经讨论过基于优先队列的算法，求一堆元素中的TopK元素．在那篇文章中，我们手动使用堆结构实现了优先队...

原创 leetcode:距离相等的条形码

题目来源:力扣题目描述:在一个仓库里，有一排条形码，其中第 i 个条形码为 barcodes[i]。请你重新排列这些条形码，使其中两个相邻的条形码 不能 相等。 你可以返回任何满足该要求的答案，此题保证存在答案。============================================================示例 1：输入：[1,1,1,2,2,2]输出：[2...

原创 leetcode:最小的k个数

题目来源:力扣题目描述:输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。审题:对于TopM问题,当数据量较小时,可以直接对数据进行排序,然后选择前k个数值即可.而对于海量大数据,例如十亿,百亿的数据量,如果要找出前10个数值,则使用排序算法是不现实的.因为海量的数据时可能无法一次性装进内存,更别提后...

原创 leetcode: 键值映射

题目来源:力扣题目描述:实现一个 MapSum 类里的两个方法，insert 和 sum。对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。=================================...

原创 leetcode:实现 Trie (前缀树)

题目来源:力扣题目描述:实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。=============================================================示例:Trie trie = new Trie();trie.insert(“apple”);trie.search(“apple...

原创 leetcode:词典中最长的单词

题目来源:力扣题目描述：给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。================================================================示例 1:输入:word...