1. 相交链表

image-20200720175326197
思路一：暴力求解

对 headA 中的每一个节点，遍历 headB 中的每一个节点判断是否与其相等。

  • 时间复杂度：O (mn)

  • 空间复杂度：O (1)

思路二：借助哈希表

将 headA 中的节点存入一个 HashSet 中，如果 headB 中有节点在 HashSet 中，则说明该节点为交叉点

  • 时间复杂度：O (m + n)

  • 空间复杂度：O (m)

思路三：浪漫双指针法

创建两个指针分别指向 headA 、 headB，两个指针分别向前走，若相同则返回当前节点，若为空则指向另一条链表的头

初看很难理解，但是细想就会发现很简单很巧妙 A和B两个链表长度可能不同，但是 A+B 和 B+A 的长度是相同的，所以遍历 A+B 和遍历 B+A 一定是同时结束。 如果A, B相交的话A和B有一段尾巴是相同的，所以两个遍历的指针一定会同时到达交点 如果A,B不相交的话两个指针就会同时到达 A+B（B+A）的尾节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        /**
        定义两个指针, 第一轮让两个到达末尾的节点指向另一个链表的头部, 最后如果相遇则为交点(在第一轮移动中恰好抹除了长度差)
        两个指针等于移动了相同的距离, 有交点就返回, 无交点就是各走了两条指针的长度
        **/
        if(headA == null || headB == null) return null;
        ListNode pA = headA, pB = headB;
        // 在这里第一轮体现在pA和pB第一次到达尾部会移向另一链表的表头
     	// 而第二轮体现在如果pA或pB相交就返回交点, 不相交最后就是null==null
        while(pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
}

  • 时间复杂度：O (m + n)

  • 空间复杂度：O (1)

至于，为什么说他浪漫……

image-20200720180421830

image-20200720180447776

2. Excel表列名称

image-20200720182149737
解题思路

Excel 表中相对应列的名称遵循 逢26进一 的原则，所以这题本质上考的是进制的转化！

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public String convertToTitle(int n) {
        if (n <= 0) return "";
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            n--;
            sb.append((char)(n % 26 + 'A'));
            n /= 26;
        }
        return sb.reverse().toString();
    }
}

3. Excel表列序号

image-20200723170226918
解题思路

与上题一致，主要考察进制的转化

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int titleToNumber(String s) {
        int len = s.length();
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum = sum * 26 + (int)(s.charAt(i) - 'A' + 1);
        }
        return sum;
    }
}

4. 多数元素

image-20200723160835580
我的思路

使用 HashMap 存储每个数字出现的次数，当某个数字出现的次数大于 n/2 时，返回该数字。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int majorityElement(int[] nums) {
    
        HashMap<Integer, Integer> map = new HashMap<>();
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            int num = nums[i];
            map.put(num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) > len / 2) {
                return num;
            }
        }
        return 0;
    }
}
image-20200723161041959
其他思路

对数组进行排序，排序后的数组的第 n/2 个元素一定是众数

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

/*
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/majority-element/solution/duo-shu-yuan-su-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
*/

算法题应该考验算法设计能力，而不是调用现成 api 的能力，故这种方法不推荐使用！

最优的思路：Boyer-Moore 投票算法

如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。

从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int majorityElement(int[] nums) {
        int count = 1;
        int maj = nums[0];
        int len = nums.length;
        for (int i = 1; i < len; i++) {
            if (nums[i] == maj) {
                count++;
            } else {
                count--;
                if (count == 0) {
                    maj = nums[i + 1];
                }
            }
        }
        return maj;
    }
}
image-20200723163229747

5. 阶乘后的零

image-20200723170428188
解题思路

按一般思路：先求出 n 的阶乘，如何再计算阶乘结果中末尾 0 的个数。然而这样做不能满足时间复杂度的要求

不可能去直接计算阶乘的结果看看有多少个0.

可以直接发现，尾数要为0，看看阶承中的数有多少个相乘后可以为10.

比如 5！：可以2*5.

1
10！：可以2*5，1*10，其中10又可以拆分为2*5.

说4*5也可以，不过我们要的是最小的因数.

那么就转为寻找一个阶乘有多少个2和多少个5

拿20！来分析：[110, 25, 415, 56] 即：[125, 25, 2253, 523]

再来个30！：[110, 25, 415, 56, 随便一个数20, 258, 30随便一个数]，即：[125, 25, 2253, 225, 55222, 253]

可以看出2总是比5多，那看看多少个5是不是就是多少个0

20!的结果为2432902008176640000，有4个0刚好跟有4个5相同

30！265252859812191058636308480000000有7个0,刚好也有7个5，所以可以证明

只需要看给定的数中有多少个5或者5的倍数就行

1
2
3
4
5
6
7
8
9
class Solution {
    public int trailingZeroes(int n) {
        if (n < 5) {
            return 0;
        } else {
            return n / 5 + trailingZeroes(n / 5);
        }
    }
}