前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。
一、相交链表（题号：160）
描述：编写一个程序，找到两个单链表相交的起始节点。
提示：前提是两个单向链表，而且肯定相交。
解题思路：此题比较简单，既然总是相交，我们可以先计算两个链表的长度，从对齐处开始逐个比较。
public class TestMain {
public static void main(String[] args) {
}
private static ListNode execute(ListNode h1,ListNode h2) {
int l1 = length(h1);
int l2 = length(h2);
while (l1 < l2) {
h2 = h2.next;
l2--;
}
while (l1 > l2) {
h1 = h1.next;
l1--;
};
while (h1 != h2) {
h1 = h1.next;
h2 = h2.next;
}
return h1;
}
private static int length(ListNode head) {
int i = 0;
ListNode next = head;
while (next != null) {
i++;
next = next.next;
}
return i;
}
static class ListNode {
int value;
ListNode next = null;
ListNode(int value) {
this.value = value;
}
}
}
二、最大间距（题号：164）
描述：给定一个无序数组，找到数组在排序之后，相邻元素之间最大的差值。如果元素个数小于2，则返回0。
示例 1: 输入: [3,6,9,1] 输出: 3 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 示例 2: 输入: [10] 输出: 0 解释: 数组元素个数小于 2，因此返回 0。
说明：
1）你可以假设数组中所有的元素都是非负数，且数值在32为有符号整数范围内。
2）请尝试在线性时间复杂度和空间复杂度的条件下解决此问题。
3）元素值，可能有重复出现。
解题思路：这个题，还是有些复杂，原因就在数组是无序的，如果要求复杂度为线性（只跟元素个数有正比关系），那么几乎常见的排序算法，都无法满足。此题的关键是计算“最大间距”，排序或许不是最重要的。
排序算法中，有一个“桶排序”，本题只需要用到桶排序的思想即可。有关桶排序的详解，可以参考其他资料。（核心思想，非常像hashmap的桶，每个桶表示一个区间）
1）N个元素的数组，我们使用N + 1个桶 。即额外创建一个长度为N + 1的数组。
2）找到数组中最大、最小元素，将它们的差值最为值域跨度，值域跨度除以桶个数，就是每个桶需要“承载”的值域。简单来说，我们需要知道每个桶，需要“负责”的数字区间。
3）因为本地，只需要计算“最大间距”；所以，每个桶中只需要保存其值域区间的最大、最小值即可；每个桶的最大值与下一个桶的最小值之间为“间距”，此桶的最小值与前一个桶的最大值之间为“间距”。
4）每个桶内部，无论多少个元素，其“间距”总是小于“区间”值。
5）元素个数为N，桶的个数为N + 1，那么必有一个桶是空的，那么此空桶的前后可能形成最大间距。
6）但是，如果临近两个桶，前者为区间的最小值、后者为区间的最大值，仍然有可能产生最大间距（跨了两个区间值）。所以，我们需要比较所有桶之间的“间距”，而不是只关注“空桶”。
public class TestMain {
public static void main(String[] args) {
int[] source = {3,6,9,1};
System.out.println(execute(source));
}
public static int execute(int[] source) {
int length = source.length;
if(length == 1) {
return 0;
}
//找到最大、最小值，用于计算桶的子值域宽度
int min = source[0];
int max = min;
for(int i = 1; i < length; i++){
min = source[i] < min ? source[i] : min;
max = source[i] > max ? source[i] : max;
}
if(max == min) {
return 0;
}
//桶是否与元素
boolean[] checkedBucket = new boolean[length + 1];
//每个桶的，最大值、最小值
int[] minBucket = new int[length + 1];
int[] maxBucket = new int[length + 1];
for(int i = 0; i < length; i++){
int value = source[i];
int bid = (value - min) * length / (max - min);
minBucket[bid] = checkedBucket[bid] ? Math.min(minBucket[bid],value) : value;
maxBucket[bid] = checkedBucket[bid] ? Math.max(maxBucket[bid],value) : value;
checkedBucket[bid] = true;
}
int maxGap = 0;
//已经遇到的最大值
int _max = maxBucket[0];
for(int i = 1; i <= length; i++){
if(checkedBucket[i]) {
//当前桶的最小值，与上一个桶的最大值，之间为"间距"
maxGap = Math.max(maxGap,minBucket[i] - _max);
_max = maxBucket[i];
}
}
return maxGap;
}
}
三、分数到小数（题号：166）
描述：给定两个整数，分别表述分数的分子numerator和分母denominator，以字符串的形式返回小数。如果小数部分为循环小数，则将循环的部分括在括号中。
示例 1: 输入: numerator = 1, denominator = 2 输出: "0.5" 示例 2: 输入: numerator = 2, denominator = 1 输出: "2" 示例 3: 输入: numerator = 2, denominator = 3 输出: "0.(6)"
解题思路：分子分母相除，得到的为结果的整数部分，分子分母取模结果作为分子，继续参与相除，不过此后每次相除每次都 * 10。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute(1,2));
System.out.println(execute(2,1));
System.out.println(execute(2,3));
}
/**
*
* @param numerator 分子
* @param denominator 分母
* @return
*/
private static String execute(int numerator, int denominator) {
if(numerator == 0) {
return "0";
}
if (denominator == 0) {
return "NaN";
}
StringBuilder sb = new StringBuilder();
//符号判断
if ((numerator > 0 && denominator < 0) || (numerator < 0 && denominator > 0)) {
sb.append("-");
}
int n = Math.abs(numerator);
int d = Math.abs(denominator);
int i = n / d;
sb.append(i);
int r = n % d;
while (r != 0) {
sb.append(".");
int x = (r * 10) % d;
int y = (r * 10) / d;
if (x == r) {
sb.append("(").append(y).append(")");
break;
}
sb.append(y);
r = x;
}
return sb.toString();
}
}
四、Excel表列名称（题号：168）
描述：给定一个正整数，返回它在excel表中对应的列名称。
例如，
1 -> A
2 -> B
3 -> C
...
26 -> Z
27 -> AA
28 -> AB
...
示例 1:
输入: 1
输出: "A"
示例 2:
输入: 28
输出: "AB"
示例 3:
输入: 701
输出: "ZY"
解题思路：A - Z，共26个字母，其实就是26进制转换问题。跟历史题目中的16进制是一个思路。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute(1));
System.out.println(execute(28));
System.out.println(execute(701));
}
private static String execute(int source) {
StringBuilder sb = new StringBuilder();
while (source > 0) {
int x = (source - 1) % 26;
sb.append((char)( 'A' + x));
source = ((source - 1) / 26);//退1，除法退1
}
return sb.reverse().toString();
}
}
五、阶乘后的零（题号：172）
给定一个整数 n，返回 n! 结果尾数中零的数量。
示例 1: 输入: 3 输出: 0 解释: 3! = 6, 尾数中没有零。 示例 2: 输入: 5 输出: 1 解释: 5! = 120, 尾数中有 1 个零.
解题思路：0的个数，取决于2 * 5的组合个数，阶乘从1 到n相乘，2的个数远大于5，因此5的个数决定0的个数；我们只要能够计算出n阶乘中5的个数，就可以得知0的个数。
public class TestMain {
public static void main(String[] args) {
}
public static int execute(int n) {
int result = 0;
while (n > 4) {
n /= 5;//除数中也可能包含5
result += n;
}
return result;
}
}
六、二叉搜索树迭代器（题号：173）
描述：实现一个二叉树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用next()将返回二叉搜索树的下一个最小的数。
BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator.next(); // 返回 9 iterator.hasNext(); // 返回 true iterator.next(); // 返回 15 iterator.hasNext(); // 返回 true iterator.next(); // 返回 20 iterator.hasNext(); // 返回 false
解题思路：很明显，这是中序遍历的一个非递归操作，为了能够支持迭代，我们唯一能做的，就是先把树中的数据按照中序遍历展开，并存储在一个线性结构中，这个线性结构，你可以使用数组（带游标指针）或者队列中。
public class TestMain {
public static void main(String[] args) {
TreeNode root = new TreeNode(7);
TreeNode n1 = new TreeNode(3);
TreeNode n2 = new TreeNode(15);
TreeNode n3 = new TreeNode(9);
TreeNode n4 = new TreeNode(20);
root.left = n1;
root.right = n2;
n2.left = n3;
n2.right = n4;
BSTIterator iterator = new BSTIterator(root);
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
public static class BSTIterator {
private Queue<Integer> queue = new LinkedList<>();
public BSTIterator(TreeNode root) {
dfs(root);
}
public int next() {
if (queue.isEmpty()) {
return -1;
}
return queue.poll();
}
public boolean hasNext() {
return !queue.isEmpty();
}
private void dfs(TreeNode node) {
if (node == null) {
return;
}
TreeNode left = node.left;
TreeNode right = node.right;
int value = node.value;
if (left != null) {
dfs(left);
}
queue.add(value);
if (right != null) {
dfs(right);
}
}
}
public static class TreeNode {
private TreeNode left;
private TreeNode right;
private int value;
public TreeNode(int value) {
this.value = value;
}
}
}
七、分数排名（题号：178，SQL）
描述：编写一个 SQL 查询来实现分数排名。如果两个分数相同，则两个分数排名（Rank）相同。请注意，平分后的下一个名次应该是下一个连续的整数值。换句话说，名次之间不应该有“间隔”。
+----+-------+ | Id | Score | +----+-------+ | 1 | 3.50 | | 2 | 3.65 | | 3 | 4.00 | | 4 | 3.85 | | 5 | 4.00 | | 6 | 3.65 | +----+-------+ 例如，根据上述给定的 Scores 表，你的查询应该返回（按分数从高到低排列）： +-------+------+ | Score | Rank | +-------+------+ | 4.00 | 1 | | 4.00 | 1 | | 3.85 | 2 | | 3.65 | 3 | | 3.65 | 3 | | 3.50 | 4 | +-------+------+
解题思路：这个题的关键是rank排名，且不能有间隙，相同score的rank值一样。我们很容易对score进行排序，但是计算rank需要额外的SQL，所谓rank就是当前score在所有不同score中所对应的倒叙位置；rank的值就是“大于等于当前score值的、且不同的score的个数”。
SELECT Score, (SELECT count(DISTINCT score) FROM Scores WHERE score >= s.score) AS Rank FROM Scores s ORDER BY Score DESC ;
八、最大数（题号：179）
描述：给定一个非负数，重新排列它们的顺序使之组成一个最大的整数。
示例 1: 输入: [10,2] 输出: 210 示例 2: 输入: [3,30,34,5,9] 输出: 9534330
说明：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
解题思路：这个题，其实很简单，但是我们总是困扰在一些细节上，我本人就是在数据排序上花费了很多时间，其实这些排序SDK API已经有了，直接使用即可。简单来说，按照元素的“字符字面值”排序即可。
public class TestMain {
public static void main(String[] args) {
int[] source = {3,30,34,5,9};
System.out.println(execute(source));
}
private static String execute(int[] source) {
String[] target = new String[source.length];
for (int i = 0; i < source.length; i++) {
target[i] = String.valueOf(source[i]);
}
Arrays.sort(target);
StringBuilder sb = new StringBuilder();
for (int i = 0; i < target.length; i++) {
sb.append(target[i]);
}
return sb.reverse().toString();
}
}
九、二叉树的右视图（题号：199）
描述：给定一颗二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
示例: 输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释: 1 <--- / \ 2 3 <--- \ \ 5 4 <---
解题思路：想通的就比较简单，二叉树的广度遍历，只打印最右侧节点。当然也可以增加一个技巧，广度遍历时右节点优先，值打印每层首个节点。
public class TestMain {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
TreeNode n1 = new TreeNode(2);
TreeNode n2 = new TreeNode(3);
TreeNode n3 = new TreeNode(5);
TreeNode n4 = new TreeNode(4);
root.left = n1;
root.right = n2;
n1.right = n3;
n2.right = n4;
List<Integer> result = execute(root);
System.out.println(result);
}
private static List<Integer> execute(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
List<Integer> result = new ArrayList<>();
while (!queue.isEmpty()) {
int size = queue.size();//计算当前层的长度
for (int i = 0;i < size; i++) {
TreeNode node = queue.poll();
if (i == 0) {
result.add(node.value);
}
if (node.right != null) {
queue.offer(node.right);
}
if (node.left != null) {
queue.offer(node.left);
}
}
}
return result;
}
public static class TreeNode {
private TreeNode left;
private TreeNode right;
private int value;
public TreeNode(int value) {
this.value = value;
}
}
}
十、计算质数（题号：204）
描述：统计所有小于非负整数n的质数的数量。
示例: 输入: 10 输出: 4 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
解题思路：这个题有效的解题方式并不太多，1）直接计算，就是遍历小于n的每个数字，并对每个数字与小于它的所有数字取模、查看结果是否为0，如果有为0的数字则不是质数。 2）思路1的缺点就是耗时，我们可以改进，使用空间换时间，在遍历小于n的数字时，如果它不是质数，则记录下来。
public class TestMain {
public static void main(String[] args) {
System.out.println(execute(10));
}
private static int execute(int n) {
boolean[] notPrime = new boolean[n];
int count = 0;
for (int i = 2; i < n; i++) {
if (!notPrime[i]) {
count++;
for (int j = 2; i * j < n; j++) {
notPrime[i * j] = true;
}
}
}
return count;
}
}
十一、课程表（题号：207）
描述：现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]，给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
示例 1: 输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。 示例 2: 输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
说明:
1）输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
2）你可以假定输入的先决条件中没有重复的边。
解题思路：主要是考察拓扑排序（DAG，有向无环图）的设计算法，通过拓扑排序之后，查看此图中是否有“环形依赖”；如果存在环形路径，表示节点之间存在循环依赖，则条件无法达成。这个算法的核心思想，就是背下来。
public class TestMain {
public static void main(String[] args) {
int[][] source = {{1,0},{0,1}};
System.out.println(execute(2,source));
}
/**
*
* @param number 课程数量，即顶点个数
* @param source 数组列表，先决条件（顶点为第二个元素）
* @return 是否可达。false表示为"有环图"不可达
*/
private static boolean execute(int number, int[][] source) {
int[] indegree = new int[number];
//记录每个顶点（题目的前提是，课程ID是连续的，0-n）
//被指向的次数，最终在删除边的时候，用于决定此顶点，是否还有被指向的边，
//以判断此节点是否还有前驱节点。
//如果节点不是数字，我们可能需要使用map来存储。
for (int[] item : source) {
indegree[item[0]]++;
}
//找到零入度
Set<Integer> zeroDegree = new HashSet();
for (int i = 0; i < number; i++) {
if (indegree[i] == 0) {
zeroDegree.add(i);
}
}
//如果没有零入度，即基本条件缺失，则返回false
if (zeroDegree.isEmpty()) {
return false;
}
//根据DAG的设计原则，从图中，
// 由零入度开始,删除其所有的"边"
//然后从新找到新的没有"前驱"的顶点（即新的零入度），继续删除
//直到为空，或者剩余节点均需要前驱（前置条件，false，有环）
while (!zeroDegree.isEmpty()) {
Iterator<Integer> it = zeroDegree.iterator();
int value = it.next();//当前零入度节点
it.remove();
for (int[] item : source) {
//删除，所有零入度的边
if (item[1] == value) {
indegree[item[0]]--;//删除边，其实就是减小被指向次数
//如果此节点被指向次数为0，表示其没有前驱引用，则作为新的零入度节点
if (indegree[item[0]] == 0) {
zeroDegree.add(item[0]);
}
}
}
}
//检测是否还有节点，尚有"前驱引用"，如果有，表表示有环。
//即互相依赖的条件。
for (int i : indegree) {
if (i != 0) {
return false;
}
}
return true;
}
}
相关推荐
如何正确刷题？LeetCode刷题误区和刷题方法论分享【LeetCode刷题套路教程1】
《LeetCode刷题笔记》是针对LeetCode这个在线编程挑战平台的个人学习心得与总结，主要涵盖数据结构和算法两大核心领域。LeetCode是一个全球知名的编程训练网站，它提供了丰富的编程题目，帮助开发者提升编程技能，...
《LeetCode刷题笔记withJava》是一份专为Java开发者准备的算法实战指南，涵盖了LeetCode网站上前一百道编程挑战题目。这份资料旨在帮助程序员提升算法能力，掌握数据结构和问题解决技巧，对于准备面试或者想要提升...
总的来说，《leetcode刷题班题库》是一份全面而深入的学习资料，它不仅提供了大量的编程题目，更关键的是，它提供了详细的解题过程，帮助学习者逐步建立解决问题的能力。通过系统地学习和实践，你将能够在算法和数据...
Backtracking回溯解题套路【LeetCode刷题套路教程18】
Heap堆解题套路【LeetCode刷题套路教程6】
《谷歌和阿里大佬Leetcode刷题笔记》是一个珍贵的学习资源，专为提升算法能力和准备面试设计。LeetCode是一个在线平台，提供了大量的编程题目，旨在帮助程序员提升算法技能，特别是对于那些希望进入顶级科技公司如...
《LeetCode刷题，C++刷题技巧》是一本针对有C++编程基础，希望通过LeetCode平台提升算法和数据结构能力的读者所编写的指南。作者高畅在准备实习秋招的过程中，积累了大量的LeetCode刷题经验，并在书中分享了这些宝贵...
在本课程中，"C++ LeetCode刷题班.zip"，我们的目标是深入学习和实践C++编程语言，特别是聚焦于数据结构与算法的应用，这对于准备面试，尤其是BAT（百度、阿里巴巴、腾讯）等知名互联网公司的面试至关重要。...
这本书名为《LeetCode101：和你一起你轻松刷题（C++）》的电子书，作者高畅ChangGao，旨在帮助有C++基础但缺乏刷题经验的读者。本文将详细阐述该电子书中提及的IT知识点，覆盖算法与数据结构两大板块，以及十五个...
这个基于Java的LeetCode刷题与复习指南算法模板代码集合，将为学习者提供宝贵的资源和起点。 首先，让我们深入理解Java在LeetCode中的应用。Java是一种广泛使用的面向对象的编程语言，其语法清晰，性能优秀，特别...
《LeetCode刷题题解》是一份集合了多个资源的压缩包，主要目的是帮助学习者在准备面试或者提升编程技能时，通过解决LeetCode上的问题来加深对算法和数据结构的理解。LeetCode是一个在线的编程挑战平台，它包含了各种...
Stack堆栈解题套路【LeetCode刷题套路教程5】
该项目为Java语言编写的LeetCode刷题算法设计与实现源码，包含187个文件，其中181个为Java源文件，3个为YAML配置文件，1个为Git忽略文件，以及1个LICENSE...该源码旨在记录LeetCode刷题过程，为算法学习提供辅助工具。
哈希表HashMap解题套路【LeetCode刷题套路教程7】
该项目为《代码随想录》LeetCode 刷题攻略的200题学习源码包，涵盖286个Markdown文件、6个PNG图片文件和2个JPG图片文件，共计295个文件。内容丰富，包括60万字的详细图解、视频难点剖析和50余张思维导图，支持C++、...
在这个“Leetcode刷题笔记.zip”压缩包中，我们可以期待找到作者在解决LeetCode题目过程中积累的珍贵心得和解题策略。这份笔记可能涵盖了多种算法和数据结构的应用，对于学习和提升编程能力，特别是准备技术面试的...
【标题】：“谷歌高畅、BAT霜神leetcode刷题笔记.zip”是一份压缩包文件，包含两位业内专家——“谷歌高畅”和“BAT霜神”的LeetCode刷题笔记。LeetCode是一个广受欢迎的在线平台，它提供了各种编程挑战题目，帮助...
【标题】"leetcode刷题LeetCode1500道单词接龙Python3"涉及的是一个在编程学习领域常见的挑战——通过解决LeetCode平台上的问题来提升技能，特别是使用Python3语言进行实现。LeetCode是一个在线的算法练习平台，提供...
DynamicProgramming2D解题套路【LeetCode刷题套路教程15】