算法学习(4)

近期刷题小结:

Palindrome Number

之前的方法主要是转成字符串,或者是翻转数字之后比较。但是题目要求不能使用额外的空间,所以需要直接取出数字的首末位比较。先求得数字的位数,然后用(x % 10) != (x / (int) (Math.pow(10, len – 1))) 比较头尾,每次比较完之后会掐头去尾得到一个新的数,依次可求是否为回文数。

Regular Expression Matching

模式匹配还是需要用到递归的,看起来也比较清楚。每次获取两个字符串的首位,然后主要有两种情况:1、单个字符,且后续没有*号,直接比较,然后比较各自-1的子串;2、后续有*号,这种情况相对复杂,又分成三种可能,最常见的是aaa和a*这样,a*匹配所有的a;一种是像aaa和aa*a这种,可能a*只匹配1个a;另外一种是像aa和c*a*,c*根本不匹配。

Container With Most Water

暴力算法就是循环两遍,找到所有的组合比较,效率较低

可以分析得出,如果从两端开始计算,依次缩小范围,只有可能中间的两块板特别高,才有可能比摊平的要大。所以依次取left和right计算area,然后将较小的抛弃,计算内部的可能area。

Integer to Roman

Roman to Integer

这两个的思想都是先定义了对应关系:

int[] nums = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
String[] romans = { “I”, “IV”, “V”, “IX”, “X”, “XL”, “L”, “XC”, “C”, “CD”, “D”, “CM”, “M” };

然后使用累加的思想,每次累加依次,就输出一个罗马数字,这也是罗马数字本身的思想。比如III是3个1累加和VI是5加1

反过来也是,依次从最大的开始匹配字符串,然后累加,比如DCXXI,依次匹配D,C,X,X,I,因为不存在DC或者XI这样的组合

注意都是要从最大的数开始累加

Longest Common Prefix

这个的思想比较直接,时间复杂度是O(nm),n个字符串,m是最长前缀子串的长度。

依次取出第i个字符,看是不是每个字符串都包括,如果包括就加入common prefix

 

 

Objective-C语法快速参考

大部分有一点其他平台开发基础的初学者看到XCode,第一感想是磨拳擦掌,看到Interface Builder之后,第一感想是跃跃欲试,而看到Objective-C的语法,第一感想就变成就望而却步了。好吧,我是在说我自己。

如果你和我一样,对苹果相关的开发:Mac OS X或是iPhone有兴趣,但是第一时间看到Objective-C就会头疼并伴有发烧症状的话,疗效比较好的快速治疗方法是阅读本文。大概花二十分钟左右,而且绝不无聊的时间,你就会对Objective-C有那么一点点了解,至少读读例子不会那么头疼了。

不过假定你要有那么一点点c++、c#或是java的基础,至少能看到c++、c#或是java的源码,能够大致明白说得是什么。

这篇文章不是一篇科技文章,希望你也不要把它当做科技文章来读。文章非常不严谨,但是我相信你能看得懂。

一、XCode、Objective-C、Cocoa说的是几样东西?

答案:三样东西。

XCode:你可以把它看成是一个开发环境,就好像Visual Studio或者Netbeans或者SharpDevelop一样的玩意。你可以将Interface Builder认为是Visual Studio中用来画界面的那部分功能单独提出来的程序。

Objective-C:这是一种语言,就好像c++是一种语言,Java是一种语言,c#是一种语言,莺歌历史也是一种语言一样。

Cocoa:是一大堆函数库,就好像MFC.NETSwing这类玩意,人家已经写好了一堆现成的东西,你只要知道怎么用就可以了。

有些人会比较容易混淆Objective-CCocoa,就好像有些人会混淆c#.NET一样。这两个东西真的是两个不一样的东西。

二、Objective-C是什么?

你可以把它认为是语法稍稍有点不一样的c语言。虽然第一眼望上去你可能会认为它是火星语,和你所认知的任何一种语言都不一样。

先简单列出一点差别:

 

问题一:我在程序中看到大量的减号、中括号和NS****这种东西,他们是什么玩意儿?

1 减号(或者加号)

减号表示一个函数、或者方法、或者消息的开始,怎么说都行。

比如c#中,一个方法的写法可能是:

private void hello(bool ishello)

{

//OOXX

}

用Objective-C写出来就是

-(void) hello:(BOOL)ishello

{

//OOXX

}

挺好懂的吧?

不过在Objective-C里面没有publicprivate的概念,你可以认为全是public

而用加号的意思就是其他函数可以直接调用这个类中的这个函数,而不用创建这个类的实例。

2 中括号

中括号可以认为是如何调用你刚才写的这个方法,通常在Objective-C里说“消息”。

比如C#里你可以这么写:

this.hello(true);

在Objective-C里,就要写成:

[self hello:YES];

3 NS****

老乔当年被人挤兑出苹果,自立门户的时候做了个公司叫做NextStep,里面这一整套开发包很是让一些科学家们喜欢,而现在Mac OS用的就是NextStep这一套函数库。

这些开发NextStep的人们比较自恋地把函数库里面所有的类都用NextStep的缩写打头命名,也就是NS****了。比较常见的比如:

继续阅读“Objective-C语法快速参考”

算法学习(3)

继续刷题

atoi函数的实现,需要注意的问题:

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found. Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.

1.从第一个不是空格的开始转换

2.如果空串,或者全是空格,或者没有符号+数字这种组合出现,返回0

3.注意正负和int越界的问题

4.连续符号出现返回0

5.转换过程中如果遇到其他非数字字符,停止转换,返回现有值