zhpf225的博客

原创 收集螺旋矩阵元素

【代码】收集螺旋矩阵元素。

原创 建造者设计模式 + 高阶函数 =＞ DSL

该设计模式适用于创建复杂对象，该复杂对象通常是由各个部分的子对象用一定的算法或者步骤构成，针对每个子对象内部算法和步骤通常是稳定的，但是该复杂对象的确实由于不同的需求而选择使用不同的子对象进行组装。对于构建该复杂的对象，通常可以使用builder设计模式。而对于kotlin语言，结合高阶函数所实现的建造者设计模式算是DSL代码分享的实践。但是考虑到创建该对象比较复杂（该对象的成员比较多），且每一个成员的最终取值需要一定的算法策略，为了减少。

原创 Exposed ORM框架介绍

Exposed框架接入

原创 java中的回调函数

什么是回调函数考虑两个类以及一个接口：A类和B类以及A类所实现的接口。A类package com.company.callbacktest;public class AClass implements Callback{ @Override public void caller() { System.out.println("第三步：该函数是回调函数，即A的函数在B中被调用"); } // A委托B做某事 public void aUse

原创 面试题: k个一组翻转单链表

题目地址链表中的节点每k个一组翻转注意点：本题考频很高！！！题目要求空间复杂度为O(1)O(1)O(1), 因此无法使用递归本题可以借鉴翻转单链表一题，只是翻转单链表不需要引入辅助的头结点，为什么本题需要引入单独的辅助的头结点，下文会讲解。对于上面注意点的第一条，要封装的函数如下：注意下面的函数是左闭右开即只翻转绿色的部分：//翻转一段链表（左闭右开）//翻转从start到end之间的链表 public ListNode ReverseList(ListNod

原创 2021-02-27

最大正方形题目描述给定一个由0和1组成的2维矩阵，返回该矩阵中最大的由1组成的正方形的面积。代码class Solution {public: /** * 最大正方形 * @param matrix char字符型vector<vector<>> * @return int整型 */ int solve(vector<vector<char> >& matrix) {

原创 leetcode 4. 寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？示例 1：输入：nums1 = [1,3], nums2 = [2]输出：2.00000解释：合并数组 = [1,2,3] ，中位数 2方法1：时间复杂度O(log(m+n))O(log(m+n))O(log(m+n))class Solution { public double findMedi

原创 leetcode 456. 132模式

题目描述给定一个整数序列：a1, a2, …, an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。注意：n 的值小于15000。示例1:输入: [1, 2, 3, 4]输出: False解释: 序列中不存在132模式的子序列。分析方法1：直接使用三层循环进行暴力求解。但是会超时。class Solution {pu

原创 leetcode 547.省份的个数

题目叙述有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。返回矩阵中 省份 的数量。分析属于常规的并查集求连通分量

原创 并查集

并查集的用途主要用于不相交集合的合并和查询。这种数据结构主要用来进行表示集合信息，用以实现确定集合中含有哪些元素，判断两个元素是否在同一个集合中，求集合中元素的数量。求连通分量的个数并查集的特点树的特点（双亲表示法）：对于一个集合来说，一个集合可以被构建成一棵树，只是这棵和常规数据结构中的树不同的是：每一棵树的结点没有左、右孩子，而是只有一个父结点，即每一个结点（除了根节点）都会保存其父亲结点的信息，而该树的根节点被认为是集合的首领（该首领方便进行集合的合并操作即树的合并）。合并：集合的合并

原创 leetcode 5.最长回文子串

题目叙述给你一个字符串 s，找到 s 中最长的回文子串。示例 1：输入：s = “babad”输出：“bab”解释：“aba” 同样是符合题意的答案。示例 2：输入：s = “cbbd”输出：“bb”示例 3：输入：s = “a”输出：“a”分析本题目是找出最长的回文子串，注意子串一般都是连续的采用中心扩展的方式, 即遍历原始的字符串，以原始字符串的每一个位置作为中心去扩展，最终得到一个最长的回文子串。代码class Solution { public String

原创 leetcode 124.二叉树中的最大路径和

题目叙述路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。分析本题的关键就是使用一个全局变量进行动态维护最值。引入了辅助函数进行返回以当前根节点为根的和最大的路径，为了防止因左右孩子可能为负值带来对根节点的抵消，因此左右孩子的返回结果要和0取较大值。也正是有了此技巧的处理使得在res的更新部分, 一行代码就处理了很多种情况，即根节点

原创 leetcode 11.盛最多水的容器

题目叙述给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。说明：你不能倾斜容器。分析使用双指针的方式，每次进行移动较短的柱子，然后进行求最值。代码class Solution {public: int maxArea(vector<int>& height) {

原创 leetcode 63. 不同路径 II

题目叙述一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？分析在原来的62题的基础上进行加了一些障碍点。本题同时也要注意一些边界问题。比如如果起点和终点就是障碍点的话，那么问题的答案直接就可以进行返回为0。代码class Solution {public: int dfs(vecto

原创 leetcode 62.不同的路径

题目一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？分析就是普通的深度搜索加备忘录求解即可。注意递归常常采用自顶向下，即从矩阵的右下角开始进行求解。像这种矩阵路径问题都属于尾递归问题，可以使用备忘录，即在返回结果前进行先使用备忘录存起来。代码class Solution {public: int m; int n;

原创 leetcode 139. 单词拆分I,II

题目I给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。说明：拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：输入: s = “leetcode”, wordDict = [“leet”, “code”]输出: true解释: 返回 true 因为 “leetcode” 可以被拆分成 “leet code”。分析本题和322题的零钱兑换很类似，即字典中的单词看做是硬币，将字符串s看作

原创 一天一个设计模式-观察者设计模式

用处主要用于事件响应场景下，在游戏和窗口程序中用的较多，在Spring的ApplicationContex中也有用到。实现主要的结构：观察者接口被观察者抽象类多个观察者接口实现类一个被观察者实现类观察者接口public interface MyObserver { public void action();}被观察者抽象类abstract public class Subject { //一个列表，用于存储观察者 List<MyObserve

原创 leetcode 131. 分割回文串I,II

题目叙述分割回文串给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。输入: “aab”输出:[[“aa”,“b”],[“a”,“a”,“b”]]分析方法1使用朴素的递归，对于一个长度为N的字符串，其可以切割的地方有N-1处，因此这个时间复杂度为o(2(n−1))o(2^(n-1))o(2(n−1))class Solution {public: vector<vector<string>> res;

原创 vscode中针对插件pylint报have no member的问题解决

在vscode中进行使用第三方库的时候，在引用库中相关的参数的时候，如numpy中的array模块，总是提示出错（但是可以执行）解决方式：

原创 leetcode 377. 组合总和 Ⅳ

题目叙述给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。示例:nums = [1, 2, 3]target = 4所有可能的组合为：(1, 1, 1, 1)(1, 1, 2)(1, 2, 1)(1, 3)(2, 1, 1)(2, 2)(3, 1)请注意，顺序不同的序列被视作不同的组合。因此输出为 7。分析方法1 简单递归直接使用进行递归求解。但是代码会超时。class Solution {public: int res = 0;

原创 leetcode 75. 颜色分类

题目叙述给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。进阶：你可以不使用代码库中的排序函数来解决这道题吗？你能想出一个仅使用常数空间的一趟扫描算法吗？示例 1：输入：nums = [2,0,2,1,1,0]输出：[0,0,1,1,2,2]分析本题主要要求实现一个时间复杂度为O(n)O(n)O(n), 空间复杂度为O(1)O(1)O(1)的算

原创 leetcode 137. 只出现一次的数字 II

题目叙述给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？示例 1:输入: [2,2,3,2]输出: 3示例 2:输入: [0,1,0,1,0,1,99]输出: 99分析方法1：对于除出现⼀次之外的所有的整数，其⼆进制表示中每⼀位1出现的次数是3的整数倍，将所有这些1清零，剩下的就是最终的数。具体做法： 统计所有数字的所有二进制位上的所有的和，然后进行Mod

原创 剑指 Offer 28. 对称的二叉树

题目描述请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。例如，二叉树 [1,2,2,3,4,4,3] 是对称的。1/ 2 2/ \ / 3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:1/ 2 2\ 3 3示例 1：输入：root = [1,2,2,3,4,4,3]输出：true分析本题和https://blog.csdn.net/zhpf225/article

原创 leetcode 99. 恢复二叉搜索树

题目叙述给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用常数空间的解决方案吗？分析方法1：O(n)O(n)O(n)的时间复杂度，使用中序遍历使用中序遍历，先从前往后找第一个逆序的位置，再往后找第二个逆序的位置。然后进行交换。代码class Solution {public: //从前往后的中序遍历 //从后往前的中序遍历 TreeNode* an

原创 leetcode 38. 外观队列

题目描述给定一个正整数 n ，输出外观数列的第 n 项。「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。你可以将其视作是由递归公式定义的数字字符串序列：countAndSay(1) = “1”countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。前五项如下：111211211111221第一项是数字 1描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”

原创 leetcode 字符串转换整数 (atoi)

题目叙述字符串转换整数 (atoi)请你来实现一个 atoi 函数，使其能将字符串转换成整数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。注意：假如该字符

原创 28. 实现 strStr()

题目叙述实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。示例 1:输入: haystack = “hello”, needle = “ll”输出: 2分析使用滑动窗口进行暴力求解。窗口的大小最大是匹配字符串needle的长度。时间复杂度为O(m∗n)O(m*n)O(m∗n)。class Solution {public:

原创 leetcode 74. 搜索二维矩阵

题目叙述编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。分析本题所叙述的矩阵，整体都是有序的，即从左到右，从上到下都是有序的。所以对于这种从左到右，从上到下依次遍历的矩阵，可以当做一个一维的数组来进行遍历。该一维数组的起点是0， 终点是行数乘以列数 -1 。然后进行求得中间的位置，对于该中间位置，如何确定其对应的行号和列号是一个问题，即中间索引如果是mid_index, 那么对应的行

原创 leetcode 240. 搜索二维矩阵 II

题目叙述编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：每行的元素从左到右升序排列。每列的元素从上到下升序排列。示例:现有矩阵 matrix 如下：[[1, 4, 7, 11, 15],[2, 5, 8, 12, 19],[3, 6, 9, 16, 22],[10, 13, 14, 17, 24],[18, 21, 23, 26, 30]]给定 target = 5，返回 true。给定 target

原创 leetcode 135. 分发糖果

题目叙述老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。相邻的孩子中，评分高的孩子必须获得更多的糖果。那么这样下来，老师至少需要准备多少颗糖果呢？示例 1:输入: [1,0,2]输出: 5解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。示例 2:输入: [1,2,2]输出: 4解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。第三个孩子只得

原创 leetcode 134. 加油站

题目叙述在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。说明:如果题目有解，该答案即为唯一答案。输入数组均为非空数组，且长度相同。输入数组中的元素均为非负数。示例 1:输入:gas = [1,2,3,4,5]cost = [3,4,5,1,2]

原创 如何在软件CodeRunner3中使用C++11的标准

原创 leetcode 73. 矩阵置零

题目给定一个 m x n 的矩阵，如果一个元素为 0，则将其所在行和列的所有元素都设为 0。请使用原地算法。示例 1:输入:[[1,1,1],[1,0,1],[1,1,1]]输出:[[1,0,1],[0,0,0],[1,0,1]]分析本题主要是对空间复杂度要求比较高。正如题目所说，本题最简单的写法就是申请一个新的空的二维数组，然后对原来的数组保持不变，遍历整个原始的数组，并对新的数组进行赋值，空间复杂度为O(m∗n)O(m*n)O(m∗n)。方法1一个好的空间复杂度为O(

原创 leetcode 89. 格雷编码

题目叙述格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。格雷编码序列必须以 0 开头。示例 1:输入: 2输出: [0,1,3,2]解释:00 - 001 - 111 - 310 - 2对于给定的 n，其格雷编码序列并不唯一。例如，[0,2,3,1] 也是一个有效的格雷编码序列。00 - 010 - 211 - 301 - 1题目分析什么是格

原创 leetcode 36. 有效的数独

题目叙述判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。题目分析遍历每行是否有相同的元素遍历每列是否有相同的元素遍历九个小方格代码class Solution {public: bool isValidSudoku(vector<vector<char>>& board

原创 使用vue-cli编写一个to-do-list

准备工作安装node安装npm安装vue-cli使用vue-cli创建一个vue项目我们打算在桌面进行创建一个vue项目。在命令行中的桌面文件下进行执行以下的命令：vue init webpack todolist进行上面的简单设置之后，即可进行项目的初始化，期间主要会进行安装一些项目所依赖的包。启动项目在命令行工具中运行如下：npm run dev或者 npm run start然后进行访问localhost8080即可进行访问我们所创建的vue项目...

原创 leetcode 76. 最小覆盖子串

题目叙述给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。示例：输入：S = “ADOBECODEBANC”, T = “ABC”输出：“BANC”提示：如果 S 中不存这样的子串，则返回空字符串 “”。如果 S 中存在这样的子串，我们保证它是唯一的答案。分析本题属于典型的滑动窗口的题目，滑动窗口的核心在于：遍历求解连续的子字符串的问题对时间复杂度有一定的高效率设定左指针和右指针什么时候

原创 leetcode 221. 最大正方形

题目描述在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。示例:输入:1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4分析本题考虑使用动态规划。定义状态dp[i][j]是以matrix[i][j]为右下角的最大的正方形的边长。那么状态转移方程就是：dp[i][j]=min(dp[i−1][j],dp[i][j−1],dp[i−1][j−1])+1dp[i][j] = min(dp[i-1][j], dp[i][j-1]

原创 leetcode 41. 缺失的第一个正数

题目叙述给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。示例 1:输入: [1,2,0]输出: 3示例 2:输入: [3,4,-1,1]输出: 2示例 3:输入: [7,8,9,11,12]输出: 1分析采用数组归为的方式，即将数组中的元素，放到对应的索引的位置。即将1放在下标为1的地方，2放在下标为2的地方，3放在下标为3的地方，以此类推。此外还有几种特殊情况需要考虑：如果当前的元素为负数则就跳过如果当前的元素大于等于数组的长度就跳过这样，每个合法的正数总

原创 将一个N*N的数组进行顺时针翻转90度

题目描述将一个N*N的数组进行翻转90度输入：第一行是矩阵的总的行数。接下来的N行，每行是以逗号隔开的数字41,2,3,45,6,7,89,10,11,1213,14,15,16输出：翻转之后的矩阵的所有的元素都在同一行进行输出，并且以逗号进行隔开13, 9, 5, 1, 14, 10, 6, 2, 15, 11, 7, 3,16, 12, 8, 4要求时间复杂度为O(1)。分析主要分为两个步骤，第一个步骤是以对角线作为对称线进行交换两边。第二个步骤是反转所有的行元素。具体