月度归档:2016年04月

LeetCode-9

title: LeetCode-9

date: 2016-04-20 23:13:59

categories: Try

tags: LeetCode

概述

Palindrome Number 判断文字是否是回文,输出布尔值。

分析

作为一道 Easy 的题目,看起来并不是特别麻烦,不过这题要求无需增加附加的空间复杂度。

题目要求判断是否为回文数,那么负数肯定不是回文数,因为负数带有符号位。

从字符串的角度来看,回文只需判断反转之后是否相同即可,那么针对数字亦可以使用这一方法。

考虑到数字反转之后会出现溢出的情况,而正数溢出之后在 Java 中的处理方式则是变为一个负数(参见 SO 上的问题 How does Java handle integer underflows and overflows and how would you check for it?),那么反转后变为负数的数字自然不是一个回文数了,因为反转之后在非负整数的范围内显然这个数字不存在。

不新增变量的情况下,只能通过递归来解决问题了。

解法

public class Solution {
    public static int len(int v) {
        return (v == 0 ? 0 : 1 + len(v / 10));
    }

    public static int reverse(int x) {
        if (x < 10) {
            return x;
        }

        return reverse(x / 10) + (x % 10) * (int)Math.pow(10, len(x) - 1);
    }

    public boolean isPalindrome(int x) {
        if (x < 0) {
            return false;
        }

        if (x == 0) {
            return true;
        }

        return x == reverse(x);
    }
}

LeetCode-7

 

概述

Reverse Integer 简单题,要求将不带符号位的整数反转,如果遇到溢出问题,则输出0。

分析

题目的特别之处在于溢出的处理,数字反转之后很可能超过了 Integer.MAX_VALUE 或者Integer.MIN_VALUE 的范围,应对这种情况,可以将溢出整数范围的的结果认定为0。

参见 SO 上的问题 How does Java handle integer underflows and overflows and how would you check for it?, Java的处理方式是在两个极值之间轮转,超过最大值(2147483647),则从最小值开始逐步趋近最小值(-2147483648),如:

输出结果为:

反之亦然。

解法先用字符串操作的方式进行,还需要探究更高效的算法。

解法

LeetCode-6

title: LeetCode-6

date: 2016-04-14 20:25:06

categories: Try

tags: LeetCode

概述

作为一道简单题,ZigZag Conversion 即将字符串按照之字形显示后,再逐行打印字符串。

分析

这一题题意自然是很明显的,但是,这个之字形的形状需要注意,这一个之字形的形状应该是:

A     G     M     S     Y
B   F H   L N   R T   X Z
C E   I K   O Q   U W
D     J     P     V

而不是类似字母 N 的模样。这里是需要注意的一点,题目中的示例为三行,并不是很明显。

简单来说,可以直接模拟重新排布字字母的过程,字母可以看做填写在一个 m * n 的矩阵中(m * n >= s.length())。

如果想要在 O(n) 的时间复杂度内解决问题,那么最理想的方法应该是根据行列的位置,确定当前是填充字母还是留空。

观察这一个矩阵,若行数为 n,那么可以看做有多个 n * (n - 1) 的子矩阵,形状都是重复的,只需要得到各个位置上的字符与源字符串中的下标的对应关系即可得知当前应该出现的字母。

对于一个行数为 n 的子矩阵,包含的字符个数应为 <= 2n – 2。从左往右,第 i 个(i >= 1)子矩阵的字符串包含的字母下标范围为 [(i - 1) * (2n - 2), i * (2n - 2))

从行的角度来看,每行在每个子矩阵中,子矩阵的第一列一定是有字母的,而这个字母在源字符串中正是连续的,所以,每行直接输出子矩阵对应的字母的前 n 个字符即可。

而剩下的 n – 2 个字符,则是类似斜率为1的一条直线的排布,我们要做的,即当运行到对应点时,结合横纵位置,判断当前是否有字符,如果没出现下标越界,说明此处应显示对应的字母。

解法

public class Solution {
    public String convert(String s, int numRows) {
        if (numRows == 1) {
            return s;
        }

        int sLen = s.length();
        int colNum = (int) Math.ceil(1.0 * sLen / numRows);
        int sectionNum = 2 * numRows - 2;

        String result = "";

        for (int r = 0; r < numRows; ++r) {
            for (int c = 0; c < colNum; ++c) {
                int idx = c * sectionNum + r;

                if (idx < sLen) {
                    result += s.substring(idx, idx + 1);

                    if (r >= 1 && r <= numRows - 2) {
                        int idxAppend = (c + 1) * sectionNum - r;

                        if (idxAppend >= 0 && idxAppend < sLen) {
                            result += s.substring(idxAppend, idxAppend + 1);
                        }
                    }
                }
            }
        }

        return result;
    }
}

LeetCode-4

 

概述

作为复杂题的第一题(Median of Two Sorted Arrays),在时间复杂度为O(log (m+n))

mn均为数组长度)的要求之下,求两个已排序数组的中位数。

分析

首先中位数的定义可以在 WikiPedia 上了解到。在已排序的前提下,即奇数元素个数的数组,为中间值;偶数元素个数的数组则为中间二值的算数平均数。

那么两个序列求中位数,可以考虑先将二者合并排序之后,进行中位数的求值。

考虑到两数组已经排序,那么我们所需要做的就是进行一次归并排序。

归并排序作为一个相当稳定的排序方式,在时间复杂度上能够满足需求。

考虑到虽然数组是排序数组,但是并没有说明是升序或是降序,无妨,如果是降序,那么将下标从尾部开始即可,但是个人测试,应该没有出现这类 case 。

解法

LeetCode-3

 

概述

今天份的LeetCode题目 Longest Substring Without Repeating Characters 也是一道 Medium 的题目。

大意即找出给定字符串中的连续最长非重复子序列的长度。

分析

首先,字符串连续的前提之下,若在位置 nm (m>n)出现了重复的字符,n位置以及之前的字符是不能再继续算入连续的非重复字符串的,所以,这时候统计的字符串的起始位置要变为 n + 1 位置下的字符。

在出现重复时,判断当前已经连续的非重复字符的个数是否已经大于已记录的最长字符串的长度,如大于则替换之。

最后返回计算出的结果即可。

这一方法只需一次遍历字符串即可得知最大的长度,由于使用了HashMap存储最长子串中的字符与下标的对应关系,时间复杂度为O(n)

解法