队列

发布： 分类： 评论： 阅读：

队列

1
2
3
4
Queue<Integer> que = new LinkedList();
que.offer(1);  // 添加元素
int v1 = que.poll();   // 返回第一个元素，并在队列中删除，如果队列为空，返回null
int v2 = que.peek();   // 返回第一个元素

双端队列

1
2
3
4
5
6
7
8
9
Deque<Integer> mDeque = new ArrayDeque<Integer>();
que.offerFirst(1);  // 在队头添加元素
que.offerLast(1);   // 在队尾添加元素

int v1 = que.pollFirst();  // 返回队头元素并删除
int v2 = que.pollLast();   // 返回队尾元素并删除

int v1 = que.peekFirst();  // 返回队头元素
int v2 = que.peekLast();   // 返回队头元素

例题

leetcode 239. 求滑动窗口中的最大值 Sliding Window Maximum

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3, k为窗口大小
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7
  • 滑动窗口就相当于一个队列，因为每滑动一次，就相当于从队列头移出一个元素，从队列尾移入一个元素。
  • 那么该问题就转换成了求队列中的最大值的问题。
  • 如果每次滑动窗口，都遍历求窗口中的最大值，那么时间复杂度是 O(nk)， 比较耗时。
  • 分析：因为是滑动窗口，所以相当于中间的部分不变，只有两端元素发生了变化。如果移出的不是当前最大值，移入的元素也不是比当前最大值更大的值，那么当前的最大值是没有变化的。但是如果当前最大值被移出了，那么怎么确定现在这个窗口里的最大值呢，不可能重新遍历一次。所以我们需要定义一个队列来维护当前队列中的最大值。
  • 就像之前一个求栈中的最大值时，我们维护了一个栈，用来存储当前的最大值。
  • 如上面的例子所示：
    1. 建立一个队列
    2. 1：将1入队 que = [1]
    3. 3：发现3>1，也就是1不可能在接下来成为最大元素，那么我们将1出队，3入队。que = [3]
    4. -1：虽然-1<3，但当3在滑动窗口中移出时，-1还是有可能成为最大元素的，所以-1入队。que = [3, -1]
    5. -3: 同上，-3入队。que = [3, -1, -3]
    6. 5：5过来时，队列前面的元素都小于5，也就是遇到5之后，前面的小值都不可能再作为最大值，那么把前面的元素全部出队列，将5入队。que = [5]
    7. 3: que = [5, 3]
    8. 剩下的元素都同理。我们发现队头的元素一直都是滑动窗口的最大值。
  • 问题：如果 1 3 [-1 -3 -2] 3 6 7, 那么就相当于上面的第6步发生了变化。-2 过来时，我们需要把3移出队列。因为此时滑动窗口已经不包含3这个元素了。那么怎么知道滑动窗口是否包含一个元素？如果说被移出的元素和当前对头元素值相等，那么不一定，如果存在重复元素，这样是不是会出错？所以，我们可以让双端队列中存储元素的index，而不是值，这样如果当前被移出的元素的index和对头index相等，那么就需要移出当前对头元素。
  • 同时，遇到-2，我们需要删除-3，因为-3不可能是滑动窗口的最大值了，但是-3是队尾元素，如何删除队尾元素，那么就要用到双端队列！
  • 好复杂的一道题！！！！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int[] maxSlidingWindow(int[] nums, int k) {
  	if(nums.length==0)  return new int[0];

    int[] result = new int[nums.length-k+1];
    Deque<Integer> que = new ArrayDeque<>();

    for(int index=0;index<nums.length;index++) {
      if(que.size()==0)
        que.offerFirst(index);
      else if(nums[index]>nums[que.peekFirst()]) {
        que.clear();
        que.offerFirst(index);
      }
      else if(nums[index]<nums[que.peekLast()])
        que.offerLast(index);
      else {
        while (nums[que.peekLast()] < nums[index])
          que.pollLast();
        que.offerLast(index);
      }
      if(index-k+1>=0) {
        result[index-k+1] = nums[que.peekFirst()];
        // 因为下一次移动的时候，对头元素就会被移出去，所以将其在对头删除
        if(index-k+1==que.peekFirst()) que.pollFirst();
      }
    }
    return result;
}

leetcode 3. 最长无重复字符的子串

  • dp[i][j] : i到j无重复字符，那么求的就是 j-i 的最大值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int lengthOfLongestSubstring(String s) {
  if(s.isEmpty())
    return 0;
  int begin = 0;
  int end = 0;
  boolean[][] dp = new boolean[s.length()][s.length()];
  for(int i=0;i<s.length();i++) {
    dp[i][i] = true;
    int index = -1;
    for(int j=i+1;j<s.length();j++) {
      String tmp = s.substring(i, j);
      dp[i][j] = !tmp.contains(s.charAt(j) + "") && dp[i][j - 1];
      index = j;
      if(!dp[i][j])  {
        index = j-1;
        break;
      }
    }
    if((index-i)>=(end-begin)) {
      end = index;
      begin = i;
    }
  }
  return end-begin+1;
}
  • 这样写是对的，但是会超时。。。当字符串特别长的时候。
  • 问题在于tmp.contains(), 这一步是一个o(n)的时间复杂度，每次都要查找，肯定很耗时。
  • 那么我们可以把它放在一个set里面，如果插入当前元素前后，set的大小没变，那就说明重复了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int lengthOfLongestSubstring(String s) {
  if(s.length()==0) return 0;
  int result = -1;
  Set<Character> set = new HashSet();
  for(int j = 0;j<s.length();j++)
  {
    for(int i=j;i<s.length();i++)
    {
      int num = set.size();
      set.add(s.charAt(i));
      if(set.size()==num)
        break;
    }
    result = set.size()>result?set.size():result;
    set.clear();
  }
  return result;
}

leetcode 264. 查找第n个丑数 Ugly Number II

1
2
3
4
5
6
Write a program to find the n-th ugly number.
Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. 
Example:
trueInput: n = 10
trueOutput: 12
trueExplanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
  • dp[i]: 第i个数字是不是丑数。
  • dp[i] = (i%2==0 && dp[i%2])||(i%3==0 && dp[i%3])||(i%3==0 && dp[i%3])
  • 还是会超时 。。。。。。。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int nthUglyNumber(int n) {
  if(n<6) return n;
  ArrayList<Boolean> list = new ArrayList();
  list.add(false); // 0 位置不用
  for(int i=0;i<5;i++)
    list.add(true);   // 1到5都是丑数
  int num = 5;
  int i=6;
  while(num<n) {
    boolean flag = (i%2==0 && list.get(i/2))||(i%3==0 && list.get(i/3))||(i%5==0 && list.get(i/5));
    list.add(flag);
    if(flag) num += 1;
    i += 1;
  }
  return i-1;
}

We have an array k of first n ugly number. We only know, at the beginning, the first one, which is 1. Then

k[1] = min( k[0]x2, k[0]x3, k[0]x5). The answer is k[0]x2. So we move 2’s pointer to 1. Then we test:

k[2] = min( k[1]x2, k[0]x3, k[0]x5). And so on. Be careful about the cases such as 6, in which we need to forward both pointers of 2 and 3.

x here is multiplication.

  • 这种方法相当于直接去生成丑数，那么生成到n就行了
  • 而不是逐个去判断是不是丑数，那样可能第1500个丑数，需要判断3000个数字。就会增加很多无用的判断，而且占用的空间也更多。
1
2
3
4
5
6
7
8
9
10
11
12
13
public int nthUglyNumber(int n) {
  int[] nums = new int[n + 1];
  nums[1] = 1;
  int i2 = 0, i3 = 0, i5 = 0;
  int u2 = nums[1], u3 = nums[1], u5 = nums[1];
  for (int i = 1; i <= n; i++) {
    nums[i] = Math.min(u2, Math.min(u3, u5));
    if (nums[i] == u2) u2 = nums[++i2] * 2;
    if (nums[i] == u3) u3 = nums[++i3] * 3;
    if (nums[i] == u5) u5 = nums[++i5] * 5;
  }
  return nums[n];
}

leetcode 387. First Unique Character in a String