6 陈喻

深信服科技 android开发工程师

https://selfboot.cn/2016/09/01/lost_partition/ http://www.dooccn.com/cpp/#id/5285d6c8651adc393110694371de5da2 https://www.cnblogs.com/liwei2222/p/8013367.html

等级
TA的排名 237

剑指offer之最小的K个数

1问题输入N个整数,找出其中最小的K个,例如输入数组6、5、1、4、2、7、3、8,最小的4个数是1、2、3、42分析1)我们可以用快速排序从小到大,但是时间复杂度是O(nlogn)我们取出最前面的K个数就行。2)用partition算法,时间复杂度是O(n)我之前的博客讲解partition算法的总结如下:我们使用partition算法的时...

2019-10-20 01:56:19

剑指offer之快速排序

1快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列2分析思路很明显,先是用到了partition算法思想(前面的博客提到了),然后再把原始数据分成几部分然后递归同样用partition算法处理...

2019-10-19 02:20:35

剑指offer之partition算法

1问题partition算法:从无序数组中选出枢轴点pivot,然后通过一趟扫描,以pivot为分界线将数组中其他元素分为两部分,使得左边部分的数小于等于枢轴,右边部分的数大于等于枢轴(左部分或者右部分都可能为空),最后返回枢轴在新的数组中的位置。如果原始数组为[5,9,2,1,4,7,5,8,3,6],那么整个处理的过程如下图Partition可不只用在快速排序...

2019-10-18 01:36:54

linux shell之删除当前文件夹不包含文件1和文件2的其他所有文件

1问题删除当前文件夹不包含文件1和文件2的其他所有文件,这个当前文件夹里面可以包含子文件夹,然后子文件夹里面也有文件1和文件2,但是这里的文件1和文件2也不应该被删除。2解决办法可以用如下shell命令都行find.-typef-not-name"1.txt"-not-name"2.txt"-execrm-rf{}\;...

2019-10-17 21:29:11

剑指offer之数组出现次数超过一半的数字

1问题数组中有一个数字出现了次数超过数组长度的一半,请找出这个数字。比如{1,2,3,2,2,2,5,4,2},我们知道这个数是22分析我们数组元素个数分为单数和双数1)数组长度是单数的情况下我们有5个元素,里面至少3个2,还有2个元素我们可能重复也可能不重复我们可以定义一个计数为1,先用变量保存数组第一个数据,然后遍历数组,如果发现后面的数...

2019-10-17 00:24:24

剑指offer之重建二叉树

1问题重建二叉树:给定二叉树的先序遍历(根左右)和中序(左中右)遍历结果,建立这棵二叉树。输入保证二叉树无重复结点以先序{1,2,4,7,3,5,6,8}和中序{4,7,2,1,5,3,8,6}为例2分析先序遍历的特点,我们知道{1,2,4,7,3,5,6,8}第一个元素1就是树的根节点,然后中序遍历{4,...

2019-10-15 01:09:55

剑指offer之求二叉树中两个节点的最低共同父节点

1问题求二叉树中俩个节点的最低共同父节点,比如二叉树如下4261357比如节点1和3两个节点的最低共同父节点是2,节点3和5两个节点的最低共同父节点是4,节点5和6两个节点的最低共同父节点是6,也有可能其中1个节点或者2个节点不在二叉树里面,那么他们就...

2019-10-12 23:41:00

剑指offer之二叉树的下一个结点

1问题给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针2分析比如我现在的二叉树如下4261357这里分3种情况1)如果这个节点包含右子树,...

2019-10-11 23:26:01

剑指offer之二叉搜索树和双向链表

1问题比如我们搜索二叉树如下,我们需要变成双向链表2分析我们知道这个变成双向链接的时候是按照树的中序遍历打印的,我们只需要在中序遍历打印的时候操作该节点,我们可以用临时变量保存这个节点,同时我们也需要单独增加一个链表节点变量,我们需要保证这个节点的左边指向是该链表节点,然后该链表节点的右指向是这个节点,然后我们再把这个节点赋值给这个链表节点,...

2019-10-11 00:37:11

剑指offer之二叉搜索树的第K个节点

1问题给定一颗二叉搜索树,请找出其中的第k小的结点。例如,5372468中,按结点数值大小顺序第三个结点的值为4。2分析二叉树定义:二叉查找树(BinarySearchTree),(又:二叉搜索树,二叉排序树)它或者是一棵空树,或者是具有下列性质的二叉树:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树...

2019-10-10 01:15:44

剑指offer之两个队列实现栈的问题

1问题两个队列实现栈的插入和获取头部元素的功能2分析1)获取头部元素的功能分析:我们有2个队列,我们知道队列的特点的先进先出,而栈的特点是先进后出,比如我们有数据1,2,3,4,我们分别依次压入队列1,队列2目前是空,我们需要有栈的效果,加上队列2也是先进先出的特点,意味着我们队列2里面的数据依次是4,3,2,1入队列2,现在问题转成了...

2019-09-29 23:27:33

剑指offer之两个栈实现队列问题

1问题两个栈实现队列的插入和获取头部元素的功能2分析我们定义连个栈stack1,stack2,当队列弹出头部元素的时候,我们知道队列先进后出,我们先把一个元素压到stack1,然后再压一个元素到stack1,然后我们把stack1的top函数得到栈顶值然后pop弹出来,push到stack2里面去,这个时候后面进的元素就在stack2...

2019-09-28 23:58:11

剑指offer之青蛙跳台阶问题

1问题一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶,求该青蛙跳上一个n级的台阶总共有多少种跳法?2分析我们可以定位函数f(n),n为n级别的台阶,f(n)的值是青蛙有多少种跳法,我们知道当n为1的时候,f(1)=1;当n为2的时候,我们知道可以先跳一级再跳一级,或者直接跳2级,这里就有2种跳法,所以f(2)=2;当n为3的时候,我们可以这样理解...

2019-09-27 23:04:18

剑指offer之斐波那契数列

1问题写一个函数,输入n,求斐波那契数列的第n项。斐波那契数列定义如下。f(n)=0;(n=0)f(n)=1;(n=1)f(n)=f(n-1)+f(n-2);(n>=2);2分析1)直接用递归2)我们用两个变量保持每次需要计算下一个值得前面2个数,从最前面开始迭代。...

2019-09-26 22:36:46

剑指offer之剪绳子问题

1问题给你一根长度为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.2分析1)分析边界值n和m题目说了,要求大于1,所以...

2019-09-25 22:22:55

谷歌浏览器之安装插件(SwitchyOmega_Chromium)提示程序包无效:"CRX_HEADER_INVALID"

1问题我在google浏览器里面安装插件,打开了浏览器的"更多工具"--->"扩展程序"后,打开了“”发开者模式”,然后我把下载好的SwitchyOmega_Chromium.crx插件直接拖到浏览器,提示错误如下。SwitchyOmega_Chromium.crx的下载地址:https://github.com/FelisCatus/SwitchyOmega/rele...

2019-09-24 16:08:41

剑指offer之和为s的数组

1问题输入一个递增排序数组和数字和s,在数组里面找2个数,他们的和是s,如果有多对,只需要输出一对。比如数组{1,2,4,7,11,15},我们输出4,112思路我们定义2个首尾指针,先是1+15,大于15,然后我们尾巴指针左移一下,然后就是1+11小于15,然后首指针右移动一下,2+11,依次类推。3代码实现#i...

2019-08-07 18:14:03

剑指offer之左旋转字符串

1题目字符串的左旋转操作是把字符串前面的若干字符转移到字符串尾部,比如字符串abcdef和数字2,函数返回左旋转得到的结果是cdefgab2思路先反转字符串所有,通过数字n找到的边界,然后再反转字符串部分左边和部分右边。3代码实现#include<stdio.h>/**反转整个字符串*/vo...

2019-08-06 22:41:25

剑指offer之翻转单词顺序

1题目输入一个英文橘子,翻转句子中的单词顺序,但是单词内字符串的顺序不变,简单起见,标点符号和普通字符字母一样处理,例如输入字符串"Iamastudent.",则输出"student.aamI"2思路先反转字符串所有,然后在反转里面的单词,我们用两个首尾指针操作3代码实现#include<stdio...

2019-08-06 12:12:45

剑指offer之滑动窗口的最大值

1问题给定一个数组和滑动窗口的大小,请找出所有滑动窗口里的最大值,列如,数组{2,3,4,2,6,2,5,1}的滑动窗口大小是3,一起6个滑动窗口,分别是{4,4,6,6,5}2分析2,3,4,2,6,2,5,1我们这里可以用双端队列,滑动窗口是3,我们先找出前3个数字里面的最大值,放在双端队列的头,然后依次向右滑动,确保每次滑动后队列的头是最大值。...

2019-08-03 15:28:51

查看更多

勋章 我的勋章
  • 脉脉勋章
    脉脉勋章
    绑定脉脉第三方账户获取
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。