1 喝瓶rio再跑

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 35w+

力扣41. 缺失的第一个正数 题解

题解题目思路代码题目给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。示例 1:输入: [1,2,0]输出: 3示例 2:输入: [3,4,-1,1]输出: 2思路刚开始,觉得这道题可能要考察时间复杂度,因为正确率只有40%,怀疑存在坑导致样例通不过。写完代码,没想到一遍运行就过了。复杂度还不错,O(n).我使用哈希表来储存数组中的每一个元素。遍历完一遍之后,使用while循环,从i=0,开始,找到哈希表中第一个hashmap[i]==0的情况,即该正数i并没有出现在数组里

2020-06-28 22:20:07

力扣 剑指 Offer 38. 字符串的排列 题解

题解题目思路代码题目输入一个字符串,打印出该字符串中字符的所有排列。你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。示例:输入:s = “abc”输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]限制:1 <= s 的长度 <= 8思路这道题模板跟46.全排列一样。主要是考察回溯算法。需要注意的是两个点。首先我们要设置一个sign数组来表示该字母是否已经被访问过。然后我们在每一次往临时string扔字母进行回溯后,要记得删除这个字

2020-06-25 11:39:18

力扣343. 整数拆分 题解

题解题目思路代码题目给定一个正整数 n,将其拆分为至少两个正整数的和,并使这些整数的乘积最大化。 返回你可以获得的最大乘积。示例 1:输入: 2输出: 1解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:输入: 10输出: 36解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。说明: 你可以假设 n 不小于 2 且不大于 58。思路呃这道题其实用数学思路解决比较快,而且代码量少。但其实我也对其中的数学推导不太清楚,只是记忆里似乎有一个类似的定理。实

2020-06-24 18:49:37

力扣16. 最接近的三数之和 题解

题解题目思路代码题目给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。示例:输入:nums = [-1,2,1,-4], target = 1输出:2解释:与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。思路思路大致上跟“三数之和”差不多。我们可以固定数组的一个数之后,对后面的数进行双指针的遍历。设置一个int变量num表示最接近ta

2020-06-24 17:59:00

力扣 剑指Offer 31.栈的压入、弹出序列

题目题目思路代码题目输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。示例 1:输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出:true解释:我们可以按以下顺序执行:push(1), push(2), push

2020-06-23 21:00:57

力扣67.二进制求和题解

题目一级目录思路代码一级目录输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如,序列 {1,2,3,4,5} 是某栈的压栈序列,序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列,但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。示例 1:输入:pushed = [1,2,3,4,5], popped = [4,5,3,2,1]输出:true解释:我们可以按以下顺序执行:push(1), push(2),

2020-06-23 20:53:11

力扣124.二叉树中的最大路径和题解

题解题目思路代码题目思路刚开始我想通过迭代的dfs来实现,不过似乎有点困难,因为路径不一定经过根节点。参考了网友们的题解之后发现,递归在这道题可以使问题更加的形象,并且代码量很少。观察发现,一个节点如果是最大路径的一个节点,只有两种情况:节点是根节点;节点是根节点的左节点或者右节点。我们可以通过设置一个全局变量:ans,来更新每一个节点作为根节点的时候,最大路径的值——因为每一个节点都可以找出它作为根节点时的最大路径嘛。并且,最终的答案肯定也存在一个节点作为根节点。然后,我们再次讨论节点作为

2020-06-21 06:45:31

力扣405:数字转换为十六进制数 位运算

题解题目思路代码题目思路这道题要用到位运算的原因是它涉及到负数的转换。如果是正数的话,其实我们是可以通过暴力的while循环,生成二进制的数组,再转换成十六进制。但是涉及到负数的话,就需要进行补码的运算。特别对于有符号数而言,第一位永远是符号位,求反码的时候该位是不变的。然后,如果负数进行右移的话,左边是自动补充1的;如果负数转变成无符号整数的话,左边自动补充的就是0.对于这道题而言,题目给出的条件是,数字在32位有符号数之内,意味着我们求出的16进制数至多有8位。所以我们可以让4位为一组

2020-06-20 18:49:06

力扣剑指offer第42题.连续子数组的最大值题解

题解题目思路代码题目思路这道题用到了动态规划的思路,私认为动态规划从开销上是优胜于分治算法的。我们可以从最暴力的双重for循环开始寻找思路。暴力算法无非就是固定一个下标值,找出这个下标到数组末尾的这么多个子数组中,值最大的一种情况。但是我们在暴力的过程中是可以发现,有些情况是直接可以摒弃的。比如当前的下标所对应的值是负数时,会拖累到子数组后面的部分,就应该摒弃。于是,改良后的动态规划算法也呼之欲出。我们从头开始遍历,设置一个储存最终结果的数ans,以及储存临时子数组元素的和值的数tmp。我

2020-06-20 17:52:07

VS code中文注释显示乱码 解决方法

解决方法方法有一个小问题要记录一下。我尝试在VS code打开在ubuntu写好的代码时,发现了乱码的现象。解决方法是在文件->首选项->设置->搜索,找到“files.autoGuessEncoding”,把它从false改成true就行了。参考自https://blog.csdn.net/weixin_34387284/article/details/86032626...

2020-06-20 12:45:30

C设计实现一个线程池(thread pool)

C设计实现一个线程池环境思路代码main.cpool.cpool.h环境在ubuntu的linux操作系统下,使用C语言,使用pthread创建和管理线程。任务满足先进先出的原则,因此使用链表。由于课程暂未学习到线程之间的互斥和锁的问题,所以不考虑线程的问题。以链表的形式创建任务,导入线程池然后执行,再销毁线程池,即为实验的流程。思路下面开始讲解我关于线程池的构造。因为还没有学习到互斥锁的知识,所以暂时不考虑调用线程切换的时候可能出现的互斥问题。而是着重关心线程池中任务以及线程的构造。对于任务

2020-06-20 12:35:23

多线程创建:pthread()和clone()实现机制的异同

异同用户级线程与LWP不同点相同点用户级线程与LWPPthread()是基于用户级线程来实现,而clone()是基于轻量级进程(LWP)来实现的。对于用户级线程,是由用户空间运行线程库,使得任何应用程序都可以通过使用线程库被设计成多线程程序。所以对于线程的创建、消息的传递等都由线程库来完成,并且内核感知不到多线程的存在。而内核继续以进程为单位,给该进程一个执行状态。而对于LWP而言,它是由内核支持的用户线程。正如图片里面显示的一样,它可以起到逻辑上对于用户线程和内核线程的连接。事实上,它是基于

2020-06-20 12:01:25

力扣1014.最佳观光组合题解

题解题目思路代码三元素比较的算法代码(没有AC)题目思路明显题目是想要考我们dp或者贪心算法。我们可以从最基础的暴力算法来获得灵感。暴力算法是通过固定每一个a[j]-j,来获得最大的a[i]+i。那么我们可以通过贪心算法,设置一个int left,在迭代的每一步都实时更新最大的a[i]+i的值,这样就不用每一次j++都要遍历一次数组寻找最大值了。我刚开始的做法是想通过设置left和right的值,在迭代的时候,同时比较三种情况:left与right,left与a[i]-i,left变成rig

2020-06-19 20:18:20

力扣125.验证回文串题解

题解题目思路代码题目思路刚开始想要用istringstream实现对字符串的流操作。但是我忽略了一个细节,对于除了空格和回车,其他字符都被sitringstream看作是字符串的一部分。对于题目的样例输入,这种输出控制类会把“,”也看成字符一部分。在vs code试验了一波,分割结果如图所示。不过对于只有空格的字符串,利用istringstream还是很方便的——主要针对筛选字符和数字。因此,只能用比较传统的方法。先把字符和数字选出来,然后对筛选后字符串进行小写化。再通过双指针的方法,遍历判

2020-06-19 18:31:08

力扣第14题:最长公共前缀题解

题解题目思路暴力算法代码优化后的代码一些感想题目思路刚开始以为是找出最长公共子串。后来改了一下样例,发现真的是找出“前缀”。于是先来一波暴力解法。以第一个string为参考点,依次针对这个string的每个字母,对整个string数组的string进行相同位置的遍历。如果遇到字符不相等的情况,说明这个位置及其之后都不是公共前缀了。于是停止。暴力算法的时间复杂度是O(n²)。击败了7%的答案。另外一个优化的方法是,还是以第一个string作为参考点。不过与暴力法不同的是,它对string数组进行遍

2020-06-15 12:15:18

力扣1300. 转变数组后最接近目标值的数组和的题解

题解题目思路代码另外一个思路的代码(未能通过)题目思路很惭愧的是最终我的解法没有用到提示里面的二分法。刚开始以为是用贪心算法,或者往回溯递归的方面去想。后面开始思考时才发现这道题比较特别。有几种情况会让人很抓狂:当输出不为数组中任何一个元素时。如果这个元素比数组中任何一个数都要小,那么比较好解决。但是如果这个元素夹在中间,那么就很难办了。我们需要通过遍历来找到那个满足条件的值。如果题目固定给出一个恰好等于target的答案,那么会变得很简单。但是题目很鸡贼,说可能存在多个答案,若存在这种情况,

2020-06-14 12:38:04

力扣第70题:爬楼梯题解

题解题目思路代码题目思路最近力扣似乎特别喜欢出dp…都连续出了好几题了都。而且主要这几题都是比较明显的dp解法,没有什么特别难的edge case以及与其他算法的交叉。这道题主流上有三种解法。第一种是打表法。比较无脑,但是两个复杂度都是非常的可观。因为案例比较有限,所以可以在电脑的编译环境里,自己跑一遍代码,将所有的结果都保存记录下来,放到一个数组上。粘贴回到原题,直接得到答案。第二种是递归。但是由于递归存在递归栈,如果递归层数过多,会爆栈,而且时间复杂度上也不太好看。空间和时间的复杂度都不

2020-06-13 18:58:34

力扣 15.三数之和 题解

题解题目思路代码双指针位于左右两侧的代码(最后一个样例超时)调用“两数之和”的代码(没通过)题目思路第一眼看这道题的时候,我脑海里还是“两数之和”的题解。而且根据力扣的提示,似乎将一个元素固定之后,就可以调用“两数之和”的函数,来完成。于是遍历整个数组,使得target=-nums[i],这样就可以完美调用“两数之和”。最后采用set为结果数组去重。不幸的是超时了。参考网友的题解思路之后,我决定采用双指针。并将左右指针定为i-1和i+1.然后从i=1开始遍历到i=size-2.每遇到三数

2020-06-12 12:21:53

力扣面试题46.题解

题解力扣面试题46.题解思路代码力扣面试题46.题解思路这道题是动态规划的一道很典型的问题。从例子12258谈起。我们可以知道,当分割成1,2,2,5,8时,1显然只有一种分割;1,2则可以有2种,因为12<=25.那么在1,2,2,的情况下呢?有3种分割方案。怎么算出来的呢?我们知道,22<25,所以当后面的22捆绑在一起的时候,实际上就是看1以及1以前的数字,有多少种分割方案。在我们声明的dp数组里,数组里存放的元素为当前元素下标下,该元素及其前面的元素组成的数字,可以分

2020-06-11 21:48:24

力扣第739题题解

@力扣第739题题解力扣第739题题解思路我的第一个思路,是利用两个栈和一个哈希表。第一个栈存放数组数据,第二个栈存放数组下标。使用for循环遍历的时候,如果栈为空或者栈顶元素大于等于要放进去的元素,则放进去;否则,依次pop两个栈,同时,将当前元素下标与存放数组下标的栈顶元素相减,即为需要等待的天数。使用map来存放。但是这里存在一个问题。如果数组元素存在相同的元素,则后遍历的数组元素“需要等待的天数”在map里面会覆盖前遍历的相同元素。于是,我放弃了一个栈。只留下一个栈,存放下标。同时,ma

2020-06-11 21:01:49
勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv3
    勤写标兵Lv3
    授予每个自然周发布7篇到8篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。