概述

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

m，n均为数组长度）的要求之下，求两个已排序数组的中位数。

分析

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

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

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

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

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

解法

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;
    }
}

概述

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)，如：

输出结果为：

反之亦然。

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

解法