前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。
一、两数之和（题号：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】
Backtracking回溯解题套路【LeetCode刷题套路教程18】
Heap堆解题套路【LeetCode刷题套路教程6】
一些java基础算法、leetcode刷题 Java学习资料
主要介绍了如何在Intellij中安装LeetCode刷题插件方便Java刷题,本文通过图文并茂的形式给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下
Stack堆栈解题套路【LeetCode刷题套路教程5】
这个是自己收藏的一个leetcode刷题记录，分享给需要的亲。非原创，自己也正在学习中。
哈希表HashMap解题套路【LeetCode刷题套路教程7】
DynamicProgramming2D解题套路【LeetCode刷题套路教程15】
DynamicProgramming1D解题套路【LeetCode刷题套路教程14】
Search,_Dynamic_Programming1【LeetCode刷题套路教程13】
Array题型_双指针Two_Pointers套路【LeetCode刷题套路教程2】
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
DynamicProgramming2D高级解题套路【LeetCode刷题套路教程17】
DynamicProgramming2D进阶解题套路【LeetCode刷题套路教程16】
Graph图BFS广度优先搜索套路【LeetCode刷题套路教程10】
Graph图DFS深度优先搜索题型套路【LeetCode刷题套路教程12】
树Tree深度优先搜索DFS解题套路【LeetCode刷题套路教程9】
树Tree题型广度优先搜索BFS套路【LeetCode刷题套路教程8】
Graph图Best-First_Search题型套路【LeetCode刷题套路教程11】