最近的事

厦门佛事用品展

故宫博物院

准备去美国

好多好多事

做都做不完的事

希望越来越好

ps:ipad pro的键盘和鼠标都挺好用的

坐等今天晚上的新mac

算法学习(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

 

 

算法学习(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.转换过程中如果遇到其他非数字字符,停止转换,返回现有值

算法学习(2)

继续在Coursera上复习算法

包括

Union-Find:快速查找,快速连接,找到最顶端父节点连接

元素排序算法:选择排序(每次交换较小的到首位),插入排序(插入到已排序的数组),希尔排序(间隔13-4-1插入排序),乱序方法(O(n)时间复杂度的随机序方法)

随机散点的凸多边形问题,Y坐标排序,遍历取角度,判断是否逆时针

待学习:

堆栈,变长数组,队列

 

leetcode方面

最长回文子序列:反向字符串求最长子串,哨兵和反射结构

Add Two Numbers:链表反序存储和进位

ZigZag Conversion:数学问题,找位移规律

Reverse Integer:反向没有0开头,注意负数情况

 

算法学习第一篇

重新开始学习算法

Coursera在线课程,普林斯顿的算法一、二

教材是《Algorithm》

练习题主要是leetcode.com上的OJ里面题,一个一个开始刷吧

全Java实现

今天主要是复习快排,二分,集合操作,求两数和的位置,两有序数组的第K大数,最长无重复连续子串