LeetCode
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
思路：
right指针不断右移，对应的字符个数加1。如果一个字符的个数为两个，则说明出现了重复字符，需要将left指针不断右移，直到和right指针位置重合。
执行用时：3 ms, 在所有 Java 提交中击败了97.09%的用户。
class Solution {public int lengthOfLongestSubstring(String s) {int len = s.length();if (len < 2) return len;char[] arr = s.toCharArray();int[] hashmap = new int[128];int res = 1;for(int left = 0, right = 0; right < len; right++) {hashmap[arr[right]]++;if (hashmap[arr[right]] == 2) {while (hashmap[arr[right]] == 2) {hashmap[arr[left]]--;left++;}}res = Math.max(res, right - left + 1);}return res;}}
438. 找到字符串中所有字母异位词
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
思路：
s中的字符存在于p中，通过hash中对应字母的值是否大于零来判断。如果存在则将hash中该字符的个数减1，right右边界加1，count计数加1。
确定了第一段符合的字符串后，left右移，恢复hash中字符的值和count的值。从第一段符合的字符串后开始重新走循环。当走到不存在p中的字符时，走else，给字符在hash中的个数加1，count减1。然后在走if时会将该字符在hash中的个数减1，count加1。不存在的字符不会影响hash中字符个数和count的计算。
执行用时：4 ms, 在所有 Java 提交中击败了99.97%的用户。
class Solution {
public List<Integer> findAnagrams(String s, String p) {
int slen = s.length(), plen = p.length();
List<Integer> list = new ArrayList<>();
char[] sarr = s.toCharArray();
char[] parr = p.toCharArray();
int[] hashmap = new int[128];
for (int i = 0; i < parr.length; i++) {
hashmap[parr[i]]++;
}
int left = 0, right = 0, count = 0;
while (right < slen) {
if (hashmap[sarr[right]] > 0) {
hashmap[sarr[right]]--;
count++;
right++;
} else {
hashmap[sarr[left]]++;
count--;
left++;
}
if (count == plen) {
list.add(left);
}
}
return list;
}
}
76. 最小覆盖子串
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。
思路：
i作为右指针，left作为左指针。遍历字符串s，对于每一个字符，将hash中该字符的个数减1，减1后如果≥0，则count加1。
当count和字符串t的长度相等时，开始循环，记录最小覆盖子串的长度。将left指向的字符对应hash中的值加1，加1后如果＞0，则说明该字符存在于字符串t中，此时当前子串和t不匹配，需要将count减1，跳出循环。
执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户。
class Solution {
public String minWindow(String s, String t) {
int sLen = s.length(), tLen = t.length();
int[] hashmap = new int[128];
char[] sarr = s.toCharArray();
char[] tarr = t.toCharArray();
for (int i = 0; i < tLen; i++) {
hashmap[tarr[i]]++;
}
int min = sLen + 1, count = 0, left = 0, minLeft = 0;
for (int i = 0; i < sLen; i++) {
if (--hashmap[sarr[i]] >= 0) {
count++;
}
while (count == tLen) {
if (min > i - left + 1) {
min = i - left + 1;
minLeft = left;
}
if (++hashmap[sarr[left]] > 0) {
count--;
}
left++;
}
}
if (min < sLen + 1) {
return s.substring(minLeft, minLeft + min);
} else {
return "";
}
}
}
209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
思路：
当累加和sum满足≥s时，记录窗口长度，并开始移动左窗口，直到不满足条件。
执行用时：1 ms, 在所有 Java 提交中击败了99.87%的用户。
class Solution {
public int minSubArrayLen(int s, int[] nums) {
int len = nums.length;
int res = len + 1, sum = 0, left = 0;
for (int i = 0; i < len; i++) {
sum += nums[i];
while (sum >= s) {
if (res > i - left + 1) {
res = i - left + 1;
}
sum -= nums[left];
left++;
}
}
if (res < len + 1) {
return res;
} else {
return 0;
}
}
}
练习：
567. 字符串的排列
class Solution {
public boolean checkInclusion(String s1, String s2) {
char[] arr1 = s1.toCharArray();
char[] arr2 = s2.toCharArray();
int[] hashmap = new int[128];
int len = arr1.length;
for (int i = 0; i < len; i++) {
hashmap[arr1[i]]++;
}
boolean flag = false;
int left = 0, right = 0, count = 0;
while (right < arr2.length) {
if (hashmap[arr2[right]] > 0) {
hashmap[arr2[right]]--;
count++;
right++;
} else {
hashmap[arr2[left]]++;
count--;
left++;
}
if (count == len) {
return true;
}
}
return false;
}
}
剑指 Offer
剑指 Offer 48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
思路：
双指针。重点：while (hashmap[arr[right]] == 2)
执行用时：2 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：40.1 MB, 在所有 Java 提交中击败了100.00%的用户
class Solution {
public int lengthOfLongestSubstring(String s) {
int len = s.length();
if (len < 2) return len;
char[] arr = s.toCharArray();
int[] hashmap = new int[128];
int res = 1;
for(int left = 0, right = 0; right < len; right++) {
hashmap[arr[right]]++;
if (hashmap[arr[right]] == 2) {
while (hashmap[arr[right]] == 2) {
hashmap[arr[left]]--;
left++;
}
}
res = Math.max(res, right - left + 1);
}
return res;
}
}
剑指 Offer 59 - I. 滑动窗口的最大值
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
思路：
单调队列。维持一个单调递减的队列。如果队列中索引的差值大于等于窗口的大小，则弹出队首。如果当前元素比度尾元素要大，则一直弹出队尾元素，知道当前元素小于队尾元素或队列为空。然后将当前元素添加到队尾。如果当前索引达到了窗口的大小，则存储窗口最大值。
执行用时：15 ms, 在所有 Java 提交中击败了53.09%的用户
内存消耗：48 MB, 在所有 Java 提交中击败了100.00%的用户
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) {
return new int[]{};
}
int[] res = new int[nums.length - k + 1];
Deque<Integer> queue = new ArrayDeque<>();
for (int i = 0, j = 0; i < nums.length; i++) {
if (!queue.isEmpty() && i - queue.peek() >= k) {
queue.poll();
}
while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
queue.pollLast();
}
queue.offer(i);
if (i >= k - 1) {
res[j++] = nums[queue.peek()];
}
}
return res;
}
}
剑指 Offer 59 - II. 队列的最大值
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
思路：
本质上是一个求滑动窗口最大值的问题，套单调队列模板。这个队列可以看成是一个滑动窗口，入队就是将窗口的右边界右移，出队就是将窗口的左边界右移。
class MaxQueue {
private Deque<Integer> queue;
private Deque<Integer> help;
public MaxQueue() {
queue = new ArrayDeque<>();
help = new ArrayDeque<>();
}
public int max_value() {
return queue.isEmpty() ? -1 : help.peek();
}
public void push_back(int value) {
queue.offer(value);
while(!help.isEmpty() && value > help.peekLast()) {
help.pollLast();
}
help.offer(value);
}
public int pop_front() {
if(queue.isEmpty()) {
return -1;
}
int val = queue.pop();
if(help.peek() == val) {
help.pop();
}
return val;
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue obj = new MaxQueue();
* int param_1 = obj.max_value();
* obj.push_back(value);
* int param_3 = obj.pop_front();
*/
若有收获，就点个赞吧
0 人点赞
