Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.
For example,
Given nums =
Given nums =
[1,3,-1,-3,5,3,6,7], and k = 3.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
Therefore, return the max sliding window as
[3,3,5,5,6,7].
Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
You may assume k is always valid, ie: 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
Could you solve it in linear time?
Hint:
- How about using a data structure such as deque (double-ended queue)?
- The queue size need not be the same as the window’s size.
- Remove redundant elements and the queue should store only elements that need to be considered.
http://articles.leetcode.com/2011/01/sliding-window-maximum.html
compare function的写法跟用法
O(NlgN)
class Cmp{
public:
bool operator() (pair<int,int> &p1,pair<int,int> &p2) {
return p1.second < p2.second;
}
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (k == 0) {
vector<int> rt;
return rt;
}
if (k == 1) return nums;
vector<int> rt(nums.size() - k + 1);
priority_queue<pair<int,int>,vector<pair<int,int>>,Cmp> heap; // index, value
for (int i = 0; i < k - 1; i++) {
heap.push(make_pair(i,nums[i]));
}
for (int i = k - 1; i < nums.size(); i++) {
heap.push(make_pair(i,nums[i]));
while (heap.top().first < i - k + 1) {
heap.pop();
}
rt[i - k + 1] = heap.top().second;
}
return rt;
}
};
O(n)
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> rt;
deque<int> que;
for (int i = 0; i < k - 1; i++) {
while (!que.empty() && nums[i] >= nums[que.back()]) {
que.pop_back();
}
que.push_back(i);
}
for (int i = k - 1; i < nums.size(); i++) {
while (!que.empty() && nums[i] >= nums[que.back()]) {
que.pop_back();
}
if (!que.empty() && que.front() < i - k + 1) {
que.pop_front();
}
que.push_back(i);
rt.push_back(nums[que.front()]);
}
return rt;
}
};
Java
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 0) return new int[0];
int rt[] = new int[nums.length - k + 1];
Deque<Integer> q = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
if (!q.isEmpty() && q.getFirst() <= i - k) {
q.removeFirst();
}
while (!q.isEmpty() && nums[q.getLast()] < nums[i]) {
q.removeLast();
}
q.addLast(i);
if (i >= k - 1) {
rt[i - k + 1] = nums[q.getFirst()];
}
}
return rt;
}
}
另一种思路，Deque里的值是递增
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n == 0) return new int[0];
int[] rt = new int[n - k + 1];
Deque<Integer> deq = new LinkedList<>();
for (int i = 0; i < n; i++) {
while (!deq.isEmpty() && deq.peekLast() <= i - k) {
deq.pollLast();
}
if (deq.isEmpty() || nums[deq.peekLast()] <= nums[i]) deq.addLast(i);
else {
while (!deq.isEmpty() && nums[deq.peekFirst()] <= nums[i]) {
deq.pollFirst();
}
deq.addFirst(i);
}
if (i >= k - 1) rt[i - k + 1] = nums[deq.peekLast()];
}
return rt;
}
}
Delete Node in a Linked List
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Supposed the linked list is
-----------------------------------------------1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function./**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
node->next = node->next->next;
}
};
Product of Array Except Self
Given an array of n integers where n > 1,
nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given
[1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
-----------------------------------------------------------------
O(n) extra space
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> left(nums.size(),1);
vector<int> right(nums.size(),1);
vector<int> rt(nums.size());
for (int i = 1; i < nums.size(); i++) {
left[i] = nums[i - 1] * left[i - 1];
}
for (int i = nums.size() - 2; i >= 0; i--) {
right[i] = nums[i + 1] * right[i + 1];
}
for (int i = 0; i < nums.size(); i++) {
rt[i] = left[i] * right[i];
}
return rt;
}
};
constant space, output array doesn't count as extra space
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> left(nums.size(),1);
for (int i = 1; i < nums.size(); i++) {
left[i] = nums[i - 1] * left[i - 1];
}
int right = 1;
for (int i = nums.size() - 1; i >= 0; i--) {
left[i] = right * left[i];
right *= nums[i];
}
return left;
}
};
Different Ways to Add Parentheses
Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are
+, - and *.Example 1
Input:
"2-1-1".((2-1)-1) = 0 (2-(1-1)) = 2
Output:
[0, 2]Example 2
Input:
"2*3-4*5"(2*(3-(4*5))) = -34 ((2*3)-(4*5)) = -14 ((2*(3-4))*5) = -10 (2*((3-4)*5)) = -10 (((2*3)-4)*5) = 10
Output:
------------------------------------------------------[-34, -14, -10, -10, 10]Catalan number, divide and conquer
以下解法还可做优化
class Solution {
public:
vector<int> diffWaysToCompute(string s) {
vector<int> rt;
for (int i = 0; i < s.length(); i++) {
if (s[i] == '-' || s[i] == '+' || s[i] == '*') {
vector<int> first = diffWaysToCompute(s.substr(0,i));
vector<int> second = diffWaysToCompute(s.substr(i + 1));
for (int j = 0; j < first.size(); j++) {
for (int k = 0; k < second.size(); k++) {
if (s[i] == '-') {
rt.push_back(first[j] - second[k]);
}
if (s[i] == '+') {
rt.push_back(first[j] + second[k]);
}
if (s[i] == '*') {
rt.push_back(first[j] * second[k]);
}
}
}
}
}
if (rt.size() == 0) rt.push_back(stoi(s));
return rt;
}
};
DP优化
class Solution {
public:
vector<int> helper(string s, int start, int end,unordered_map<string,vector<int>> &dic) {
vector<int> rt;
for (int i = start; i <= end; i++) {
if (s[i] == '-' || s[i] == '+' || s[i] == '*') {
vector<int> first;
vector<int> second;
if (dic.find(s.substr(start,i)) == dic.end()) {
first = helper(s,start,i - 1,dic);
}else first = dic[s.substr(start,i)];
if (dic.find(s.substr(i + 1)) == dic.end()) {
second = helper(s,i + 1,end,dic);
}else second = dic[s.substr(i + 1)];
for (int j = 0; j < first.size(); j++) {
for (int k = 0; k < second.size(); k++) {
if (s[i] == '-') {
rt.push_back(first[j] - second[k]);
}
if (s[i] == '+') {
rt.push_back(first[j] + second[k]);
}
if (s[i] == '*') {
rt.push_back(first[j] * second[k]);
}
}
}
}
}
if (rt.size() == 0) rt.push_back(stoi(s.substr(start,end - start + 1)));
dic[s] = rt;
return rt;
}
vector<int> diffWaysToCompute(string input) {
unordered_map<string,vector<int>> dic;
return helper(input,0,input.length() - 1,dic);
}
};
No comments:
Post a Comment