By Long Luo

This article is the solution 2 Approaches: Base Conversion from High to Low and from Low to High of Problem 171. Excel Sheet Column Number.

Intuition

Basiclly, It’s base conversion.

We are familiar base \(10\). How do we calculate a number?

From high to low, starting with \(ans\) as \(0\), update \(ans\) with the current digit value each time, the update rule is \(ans = ans \times 10 + val\).

If there is a decimal number, encoded as \(\textit{ABC}\) not the arabic number, what’s it?

1
2
3
4

ans = 0
ans = ans * 10 + 1  => A
ans = ans * 10 + 2  => B
ans = ans * 10 + 3  => C

The answer is: \(123\).

from High to Low

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public int titleToNumber(String columnTitle) {
    int n = columnTitle.length();
    int ans = 0;
    int base = 1;
    for (int i = n - 1; i >= 0; i--) {
        int temp = 0;
        if (columnTitle.charAt(i) == 'Z') {
            temp = 26;
        } else {
            temp = columnTitle.charAt(i) - 'A' + 1;
        }
        ans = ans + base * temp;
        base *= 26;
    }

    return ans;
}

By Long Luo

This article is the solution 3 Approaches: Brute Force, HashMap and Sliding Window of Problem 219. Contains Duplicate II.

Here are \(3\) approaches to solve this problem in Java, which is Brute Force, HashMap and Sliding Window.

Brute Force

Easy, using \(2\) loops to determine whether there is the same number.

obviously, it will time out.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public boolean containsNearbyDuplicate(int[] nums, int k) {
    if (nums == null || nums.length <= 1 || k <= 0) {
        return false;
    }

    int len = nums.length;
    for (int i = 0; i < len; i++) {
        for (int j = i + 1; j < len; j++) {
            if (nums[i] == nums[j]) {
                if (Math.abs(i - j) <= k) {
                    return true;
                }
            }
        }
    }

    return false;
}

Analysis

• Time Complexity: \(O(n^2)\)
• Space Complexity: \(O(1)\)

HashMap

We use a \(\texttt{HashMap}\) to record the maximum index of each element. When scanning the array from left to right, the process:

• If an element \(\textit{nums}[i]\) already exists in the hash table and the index \(j\) of the element recorded in the hash table satisfies \(abs(i - j) \le k\), return \(\text{true}\);

• Recording \(\textit{nums}[i]\) and index \(i\) into the hash table, where \(i\) is the largest index of \(\textit{nums}[i]\).

The order of the above two-step operations cannot be changed, when the index \(i\) is traversed, the element equal to the current element and the maximum index of the element can only be found in the elements before the index \(i\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

public boolean containsNearbyDuplicate(int[] nums, int k) {
    if (nums == null || nums.length <= 1 || k <= 0) {
        return false;
    }

    int len = nums.length;
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < len; i++) {
        if (map.containsKey(nums[i])) {
            int idx = map.get(nums[i]);
            if (Math.abs(i - idx) <= k) {
                return true;
            }
            map.put(nums[i], i);
        } else {
            map.put(nums[i], i);
        }
    }

    return false;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(n)\)

By Long Luo

This article is the solution 4 Approaches: Brute Force, Exponent, Binary Search and the Newton’s Iteration Method of Problem 69. Sqrt(x) .

Here shows 4 approaches for finding the square root of a number: Brute Force, Exponent, Binary Search and the Newton’s Iteration Method.

Given an integer \(N\) and a tolerance level \(L\), the task is to find the square root of that number.

Brute Force

The Brute Force way is very easy, just enumerate a value from \(0\) to \(x\), check the product \(i^2\) and target, return the answer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public static int mySqrt(int x) {
    if (x == 0 || x == 1) {
        return x;
    }

    for (int i = 0; i < x; i++) {
        long sum = i * i;
        long bigger = (long) (i + 1) * (i + 1);
        if (sum == x) {
            return i;
        } else if (sum < x && bigger > x) {
            return i;
        }
    }

    return 0;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)

Exponent

Noted that:

\[ \sqrt{x} = x^{1/2} = (e ^ {\ln x})^{1/2} = e^{\frac{1}{2} \ln x} \]

So we can use the exponent \(\exp\) and logarithm \(\ln\) to calculate the square root of the number \(\sqrt{x}\).

It’s really a fast and simple way!

Note: Since the computer can’t store the exact value of the float number, and the parameters and return values of the exponential function and logarithmic function are float numbers, so the result may be wrong.

For example, when \(x = 2147395600\), the result of \(e^{\frac{1}{2} \ln x}\) is \(10^{-11}\) from the correct value of \(46340\) , so when taking the integer part of the result, you will get the wrong result of \(46339\) .

So after getting the integer part \(\textit{ans}\) of the result, we should find out which of \(\textit{ans}\) and \(\textit{ans} + 1\) is the real answer.

1
2
3
4
5
6
7
8

// Exp O(1) O(1)
public static int mySqrt_exp(int x) {
    if (x == 0) {
        return 0;
    }
    int ans = (int) Math.exp(0.5 * Math.log(x));
    return (long) (ans + 1) * (ans + 1) <= x ? ans + 1 : ans;
}

Analysis

• Time Complexity: \(O(1)\)
• Space Complexity: \(O(1)\).

By Long Luo

This article is the solution Fast Power Algorithm: Binary Exponentiation of Problem 50. Pow(x, n) .

We know how to find \(2.0\) raised to the power \(10\). The easiest way is to multiply \(10\) times \(2.0\) by loop, but what if we have to find \(2.0\) raised to the power very large number such as \(10000\) or more?

We will discuss how to find the solution of such problems by using an fast, efficient algorithm.

Brute Force

We multiply \(a\) to itself \(b\) times. That is, \(a^b = \underbrace{a \times a \dots \times a}_b\).

A simple java implementation of that would be:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public static double myPow(double x, int n) {
    if (n == 0 || x == 1) {
        return 1;
    } else if (x == 0) {
        return 0;
    }

    double ans = x;
    boolean isNegative = false;
    long nLong = n;
    if (nLong < 0) {
        nLong = -nLong;
        isNegative = true;
    }

    for (int i = 1; i < nLong; i++) {
        ans = ans * x;
    }

    if (isNegative) {
        ans = 1 / ans;
    }

    return ans;
}

Analysis

• Time Complexity: \(O(n)\)
• Space Complexity: \(O(1)\)

By Long Luo

傅里叶变换(Fourier Transform)是什么？

傅里叶变换 ¹ \((\textit{Fourier Transform})\) ² 和傅里叶级数 \((\textit{Fourier Series})\) ³ 是有史以来最伟大的数学发现之一。

傅里叶变换 \((\textit{Fourier Transform})\) 到底是什么，可以看下这个视频 形象展示傅里叶变换 ，讲的非常好。

傅里叶级数和傅里叶变换背后的本质: 任何函数都可以写成正弦函数之和。

如下Gif动图所示：

下面这个视频 12分钟的傅立叶级数动画 ，我们可以看到任何图像都可以用大圆套小圆来绘制。

因为我们日常看到的世间万物都会随时间流逝而变化，比如一段声音，一幅图像或者一盏闪烁的交通灯，这种以时间作为参照来观察动态世界的方法我们称其为时域分析。

傅里叶告诉我们任何一个信号都可以用 \(2\) 种方式来表达：

1. 时域表达：自变量是时间或者空间的坐标，因变量是信号在该处的强度；
2. 频域表达：把信号“展开”成不同频率的简单正弦函数的叠加，相当于看作是定义在所有频率所组成的空间（称为频域空间）上的函数，自变量是不同的频率，因变量是该频率所对应的简谐振动的幅度。

这两个函数一个定义在时域（或空域）上，一个定义在频域上。看起来的样子通常截然不同，但是它们是在以完全不同的方式殊途同归地描述着同一个信号。它们就象是两种不同的语言，乍一听完全不相干，但是其实可以精确地互相翻译。在数学上，这种翻译的过程被称为傅立叶变换\((\textit{Fourier Transform})\) 。

傅里叶变换(Fourier Transform)可以做什么？

在傅立叶变换的所有这些数学性质中，最不寻常的是这样一种特性：一个在时域或空域上看起来很复杂的信号（譬如一段声音或者一幅图像）通常在频域上的表达会很简单。这里「简单」的意思是说作为频域上的函数，它只集中在很小一块区域内，而很大一部分数值都接近于零。例如下图是一张人脸和它对应的傅立叶变换，可以看出，所有的频域信号差不多都分布在中心周围，而大部分周边区域都是黑色的（即零）。

这是一个意味深长的事实，它说明一个在空域中看起来占满全空间的信号，从频域中看起来很可能只不过占用了极小一块区域，而大部分频率是被浪费了的。这就导出了一个极为有用的结论：一个看起来信息量很大的信号，其实可以只用少得多的数据来加以描述。只要对它先做傅立叶变换，然后只记录那些不接近零的频域信息就可以了，这样数据量就可以大大减少。

基本上，这正是今天大多数数据压缩方法的基础思想。在互联网时代，大量的多媒体信息需要在尽量节省带宽和时间的前提下被传输，所以数据压缩从来都是最核心的问题之一。而今天几乎所有流行的数据压缩格式，无论是声音的mp3格式还是图像的jpg格式，都是利用傅立叶变换才得以发明的。从这个意义上说来，几乎全部现代信息社会都建立在傅立叶的理论的基础之上。

关于不确定性原理，可以看下这个讲解的视频：

直观看待不确定性原理：不只是量子现象哦 。