大家好，欢迎来到IT知识分享网。

1、两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例

输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

解题思路

• 遍历数组 nums，i 为当前下标，每个值都判断map中是否存在 nums[i] 的 key 值。
• 如果存在则找到了两个值，如果不存在则将当前的 (target – nums[i],i) 存入 map 中，继续遍历直到找到为止。

参考代码：

class Solution { public int[] twoSum(int[] nums, int target) { int[] result = new int[2]; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { result[0] = map.get(nums[i]); result[1] = i; return result; } map.put(target - nums[i], i); } return result; } }

2、无重复字符的最长子串

题目链接

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

示例

输入: s = "abcabcbb" 输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

解题思路

这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)

代码实现

class Solution { public int lengthOfLongestSubstring(String s) { if (s.length()==0) return 0; HashMap<Character, Integer> map = new HashMap<Character, Integer>(); int max = 0; int left = 0; for(int i = 0; i < s.length(); i ++){ if(map.containsKey(s.charAt(i))){ left = Math.max(left,map.get(s.charAt(i)) + 1); } map.put(s.charAt(i),i); max = Math.max(max,i-left+1); } return max; } }

3、最长回文子串

原题链接

题目描述

从给定的字符串 s 中找到最长的回文子串的长度。

例如 s = “babbad” 的最长回文子串是 “abba” ，长度是 4 。

解题思路

1. 定义状态。dp[i][j] 表示子串 s[i..j] 是否为回文子串
2. 状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i + 1][j – 1]
3. 初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true 。
4. 只要一得到 dp[i][j] = true，就记录子串的长度和起始位置

注意事项：总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要。

时间复杂度O(N2)，空间复杂度O(N2)，因为使用了二维数组。

public class Solution { public String longestPalindrome(String s) { // 特判 int len = s.length(); if (len < 2) { return s; } int maxLen = 1; int begin = 0; // dp[i][j] 表示 s[i, j] 是否是回文串 boolean[][] dp = new boolean[len][len]; char[] charArray = s.toCharArray(); for (int i = 0; i < len; i++) { dp[i][i] = true; } for (int j = 1; j < len; j++) { for (int i = 0; i < j; i++) { if (charArray[i] != charArray[j]) { dp[i][j] = false; } else { if (j - i < 3) { dp[i][j] = true; } else { dp[i][j] = dp[i + 1][j - 1]; } } // 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置 if (dp[i][j] && j - i + 1 > maxLen) { maxLen = j - i + 1; begin = i; } } } return s.substring(begin, begin + maxLen); //substring(i, j)截取i到j(不包含j)的字符串 } }

4、整数反转

题目链接

题目描述

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例

输入：x = 123 输出：321 输入：x = 120 输出：21

解题思路

• 本题如果不考虑溢出问题，是非常简单的。解决溢出问题有两个思路，第一个思路是通过字符串转换加try catch的方式来解决，第二个思路就是通过数学计算来解决。
• 由于字符串转换的效率较低且使用较多库函数，所以解题方案不考虑该方法，而是通过数学计算来解决。
• 通过循环将数字x的每一位拆开，在计算新值时每一步都判断是否溢出。
• 溢出条件有两个，一个是大于整数最大值MAX_VALUE，另一个是小于整数最小值MIN_VALUE，设当前计算结果为ans，下一位为pop。
• 从ans * 10 + pop > MAX_VALUE这个溢出条件来看当出现 ans > MAX_VALUE / 10 且 还有pop需要添加 时，则一定溢出当出现 ans == MAX_VALUE / 10 且 pop > 7 时，则一定溢出，7是2^31 – 1的个位数
• 从ans * 10 + pop < MIN_VALUE这个溢出条件来看当出现 ans < MIN_VALUE / 10 且 还有pop需要添加 时，则一定溢出当出现 ans == MIN_VALUE / 10 且 pop < -8 时，则一定溢出，8是-2^31的个位数

class Solution { public int reverse(int x) { int ans = 0; while (x != 0) { int pop = x % 10; if (ans > Integer.MAX_VALUE / 10 || (ans == Integer.MAX_VALUE / 10 && pop > 7)) return 0; if (ans < Integer.MIN_VALUE / 10 || (ans == Integer.MIN_VALUE / 10 && pop < -8)) return 0; ans = ans * 10 + pop; x /= 10; } return ans; } }

5、回文数

题目描述

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例

输入：x = 121 输出：true 输入：x = -121 输出：false 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

解题思路

将数字后半段反转，跟数字前半段相比即可。

class Solution { public boolean isPalindrome(int x) { //排除负数和整十的数 if (x < 0 || (x % 10 == 0 && x != 0)) { return false; } int reverseNum = 0; //反转x的后半段数字，再做比较即可 while(x > reverseNum) { reverseNum = reverseNum * 10 + x % 10; x /= 10; } //x为奇数位时，转换后reverseNum会比x多一位//如x为，转换后reverseNum为1234，x为123 return x == reverseNum || x == reverseNum / 10; } }

6、盛最多水的容器

题目描述

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

说明：你不能倾斜容器。

示例

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。 输入：height = [1,1] 输出：1

解题思路

左右指针，数字小的指针往数字大的指针移动，面积才有可能变大。注意左右指针数字相同的情况。

class Solution { public int maxArea(int[] height) { int maxArea = 0; int left = 0; int right = height.length - 1; while(left < right) { maxArea = Math.max(maxArea, Math.min(height[left], height[right]) * (right - left)); if(height[left] > height[right]) { right--; } else { left++; } } return maxArea; } }

7、三数之和

题目链接

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例

输入：nums = [-1,0,1,2,-1,-4] 输出：[[-1,-1,2],[-1,0,1]]

解题思路

固定 3 个指针中最左（最小）数字的指针 k，双指针 i，j 分设在数组索引 k 两端，通过双指针交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：

• 当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 3 个数字都大于 0 ，在此固定指针 k 之后不可能再找到结果了。
• 当 k > 0且nums[k] == nums[k – 1]时即跳过此元素nums[k]：因为已经将 nums[k – 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
• i，j 分设在数组索引 (k, len(nums))(k,len(nums)) 两端，当i < j时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：当s < 0时，i += 1并跳过所有重复的nums[i]；当s > 0时，j -= 1并跳过所有重复的nums[j]；当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合。

参考代码：

class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> res = new ArrayList<>(); for(int k = 0; k < nums.length - 2; k++){ if(nums[k] > 0) break; if(k > 0 && nums[k] == nums[k - 1]) continue; int i = k + 1, j = nums.length - 1; while(i < j){ int sum = nums[k] + nums[i] + nums[j]; if(sum < 0){ while(i < j && nums[i] == nums[++i]); } else if (sum > 0) { while(i < j && nums[j] == nums[--j]); } else { res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j]))); while(i < j && nums[i] == nums[++i]); while(i < j && nums[j] == nums[--j]); } } } return res; } }

8、四数之和

题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例

输入：nums = [1,0,-1,0,-2,2], target = 0 输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]] 输入：nums = [2,2,2,2,2], target = 8 输出：[[2,2,2,2]]

解题思路

参考代码：

class Solution { public List<List<Integer>> fourSum(int[] nums, int target) { List<List<Integer>> ans = new ArrayList<>(); if (nums == null || nums.length < 4) { return ans; } int len = nums.length; Arrays.sort(nums); for (int i = 0; i < len; i++) { if (i > 0 && nums[i] == nums[i - 1]) { // forgot, 去重复 continue; } for (int j = i + 1; j < len; j++) { if (j > i + 1 && nums[j] == nums[j - 1]) {//j大于i+1才去重复 continue; } int left = j + 1; int right = len - 1; while (left < right) { int sum = nums[i] + nums[j] + nums[left] + nums[right]; if (sum == target) { ans.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); while (left < right && nums[left] == nums[left + 1]) { left++;//去重复 } while (left < right && nums[right] == nums[right - 1]) { right--;//去重复 } left++;//forgot right--;//forgot } else if (sum < target) { left++; } else { right--; } } } } return ans; } }

9、删除链表的倒数第 N 个结点

原题链接

题目描述

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例

输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]

解题思路

我们可以设想假设设定了双指针 p 和 q 的话，当 q 指向末尾的 NULL，p 与 q 之间相隔的元素个数为 n 时，那么删除掉 p 的下一个指针就完成了要求。

• 设置虚拟节点 dummyHead 指向 head
• 设定双指针 p 和 q，初始都指向虚拟节点 dummyHead
• 移动 q，直到 p 与 q 之间相隔的元素个数为 n
• 同时移动 p 与 q，直到 q 指向的为 NULL
• 将 p 的下一个节点指向下一个节点

代码实现

class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre = dummy; ListNode slow = head; ListNode fast = head; for(int i=0;i<n;i++){ fast = fast.next; } while(fast!=null){ pre = pre.next; slow = slow.next; fast = fast.next; } pre.next = slow.next; return dummy.next; } }

10、有效的括号

题目描述

给定一个只包括 ‘(‘，’)’，'{‘，’}’，'[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。
• 每个右括号都有一个对应的相同类型的左括号。

示例

输入：s = "()" 输出：true 输入：s = "()[]{}" 输出：true

解题思路

使用栈实现。

class Solution { public boolean isValid(String s) { Stack<Character> stack = new Stack<>(); for (int i = 0; i < s.length(); i++) { switch (s.charAt(i)) { case '(': stack.push(')');//存进相反符号 break; case '[': stack.push(']'); break; case '{': stack.push('}'); break; default: if (stack.isEmpty() || s.charAt(i) != stack.pop()) { return false; } break; } } return stack.isEmpty(); } }

11、合并两个有序链表

题目描述

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入：l1 = [1,2,4], l2 = [1,3,4] 输出：[1,1,2,3,4,4]

参考代码

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode ans = new ListNode(0); ListNode tmp = ans; while (l1 != null && l2!= null) { if (l1.val > l2.val) { tmp.next = l2; //tmp.next = new ListNode(l2.val); 没必要这么做 l2 = l2.next; } else { tmp.next = l1; l1 = l1.next; } tmp = tmp.next; } tmp.next = l1 == null ? l2 : l1; return ans.next; } }

12、括号生成

题目描述

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例

输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]

解题思路

深度优先算法。

如果完成一件事情有很多种方法，并且每一种方法分成若干步骤，那多半就可以使用“回溯”算法完成。

“回溯”算法的基本思想是“尝试搜索”，一条路如果走不通（不能得到想要的结果），就回到上一个“路口”，尝试走另一条路。

因此，“回溯”算法的时间复杂度一般不低。如果能提前分析出，走这一条路并不能得到想要的结果，可以跳过这个分支，这一步操作叫“剪枝”。

做“回溯”算法问题的基本套路是：

1、使用题目中给出的示例，画树形结构图，以便分析出递归结构；

一般来说，树形图不用画完，就能够分析出递归结构和解题思路。

2、分析一个结点可以产生枝叶的条件、递归到哪里终止、是否可以剪枝、符合题意的结果在什么地方出现（可能在叶子结点，也可能在中间的结点）；

3、完成以上两步以后，就要编写代码实现上述分析的过程，使用代码在画出的树形结构上搜索符合题意的结果。

在树形结构上搜索结果集，使用的方法是执行一次“深度优先遍历”。在遍历的过程中，可能需要使用“状态变量”。

我们以 n = 2 为例，画树形结构图。

画图以后，可以分析出的结论：

• 左右都有可以使用的括号数量，即严格大于 0 的时候，才产生分支；
• 左边不受右边的限制，它只受自己的约束；
• 右边除了自己的限制以外，还收到左边的限制，即：右边剩余可以使用的括号数量一定得在严格大于左边剩余的数量的时候，才可以“节外生枝”；
• 在左边和右边剩余的括号数都等于 0 的时候结算。

参考代码如下：

import java.util.ArrayList; import java.util.List; public class Solution { // 做减法public List<String> generateParenthesis(int n) { List<String> res = new ArrayList<>(); // 特判if (n == 0) { return res; } // 执行深度优先遍历，搜索可能的结果 dfs("", n, n, res); return res; } /** * @param curStr 当前递归得到的结果 * @param left 左括号还有几个可以使用 * @param right 右括号还有几个可以使用 * @param res 结果集 */private void dfs(String curStr, int left, int right, List<String> res) { // 因为每一次尝试，都使用新的字符串变量，所以无需回溯// 在递归终止的时候，直接把它添加到结果集即可，注意与「力扣」第 46 题、第 39 题区分 if (left == 0 && right == 0) { res.add(curStr); return; } // 剪枝（如图，左括号可以使用的个数严格大于右括号可以使用的个数，才剪枝，注意这个细节） if (left > right) { return; } if (left > 0) { dfs(curStr + "(", left - 1, right, res); } if (right > 0) { dfs(curStr + ")", left, right - 1, res); } } }

13、两两交换链表中的节点

两两交换链表中的节点

题目描述

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例

输入：head = [1,2,3,4] 输出：[2,1,4,3]

解题思路

使用递归实现。

class Solution { public ListNode swapPairs(ListNode head) { if (head == null) { return head; } ListNode left = head; ListNode right = head.next; if (right == null) { right = left; } else { left.next = swapPairs(right.next); right.next = left; } return right; } }

14、删除有序数组中的重复项

题目链接

题目描述

给你一个 升序排列 的数组 nums ，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例：

输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

参考代码

class Solution { public int removeDuplicates(int[] nums) { if (nums == null || nums.length == 0) { return 0; } int left = 0; int right = 1; int count = 1; while (right < nums.length) { if (nums[right] == nums[left]) { if (count < 2) { nums[++left] = nums[right++]; } else { right++; } count++; } else { count = 1; nums[++left] = nums[right++]; } } return left + 1; } }

15、移除元素

移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例

输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

解题思路

class Solution { public int removeElement(int[] nums, int val) { int ans = 0; for(int num: nums) { if(num != val) { nums[ans] = num; ans++; } } return ans; } }

16、对称的二叉树

题目描述

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

示例

输入：root = [1,2,2,3,4,4,3] 输出：true

解题思路

从顶至底递归，判断每对节点是否对称，从而判断树是否为对称二叉树。

class Solution { public boolean isSymmetric(TreeNode root) { if (root == null) { return true; } return isMirror(root.left, root.right); } public boolean isMirror(TreeNode node1, TreeNode node2) { if (node1 == null && node2 == null) { return true; } if (node1 == null || node2 == null || node1.val != node2.val) { return false; } return isMirror(node1.left, node2.right) && isMirror(node1.right, node2.left); } }

17、两数相除

题目描述

给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。

返回被除数 dividend 除以除数 divisor 得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例

输入: dividend = 10, divisor = 3 输出: 3 解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

解题思路

Integer.MIN_VALUE 转为正数会溢出，故将 dividend 和 divisor 都转化为负数。两个负数相加溢出会大于0。

class Solution { //dividend / divisor public int divide(int dividend, int divisor) { if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } if (divisor == 1) { //不加上会超时return dividend; } int sign = 1; if ((dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0)) { sign = -1; } int a = dividend > 0 ? -dividend : dividend; int b = divisor > 0 ? -divisor : divisor; if (a > b) { return 0; } int ans = divideHelper(a, b); return sign > 0 ? ans : -ans; } private int divideHelper(int a, int b) { if (a > b) { return 0; } int count = 1; int tmp = b; while (tmp + tmp >= a && tmp + tmp < 0) { //两个负数相加溢出会大于0 tmp += tmp; count += count; } return count + divideHelper(a - tmp, b); } }