spiral matrix中任意位置的元素

发表于 2017-04-14 | 分类于 Algorithm |

今天面试的一道题，回来的路上想出来了。。结果当然是杯具了。。

题目

给一个回形矩阵，例如

1
2
3

123
894
765

问任意(i, j)位置的元素是多少

解法

假设是一个M*N的矩阵，既然是回形的，对于所求位置(i, j)，我们可以判断它所处于第几个环，即

1	min(i, j, M - i - 1, N - j - 1)

而第k环，所包含的元素个数为(k从1计)

1	2(M + N - 2) - 8(k - 1)

所以前n环的元素个数为(n从0计)

1
2
3

sum(0 <= i < n : 2*(M + N - 2) - 8*i) = 2*n*(M + N - 2) - 8 * sum(0 <= i < n : i)
                                      = 2*n*(M + N - 2) - 8 * n * (n - 1) / 2
                                      = 2*n*(M + N - 2*n)

最终结果（copy from stackoverflow）

if (n == y) {
    // top of this round
    index += x - n;
} else {
    // add full top of this round
    index += M - 2 * n;
    if (n == M - x - 1) {
        // right side of this round
        index += y - (n + 1);
    } else {
        // add full right side  of this round
        index += N - 2 * n - 1;
        if (n == N - y - 1) {
            // bottom of this round
            index += N - x - 1 - (n + 1);
        } else {
            // add full bottom of this round
            index += M - 2 * n - 1;
            // left side of this round
            index += M - y - 1 - (n+1);
        }
    }
}

小结

好好学基础（语言+算法），然后深入一个领域。至于碰上文不对题的面试官，那就是运气玄学了。

大数据平台介绍

发表于 2017-03-09 | 分类于 Big Data |

本文主要对当前主流的大数据处理平台做一个简介，包括它们的发展史、整体结构、相互之间关系和使用场景，属于科普文章。

阅读全文 »

hihocoder-Offer收割编程练习赛8

发表于 2017-03-05 | 分类于 Algorithm |

2017-03-05 hihocoder[Offer收割]编程练习赛8题解

阅读全文 »

Spark vs Flink

发表于 2017-02-24 | 分类于 Big Data |

Spark和Flink是当今最主流的两个处理平台，早期Flink主要针对流处理，与之对应的是Spark Streaming，但随着两者的发展，许多地方逐渐统一。无论是Spark还是Flink都在解决MR针对迭代型数据处理需要反复存/读取硬盘的问题，并且在传统map，reduce算子的基础上扩充了许多算子。本文主要包括两个方面，Spark、Flink的介绍和比较。

阅读全文 »