主流网站建设,写作网站可以签约未成年吗,介休网站建设,新媒体网络营销的概念目录 前言第一天#xff08;整数#xff09;剑指 Offer II 002. 二进制加法#xff08;简单#xff09; 第二天#xff08;整数#xff09;剑指 Offer II 004. 只出现一次的数字 #xff08;中等#xff09;剑指 Offer II 005. 单词长度的最大乘积#xff08;中等整数剑指 Offer II 002. 二进制加法简单 第二天整数剑指 Offer II 004. 只出现一次的数字 中等剑指 Offer II 005. 单词长度的最大乘积中等剑指 Offer II 006. 排序数组中两个数字之和简单 第三天数组剑指 Offer II 007. 数组中和为 0 的三个数中等剑指 Offer II 008. 和大于等于 target 的最短子数组中等***剑指 Offer II 009. 乘积小于 K 的子数组中等 第四天数组滑动窗口剑指 Offer II 010. 和为 k 的子数组中等剑指 Offer II 012. 左右两边子数组的和相等简单 第五天字符串剑指 Offer II 016. 不含重复字符的最长子字符串中等 第六天字符串剑指 Offer II 018. 有效的回文简单剑指 Offer II 019. 最多删除一个字符得到回文简单剑指 Offer II 020. 回文子字符串的个数中等* 第七天链表剑指 Offer II 021. 删除链表的倒数第 n 个结点中等剑指 Offer II 022. 链表中环的入口节点中等剑指 Offer II 023. 两个链表的第一个重合节点简单 第八天链表剑指 Offer II 024. 反转链表简单剑指 Offer II 025. 链表中的两数相加中等剑指 Offer II 026. 重排链表中等 第九天链表剑指 Offer II 027. 回文链表简单 第十二天栈剑指 Offer II 036. 后缀表达式中等 第十四天队列剑指 Offer II 041. 滑动窗口的平均值简单剑指 Offer II 042. 最近请求次数简单 第十五天队列剑指Offer II 044. 二叉树每层的最大值中等剑指 Offer II 045. 二叉树最底层最左边的值中等剑指 Offer II 046. 二叉树的右侧视图中等 前言
以下文章主要是方便自我学习总结 感兴趣的也可一键三连互相学习
大部分算法题都是刷过很多次知识点也比较重复特殊情况下会重点讲解下代码思路
对应另一套算法题
字节校园精选 66 道高频经典笔面试题含多种思路上字节校园精选 66 道高频经典笔面试题含多种思路下
第一天整数
剑指 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. 只出现一次的数字 中等
题目剑指 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. 单词长度的最大乘积中等
题目剑指 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,-1return 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 ListListInteger threeSum(int[] nums) {Arrays.sort(nums);int n nums.length;ListListInteger list new ArrayListListInteger();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){ListInteger 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, numsl1, …, 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 ,整体答案为【105】【5】共有2个第三个窗口为10,5,2,因为不满足所以把10排出去窗口为52.整体答案为【52】【2】共有2个第四个窗口为5 2 6整体答案为【526】【26】【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 rightwhile(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;MapInteger,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);}// 为下一个临界值 增加一个1map.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则返回ifor(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) {// 哈希集合记录每个字符是否出现过SetCharacter set new HashSetCharacter();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. 有效的回文简单
题目剑指 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. 回文子字符串的个数中等*
题目剑指 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的时候返回为nullif(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) {// 到达最后一个节点的时候返回headif(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) {// 将两个链表的所有值都存储在栈中// 而且比较的是进位每个数值所以直接使用IntegerDequeInteger stack1 new LinkedList();DequeInteger 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) {ListListNodelist new ArrayList();ListNode cur head;while(cur ! null){list.add(cur);cur cur.next;}// 定义全局的变量int i 0;// 注意下标是0到3int 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).nextnull;}
}另一种思路就是 取中间节点快慢指针反转后缀对其两者进行合并 中间有个节点是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) {DequeInteger 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 {QueueInteger 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;// 此处的分母是队列的尺寸而不是sizereturn 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 {QueueInteger 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 ListInteger largestValues(TreeNode root) {ListInteger list new ArrayList();if(root null) return list;QueueTreeNode 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遍历筛选最大的maxMax 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;QueueTreeNode 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 ListInteger rightSideView(TreeNode root) {ListInteger list new ArrayList();if(root null)return list;QueueTreeNode 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;}
}
