LeetCode题目解析

Easy

168. Excel表列名称

题目描述

给定一个正整数 columnNumber，返回它在 Excel 表中对应的列名称。

示例：

1
2
3
4
5
6
7
8
输入：columnNumber = 1
输出："A"

输入：columnNumber = 28
输出："AB"

输入：columnNumber = 701
输出："ZY"

解题思路

这题本质上是一个特殊的 26 进制转换。

普通的进制转换通常从 0 开始计数，而 Excel 列名是从 1 开始计数：

1
2
3
4
5
6
A -> 1
B -> 2
...
Z -> 26
AA -> 27
AB -> 28

因此在每一轮取余之前，需要先执行 columnNumber--，把 1 ~ 26 映射成 0 ~ 25。

然后通过：

1
char ch = (char) ('A' + remainder);

就可以得到当前位对应的字母。

由于每次得到的是最低位字符，所以需要把字符插入到结果字符串的最前面。

代码实现

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

public class _168ExcelSheetColumnTitle {
    public String convertToTitle(int columnNumber) {
        StringBuilder result = new StringBuilder();
        int remainder;
        while (columnNumber != 0) {
            columnNumber--;
            remainder = columnNumber % 26;
            char ch = (char) ('A' + remainder);
            columnNumber /= 26;
            result.insert(0, ch);
        }
        return result.toString();
    }
}

复杂度分析

  • 时间复杂度：O(log26 n)，每次循环都会将 columnNumber 除以 26。
  • 空间复杂度：O(log26 n)，结果字符串的长度与转换后的列名长度有关。

易错点

  • 不能直接对 columnNumber 取余，否则 26 会得到 0，无法正确映射到 Z。
  • 每轮循环都要先执行 columnNumber--，再进行取余和除法操作。

169.多数元素

题目描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例：

1
2
3
4
5
输入：nums = [3,2,3]
输出：3

输入：nums = [2,2,1,1,1,2,2]
输出：2

解题思路

使用摩尔投票算法（Boyer-Moore）。

这个算法专门解决出现次数>1/2的情况，使用互相抵消的机制，如果前一位和后一位不同，则标记值-1，到0则换为下一个元素进行标记。
既然最多的数出现大于1/2，那么最后抵消完之后，剩余的肯定是标记值，即可找到要求的元素。

代码实现

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

public class _169MajorityElement {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += candidate == num ? 1 : -1;
        }

        return candidate;
    }
}

复杂度分析

  • 时间复杂度：O(n)，每次循环都会将 columnNumber 除以 26。
  • 空间复杂度：O(1)，结果字符串的长度与转换后的列名长度有关。

171.Excel表列序号

题目描述

给定一个字符串 columnTitle，表示 Excel 表格中的列名称，返回该列名称对应的列序号。

示例：

1
2
3
4
5
6
7
8
输入：columnTitle = "A"
输出：1

输入：columnTitle = "AB"
输出：28

输入：columnTitle = "ZY"
输出：701

解题思路

这题和第 168 题正好相反：第 168 题是把数字转换成 Excel 列名，而本题是把 Excel 列名转换成数字。

Excel 列名可以看成一个 26 进制数，只不过每一位不是从 0 开始，而是从 1 开始：

1
2
3
4
A -> 1
B -> 2
...
Z -> 26

例如 AB：

1
2
3
A 位于高位，表示 1 * 26
B 位于低位，表示 2 * 1
结果为 1 * 26 + 2 = 28

遍历字符串时，当前字符对应的数值可以通过：

1
columnTitle.charAt(i) - 'A' + 1

得到。

然后根据当前字符所在的位置，乘上对应的 26 的幂次，并累加到结果中即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
package easy;

public class _171ExcelSheetColumnNumber {
    public int titleToNumber(String columnTitle) {
        int count = 0;
        for (int i = 0; i < columnTitle.length(); i++) {
            count += (int) ((columnTitle.charAt(i) - 'A' + 1) * Math.pow(26, columnTitle.length() - i - 1));
        }
        return count;
    }
}

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 columnTitle 的长度，需要遍历每一个字符。
  • 空间复杂度：O(1)，只使用了常数个额外变量。

易错点

  • 字符 A 对应的是 1，不是 0，所以需要加上 1。
  • 越靠左的字符位权越高，需要乘以更高次的 26。
  • Math.pow 返回的是 double，本题最终结果是整数，所以需要强制转换为 int。

191.位1的个数

题目描述

给定一个正整数 n，编写一个函数，获取一个正整数的二进制形式并返回其二进制表达式中 设置位（1）的个数（也被称为汉明重量）。

示例 1：

1
2
3
输入：n = 11
输出：3
解释：输入的二进制串 1011 中，共有 3 个设置位。

示例 2：

1
2
3
输入：n = 128
输出：1
解释：输入的二进制串 10000000 中，共有 1 个设置位。

示例 3：

1
2
3
输入：n = 2147483645
输出：30
解释：输入的二进制串 1111111111111111111111111111101 中，共有 30 个设置位。

解题思路

使用除2取余法在转换为二进制的途中，判断是否为1，进行累加计算。

代码实现

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

public class _191NumberOf1Bits {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            if (n % 2 == 1) {
                count++;
            }
            n /= 2;
        }

        return count;
    }
}

复杂度分析

时间复杂度：O(k)，k 是二进制中 1 的个数，最多 32 次，所以也是 O(1)
空间复杂度：O(1)

202.快乐数

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

解题思路

这道题的关键在于循环，一旦出现相同的数字则必定会成为一个循环，此外则会算到1。

方案一：使用HashSet记录出现过的数字，可以判断是否出现过相同的数字。

方案二：使用快慢指针，如果存在循环，则快慢指针一定会相遇。

代码实现

方案一：

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
26
27
28
29
30
31
32
package easy;

import java.util.HashSet;
import java.util.Set;

public class _202HappyNumber {
    public boolean isHappy(int n) {
        Set<Integer> set = new HashSet<>();
        while (n != 1) {
            boolean flag = set.add(n);

            if (!flag) {
                return false;
            }
            n = this.getNext(n);
        }

        return true;
    }

    public int getNext(int n) {
        int count = 0;

        while (n != 0) {
            count += (int) Math.pow(n % 10, 2);
            n /= 10;
        }

        return count;
    }
}

方案二：

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
26
27
package easy;

public class _202HappyNumber {
    public boolean isHappy(int n) {
        int slow = n;
        int fast = this.getNext(n);

        while (slow != fast && fast != 1) {
            slow = this.getNext(slow);
            fast = this.getNext(this.getNext(fast));
        }

        return fast == 1;
    }

    public int getNext(int n) {
        int count = 0;

        while (n != 0) {
            count += (int) Math.pow(n % 10, 2);
            n /= 10;
        }

        return count;
    }
}

总结

如果遇到循环类型的题目，优先考虑使用快慢指针进行处理。

203.移除链表元素

题目描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

解题思路

使用哑结点（dummy node）可以避免对链表头结点进行特殊处理，最后取值直接返回dummyNode的next即可。
使用prev和curr两个指针指向前一位和当前位保证链表的接续。

代码实现

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
26
27
28
29
30
31
32
33
34
35
36
37
38
package easy;

public class _203RemoveLinkedListElements {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        ListNode curr = head;
        while (curr != null) {
            if (curr.val == val) {
                prev.next = curr.next;
            } else {
                prev = curr;
            }
            curr = curr.next;
        }

        return dummy.next;
    }

    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}

Medium

hard