8 kikajack

尚未进行身份认证

暂无相关简介

等级
TA的排名 2k+

【二叉树】O(1)空间复杂度的Morris遍历

对于二叉树的遍历,常规的递归或迭代都需要用到栈,不管是函数调用栈还是手动创建的栈。因此空间复杂度都是O(n)。如果要省掉栈的开销,将空间复杂度降低到O(1),则需要借助二叉树中的叶子节点来保存临时信息。只要当前节点cur不为空,就一直循环:如果当前节点cur的左子节点不存在,则输出cur,并设置cur=cur.right否则,寻找当前节点中序遍历的前驱节点prev...

2019-11-03 15:17:03

【二叉树】Python 从List创建二叉树及4种遍历的递归和非递归实现

#-*-coding:UTF-8-*-fromcollectionsimportdequeclassTreeNode:def__init__(self,val):self.val=valself.left=Noneself.right=NoneclassTree:def__ini...

2019-11-01 13:25:36

【算法与数据结构】字符串模式匹配

语义在一个很长的字符串T中,查找是否存在子字符串P。例如搜索引擎收录的大量网站数据,当用户输入关键字后,就会在这些数据中进行匹配,并返回合适的网站。语义:假定字符串长度为j,则所有字符串都在[0,j)这样的集合中。返回首次匹配的字符的位置。注意这里调用方需要判断位置是否正确,例如对于长度为i的字符串,要查找是否有长度为j的字符串,如果返回值在[0,i-j)则为...

2019-10-20 22:21:48

【算法与数据结构】查找算法语义约定及二分查找

对于有序数组,通常用二分查找(包括改进型的Fibonacci查找和插值查找)。查找算法语义约定一般简单的查找算法,可以在查找失败时直接返回-1。但为了让函数更具有通用性(例如对于插入操作,需要定位到精确的位置),通常约定的语义为(假设数组A[lo,hi),要查找元素e):返回不大于e的最大的下标,几种特殊情况:如果数组中有多个等于e的元素,返回最大下标如果e比所有元...

2019-10-07 15:08:34

【算法与数据结构】分治法和快速排序

快排思想:从待排序数据中,选取一个数字做基准pivot把所有比pivot小的数据放在pivot左边,大的放在右边对左右两个子序列递归使用上面两个步骤子序列中仅有一个元素时,退出C代码:#include<stdio.h>voidquickSort(intarr[],intlo,inthi){intbeg=lo,end=...

2019-10-06 13:31:03

【算法与数据结构】分治策略与归并排序

分治策略对于所求的问题域,每次将其分为大小相似的两部分,然后再把每一部分当作最初的问题域再次分割,依次递归,直到得到基本问题(递归基),求解。然后,再逐步合并直到完成最初的问题域。通常用递归的方式分割问题,例如这里的归并排序,每次将数组一分为二,然后分别判断分割动作是否到不可再分割了(数组中仅剩最后一个元素),否则继续对左右两个子数组进行分割:voidmerge_sort(intarr[...

2019-09-28 15:03:18

【Linux 应用编程】IO 多路转接 - epoll

跟select、poll的对比epoll性能更高,Nginx、redis等流行的软件,都是基于epoll实现的。epoll优点有:监听描述符数量大于1024只返回准备好的描述符,不需要浪费时间遍历描述符集合基于红黑树实现,高效使用步骤epoll有3个函数:epoll_create指定epoll对应的红黑树的大概节点数,并返回epoll描述符ep...

2019-09-22 19:32:02

MySQL - 慢查询日志

开启慢查询日志通过set命令可以临时开启慢查询日志,MySQL重启后修改丢失。如果想要永久开启,则需要修改配置文件,Linux中是/etc/my.conf文件。临时开启慢查询日志mysql>setglobalslow_query_log=1;QueryOK,0rowsaffected(1.80sec)mysql>showvariable...

2019-09-22 11:35:13

【Linux 应用编程】IO 多路转接 - select 和 poll

Linux中,read和write函数默认实现的是阻塞式的IO。例如:while((n=read(STDIN_FILENO,buf,BUFSIZ)>0){ if(write(STDOUT_FILENO,buf,n)!=n){ perror("write"); eixt(EXIT_FAILURE); }}如果需要同时从多个描述符读,则不...

2019-09-16 22:19:40

MySQL - explain 输出信息详解

常用SQL(假设表名是student)连接查询、联合查询、子查询:查看表结构:showcreatestudent;descstudent;增删索引:增加主键:altertableclassaddconstraintprimarykeycid_pk(cid);删除主键:altertableclassdropprimarykey;增加索引:alter...

2019-09-20 19:59:04

MySQL 连接查询、联合查询和子查询

准备测试数据createtableclass( cidint(10), cdescvarchar(20));createtablestudent( sidint(10), namevarchar(20), ageint(3), cidint(10));createtableteacher( tidint(10), namevarchar(2...

2019-09-20 19:44:16

【Linux 网络编程】多进程、多线程服务器并发模型

服务器在执行accept等待客户端连接时,会阻塞。客户端连接成功后accept函数返回,执行后面的代码。如果想要服务器同时为多个客户端服务,有以下几种方式:多进程:每来一个客户端,就开一个进程与其通讯。多线程:跟多进程类似,但每个客户端对应一个单独的线程IO多路复用:借助select、poll函数实现多进程服务器多进程模型中,为了避免产生僵尸进程,父进程必须回收子进程资...

2019-09-16 15:37:45

【Linux 网络编程】socket 实现服务器和客户端

IP地址可以标识网络中的主机,协议类型(TCP或UDP)加端口号可以表示主机上的进程。基本原理文件类型Linux中有七种类型的文件,这些文件类型可以使用一些基本的函数,例如read、write:普通文件目录链接文件字符设备块设备管道:pipe匿名管道,fifo有名管道套接字:socket套接字是全双工的,虽然只有一个文件描述符,但是在Linux内核中读写操作分别...

2019-09-15 12:47:06

C 语言中使用多字节字符,通过 UTF-8 支持中文

C语言默认的char类型是单字节字符,仅支持ASCII码。但是ISOC90标准开始,定义了wchar_t类型用于支持多字节字符(头文件wchar.h)。这一版标准中还定义了本地化和国际化相关的头文件locale.h,可以通过其中的setlocale函数设置使用的字符集编码,一般用UTF-8足够了。每一种语言都分为内部编码(程序代码中使用的)和外部编码(例如打开的...

2019-09-01 15:26:49

【算法与数据结构】双端队列示例

双端队列可以从两侧入队和出队:#include<stdio.h>#include<stdlib.h>structdequeNode{intdata;structdequeNode*next;structdequeNode*prev;};typedefstructdequeNodeNode;typedefNode*...

2019-08-25 18:12:00

【算法与数据结构】优先级队列 - 用二叉堆求数据流中的第K大的元素

数据流中的第K大的元素,总数据个数不足K个元素时返回-1。#include<stdio.h>#include<stdlib.h>typedefstruct{int*data;intcount;intcapacity;}KthLargest;voidheap_up(KthLargest*obj,intloc)...

2019-08-24 10:58:24

【算法与数据结构】 用栈实现队列、用队列实现栈

用栈实现队列效果(需要两个栈)思路:栈1负责进数据,每次要实现出队效果的时候,借助栈2颠倒顺序后出栈即可。元素出队后可以有两种方式:把出队后栈2中的数据再依次放入栈1。效率低。出队后,栈2中的数据不需要动,此时仍然用栈1入栈,栈2出栈,只有在栈2空的时候,再把栈1中的所有数据搬入栈1。高效。#include<stdio.h>#include<stdlib.h&...

2019-08-20 22:31:47

【算法与数据结构】链表逆序、相邻两元素逆序、探测环路

链表常见操作有:链表逆序链表每相邻两个元素逆序,例如1,2,3,4=>2,1,4,3探测是否构成环路#include<stdio.h>#include<stdlib.h>typedefstructNodeStruct{intdata;structNodeStruct*next;}Node,*...

2019-08-19 23:07:53

【算法与数据结构】无重复字符的最长子串 -暴力破解和滑动窗口

滑动窗口创建两个指针start和end,分别指向窗口起止位置。对于长度为n的字符串,总共需要循环n次。每次循环时,end指针加一,同时保存当前字符的下一个位置,然后判断是否出现重复字符。如果无重复,则继续下次循环如果重复,则把start移到记录中对应字符的下一个位置#include<stdio.h>#include<string.h>...

2019-08-18 12:28:21

HashTable 示例 - 找出数组中和为指定值的两个数

数组[2,4,6,8],和为8,则返回[0,2]数组[2,3,3],和为6,则返回[1,2]#include<stdio.h>#include<stdlib.h>typedefunsignedintIndex;typedefstructnode{intdata;structnode*next;...

2019-08-17 22:40:57

查看更多

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