程序员面试金典(二)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的数组,然后将第一行保存到中间数组,然后将第一列拷贝到第一行,然后将最后一行拷贝到第一列,然后再将最右边一列拷贝到最下一行,然后再......

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

确定字符互异

题目描述

请实现一个算法,确定一个字符串的所有字符是否全都不同。这里我们要求不允许使用额外的存储结构。

给定一个string iniString,请返回一个bool值,True代表所有字符全都不同,False代表存在相同的字符。保证字符串中的字符为ASCII字符。字符串的长度小于等于3000。

测试样例:

"aeiou"

返回:True

"BarackObama"

返回:False

#include <stdio.h>

#include <stdbool.h>

bool checkdiff(ch......

如何快速尝出毒酒

问题描述

国王有一百桶酒,比自己的生命还重要。结果有一天其中一桶被投了慢性毒药,喝了以后半个小时以后就会死掉。国王大怒,命令玩忽职守的侍卫去试毒。酒不能被混合,一个侍卫可以喝多桶酒,一桶酒也可以由多个侍卫喝,怎么样才能用最少的侍卫、在最短的时间知道哪桶是毒酒。侍卫可以理解为线程,即怎么样用最少的线程用最快的速度完成这个工作。

方案

最简单的方案肯定是找100个人,每个人试一桶酒,那么用时30分钟,就可以判断出哪一桶就有毒。

再进一步的,可以使用分段法,把酒分成n(n>=2)份,先找n个侍卫试酒,可以定位出哪一段的酒有毒,再接着分段试酒。但这种方案,分段数目越少,试出毒酒的平均耗......

替换空格

请实现一个函数,把字符串中的每个空格替换成”%20”。例如输入“We are happy.”, 则输出”We%20are%20happy.”。

在网络编程中,如果URL参数中含有特殊字符,如空格、'#'等,可能导致服务器端无法获得正确的参数值。我们需要将这些特殊符号转换成服务器可以识别的字符。转换的规则是在'%'后面跟上ASCII码的两位十六进制的表示。比如空格的ASCII码是32,即十六进制的0x20,因此空格被替换成"%20"。再比如'#'的ASCII码为35,即十六进制的0x23,它在URL中被替换为"%23......

二维数组中的查找

题目描述

在一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。

分析:

1

2

8

9

2

4

9

12

4

7

10

13

6

8

11

15

从二维数组最右上角的数值(9)开始比较,若目标比该数大,则目标肯定在该数的下方,反之,在该数的左方。根据此规则,寻找下一个比较的数值,重复以上规则,直到找到目标数,或者数组越界。

//

// main.c

// func

//

// Created by 52coder o......

算法概论

本文是算法概论读书笔记,算法概论这本书在豆瓣评分高达9分,在收到学弟寄来的这本书我随手翻了几页就被书中所述内容所吸引,因此本文持续记录书中对于我来说比较有意思又或者我之前理解不深刻或错误的地方。

序言

序言部分从费波那奇数列介绍开始,引入费波那奇数列的递归实现,接着分析递归实现算法慢的原因,因为很多求解步骤都是重复的。一种更合理的机制是随时存储中间计算结果。

C语言实现:

#include <stdio.h>

int Fibonacci(int n)

{

// 递归结束条件

if (0 == n)

{

return 0;

}

if (1 == n)

{

return ......

排序算法总结

排序就是将一组对象按照某种逻辑顺序重新排列的过程,本文是记录学习排序的总结,持续更新,计划一周时间,视工作忙与否而定。

选择排序

算法思路:

首先找到数组中的最小元素,其次将它和数组的第一个元素交换位置。再次在剩下的元素中找到最小元素,将它与数组的第二个元素交换位置。如此反复,直到将整个数组排序。

算法实现:

#include <stdio.h>

void SelectionSort(int a[],int n)

{

int pos = 0;

int temp = 0;

for(int i = 0;i < n;i++)

{

pos = i;

for(int j ......

Q06考拉兹猜想

本文是程序员算法趣题一书Q06 C语言实现,由于该书中所给的代码是Javascripts与Ruby,故在今后的阅读中会记录部分习题的C语言实现。

Q06考拉兹猜想

对自然数n循环执行如下操作:

n是偶数时,用n除以2

n是奇数时,用n乘以3后加1

如此循环操作,无论初始值是什么数字,最终都会得到1

但是Q06对原来的考拉兹猜想做了改动,参考题目如下:

Q05现金支付

本文是程序员算法趣题一书Q05 C语言实现,由于该书中所给的代码是Javascripts与Ruby,故在今后的阅读中会记录部分习题的C语言实现。

Q05现金支付就是大整数分解问题.将一个大整数,用指定的小整数进行组合。

Q05中作者先通过一个特定的例子,比如求1000元日元的组合,并且给出了限制,最多兑换的硬币个数不超过15.

1000日元的组合情况:

/......

Q04切分木棒

本文是程序员算法趣题一书Q04 C语言实现,由于该书中所给的代码是Javascripts与Ruby,故在今后的阅读中会记录部分习题的C语言实现。

Q04问题后面的Column中介绍了深度优先搜索和广度优先搜索。

深度优先搜索算法(英语:Depth-First-Search,简称DFS)是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点,尽可能深的搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访问......