[置顶]关于博主

首先感谢各位通过域名52coder.net 52murong.com访问本站。52murong.com 慕蓉是我女朋友的名字,她也是一名程序员,现在访问该域与52coder.net均会打开本站。

52coder.net是很早之前与同学一起脑洞的域名:中文名可以叫做-我爱程序员。我记得那年冬天孟非主持的非诚勿扰很火,我信誓旦旦的说以后要做一个网站,专门去为程序员解决个人问题,于是就有了现在的这个域名52coder.net。当时比较热衷于论坛,折腾过Discuz,在读书时折腾过,最多的时候同时在线人数超过1000,论坛的注册人数达到了2w左右,现在却早已忘记当初因为什么原因关闭论坛。

博客开始......

红黑树

红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质

1.节点是红色或黑色。

2.根是黑色。

3.所有叶子都是黑色(叶子是NIL节点)。

4.每个红色节点必须有两个黑色的子节点。(从每个叶子到根的所有路径上不能有两个连续的红色节点。)

5.从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

下面是一个具体的红黑树的图例:

二叉搜索树

二叉查找树(英语:Binary Search Tree),也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;

若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;

任意节点的左、右子树也分别为二叉查找树;

没有键值相等的节点。

[编程珠玑]第一章:开篇

书中第一章给提出了一个如下排序问题:

输入:一个至多包含n个非负整数的文件,每个数都小于n; 且这些整数都不重复;数据之间也不存在关联关系。 此处n取值10000000。

约束:①最多1MB的内存空间可用;②磁盘空间充足;③运行时间最多几分钟, 最好是线性时间。

输出:按升序排列的整数序列。

部分文字部分为节约时间来源于网络,部分内容不再提供参考链接。

位图排序

针对该题的特点,由于待排序的数据记录较多,如果使用常见的排序方法效率较低,而且内存空间有限(限制为1MB左右),不能一次性将数据如内存,需从文件中多次读入,该书引入了一种新的排序方法 ---位图法。

所谓位图法,......

贪心算法入门实例

在leetcode上刷题,学习了传说中的贪心算法,原理的话相对简单。在对动态规划有较深理解后再更新本文。

Leetcode中题目整理如下:

LeetCode C 实现 55. Jump Game

LeetCode C实现 455. Assign Cookies

动态规划入门实例

在leetcode上刷题,学习了传说中的动态规划,原理的话相对简单。可以参考如下链接,阅读之后可以对动态规划有个大概的认识。在对动态规划有较深理解后再更新本文。漫画趣谈:什么是动态规划

Leetcode中题目整理如下:

LeetCode C实现 70. Climbing Stairs

LeetCode C 实现198. House Robber

栈操作C语言实现

栈是一种限制线性列表,该类列表的添加和删除操作只能在一端实现,称为栈顶。栈的实现可以使用数组也可以使用链表来实现。

下面的C语言部分实现了顺序栈的基本操作,包括栈的初始化、入栈、出栈、获得栈顶元素的值等。

#include <stdio.h>

#include <stdbool.h>

/*定义栈的大小*/

#define maxsize 100

typedef int ElemType;

/*顺序栈的实现*/

typedef struct SqStack

{

ElemType data[maxsize];

int top;

}SqStack;

/*栈的初始化*......

程序员面试金典(三)C实现

题目描述

编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前。

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdbool.h>

typedef int ElemType;

/*定义结构体*/

typedef struct LNode

{

struct LNode *next;

ElemType num;

}LNode;

/*链表初始化*/

void initList(LNode ** head)

{

i......

链表基本操作-C语言实现

目前已实现的基本操作包含:

链表初始化

求链表个数

链表插入

链表删除

销毁链表

打印链表

找出单链表中倒数第k个节点

删除单链表中第k个结点,限制条件只能访问第k个结点,不能删除第k个结点

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <stdbool.h>

typedef int ElemType;

/*定义结构体*/

typedef struct LNode

{

struct LNode *next;

ElemType num;......

程序员面试金典(二)C实现

像素反转

题目描述

有一副由NxN矩阵表示的图像,这里每个像素用一个int表示,请编写一个算法,在不占用额外内存空间的情况下(即不使用缓存矩阵),将图像顺时针旋转90度。

给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于500,图像元素小于等于256。

测试样例:

[[1,2,3],[4,5,6],[7,8,9]],3

返回:[[7,4,1],[8,5,2],[9,6,3]]

此题最开始的实现是申请一个大小为N的数组,然后将第一行保存到中间数组,然后将第一列拷贝到第一行,然后将最后一行拷贝到第一列,然后再将最右边一列拷贝到最下一行,然后再......