算法训练营——双指针问题

349. 两个数组的交集

这个是保留所有的重复的数组还有一种的只是保留一种的结果的

package 计算机程序算法分类.双指针问题;

import java.util.*;

/**
 * @Classname 两个数组的交集
 * @Description TODO
 * @Date 2021/4/12 21:18
 * @Created by xjl
 */
public class 两个数组的交集 {
    /**
     * @description TODO  采用的是的双指针来实现 这个题目是知识保留一份的结果
     * @param: nums1
     * @param: nums2
     * @date: 2021/4/13 14:05
     * @return: int[]
     * @author: xjl
     */
    public int[] intersect(int[] nums1, int[] nums2) {
        // 先对两个数组进行排序
        Arrays.sort(nums1);//时间复杂度为O(nlog(n))
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        //存放的结果
        HashSet set = new HashSet();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                set.add(nums1[i]);
                i++;
                j++;
            }
        }
        ArrayList list = new ArrayList(set);
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * @description TODO  这个题目是知识保留一份的结果
     * @param: nums1
     * @param: nums2
     * @date: 2021/4/13 14:41
     * @return: int[]
     * @author: xjl
     */
    public int[] intersection(int[] nums1, int[] nums2) {
        ArrayList result = new ArrayList();
        ArrayList list = new ArrayList();
        for (int i : nums1) {
            list.add(i);
        }
        for (int i : nums2) {
            if (list.contains(i)&&!result.contains(i)) {
                result.add(i);
            }
        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    /**
     * @description TODO  采用的是的双指针来实现 保留所有的重复的结果
     * @param: nums1
     * @param: nums2
     * @date: 2021/4/13 14:05
     * @return: int[]
     * @author: xjl
     */
    public int[] intersect_2(int[] nums1, int[] nums2) {
        // 先对两个数组进行排序
        Arrays.sort(nums1);//时间复杂度为O(nlog(n))
        Arrays.sort(nums2);
        int i = 0;
        int j = 0;
        //存放的结果
        List list = new ArrayList();
        while (i < nums1.length && j < nums2.length) {
            if (nums1[i] < nums2[j]) {
                i++;
            } else if (nums1[i] > nums2[j]) {
                j++;
            } else {
                list.add(nums1[i]);
                i++;
                j++;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }
}

424. 替换后的最长重复字符（没有太理解）

• 右边界先移动找到一个满足题意的可以替换 k 个字符以后，所有字符都变成一样的当前看来最长的子串，直到右边界纳入一个字符以后，不能满足的时候停下；
• 然后考虑左边界向右移动，左边界只须要向右移动一格以后，右边界就又可以开始向右移动了，继续尝试找到更长的目标子串；
• 替换后的最长重复子串就产生在右边界、左边界交替向右移动的过程中。

package 计算机程序算法分类.双指针问题;

import leetcode练习题.reverse;
import org.junit.Test;
import 牛客网练习题.Solution;

import java.util.HashMap;

/**
 * @Classname 最长字符串
 * @Description TODO
 * @Date 2021/4/13 14:22
 * @Created by xjl
 */
public class 替换的最长的重复字符 {
    public int characterReplacement(String s, int k) {
        int len = s.length();
        if (len < 2) {
            return len;
        }

        char[] charArray = s.toCharArray();
        int left = 0;
        int right = 0;

        int res = 0;
        int maxCount = 0;
        int[] freq = new int[26];
        // [left, right) 内最多替换 k 个字符可以得到只有一种字符的子串

        while (right < len) {
            freq[charArray[right] - 'A']++;
            // 在这里维护 maxCount，因为每一次右边界读入一个字符，字符频数增加，才会使得 maxCount 增加
            maxCount = Math.max(maxCount, freq[charArray[right] - 'A']);
            right++;

            if (right - left > maxCount + k) {
                // 说明此时 k 不够用
                // 把其它不是最多出现的字符替换以后，都不能填满这个滑动的窗口，这个时候须要考虑左边界向右移动
                // 移出滑动窗口的时候，频数数组须要相应地做减法
                freq[charArray[left] - 'A']--;
                left++;
            }
            res = Math.max(res, right - left);
        }
        return res;
    }
}

剑指 Offer 48. 最长不含重复字符的子字符串

我们使用两个指针，一个i一个j，最开始的时候i和j指向第一个元素，然后i往后移，把扫描过的元素都放到map中，如果i扫描过的元素没有重复的就一直往后移，顺便记录一下最大值max，如果i扫描过的元素有重复的，就改变j的位置，我们就以pwwkew为例画个图看一下

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