面试题随笔-21/4/6

滑动窗口最大值

// 滑动窗口的最大值 (暴力破解）
public int[] maxSlidingWindow(int[] nums, int k) {
  int len = nums.length;
  if (len * k == 0) {
    return new int[0];
  }

  int[] win = new int[len - k + 1];

  // 遍历所有的滑动窗口
  for (int i = 0; i < len - k + 1; i++) {
    int max = Integer.MAX_VALUE;
    // 找到每一个滑动窗口的最大值
    for (int j = i; j < i + k; j++) {
      max = Math.max(max, nums[j]);
    }
    win[i] = max;
  }
  return win;
}

// 双向队列法
public int[] maxSlidingWindow2(int[] nums, int k) {
  if (nums.length == 0 || k == 0) {
    return new int[0];
  }

  Deque<Integer> deque = new LinkedList<>();
  int[] res = new int[nums.length - k + 1];
  for (int j = 0, i = 1 - k; j < nums.length; i++, j++) {
    // 删除 deque 中对应的 nums[i-1]
    if (i > 0 && deque.peekFirst() == nums[i - 1]) {
      deque.removeFirst();
    }

    // 保持 deque 递减
    while (!deque.isEmpty() && deque.peekLast() < nums[j]) {
      deque.removeLast();
    }
    deque.addLast(nums[j]);
    // 记录窗口最大值
    if (i >= 0) {
      res[i] = deque.peekFirst();
    }
  }
  return res;
}

无重复字符的最长子串

public static int lengthOfLongestSubstring(String s) {
  int n = s.length();
  Set<Character> set = new HashSet<>();

  int result = 0, i = 0, j = 0;
  while (i < n && j < n) {
    // charAt: 返回指定位置处的字符
    if (!set.contains(s.charAt(j))) {
      set.add(s.charAt(j));
      j++;
      result = Math.max(result, j - i);
    } else {
      set.remove(s.charAt(i));
      i++;
    }
  }
  return result;
}

字母异位词

public List<Integer> findAnagrams(String s, String p) {
  if (s == null || p == null || s.length() < p.length()) {
    return new ArrayList<>();
  }

  List<Integer> list = new ArrayList<>();

  int[] pArr = new int[26];
  int[] sArr = new int[26];

  for (int i = 0; i < p.length(); i++) {
    sArr[s.charAt(i) - 'a']++;
    pArr[p.charAt(i) - 'a']++;
  }

  int i = 0;
  int j = p.length();

  // 窗口大小固定为p的长度
  while (j < s.length()) {
    if (isSame(pArr, sArr))
      list.add(i);
    sArr[s.charAt(i) - 'a']--;
    i++;

    sArr[s.charAt(j) - 'a']++;
    j++;
  }

  if (isSame(pArr, sArr)) {
    list.add(i);
  }

  return list;
}

private boolean isSame(int[] arr1, int[] arr2) {

  for (int i = 0; i < arr1.length; ++i) {
    if (arr1[i] != arr2[i]) {
      return false;
    }
  }

  return true;
}

和为s的连续正数序列

// 和为s的连续正数序列
public int[][] findContinuousSequence(int target) {
  ArrayList<int[]> res = new ArrayList<>();

  int i = 1;
  int j = 1;
  int win = 0;
  while (i <= target / 2) {
    if (win < target) {
      win += j;
      j++;
    } else if (win > target) {
      win -= i;
      i++;
    } else {
      int[] arr = new int[j - i];
      for (int k = i; k < j; k++) {
        arr[k - i] = k;
      }
      res.add(arr);
      win -= i;
      i++;
    }
  }
  return res.toArray(new int[res.size()][]);
}