前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。
一、两数之和（题号：1）
描述：给定一个整数数组nums和一个目标值target，请在该数组中找出和为目标值的两个整数，并返回它们的数组下标。(假定，数组中中数字不重复，和值等于target的情况只需要一种即可)
示例： 给定 nums = [2,7,11,15],target = 9 则返回[0,1],因为nums[0] + nums[1] = 9
解题思路之一：使用hashMap保存数组元素，并逐个遍历，如果与当前元素的差值也在map中，则返回。
public static int[] execute(int[] source, int target) {
Map<Integer,Integer> mapping = new HashMap<>();
//一遍hash即可，差值是幂等的。
for(int i = 0; i < source.length; i++) {
int t = target - source[i];
if (mapping.containsKey(t)) {
return new int[] {i,mapping.get(t)};
}
mapping.put(source[i],i);
}
throw new IllegalArgumentException("Cant find two nums.");
}
二、两数相加（题号：2）
描述：使用两个非空的链表表示两个非负整数，链表为单向链表，它们各自的位数是按照逆序的方式存储，链表中每个节点只存储一位数字。（链表节点与整数字面值输入顺序一致）
返回一个新的链表，表示两个整数之和。（逆序）
分解：比如输入302数字，转换成链表应该为2 -> 0 -> 3，认为是键盘字符输入顺序的逆序。
示例： 输入： 342：2 -> 4 -> 3 465：5 -> 6 -> 4 输出和： 807: 7 -> 0 -> 8
思路之一：链表数据从低位到高位，逐位对齐，然后逐位相加（结果加入结果链表），满10进1 并参与下一位的计算。这个很像我们小时候的数字加减的计算式。
public class TestMain {
public static void main(String[] args) {
//构建部分
ListNode l1 = new ListNode(0);
ListNode ll1 = l1;
ll1 = (ll1.next = new ListNode(2));
ll1 = (ll1.next = new ListNode(4));
ll1.next = new ListNode(3);
ListNode l2 = new ListNode(0);
ListNode ll2 = l2;
ll2 = (ll2.next = new ListNode(5));
ll2 = (ll2.next = new ListNode(6));
ll2.next = new ListNode(4);
ListNode result = execute(l1,l2);
System.out.println("result:");
System.out.println(result.next);
}
public static ListNode execute(ListNode l1,ListNode l2) {
ListNode r = new ListNode(0);
ListNode p = l1.next;
ListNode q = l2.next;
ListNode result = r;//指向head
int c = 0;
while (true) {
int x = p == null ? 0 : p.value;
int y = q == null ? 0 : q.value;
int t = x + y + c;
if (t > 9) {
c = 1;
r.next = new ListNode(t % 10);
} else {
c = 0;
r.next = new ListNode(t);
}
p = p.next;
q = q.next;
r = r.next;
if (p == null && q == null) {
break;
}
}
return result;
}
public static class ListNode {
int value = 0;
ListNode next = null;
ListNode(int value) {
this.value = value;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(value);
ListNode t = next;
while (t != null) {
sb.append(t.value);
t = t.next;
}
return sb.toString();
}
}
}
三、无重复字符的最长子串（题号：3）
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
解题思路：本题思路很多，本人采用比较易于理解的方式，遍历字符串字符集，并将遇到的字符保存在Set中，如果set中已经存在当前字符，则重新计算。
public class TestMain {
public static void main(String[] args) {
String source = "abcabcbb";
System.out.println(execute(source));
}
public static int execute(String source) {
Set<Character> container = new HashSet<>();
int s = 0;//辅助，无重复子串的开始index
int e = 1;//辅助，无重复子串的结束index + 1，便于计算长度
int max = e - s;
for (int i = 0; i < source.length(); i++) {
char value = source.charAt(i);
//如果发现重复字符，则清空set，计算max，重新开始
if (container.contains(value)) {
max = Math.max(max,e -s);
System.out.println(source.substring(s,e));
s = i;
container.clear();
}
container.add(value);
e = i + 1;
}
return max;
}
}
四、求字符串中最长回文字（题号：5）
回文字：一个字符串，正向和反向的字面值一致，比如“abba”、“abcba”等。
描述：给定一个字符串，找到其最常的回文字子串。
示例： 输入：babad 输出：aba （或者bab） 输入：cbbd 输出：bb
思路之一：中心分散法，任何一个回文字，从其中间字符分别向两边逐对比较，都是一样的。需要注意特殊“abba”，这种偶数字符的，中间字符是两个，为了兼容这种情况，中间字符分别取两次。
复杂度分析：
1）时间复杂度：O(n^2)，因为每个字符都需要O(n)次展开和比较，所以总时间为O(n^2)。
2）空间复杂度：O(1)，无额外消耗
public class TestMain {
public static void main(String[] args) {
String source = "adabbaec";
System.out.println(execute(source));
}
public static String execute(String source) {
if (source == null || source.length() < 1) {
return "";
}
int start = 0;
int end = 0;
for (int i = 0; i < source.length(); i++) {
int[] result = compare(expand(source, i, i),expand(source, i, i + 1));
int l = result[1] - result[0];
if (l > end - start) {
start = result[0];
end = result[1];
}
}
return source.substring(start, end + 1);
}
/**
* 获取长度较长的子串区间
* @param r1
* @param r2
* @return
*/
private static int[] compare(int[] r1,int[] r2) {
int l1 = r1[1] - r1[0];
int l2 = r2[1] - r2[0];
return l1 >= l2 ? r1 : r2;
}
/**
* 返回子串区间
* @param source
* @param left
* @param right
* @return
*/
private static int[] expand(String source, int left, int right) {
int l = left;
int r = right;
while (l >= 0 && r < source.length() && source.charAt(l) == source.charAt(r)) {
l--;
r++;//左右两边分别成对对比，遇到不同，则退出，否则继续。
}
return new int[] {l + 1,r - 1};
}
}
五、Z字形变换（题号：6）
描述：将一个给定的字符串，以从上到下，从左到右进行Z字形排列（之字形），并输出变换之后的字符串。
示例：ABCDEFGHIGKLMNOP 图示： A G M B F H L N C E I K O D J P 输出结果： AGMBFHLNCEIKODJP
思路：主要是寻找字符变化的规律，发现步长为2 (K - 1)。
复杂度分析：
1）时间复杂度：O(n)，只遍历一次且无重复遍历。
2）空间复杂度：O(1)，暂且认为返回结果不占用空间。
public class TestMain {
public static void main(String[] args) {
String source = "ABCDEFGHIJKLMNOP";
int row = 4;
System.out.println(convert(source,row));
}
/**
* A G M
* B F H L N
* C E I K O
* D J P
* @param source
* @param row
* @return
*/
public static String convert(String source, int row) {
if (row == 1) {
return source;
}
StringBuilder sb = new StringBuilder();
int n = source.length();
//一个周期的步长：2 * (n - 1)
//图示中，A -> G -> M，B -> H -> N
int step = 2 * row - 2;//
//思路：逐行打印，假定4行，
//1）我们需要特别清楚的认识到，第一列是"标杆"起点，即每行的迭代的起始位置。
//2）每行，每个元素，都是根据第一列元素，按照一定步长循环。
//3) 除了首尾两行，其他行，每次迭代，都与判断一次是否补偿一个连线的元素。
//4） 连线的元素位置，就是当前位置 + 补偿 - 行号
//每行打印（操作）的循环次数数，取决于当前行数
//第一行：
// A
// G
// M
// 控制因子：每次增加步长step
// 第二行：
// B F
// H L
// N
// 第三行：
// C E
// I K
// 0
// 第四行：
// D
// J
// P
for (int i = 0; i < row; i++) {
for (int j = 0; j + i < n; j += step) {
sb.append(source.charAt(j + i));
//检测当前step，是否需要增加一个补偿。
//第一行和最后一行特殊对待，因为不需要
//当前（位置 + 步长
if (i != 0 && i != row - 1 && j + step - i < n)
sb.append(source.charAt(j + step - i));
}
}
return sb.toString();
}
}
六、整数反转（题号：7）
描述：输入一个数字（可能为负数，有符号），输出其反转值
比如：321，反转值为123.
思路：比较简单，因为数字都是10进制的，取余可以得到当前位的字面值，相除可以得到下一位的值。注意溢出即可。
public class TestMain {
public static void main(String[] args) {
int source = 321;
System.out.println(Integer.MAX_VALUE);
System.out.println(Integer.MIN_VALUE);
System.out.println(reverse(source));
}
/**
* 主要考察点：溢出，负数问题
* 思路：
* 1、数子对10相除，得出下一位的数字值（降位）
* 2、数字对10取余，得出当前位的数字字面值。
* 3、逐位向前推进。
* @param source
* @return
*/
public static int reverse(int source) {
int result = 0;
while (source != 0) {
int pop = source % 10;
source = (source / 10);//原数字降位
//整数最大值：2147483647，尾数7需要注意溢出。
if (result > Integer.MAX_VALUE / 10 || (result == Integer.MAX_VALUE / 10 && pop > 7)) {
return 0;
}
//整数最小值：-2147483648，尾数8需要注意
if (result < Integer.MIN_VALUE / 10 || (result == Integer.MIN_VALUE / 10 && pop < -8)) {
return 0;
}
result = result * 10 + pop;//结果数字升位
}
return result;
}
}
七、回文数（题号：9）
描述：判断一个数字为回文数，即数字正向、反向字面值一样，比如“0”、“121”、“1221”等。
解题思路：根据上述（五）反转数字，然后比较结果即可。首选可以断定，负数肯定不是回文数、反转过程中溢出最大最小值时肯定不是。
八、盛水最多的容器（题号：11）
描述：输入一个整数数组，用于表示一个二维坐标图，元素值为纵轴点，元素索引值为横轴点；求构成面积最大的两个位点。
思路：
1）面积大小是有长 * 宽的值决定
2）此题中，宽为两个位点的横轴值差；面积受限于两个位点中纵轴的较小的那个。
3）暴力的办法，就是所有的点，都比较一遍。
4）通常这种比较，复杂度略过。我们使用双指针方式，首先让位点最左、最右的两个开始计算，计算面积，然后让纵轴较小的向里收缩。之所以小的向里收缩，因为它是限制面积的变量。
5）一遍对比，即可获得。
public class TestMain {
public static void main(String[] args) {
int[] source = {1,8,6,2,5,4,8,3,7};
System.out.print(execute(source));
}
/**
* @param source，元素的index对应横轴值，元素值为纵轴
* @return
*/
public static int execute(int[] source) {
int max = 0;
int l = 0;//最左
int r = source.length - 1;//最右
while (l < r) {
int lh = source[l];
int rh = source[r];
int width = r - l;
max = Math.max(max, Math.min(lh,rh) * width);
//纵轴较小的，向里收缩
if (lh < rh) {
l++;
}
else {
r--;
}
}
return max;
}
}
九、三数之和（题号：15，改）
描述：指定一个有序且无重复数字的数组，请找到其中三个数字之和为0的三元组。
示例： 输入：[-2,-1,0,2,3] 打印： [-2,0,2] [-2,-1,3]
思路：构建一个hashMap（或者hashSet），把所有元素都保存起来以便快速查找。我们遍历数组，使用双指针，同时从左、右遍历，如果此时两个元素之和大于0则右边指针向内移动，如果两个元素之和小于0则左边指针向内移动。
public class TestMain {
public static void main(String[] args) {
int[] source = {-4,-2,-1, 0, 1, 2,3};
execute(source);
}
public static void execute(int[] source) {
Map<Integer,Integer> mapping = new HashMap<>();
for (int i = 0; i < source.length; i++) {
mapping.put(source[i],i);
}
int i = 0;
int j = source.length - 1;
while (i < source.length && i < j) {
int l = source[i];
int r = source[j];
int t = 0 - (l + r);
if (mapping.containsKey(t)) {
System.out.println("[" + l + "," + r + "," + t + "]");
}
if (t > 0) {
i++;
} else if (t < 0) {
j--;
} else {
i++;
j--;
}
}
}
}
十、删除链表（单向）的倒数第N个节点（题号：19）
描述：构建（或者指定）一个单向链表，请移除倒数第N个节点。假定N肯定大于0且小于链表的长度。
示例： head -> 1 -> 2 -> 3 -> 4 -> 5 -> null 移除倒数第二个 结果： head -> 1 -> 2 -> 3 -> 5 -> null
思路：最简单的办法，就是两次遍历，第一次遍历获得链表总长度L，第二遍历找到第L - N位置的节点，然后进行移除操作。这种简单的办法，其实实现起来很容易，不过我们也可以使用一次遍历。我们可以采用类似于“滑动窗口”的思想，采用两个指针，前后两个指针之间的元素个数差为N，直到首个指针到达尾部，第二个指针的位置就是我们关注的节点。
public class TestMain {
public static void main(String[] args) {
ListNode node = new ListNode(0);
ListNode head = node;
node = (node.next = new ListNode(1));
node = (node.next = new ListNode(2));
node = (node.next = new ListNode(3));
node = (node.next = new ListNode(4));
node.next = new ListNode(5);
ListNode result = execute(head,2);
System.out.println(result);
}
public static ListNode execute(ListNode node,int n) {
//我们借用"滑动窗口"的思路，倒数第N个，其实就是正数L - n + 1
//可以首先使用一个指针遍历到正数第N个，然后再开始第二个指针从第一个节点开始，
//当第一个指针到达尾端，此时第二个指针的位置的下一个元素就是结果。然后操作remove即可。
int i = 0;
ListNode fist = node;
ListNode second = node;
while (true) {
if (i < n) {
i++;
fist = fist.next;
continue;
}
//如果到底最后一个，则终止
if (fist.next == null) {
break;
}
fist = fist.next;
second = second.next;
}
second.next.next = null;
second.next = fist;
return node.next;
}
public static class ListNode {
int value = 0;
ListNode next = null;
ListNode(int value) {
this.value = value;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append(value).append(" -> ");
ListNode t = next;
while (t != null) {
sb.append(t.value).append(" -> ");
t = t.next;
}
sb.append("null");
return sb.toString();
}
}
}
十一、有效括号（题号：20）
描述：给定一个只包含'('、')、'['、']'、'{'、'}'的字符串，判断字符串是否有效。有效的字符串需要满足：同类型括号必须成对出现、且括号的闭合顺序必须一致。
示例：
输入：(){}[]
返回：true
输入：(({}))
返回：true
输入：({])
返回：false
思路：这个题或者同类的题（配对），大学数据结构的教材中就提到过类似情况；解题方式很简单：使用栈，遇到左括号入栈，遇到右括号则出战同时比较类型是否一致。
public class TestMain {
public static void main(String[] args) {
String source = "()[]{}[}";
System.out.println(execute(source));
}
public static boolean execute(String source) {
int l = source.length();
if (l % 2 != 0) {
return false;
}
Map<Character,Character> mapping = new HashMap<>();
mapping.put(')','(');
mapping.put(']','[');
mapping.put('}','{');
Stack<Character> stack = new Stack<>();
for(int i = 0; i < l; i++) {
char c = source.charAt(i);
if (mapping.containsKey(c)) {
char x = stack.pop();
if (x != mapping.get(c)) {
return false;
}
} else {
stack.push(c);
}
}
return stack.empty();
}
}
相关推荐
如何正确刷题？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是一个在线的编程挑战平台，它包含了各种...
该项目为Java语言编写的LeetCode刷题算法设计与实现源码，包含187个文件，其中181个为Java源文件，3个为YAML配置文件，1个为Git忽略文件，以及1个LICENSE文件和1个Markdown描述文件。该源码旨在记录LeetCode刷题过程...
Stack堆栈解题套路【LeetCode刷题套路教程5】
哈希表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】