剑指offer
剑指 Offer II 018. 有效的回文【简单】
题目链接： 剑指 Offer II 018. 有效的回文
题目内容：给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
思路：双指针判断法
复杂度分析：
时间复杂度：O(n) 空间复杂度：O(1) class Solution { public boolean isPalindrome(String s) { int i = 0, j = s.length() - 1; while (i < j) { while (i < s.length() && !isSatisfy(s.charAt(i))) { i++; } while (j >= 0 && !isSatisfy(s.charAt(j))) { j--; } if (i >= j) { break; } if (transfer(s.charAt(i++)) != transfer(s.charAt(j--))) { return false; } } return true; } public boolean isSatisfy(char ch) { if ((ch >= '0' && ch <= '9') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) { return true; } return false; } public char transfer(char ch) { if (ch >= 'A' && ch <= 'Z') { return (char)(ch + 32); } return ch; } }
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面【简单】
题目链接：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
题目内容：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
思路：
1、双指针，从左右两端开始。
复杂度分析：
时间复杂度：O(n) 空间复杂度：O(1) class Solution { //1234 //12345 public int[] exchange(int[] nums) { int n = nums.length; int left = 0, right = nums.length - 1; while (left < right) { while (left < right && nums[left] % 2 == 1) { left++; } while (left < right && nums[right] % 2 == 0) { right--; } //若是成立那么就兑换 if (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } } return nums; } }
剑指 Offer 57 - II. 和为s的连续正数序列【简单】
题目链接：剑指 Offer 57 - II. 和为s的连续正数序列
题目内容：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
思路：
1、滑动窗口
复杂度分析：
时间复杂度：O(n)，最大为2n。 空间复杂度：O(1) class Solution { //滑动窗口 public int[][] findContinuousSequence(int target) { List<int[]> list = new ArrayList<>(); //指定一个区间 for (int l = 1, r = 1, sum = 0; r < target; r++) { sum += r; //若是>当前的窗口，及时进行缩减窗口 while (l < r && sum > target) { sum -= l++; } //若是当前窗口符合 if (sum == target && r - l > 0) { int [] res = new int[r - l + 1]; for (int i = l; i <= r; i++) { res[i - l] = i; } list.add(res); } } //将list转换为int数组 int[][] res = new int[list.size()][]; for (int i = 0; i < list.size(); i++) { res[i] = list.get(i); } return res; } }
剑指 Offer 48. 最长不含重复字符的子字符串【中等】
题目链接：剑指 Offer 48. 最长不含重复字符的子字符串
题目内容：请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
思路：
1、滑动窗口+哈希表
复杂度分析：时间复杂度O(n)，空间复杂度O(n)
class Solution { public int lengthOfLongestSubstring(String s) { //哈希+滑动窗口 Set<Character> set = new HashSet<>(); char[] arr = s.toCharArray(); int max = 0; for (int l = 0, r = 0; r < arr.length; r++) { //缩减窗口 while (l < r && !set.isEmpty() && set.contains(arr[r])) { set.remove(arr[l]);//先进行移除再左指针移动 l++; } set.add(arr[r]); max = Math.max(max, r - l + 1); } return max; } }
优化一下，对于set集合我们可以使用int数组来替代【最优】：
class Solution { public int lengthOfLongestSubstring(String s) { //哈希+滑动窗口 int[] buckets = new int[128]; char[] arr = s.toCharArray(); int max = 0; for (int l = 0, r = 0; r < arr.length; r++) { //缩减窗口 while (l < r && buckets[arr[r]] > 0) { buckets[arr[l]]--; l++; } buckets[arr[r]]++; max = Math.max(max, r - l + 1); } return max; } }
牛客网
合并两个有序的数组【简单】
题目链接：合并两个有序的数组
题目内容：给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组。
思路1：合并数组。从大到小，针对A数组来从后往前填。
复杂度分析：
时间复杂度：O(n) 空间复杂度：O(1) import java.util.*; public class Solution { public void merge(int A[], int m, int B[], int n) { int i = m - 1; int j = n - 1; int k = m + n - 1; while (i >= 0 && j >= 0) { if (A[i] > B[j]) { A[k--] = A[i--]; }else { A[k--] = B[j--]; } } //若是B还有剩余继续往前添加，若是B没有，那就直接结束了 while (j >= 0) { A[k--] = B[j--]; } } }
反转字符串【简单】
题目链接：反转字符串
题目内容：写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）。
思路：双指针来进行交换替换字符。
复杂度分析：
时间复杂度：O(n)。 空间复杂度：O(1)。 import java.util.*; public class Solution { /** * 反转字符串 * @param str string字符串 * @return string字符串 */ public String solve (String str) { int i = 0, j = str.length() - 1; char[] chars = str.toCharArray(); while (i < j) { char temp = chars[i]; chars[i] = chars[j]; chars[j] = temp; i++; j--; } return new String(chars); } }
判断是否为回文字符串【中等】
题目链接：合并两个有序的数组
题目内容：给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。
思路1：使用双指针，一个从前开始，一个从后开始来进行遍历比较。
复杂度分析：
时间复杂度：O(n) 空间复杂度：O(1) import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * @param str string字符串 待判断的字符串 * @return bool布尔型 */ public boolean judge (String str) { int i = 0, j = str.length() - 1; while (i <= j) { if (str.charAt(i) != str.charAt(j)) { return false; } i++; j--; } return true; } }
最长无重复子数组【中等】
题目链接：最长无重复子数组
题目内容：给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。子数组是连续的，
比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组。
思路：滑动窗口。
复杂度分析：
时间复杂度：O(n) 空间复杂度：O(n) import java.util.*; public class Solution { /** * * @param arr int整型一维数组 the array * @return int整型 */ public int maxLength (int[] arr) { //滑动窗口 Map<Integer, Integer> map = new HashMap<>(); int res = 0; for (int left = 0, right = 0; right < arr.length; right++) { //这个if操作就是往map里面添加值的 if (map.containsKey(arr[right])) { map.put(arr[right], map.get(arr[right]) + 1); }else { map.put(arr[right], 1); } //移动left指针 while (map.get(arr[right]) > 1) { map.put(arr[left], map.get(arr[left++]) - 1); } //计算长度最大值 res = Math.max(res, right - left + 1); } return res; } }
盛水最多的容器【中等】
题目链接：盛水最多的容器
题目内容：给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水。
思路：定义左右指针，然后不断的缩短容量，移动位置。
复杂度分析：
时间复杂度：O(n) 空间复杂度：O(1) import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param height int整型一维数组 * @return int整型 */ public int maxArea (int[] height) { int res = 0; int left = 0, right = height.length - 1; while (left < right) { //贪心策略 res = Math.max(res, Math.min(height[left], height[right]) * (right - left)); //如果左边的高度<右边的高度，那么左边位置向右移动 if (height[left] < height[right]) { left++; }else{ right--; } } return res; } }
接雨水问题【中等】
题目链接：接雨水问题
题目内容：给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)。
思路1：双指针方案。定义左右各个最大高度，然后来进行比较平移，若是右边更高，那么就开始平移左边的并且进行计算。
复杂度分析：
时间复杂度：O(n) 空间复杂度：O(1) import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater (int[] arr) { int i = 0, j = arr.length - 1; int maxL = 0; int maxR = 0; long res = 0; while (i < j) { //取出当前左右边最大的边界 maxL = Math.max(maxL, arr[i]); maxR = Math.max(maxR, arr[j]); //若是右边>左边，移动左边位置 if (maxR > maxL) { res += maxL - arr[i++]; }else { res += maxR - arr[j--]; } } return res; } }
合并区间【中等】
题目链接：合并区间
题目内容：给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。
思路：排序比较。①根据start来进行排序。②不断的进行判断star<=新添加集合中元素的end，就可以直接添加进去。
复杂度分析：
时间复杂度：O(nlogn) 空间复杂度：O(n) import java.util.*; /** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution { public ArrayList<Interval> merge(ArrayList<Interval> intervals) { if (intervals == null || intervals.size() == 0 || intervals.size() == 1) { return intervals; } //1、先对集合中的所有元素根据start来进行排序 Collections.sort(intervals, (o1, o2)->o1.start - o2.start); //2、不断的拿intervals中的start来与list最后一个end来比较 ArrayList<Interval> list = new ArrayList<>(); list.add(intervals.get(0)); for (int i = 1; i < intervals.size(); i++) { if (intervals.get(i).start <= list.get(list.size() - 1).end) { //list.get(list.size() - 1).end = intervals.get(i).end; //优化：针对[[1,4],[2,3]]，所以需要进行比较 list.get(list.size() - 1).end = Math.max(intervals.get(i).end, list.get(list.size() - 1).end); }else { list.add(intervals.get(i)); } } return list; } }
最小覆盖子串【中等】
题目链接：最小覆盖子串
题目内容：给出两个字符串 s 和 t，要求在 s 中找出最短的包含 t 中所有字符的连续子串。
思路1：滑动窗口，先不断的进行窗口扩大，满足条件之后进行缩减，然后不断的使用两个指针进行移动比较。
复杂度分析：
时间复杂度：O(n*m) 空间复杂度：O(1) import java.util.*; public class Solution { /** * * @param S string字符串 * @param T string字符串 * @return string字符串 */ //滑动窗口 public String minWindow (String S, String T) { //使用一个hash表，index下标表示对应的字符，value表示出现的次数，初始为0，若是有两个就是-2 int[] hash = new int[128]; for (int i = 0; i < T.length(); i++) { //可能会有重复的字符 hash[T.charAt(i)]--; } //快慢指针来进行移动的 int slow = 0, fast = 0; //左右指针用来记录最小子串的左右位置 int left = -1, right = -1; //记录最小长度 int min = S.length() + 1; for (;fast < S.length(); fast++) { //对字符所在位置下标+1 hash[S.charAt(fast)]++; //如果当前已经覆盖所有的字符，那么进行缩减当前的窗口 while (check(hash, T)) { if (min > (fast - slow + 1)) { min = fast - slow + 1; left = slow; right = fast; } //窗口进行缩减 hash[S.charAt(slow)]--; slow++; } } //没有找到情况 if (left == -1 && right == -1) { return ""; } //返回指定的字符串 return S.substring(left, right + 1); } //check检查当前hash是否已经存在 public boolean check(int[] hash, String T) { for (int i = 0; i < T.length(); i++) { if (hash[T.charAt(i)] < 0){ return false; } } return true; } }
上面代码在leetcode中超时，对其进行优化：主要是针对check()函数遍历做优化，更改为一个all的int型进行表示是否已经全部包含
class Solution { public String minWindow(String s, String t) { //hash表：128个字符（ascii码）。【>=0的表示符合t中的元素，<0的即为不符合元素】 int[] hash = new int[128]; for (int i = 0; i < t.length(); i++) { hash[t.charAt(i)]++; } //保存一个最小窗口值 int min = s.length() + 1; //左右指针，用于最后进行返回 int left = -1, right = -1; //当前符合条件的数量 int all = t.length(); //滑动窗口 for (int slow = 0, fast = 0; fast < s.length(); fast++) { hash[s.charAt(fast)]--; //说明上面对某个字符操作，该字符是属于t中的 if (hash[s.charAt(fast)] >= 0) { all--; } //若是all=0表示，已经找到了所在的范围 if (all == 0) { while (hash[s.charAt(slow)] < 0) { hash[s.charAt(slow++)]++; } //当前范围包含t的所有元素 if (min > (fast - slow + 1)) { min = fast - slow + 1; left = slow; right = fast; } //此时最左边的一定是在t中包含的，此时value值+1，以及all也进行+1 hash[s.charAt(slow++)]++; all++; } } //没有符合条件的情况 if (min == s.length() + 1) { return ""; } //【left,right】 return s.substring(left, right + 1); } }
leetcode
合并区间【中等】(等同于牛客7)
题目链接：合并区间
题目内容：给出一组区间，请合并所有重叠的区间。请保证合并后的区间按区间起点升序排列。
思路：排序比较。①根据start来进行排序。②不断的进行判断star<=新添加集合中元素的end，就可以直接添加进去。
复杂度分析：
时间复杂度：O(nlogn) 空间复杂度：O(n) class Solution { public int[][] merge(int[][] intervals) { if (intervals == null || intervals.length == 0 || intervals.length == 1) { return intervals; } //1、进行排序 Arrays.sort(intervals, (a, b)->a[0] - b[0]); //2、来进行排序 List<int[]> res = new ArrayList<>(); res.add(intervals[0]); for (int i = 1; i < intervals.length; i++) { if (intervals[i][0] <= res.get(res.size() - 1)[1]) { res.get(res.size() - 1)[1] = Math.max(intervals[i][1], res.get(res.size() - 1)[1]); }else { res.add(intervals[i]); } } return res.toArray(new int[0][]); } }
11. 盛最多水的容器【中等】
学习：leetcode题解
题目链接：11. 盛最多水的容器
题目内容：
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
思路：
1、暴力
思路：通过暴力列举出所有面积的可能性再一一比对最终求得最大面积。
复杂度分析：时间复杂度O(n2)、空间复杂度O(1)
特征：实际是两个指针同时从左边出发来进行不对列举比较，每次按照指定的顺序同步移动导致每次需要计算面积，就会有额外许多不必要的计算。
/** * 解法1：暴力解法 * @param height * @return */ public int maxArea(int[] height) { int maxArea = 0; for (int i = 0; i < height.length; i++) { for (int j = i + 1; j < height.length; j++) { //最大面积 vs 当前面积（高度最矮 * 两边距离） maxArea = Math.max(maxArea, Math.min(height[i],height[j]) * (j - i)); } } return maxArea; }
2、左右指针
特征：左右两边 模式识别：需要移动左右两头的问题可以考虑双指针 难点：如何移动指针？①相同情况下两边距离越远越好。②区域受限于短边。
思路：通过不断的移动左右指针位置来减少不必要的面积计算比较，移动的依据是根据当前指针指向的两个高度比较，较矮的一方进行移动，最终来减少不必要的比较！
复杂度分析：时间复杂度O(n)、空间复杂度O(1)
/** * 解法2：左右指针根据两个高度大小来移动 * @param height * @return */ public int maxArea(int[] height) { int max = 0, l = 0, r = height.length - 1; while (l < r){ max = max = Math.max(max, Math.min(height[l],height[r]) * (r - l)); if (height[l] < height[r]){ l++; }else { r--; } } return max; }
文章知识点与官方知识档案匹配，可进一步学习相关知识
