【leetcode】剑指Offer专项突击版含注释 Java版本（一）
目录
前言
以下文章主要是方便自我学习总结
感兴趣的也可一键三连互相学习
大部分算法题都是刷过很多次，知识点也比较重复，特殊情况下会重点讲解下代码思路
对应另一套算法题：
第一天（整数）
剑指 Offer II 002. 二进制加法（简单）
题目：剑指 Offer II 002. 二进制加法
此题和 67. 二进制求和 一模一样
给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = “11”, b = “10”
输出: “101”
示例 2:
输入: a = “1010”, b = “1011”
输出: “10101”
提示：
每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
1 <= a.length, b.length <= 104
字符串如果不是 “0” ，就都不含前导零。
思路：
class Solution {
public String addBinary(String a, String b) {
int i = a.length() - 1;
int j = b.length() - 1;
int carry = 0;
StringBuilder sb = new StringBuilder();
while(i >= 0 || j >= 0 || carry != 0){
int x = i >= 0 ? a.charAt(i) - '0' : 0;
int y = j >= 0 ? b.charAt(j) - '0' : 0;
int add = x + y + carry;
// 添加对应的进位以及保留元素
sb.append(add % 2);
carry = add / 2;
i--;
j--;
}
return sb.reverse().toString();
}
}
第二天（整数）
剑指 Offer II 004. 只出现一次的数字 （中等）
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2]
输出：3
示例 2：
输入：nums = [0,1,0,1,0,1,100]
输出：100
提示：
1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
注意：本题与主站 137 题相同：137. 只出现一次的数字 II
class Solution {
public int singleNumber(int[] nums) {
// 此ans为累加的值
int ans = 0;
// 遍历32个 位
for(int i = 0;i < 32;i++){
int total = 0;
// 遍历数组中每个位的运算，如果这个位是3的倍数则一定不是答案
for(int num : nums){
// num从右往左，而且是和1相与查看
total += ((num >> i) & 1);
}
if(total % 3 != 0){
// 对应将其所有的ans进行或，也就是合并。
ans |= (1 << i);
}
}
return ans;
}
}
剑指 Offer II 005. 单词长度的最大乘积（中等）
给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。
示例 1:
输入: words = [“abcw”,“baz”,“foo”,“bar”,“fxyz”,“abcdef”]
输出: 16
解释: 这两个单词为 “abcw”, “fxyz”。它们不包含相同字符，且长度的乘积最大。
示例 2:
输入: words = [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]
输出: 4
解释: 这两个单词为 “ab”, “cd”。
示例 3:
输入: words = [“a”,“aa”,“aaa”,“aaaa”]
输出: 0
解释: 不存在这样的两个单词。
提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母
注意：本题与主站 318 题相同：318. 最大单词长度乘积
利用位运算的存储
class Solution {
public int maxProduct(String[] words) {
// 定义一个marks来存储 每个单词的 位
int[] marks = new int[words.length];
for(int i = 0;i < words.length;i++){
String word = words[i];
// 将其每个位都存储起来，通过1左移多少位，并且 或
for(int j = 0;j < word.length();j++){
marks[i] |= 1 << (word.charAt(j) - 'a');
}
}
int ans = 0;
for(int i = 0;i < marks.length;i++){
for(int j = i + 1;j < marks.length;j++){
// 如果两者为0，说明不含相同字母，将其words数组的length相乘
if((marks[i] & marks[j]) == 0){
ans = Math.max(ans,words[i].length() * words[j].length());
}
}
}
return ans;
}
}
剑指 Offer II 006. 排序数组中两个数字之和（简单）
题目：剑指 Offer II 006. 排序数组中两个数字之和
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。
假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。
示例 1：
输入：numbers = [1,2,4,6,10], target = 8
输出：[1,3]
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[0,2]
示例 3：
输入：numbers = [-1,0], target = -1
输出：[0,1]
提示：
2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 递增顺序 排列
-1000 <= target <= 1000
仅存在一个有效答案
注意：本题与主站 167 题相似（下标起点不同）：167. 两数之和 II - 输入有序数组
本身已经排序好，可以使用二分查找
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
// 此处定义的sum总值，需为numbers[left] + numbers[right];
while(left <= right){
int sum = numbers[left] + numbers[right];
if(sum == target){
return new int[]{left,right};
}else if (sum < target) {
left++;
}else if(sum > target){
right--;
}
}
// 如果值不符，则返回-1,-1
return new int[]{-1,-1};
}
}
第三天（数组）
剑指 Offer II 007. 数组中和为 0 的三个数（中等）
题目：剑指 Offer II 007. 数组中和为 0 的三个数
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000
-105 <= nums[i] <= 105
注意：本题与主站 15 题相同：15. 三数之和
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
List<List<Integer>> list = new ArrayList<List<Integer>>();
for(int i = 0;i < n - 2;i++){
// 大于0，则后面的数字也是大于零（排序后是递增的）
if(nums[i] > 0)break;
// 代表第一个值重复了，去重,此处的去重是 不同子list的开头
if(i > 0 && nums[i] == nums[i - 1])continue;
System.out.println(i);
int left = i + 1;
int right = n - 1;
while(left < right){
int sum = nums[left] + nums[right] + nums[i];
if(sum == 0){
List<Integer> sonlist = new ArrayList<>();
sonlist.add(nums[left]);
sonlist.add(nums[right]);
sonlist.add(nums[i]);
list.add(sonlist);
//list.add(new ArrayList<>(Arrays.asList(nums[i],nums[left],nums[right])));
//左指针前进并去重
while(left < right && nums[left] == nums[++left]);
//右指针前进并去重
while(left < right && nums[right] == nums[--right]);
}else if(sum < 0){
//左指针前进并去重
while (left < right && nums[left] == nums[++left]);
}else if(sum > 0){
//右指针前进并去重
while (left < right && nums[right] == nums[--right]);
}
}
}
return list;
}
}
剑指 Offer II 008. 和大于等于 target 的最短子数组（中等）***
题目：剑指 Offer II 008. 和大于等于 target 的最短子数组
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：
输入：target = 4, nums = [1,4,4]
输出：1
示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
提示：
1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105
进阶：
如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。
注意：本题与主站 209 题相同：209. 长度最小的子数组
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int start = 0;
int end = 0;
int n = nums.length;
int sum = 0;
// 设置一个最大值
int ans = Integer.MAX_VALUE;
while(end < n){
// 对应将其end的值都加入
sum += nums[end];
// 如果大于等于target 则进行筛选ans的下标差
while(sum >= target){
ans = Math.min(ans,end - start + 1);
// 不要忘记将其nums【start】 减去，因为是滑动串窗口
sum -= nums[start];
start++;
}
end++;
}
// 判定最后的值是否符合
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
剑指 Offer II 009. 乘积小于 K 的子数组（中等）
题目：剑指 Offer II 009. 乘积小于 K 的子数组
给定一个正整数数组 nums和整数 k ，请找出该数组内乘积小于 k 的连续的子数组的个数。
示例 1:
输入: nums = [10,5,2,6], k = 100
输出: 8
解释: 8 个乘积小于 100 的子数组分别为: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘积小于100的子数组。
示例 2:
输入: nums = [1,2,3], k = 0
输出: 0
提示:
1 <= nums.length <= 3 * 104
1 <= nums[i] <= 1000
0 <= k <= 106
注意：本题与主站 713 题相同：713. 乘积小于 K 的子数组
每次加上以当前数字为结尾的所有子数组数量
/**
如果值为10 5 2 6
第一个窗口为10，整体答案为【10】共有1个
第二个窗口为10 5 ,整体答案为【10，5】【5】共有2个
第三个窗口为10,5,2,因为不满足，所以把10排出去，窗口为5，2.整体答案为【5，2】，【2】共有2个
第四个窗口为5 2 6，整体答案为【5，2，6】【2，6】【6】共有三个
*/
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int left = 0;
int right = 0;
int n = nums.length;
int sum = 1;
int ans = 0;
while(right < n){
sum *= nums[right];
// 注意边界条件，不要忘记left <= right
while(sum >= k && left <= right){
sum /= nums[left];
left++;
}
// 每次加上以当前数字为结尾的所有子数组数量。
ans += right - left + 1;
right++;
}
return ans;
}
}
第四天（数组）滑动窗口
剑指 Offer II 010. 和为 k 的子数组（中等）
题目：剑指 Offer II 010. 和为 k 的子数组
此题和 560. 和为 K 的子数组题目一样
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
示例 1：
输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2：
输入:nums = [1,2,3], k = 3
输出: 2
提示:
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
思路：
class Solution {
public int subarraySum(int[] nums, int k) {
int n = nums.length;
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int pre = 0;
int count = 0;
for(int i = 0;i < n;i++){
// 前缀和
pre += nums[i];
if(map.containsKey(pre - k)){
count += map.get(pre - k);
}
// 为下一个临界值 增加一个1
map.put(pre,map.getOrDefault(pre,0) + 1);
}
return count;
}
}
剑指 Offer II 012. 左右两边子数组的和相等（简单）
题目：剑指 Offer II 012. 左右两边子数组的和相等
此题和724. 寻找数组的中心下标 题目一样
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1：
输入：nums = [1,7,3,6,5,6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。
示例 3：
输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
提示：
1 <= nums.length <= 104
-1000 <= nums[i] <= 1000
思路：
class Solution {
public int pivotIndex(int[] nums) {
// 通过java8的特性，使用stream函数，计算总和
int total = Arrays.stream(nums).sum();
int n = nums.length;
int sum = 0;
// 计算前缀和，对应是2倍的sum + nums 等于total则返回i
for(int i = 0;i < n;i++){
if(2 * sum + nums[i] == total){
return i;
}
sum += nums[i];
}
return -1;
}
}
另外一种思路是，计算前缀和都存储在数组中，计算后缀和也存储在数组中，比较两个数组是否有相等的值，返回对应的i即可
第五天（字符串）
剑指 Offer II 016. 不含重复字符的最长子字符串（中等）
题目：剑指 Offer II 016. 不含重复字符的最长子字符串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。
示例 1:
输入: s = “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子字符串是 “abc”，所以其长度为 3。
示例 2:
输入: s = “bbbbb”
输出: 1
解释: 因为无重复字符的最长子字符串是 “b”，所以其长度为 1。
示例 3:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，“pwke” 是一个子序列，不是子串。
示例 4:
输入: s = “”
输出: 0
提示：
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
注意：本题与主站 3 题相同： 3. 无重复字符的最长子串
class Solution {
public int lengthOfLongestSubstring(String s) {
// 哈希集合，记录每个字符是否出现过
Set<Character> set = new HashSet<Character>();
int n = s.length();
// 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
int rk = -1, ans = 0;
for (int i = 0; i < n; ++i) {
if (i != 0) {
// 左指针向右移动一格，移除一个字符
set.remove(s.charAt(i - 1));
}
while (rk + 1 < n && !set.contains(s.charAt(rk + 1))) {
// 不断地移动右指针
set.add(s.charAt(rk + 1));
++rk;
}
// 第 i 到 rk 个字符是一个极长的无重复字符子串
ans = Math.max(ans, rk - i + 1);
}
return ans;
}
}
第六天（字符串）
剑指 Offer II 018. 有效的回文（简单）
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
本题中，将空字符串定义为有效的 回文串 。
示例 1:
输入: s = “A man, a plan, a canal: Panama”
输出: true
解释：“amanaplanacanalpanama” 是回文串
示例 2:
输入: s = “race a car”
输出: false
解释：“raceacar” 不是回文串
提示：
1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成
注意：本题与主站 125 题相同：125. 验证回文串
在原字符串进行操作，是最优d
class Solution {
public boolean isPalindrome(String s) {
// 将其拆分成单个字符
char[] c = s.toLowerCase().toCharArray();
// 对应都变为边界值
int left = 0, right = c.length - 1;
while(left < right){
// 直到遇到左边第一个单词
while(!isValid(c[left]) && left < right){
++left;
}
// 直到遇到右边第一个单词
while(!isValid(c[right]) && left < right){
--right;
}
// 判断两者是否相等
if(c[left] != c[right]){
return false;
}
++left;
--right;
}
return true;
}
private boolean isValid(char c){
return (c >= 'a' && c <= 'z') || (c >= '0' && c <= '9');
}
}
剑指 Offer II 019. 最多删除一个字符得到回文（简单）
题目：剑指 Offer II 019. 最多删除一个字符得到回文
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。
示例 1:
输入: s = “aba”
输出: true
示例 2:
输入: s = “abca”
输出: true
解释: 可以删除 “c” 字符 或者 “b” 字符
示例 3:
输入: s = “abc”
输出: false
提示:
1 <= s.length <= 105
s 由小写英文字母组成
注意：本题与主站 680 题相同：680. 验证回文串 II
class Solution {
public boolean validPalindrome(String s) {
int n = s.length();
int left = 0;
int right = n - 1;
// 前后进行判断
while(left < right){
char c1 = s.charAt(left);
char c2 = s.charAt(right);
// 如果两者的值相等，则 前进以及后退
if(c1 == c2){
left++;
right--;
}else {
return validPalindrome(s,left,right - 1) || validPalindrome(s,left + 1,right);
}
}
return true;
}
public boolean validPalindrome(String s, int left, int right){
for(int i = left,j = right ; i < j ; i++,j--){
if(s.charAt(i) != s.charAt(j)){
return false;
}
}
return true;
}
}
剑指 Offer II 020. 回文子字符串的个数（中等）*
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
示例 1：
输入：s = “abc”
输出：3
解释：三个回文子串: “a”, “b”, “c”
示例 2：
输入：s = “aaa”
输出：6
解释：6个回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”
提示：
1 <= s.length <= 1000
s 由小写英文字母组成
注意：本题与主站 647 题相同：647. 回文子串
class Solution {
public int countSubstrings(String s) {
int n = s.length();
int sum = 0;
for(int i = 0;i <n;i++){
// 边界处理问题，使用奇数 偶数处理
for(int j = 0;j <= 1;j++){
// 定义left 以及 right的边界值
int left = i;
int right = i +j;
// 此处使用while来判断两者是否相等
while(left >= 0 && right < n && s.charAt(left--) == s.charAt(right++)){
sum++;
}
}
}
return sum;
}
}
第七天（链表）
剑指 Offer II 021. 删除链表的倒数第 n 个结点（中等）
题目：剑指 Offer II 021. 删除链表的倒数第 n 个结点
此题和19. 删除链表的倒数第 N 个结点一样
注意一开始定义的细节
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0,head);
// 此处的first 为head节点，second为dummy节点
// 注意其中的区别
ListNode first = head;
ListNode second = dummy;
for(int i = 0;i < n;i++){
first = first.next;
}
while(first != null){
first = first.next;
second = second.next;
}
second.next = second.next.next;
return dummy.next;
}
}
剑指 Offer II 022. 链表中环的入口节点（中等）
题目：剑指 Offer II 022. 链表中环的入口节点
和142. 环形链表 II一模一样
注意一开始循环的细节
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// 此处的条件不是fast ！= slow，因为一开始就是相等的
while(true){
// 中间为null的时候返回为null
if(fast == null || fast.next == null) return null;
slow = slow.next;
fast = fast.next.next;
// 相等的时候 break出来
if (fast == slow) break;
}
fast = head;
while(fast != slow){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
剑指 Offer II 023. 两个链表的第一个重合节点（简单）
题目：剑指 Offer II 023. 两个链表的第一个重合节点
和题目：160. 相交链表一模一样
内部的if else 要分开
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null){
return null;
}
ListNode a = headA;
ListNode b = headB;
//判断的初始条件
while(a != b){
//两者的判断条件一定要分开
if(a != null){
a = a.next;
}else{
a = headB;
}
if(b != null){
b = b.next;
}else{
b = headA;
}
}
return a;
}
}
第八天（链表）
剑指 Offer II 024. 反转链表（简单）
题目：剑指 Offer II 024. 反转链表
相似题目：206. 反转链表
class Solution {
public ListNode reverseList(ListNode head) {
// 到达最后一个节点的时候返回head
if(head == null || head.next == null) {
return head;
}else {
ListNode newhead = reverseList(head.next);
head.next.next = head;
// 递归的时候 如果不为null 会变成一个环
head.next = null;
return newhead;
}
}
}
迭代的用法：
此处迭代的用法 不用创建虚拟头结点
class Solution {
public ListNode reverseList(ListNode head) {
// 反转链表 ，prev 与 cur的值
ListNode prev = null;
ListNode cur = head;
while(cur != null){
// next值
ListNode node = cur.next;
cur.next = prev;
// 相互挪位置
prev = cur;
cur = node;
}
return prev;
}
}
剑指 Offer II 025. 链表中的两数相加（中等）
题目：剑指 Offer II 025. 链表中的两数相加
相似题目：445. 两数相加 II
倒序只能用栈，而且用的头插法，不用再reverse节点
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 将两个链表的所有值都存储在栈中
// 而且比较的是进位每个数值，所以直接使用Integer
Deque<Integer> stack1 = new LinkedList<>();
Deque<Integer> stack2 = new LinkedList<>();
while(l1 != null){
stack1.push(l1.val);
l1 = l1.next;
}
while(l2 != null){
stack2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
ListNode ans = null;
// 总体的条件不要忘记进位，最后一位的进位
// !stack1.isEmpty() 堆栈为空的判断形式
while(!stack1.isEmpty() || !stack2.isEmpty() || carry != 0){
int a = stack1.isEmpty() ? 0:stack1.pop();
int b = stack2.isEmpty() ? 0:stack2.pop();
int cur = a + b + carry;
// 方便之后进位
carry = cur / 10;
// 没有进位的位数存储起来，通过ListNode进行创建
cur %= 10;
ListNode node = new ListNode(cur);
// 移动位置 而且这是头插法 需要注意下
node.next = ans;
ans = node;
}
return ans;
}
}
剑指 Offer II 026. 重排链表（中等）
题目：剑指 Offer II 026. 重排链表
相似题目：143. 重排链表
使用list进行重排
class Solution {
public void reorderList(ListNode head) {
List<ListNode>list = new ArrayList<>();
ListNode cur = head;
while(cur != null){
list.add(cur);
cur = cur.next;
}
// 定义全局的变量
int i = 0;
// 注意下标是0到3
int j = list.size()-1;
while(i < j){
list.get(i).next = list.get(j);
i++;
list.get(j).next = list.get(i);
j--;
}
list.get(i).next=null;
}
}
另一种思路就是：
取中间节点（快慢指针），反转后缀，对其两者进行合并
中间有个节点是while(fast.next != null && fast.next.next != null ){
找中间节点，判定条件，如果是找有无环，本身if(fast == null || fast.next == null) return null;即可
class Solution {
public void reorderList(ListNode head) {
if (head == null) {
return;
}
ListNode mid = middlenode(head);
ListNode l1 = head;
// 别忘记这个节点 比如 1234 ，中点是2，则34反转
ListNode l2 = mid.next;
// 并且将其2的next置为空
mid.next = null;
l2 = reverse(l2);
merge(l1, l2);
}
// 快慢指针查找链表的终点
public ListNode middlenode(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null ){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 反转链表
public ListNode reverse(ListNode head){
ListNode prev = null;
ListNode cur = head;
while(cur != null ){
ListNode node = cur.next;
cur.next = prev;
prev = cur;
cur = node;
}
return prev;
}
// 合并链表节点
public void merge(ListNode l1,ListNode l2){
while(l1 != null && l2 != null){
// 记住下一个节点 方便遍历
ListNode cur1 = l1.next;
l1.next = l2;
// 同样记住下一个节点，方便遍历
ListNode cur2 = l2.next;
l2.next = cur1;
// 回到初始状态，方便下一次的迭代
l1 = cur1;
l2 = cur2;
}
}
}
第九天（链表）
剑指 Offer II 027. 回文链表（简单）
题目：剑指 Offer II 027. 回文链表
相似题目：234. 回文链表
回文链表的处理方式有很多种，此处讲解下最优的方式：（这题和上面的重排链表思路一致）
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return false;
}
// 找到中间节点
ListNode mid = middlenode(head);
ListNode l1 = head;
// 别忘记这个节点 比如 1234 ，中点是2，则34反转，3才是开始的节点
ListNode l2 = mid.next;
// 并且将其2的next置为空
mid.next = null;
l2 = reverse(l2);
// 此处进行比较
while(l1 != null && l2 != null){
if(l1.val != l2.val){
return false;
}
l1 = l1.next;
l2 = l2.next;
}
return true;
}
// 快慢指针查找链表的 中点前一个
public ListNode middlenode(ListNode head){
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null ){
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
// 反转链表
public ListNode reverse(ListNode head){
ListNode prev = null;
ListNode cur = head;
while(cur != null ){
ListNode node = cur.next;
cur.next = prev;
prev = cur;
cur = node;
}
return prev;
}
}
第十二天（栈）
剑指 Offer II 036. 后缀表达式（中等）
题目：剑指 Offer II 036. 后缀表达式
和150. 逆波兰表达式求值一模一样
题目：（省略）
class Solution {
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new LinkedList<>();
int n = tokens.length;
for(int i = 0 ;i < n;i++){
if(isNumber(tokens[i])){
// 将其转换为数字，再放到stack中
stack.push(Integer.parseInt(tokens[i]));
}else{
// 此处已经转换为了数字，所以pop就可
int num2 = stack.pop();
int num1 = stack.pop();
switch(tokens[i]){
case "+":
stack.push(num1 + num2);
break;
case "-":
stack.push(num1 - num2);
break;
case "*":
stack.push(num1 * num2);
break;
case "/":
stack.push(num1 / num2);
break;
}
}
}
return stack.pop();
}
public boolean isNumber(String token){
return !("+".equals(token) || ("-".equals(token) || ("*".equals(token) || ("/").equals(token))));
}
}
第十四天（队列）
剑指 Offer II 041. 滑动窗口的平均值（简单）
题目：剑指 Offer II 041. 滑动窗口的平均值
和346.数据流中的移动平均值一模一样
题目：
给定一个整数数据流和一个窗口大小，根据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。
实现 MovingAverage 类：
MovingAverage(int size) 用窗口大小 size 初始化对象。
double next(int val) 成员函数 next 每次调用的时候都会往滑动窗口增加一个整数，请计算并返回数据流中最后 size 个值的移动平均值，即滑动窗口里所有数字的平均值。
示例：
输入：
inputs = [“MovingAverage”, “next”, “next”, “next”, “next”]
inputs = [[3], [1], [10], [3], [5]]
输出：
[null, 1.0, 5.5, 4.66667, 6.0]
解释：
MovingAverage movingAverage = new MovingAverage(3);
movingAverage.next(1); // 返回 1.0 = 1 / 1
movingAverage.next(10); // 返回 5.5 = (1 + 10) / 2
movingAverage.next(3); // 返回 4.66667 = (1 + 10 + 3) / 3
movingAverage.next(5); // 返回 6.0 = (10 + 3 + 5) / 3
提示：
1 <= size <= 1000
-105 <= val <= 105
最多调用 next 方法 104 次
class MovingAverage {
Queue<Integer> queue;
int size;
// 定义为double类型
double sum;
/** Initialize your data structure here. */
public MovingAverage(int size) {
queue = new ArrayDeque<>();
// 定义size大小
this.size = size;
sum = 0;
}
public double next(int val) {
// 如果size提前为size，则将队头出队，并让sum减去
if(queue.size() == size){
sum -= queue.poll();
}
queue.offer(val);
sum += val;
// 此处的分母是队列的尺寸，而不是size
return sum / queue.size();
}
}
剑指 Offer II 042. 最近请求次数（简单）
题目：剑指 Offer II 042. 最近请求次数
此题和933. 最近的请求次数一模一样
题目：
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请实现 RecentCounter 类：
RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例：
输入：
inputs = [“RecentCounter”, “ping”, “ping”, “ping”, “ping”]
inputs = [[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]
解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3
提示：
1 <= t <= 109
保证每次对 ping 调用所使用的 t 值都 严格递增
至多调用 ping 方法 104 次
通过定义一个队列，将其队列头与其t-3000进行判定
class RecentCounter {
Queue<Integer> queue;
public RecentCounter() {
queue = new ArrayDeque<>();
}
public int ping(int t) {
queue.offer(t);
while(queue.peek() < t - 3000){
queue.poll();
}
return queue.size();
}
}
第十五天（队列）
剑指Offer II 044. 二叉树每层的最大值（中等）
题目：剑指 Offer II 044. 二叉树每层的最大值
相似题目：515. 在每个树行中找最大值
class Solution {
public List<Integer> largestValues(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int n = que.size();
// 每一层都初始化Max节点
int Max = Integer.MIN_VALUE;
for(int i = 0;i < n;i++){
TreeNode node = que.poll();
// for遍历筛选最大的max
Max = Math.max(Max,node.val);
if(node.left != null)que.offer(node.left);
if(node.right != null)que.offer(node.right);
}
list.add(Max);
}
return list;
}
}
剑指 Offer II 045. 二叉树最底层最左边的值（中等）
题目：剑指 Offer II 045. 二叉树最底层最左边的值
相似的题目：513. 找树左下角的值
大致的思想通过层次遍历，找最左下角的节点
class Solution {
public int findBottomLeftValue(TreeNode root) {
if(root == null)return 0;
// 定义一个全局变量ret，为了输出返回
int ret = 0;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int n = que.size();
for(int i = 0;i < n;i++){
TreeNode node = que.poll();
// i为0的时候，将其存储，每一层都会将其覆盖
if(i == 0)ret = node.val;
if(node.left != null) que.offer(node.left);
if(node.right != null)que.offer(node.right);
}
}
// 此为最后一层的ret值
return ret;
}
}
剑指 Offer II 046. 二叉树的右侧视图（中等）
题目：剑指 Offer II 046. 二叉树的右侧视图
相似的题目：199. 二叉树的右视图
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null)return list;
Queue<TreeNode> que = new LinkedList<>();
que.offer(root);
while(!que.isEmpty()){
int n = que.size();
for(int i = 0;i < n; i++){
TreeNode node = que.poll();
// 只保存最后一个节点，每一层都是，所以使用list列表添加
if(i == n-1)list.add(node.val);
if(node.left != null)que.offer(node.left);
if(node.right != null)que.offer(node.right);
}
}
return list;
}
}
原文地址：https://blog.csdn.net/weixin_47872288/article/details/125966532
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！