282. Find the Duplicate Number 寻找重复数

[GH1995]

282. Expression Add Operators

Difficulty: Hard

Given a string that contains only digits 0-9 and a target value, return all possibilities to add binary operators (not unary) +, -, or * between the digits so they evaluate to the target value.

Example 1:

Input: num = "123", target = 6
Output: ["1+2+3", "1*2*3"] 

Example 2:

Input: num = "232", target = 8
Output: ["2*3+2", "2+3*2"]```

**Example 3:**

Input: num = "105", target = 5 Output: ["1*0+5","10-5"]```

Example 4:

Input: num = "00", target = 0
Output: ["0+0", "0-0", "0*0"]

Example 5:

Input: num = "3456237490", target = 9191
Output: []

Solution

Language: C++

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k) {
      vector<int> res;
​
      deque<int> q;
      for (int i = 0; i < nums.size(); ++i) {
​
        // 窗口向右移了一步，则移除队首元素
        if (!q.empty() && q.front() == i - k) // 长老自然死亡
          q.pop_front();
​
        // 比较队尾元素和将要进来的值，如果小的话就都移除
        while (!q.empty() && nums[q.back()] < nums[i]) // 挑战者和团队最弱者比较，可以排除最弱者
          q.pop_back();
​
        // 不管挑战有没有成功都要进来
        q.push_back(i);
​
        // 把队首元素加入结果
        // 队首保留最大值，队尾保留最小值
        if (i >= k - 1)
          res.push_back(nums[q.front()]);
      }
​
      return res;
    }
};