前言：考虑到本人是能力有限，算法题解只能示例一种本人能够理解和实现的方式，可能不是最优的。
一、矩阵置零（题号：73）
描述：给定一个m（列） * n（行）的矩阵，如果一个元素为0，则将其所在的行和列的所有元素都设为0。请使用原地算法。
提示：原地算法，不能额外的使用新的矩阵。
示例一： 输入: [ [1,1,1], [1,0,1], [1,1,1] ] 输出: [ [1,0,1], [0,0,0], [1,0,1] ] 示例二： 输入: [ [0,1,2,0], [3,4,5,2], [1,3,1,5] ] 输出: [ [0,0,0,0], [0,4,5,0], [0,3,1,0] ]
解题思路：本身题目不是特别复杂，唯一需要注意的是“额外空间”；本例需要O(m + n)额外空间，可能不是最优的。设计思想为：使用hashset保存需要设置0的行号和列号即可。
public class TestMain {
public static void main(String[] args) {
int[] input = new int[]{0,1,2,0,3,4,5,2,1,3,1,5};
int[][] source = build(input,3);
print(source);
execute(source);
print(source);
}
private static void execute(int[][] source) {
Set<Integer> ns = new HashSet<>();//需要替换为0的行
Set<Integer> ms = new HashSet<>();//需要替换为0的列
for (int i = 0; i < source.length; i++) {
for(int j = 0; j < source[i].length;j++) {
int value = source[i][j];
if (value == 0) {
ns.add(i);
ms.add(j);
}
}
}
for (Integer v : ns) {
int[] array = source[v];
for (int i = 0;i < array.length;i++) {
array[i] = 0;
}
}
for (Integer v : ms) {
for (int i=0; i < source.length;i++) {
source[i][v] = 0;
}
}
}
/**
* 辅助方法，将一维数组构建成二维。
* @param input
* @param n
* @return
*/
private static int[][] build(int[] input,int n) {
int length = input.length;
int m = length / n;//列
int[][] result = new int[n][m];
int nn = -1;
for (int i = 0; i < length; i++) {
if (i % m == 0) {
nn++;
}
result[nn][i % m] = input[i];
}
return result;
}
/**
* 打印二维数组，辅助方法
* @param source
*/
public static void print(int[][] source) {
System.out.println("+++++++++++++++++++++++++++");
int n = source.length;
for (int i = 0 ;i < n; i++) {
for (int j = 0; j < source[i].length; j++) {
System.out.print(padding(source[i][j],5));
}
System.out.println("");
}
}
/**
* 为了让打印的结果更易于观察，进行了padding,辅助方法
* @param target
* @param length
* @return
*/
private static String padding(int target,int length) {
String value = Integer.toString(target);
for (int i = value.length(); i < length; i++) {
value += " ";
}
return value;
}
}
二、颜色分类（题号：75）
描述：给定一个包含红色、白色和蓝色，一共n个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排序。此题中，我们使用整数0、1、2分别代表红色、白色、蓝色。
特别提醒：不能直接使用代码库中的排序API直接解决问题。
示例： 输入：[2,0,0,1,1,2] 输出：[0,0,1,1,2,2]
解题思路：有多种解题办法，比较通用直观的就是2此遍历分别交换2和0，第一遍将所有的2交换到尾部并记录首个2个位置i，然后[0,i - 1]使用相同的方式把1交换到子区域的尾部。此方式需要2次遍历；我们可以使用一次遍历 + 3个指针的方式完成，第一个指针指向首个非0元素的位置，第三个指针指向首个非2的位置，中间指针用于遍历并向前移动，遇到0则与第一个指针位置交换，遇到2则与第三个指针位置交换，直到第二、三指针重叠。
public class TestMain {
public static void main(String[] args) {
int[] source = {2,0,0,1,1,2};
execute(source);
}
private static void execute(int[] source) {
int i = 0;
int j = source.length - 1;
int x = 1;
while (true) {
int v = source[x];
if (v == 0) {
int t = source[i];
if (t != 0) {
source[i] = v;
source[x] = t;
}
i++;
continue;
}
//特别注意，向前交换0之后，不能增加x指针，因为此时交换之后的x位置不是0
//需要再次确认
if (v == 2) {
int t = source[j];
if (t != 2) {
source[j] = v;
source[x] = t;
}
j--;
x++;// 只有向后交换才向前移动指针
continue;
}
if(x == j) {
break;
}
}
}
}
三、最小覆盖子串（题号：76）
描述：给定一个字符串S和一个字符串T，请在S中找到包含T所有字母的最小子串。
说明：1）如果S中不存在这样的子串，则返回空（null） 2）如果S中存在这样的子串，我们保证它是唯一的答案，这个在输入字符串时提前保证。此外T的字符个数大于1.
输入: S = "ADOBECODEBANC", T = "ABC" 输出: "BANC"
解题思路：老一套--动态规划或者回溯法。
public class TestMain {
public static void main(String[] args) {
String source = "ADOBECODEBANC";
String target = "ABC";
String result = execute(source,target,null,0);
System.out.println(result);
}
private static String execute(String source,String target,Bulk current,int i) {
while (i < source.length()) {
char v = source.charAt(i);
if (!Bulk.valid(target,v)) {
i++;
} else {
break;
}
}
//要么遍历完毕，要么遇到了target中的字符
if (i >= source.length()) {
return null;
}
char v = source.charAt(i);
//首次遇到合适的字符
if (current == null) {
return execute(source,target,new Bulk(i,v),i+1);
}
current.put(v);
//如果此时已经包含了target的所有字符列表，则决策
if (current.hasAll(target)) {
current.end(i);
return source.substring(current.b,current.e + 1);
}
//否则：1）按照当前已有字符列表继续向后
//2）当前字符也是符合要求的开始
String r1 = execute(source,target,current,i+1);
String r2 = execute(source,target,new Bulk(i,v),i+1);
//返回最小值
return shorter(r1,r2);
}
private static String shorter(String r1,String r2) {
if (r1 != null && r2 != null) {
return r1.length() > r2.length() ? r2 : r1;
}
return r1 == null ? r2 : r1;
}
static class Bulk {
Set<Character> container = new HashSet<>();
int b = 0;
int e = -1;
Bulk(int start,char c) {
b = start;
container.add(c);
}
public int length() {
return e == -1 ? 0 : e - b;
}
public void end(int end) {
e = end;
}
public void put(char c) {
container.add(c);
}
// 可以使用set保存target字符列表，考虑到target较小，性能效率与set很接近
public static boolean valid(String target,char c) {
for(int i = 0; i< target.length(); i++) {
if (c == target.charAt(i)) {
return true;
}
}
return false;
}
public boolean hasAll(String target) {
for(int i = 0; i< target.length(); i++) {
if (!container.contains(target.charAt(i))) {
return false;
}
}
return true;
}
}
}
四、删除排序数据中的重复项（题号：80）
描述：给定一个排序数组，你需要原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
前提：不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。
示例 1： 输入：[1,1,1,2,2,3] 输出：5，原数组的前五个元素被修改为[1,1,2,2,3] 输入：[0,0,1,1,1,1,2,3,3] 输出：7,原数组的七元素被修改为[0,0,1,1,2,3,3]
public class TestMain {
public static void main(String[] args) {
int[] source = {0,0,1,1,1,1,1,1,2,3,3};
execute(source);
//System.out.println(source);
}
private static int execute(int[] source) {
int i = 0;//非常好的思路，i为亟待替换的指针，n为遍历值和指针
for (int n : source) {
if (i < 2 || n > source[i - 2]) {
source[i++] = n;//向左端i - 2方向比较，符合要求时i++
}
}
return i;
}
}
五、删除排序链表中的重复元素（题号：82）
描述：给定一个排序链表，删除所有包含重复数字的节点，只保留原始链表中没有重复出现的数字。
示例： 输入: 1->2->3->3->4->4->5 输出: 1->2->5 输入: 1->1->1->2->3 输出: 2->3
解题思路：三指针法，previous、current、next（current.next）；其中previous总是指向最新发现的不重复节点（即其前、后临近都不与其重复），通过previous.next跳过重复元素；current用于遍历和比较，向前驱动；next即为current.next，辅助比较值。
public class TestMain {
public static void main(String[] args) {
//head默认值为0，当然可以是区别与实际值的任何替代值
ListNode root = new ListNode(0);
ListNode source = root;
root = (root.next = new ListNode(1));
root = (root.next = new ListNode(1));
root = (root.next = new ListNode(2));
root = (root.next = new ListNode(2));
root.next = new ListNode(3);
ListNode result = execute(source.next);
System.out.println(result.toString());
}
/**
* 0 -> 1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5
* p
* p -> 2
* p -> 2
* p
* p -> 4
* p -> 4
* p
*
* @param head
* @return
*/
private static ListNode execute(ListNode head) {
if (head == null) {
return head;
}
//特别注意，新的链表，必须有新的head，否则指针无法控制
//使用三指针方式：前驱、当前、后驱
//前驱指针的目的：当前置和后驱以及以后的值重复时，前驱可以直接跳过所有直接指向下一个新值，
// 简单来说为每个新值的位置，主要用途为发现下个新值时用于桥接。
//当前指针的目的：指向推进方向的节点，值比较，用于定位新值。
//后驱：辅助比较值的大小
ListNode result = new ListNode(0);
result.next = head;
//从虚拟头开始
ListNode previous = result;
//从第一个实际元素开始
ListNode current = head;
while (current != null) {
//current.next即为后驱指针
//边界一定要限定，否则出错
//遇到重复数据，则一路迭代下去，直到遇到新值，此时current的指针方向，就是新值位置
while (current.next != null && current.value == current.next.value) {
current = current.next;
}
//遇到新值之后（所谓新值，就是此节点和下一个节点不同），previous指向此值（下一个节点）
//核心，就是确保，previous总是指向这种特征的节点。
//previous.next指向current遍历过的值。
//如果preview.next是新值，且current.next（即preview.next.next）也是新值
//此时更换指针，因为此时数字为非重复。
if (previous.next == current) {
//关键点：更换指针
previous = previous.next;
} else {
//关键点：不更换previous指针，只是通过previous.next忽略重复节点。
previous.next = current.next;
}
//current从previous下一个节点开始继续遍历
current = current.next;
}
return result.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);
ListNode t = next;
while (t != null) {
sb.append(t.value);
t = t.next;
}
return sb.toString();
}
}
}
六、分隔链表（题号：86）
描述：给定一个链表和一个特定值x，对链表进行分隔，使得所有小于x节点的都在大于或者等于x的节点之前。
提示：链表是无序的，链表中可能存在重复值，分隔之后的结果不需要是排序的，但是应该保留两个分区中每个节点的初始相对位置。
示例： 输入: head = 1->4->3->2->5->2, x = 3 输出: 1->2->2->4->3->5 提示：结果并非排序的，只需要 小于3的节点都在大于或者等于三的之后即可。
public class TestMain {
public static void main(String[] args) {
ListNode root = new ListNode(0);//0为标记值
ListNode source = root;
root = (root.next = new ListNode(1));
root = (root.next = new ListNode(4));
root = (root.next = new ListNode(3));
root = (root.next = new ListNode(2));
root = (root.next = new ListNode(5));
root = (root.next = new ListNode(2));
//root.next = new ListNode(3);
ListNode result = execute(source.next,3);
System.out.println(result);
}
private static ListNode execute(ListNode head,int target) {
//首先创建两个链表，分表保存大于、小于target的节点
ListNode left = new ListNode(0);//比target小的链表
ListNode right = new ListNode(0);//比target大的链表
ListNode pl = left;
ListNode pr = right;//两个指针
while (head != null) {
if (head.value < target) {
//添加到左边链表
pl.next = head;
pl = pl.next;//head.next
} else {
pr.next = head;
pr = pr.next;
}
head = head.next;//向前推进
}
pr.next = null;//尾部
pl.next = right.next;//左端的尾部与右端的头，拼接
return left.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);
ListNode t = next;
while (t != null) {
sb.append(t.value);
t = t.next;
}
return sb.toString();
}
}
}
七、合并两个有序数组（题号：88）
描述：给定两个有序数组num1和num2，将num2合并到num1中，是的num1成为一个有序数据。
说明：
1）初始化num1和num2的元素数量分表为m和n。
2）我们假设nums1有足够的空间（m + n <= num1.length）来保存num2的元素。
示例： 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
解题思路：刚开始，这个题感觉挺迷惑的，按照正常方式num1和num2遍历比较，涉及到大量元素移动。我们转换思路，我们从后向前遍历比较，较大的放置在num1合适的位置，因为num1空闲的位置可以直接放置，不涉及到移动元素。
public class TestMain {
public static void main(String[] args) {
int[] source1 = {1,2,3,0,0,0};
int[] source2 = {2,5,6};
execute(source1,source2,3,3);
System.out.println(source1);
}
private static void execute(int[] source1,int[] source2,int m,int n) {
int l1 = m - 1;//较长
int l2 = n - 1;
int x = m + n - 1;
while (l1 >= 0 && l2 >= 0) {
int i = source1[l1];
int j = source2[l2];
if (j >= i) {
source1[x] = j;
l2--;
} else {
source1[x] = i;
//如果是source1的元素较大，那么我们应该把元位置置换为0，即空位置。
source1[l1] = 0;
l1--;
}
x--;
}
}
}
八、格雷编码（题号：89）
描述：格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数n，打印其格雷编码序列。格雷编码序列必须以0开头。
输入: 2 输出: [0,1,3,2] 解释: 00 - 0 01 - 1 11 - 3 10 - 2 对于给定的 n，其格雷编码序列并不唯一。 例如，[0,2,3,1] 也是一个有效的格雷编码序列。 00 - 0 10 - 2 11 - 3 01 - 1
public class TestMain {
public static void main(String[] args) {
List<Integer> result = execute(3);
System.out.println(result);
}
private static List<Integer> execute(int n) {
List<Integer> result = new ArrayList<>();
//涉及到位运算，1 << n 二进制100, 4
//二进制右端补0
for (int i = 0;i < (1 << n);i++) {
//i >> 1二进制右端补0
//异或:位差
result.add(i ^ (i >> 1));
}
return result;
}
}
九、反转链表（题号：92）
描述：反转从位置m到n的链表，请使用一趟扫描完成反转。说明：1 <= m <= n <= 链表长度。
示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
解题思路：此题的核心部分，就是链表的中间某段反转，跟一个链表的整体反转思想一致。我们需要在反转期间记录中段的head，并将head始终与next交换即可。
public class TestMain {
public static void main(String[] args) {
//head默认值为0，当然可以是区别与实际值的任何替代值
ListNode root = new ListNode(0);
ListNode source = root;
root = (root.next = new ListNode(1));
root = (root.next = new ListNode(2));
root = (root.next = new ListNode(3));
root = (root.next = new ListNode(4));
root = (root.next = new ListNode(5));
root.next = new ListNode(6);
execute(source,2,4);
System.out.println(source);
}
/**
* [0] -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
* m = 2,n = 4
*
* 1 -> 4 -> 3 -> 2 -> 5 -> 6 -> null
* @param head
* @param m
* @param n
*/
private static ListNode execute(ListNode head,int m,int n) {
//ListNode result = new ListNode(0);
ListNode previous = head;
ListNode current = head.next;
for (int i = 0 ;i < m - 1; i++) {
previous = current;
current = current.next;
}
//此时指针状态
// ph
//[0] -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
// pre cur next
ListNode ph = previous;//中段的head记住，始终与current.next交换
for (int i = 0; i < n - m; i++) {
ListNode next = current.next;
// ph
// 3 -> 2 -> 5 -> 6 -> null
// cur
// 4 ->
current.next = next.next;
// ph
// 4 -> 3 -> 2 -> 5 -> 6 -> null
// cur
next.next = ph.next;
// ph
// 4 -> 3 -> 2 -> 5 -> 6 -> null
// cur
ph.next = next;
}
return head;
}
public static class ListNode {
int value = 0;
ListNode next = null;
ListNode(int value) {
this.value = value;
}
}
}
十、复原IP地址（题号：93）
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例: 输入: "25525511135" 输出: ["255.255.11.135", "255.255.111.35"]
解题思路：典型的回溯法，需要注意几个细节，IP地址为四段，每段最大为255，除了首段之外其他段最小为0，换句话而言，每段最长3个字符/最小为1个字符。所以在回溯时，可以每三个字符为一个节奏。
public class TestMain {
public static void main(String[] args) {
List<String> result = execute("25525511135");
System.out.println(result);
}
/**
* ip地址，分四段，每段字符长度最大为3，数字值最大为255，最小为0
* 首段不为0
* 回溯法
* @param source
* @return
*/
public static List<String> execute(String source) {
List<String> result = new ArrayList<>();
backtracking(source,0,new ArrayList<>(),result);
return result;
}
/**
*
* @param source 原始字符串
* @param i 当前字符索引，从此为止开始向下遍历
* @param current 当前回溯的历史记录，即一个IP的历史片段
* @param result 总结果
*/
private static void backtracking(String source, int i, List<String> current, List<String> result) {
if (current.size() == 4) {
if (i != source.length()) {
return;
}
int dot = 0;
StringBuilder sb = new StringBuilder();
for (String segment : current) {
sb.append(segment);
if (dot < 3) {
sb.append(".");
}
dot++;
}
result.add(sb.toString());
return;
}
//每三个字符一组判断
for (int n = i; n < i + 4 && n < source.length(); n++) {
String segment = source.substring(i, n + 1);//子串
if (!isValid(segment)) {
continue;
}
current.add(segment);//加入回溯
backtracking(source, n + 1,current,result);
current.remove(current.size() - 1);//移除回溯
}
}
/**
* 字符片段是否为合法的ip段,特别注意0
* 0 <= n < 256
* @param segment 待判断待字符串片段
* @return
*/
private static boolean isValid(String segment) {
if (segment.charAt(0) == '0') {
return segment.equals("0");
}
int num = Integer.valueOf(segment);
return (num >= 0 && num < 256);
}
}
十一、对称二叉树（题号：101）
描述：给定一个二叉树，检查它是否是镜像对称的。
解题思路：比较简单，同一层的节点，最左和最右的值相同。基于递归，使用此策略。
public class TestMain {
public static void main(String[] args) {
}
private static boolean execute(TreeNode left,TreeNode right) {
if (left != null && right != null) {
if (left.value != right.value) {
return false;
}
return execute(left.left,right.right) && execute(left.right,right.left);
}
if (left == null && right == null) {
return true;
}
return false;
}
static class TreeNode {
TreeNode left;
TreeNode right;
int value;
TreeNode(int value) {
this.value = value;
}
}
}
相关推荐
如何正确刷题？LeetCode刷题误区和刷题方法论分享【LeetCode刷题套路教程1】
Backtracking回溯解题套路【LeetCode刷题套路教程18】
Heap堆解题套路【LeetCode刷题套路教程6】
一些java基础算法、leetcode刷题 Java学习资料
主要介绍了如何在Intellij中安装LeetCode刷题插件方便Java刷题,本文通过图文并茂的形式给大家介绍的非常详细，对大家的学习或工作具有一定的参考借鉴价值，需要的朋友可以参考下
二分查找Binary_Search套路和解题模板【LeetCode刷题套路教程3】
Stack堆栈解题套路【LeetCode刷题套路教程5】
这个是自己收藏的一个leetcode刷题记录，分享给需要的亲。非原创，自己也正在学习中。
哈希表HashMap解题套路【LeetCode刷题套路教程7】
DynamicProgramming2D解题套路【LeetCode刷题套路教程15】
Array题型_双指针Two_Pointers套路【LeetCode刷题套路教程2】
DynamicProgramming1D解题套路【LeetCode刷题套路教程14】
DynamicProgramming2D高级解题套路【LeetCode刷题套路教程17】
DynamicProgramming2D进阶解题套路【LeetCode刷题套路教程16】
Search,_Dynamic_Programming1【LeetCode刷题套路教程13】
Graph图BFS广度优先搜索套路【LeetCode刷题套路教程10】
Graph图DFS深度优先搜索题型套路【LeetCode刷题套路教程12】
树Tree深度优先搜索DFS解题套路【LeetCode刷题套路教程9】
树Tree题型广度优先搜索BFS套路【LeetCode刷题套路教程8】
Graph图Best-First_Search题型套路【LeetCode刷题套路教程11】