# LeetCode Maximum Length of Subarray With Positive Product

1567. Maximum Length of Subarray With Positive Product

Given an array of integers nums, find the maximum length of a subarray where the product of all its elements is positive.

A subarray of an array is a consecutive sequence of zero or more values taken out of that array.

Return the maximum length of a subarray with positive product.

Example 1:

Input: nums = [1,-2,-3,4]
Output: 4
Explanation: The array nums already has a positive product of 24.


Example 2:

Input: nums = [0,1,-2,-3,-4]
Output: 3
Explanation: The longest subarray with positive product is [1,-2,-3] which has a product of 6.
Notice that we cannot include 0 in the subarray since that'll make the product 0 which is not positive.

Example 3:

Input: nums = [-1,-2,-3,0,1]
Output: 2
Explanation: The longest subarray with positive product is [-1,-2] or [-2,-3].


Example 4:

Input: nums = [-1,2]
Output: 1


Example 5:

Input: nums = [1,2,3,5,-6,4,0,10]
Output: 4


Constraints:

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
vector<int> dp_pos(n, 0), dp_neg(n, 0);
if(nums[0] > 0) dp_pos[0] = 1;
else if(nums[0] < 0) dp_neg[0] = 1;
int ans = dp_pos[0];
for(int i = 1; i < n; ++i) {
if(nums[i] > 0) {
dp_pos[i] = dp_pos[i - 1] + 1;
dp_neg[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
} else if(nums[i] < 0) {
dp_pos[i] = dp_neg[i - 1] > 0 ? dp_neg[i - 1] + 1 : 0;
dp_neg[i] = dp_pos[i - 1] + 1;
}
ans = max(ans, dp_pos[i]);
}
return ans;
}
};

class Solution {
public:
int getMaxLen(vector<int>& nums) {
int n = nums.size();
int pos_len = 0, neg_len = 0;
if(nums[0] > 0) pos_len = 1;
else if(nums[0] < 0) neg_len = 1;
int ans = pos_len;
for(int i = 1; i < n; ++i) {
if(nums[i] > 0) {
++pos_len;
neg_len = neg_len > 0 ? neg_len + 1 : 0;
} else if(nums[i] < 0) {
int tmp = pos_len;
pos_len = neg_len > 0 ? neg_len + 1 : 0;
neg_len = tmp + 1;
} else if(nums[i] == 0) {
pos_len = neg_len = 0;
}
ans = max(ans, pos_len);
}
return ans;
}
};

# LeetCode Detect Pattern of Length M Repeated K or More Times

5499. Detect Pattern of Length M Repeated K or More Times

Given an array of positive integers arr,  find a pattern of length m that is repeated k or more times.

pattern is a subarray (consecutive sub-sequence) that consists of one or more values, repeated multiple times consecutively without overlapping. A pattern is defined by its length and the number of repetitions.

Return true if there exists a pattern of length m that is repeated k or more times, otherwise return false.

Example 1:

Input: arr = [1,2,4,4,4,4], m = 1, k = 3
Output: true
Explanation: The pattern (4) of length 1 is repeated 4 consecutive times. Notice that pattern can be repeated k or more times but not less.


Example 2:

Input: arr = [1,2,1,2,1,1,1,3], m = 2, k = 2
Output: true
Explanation: The pattern (1,2) of length 2 is repeated 2 consecutive times. Another valid pattern (2,1) is also repeated 2 times.


Example 3:

Input: arr = [1,2,1,2,1,3], m = 2, k = 3
Output: false
Explanation: The pattern (1,2) is of length 2 but is repeated only 2 times. There is no pattern of length 2 that is repeated 3 or more times.


Example 4:

Input: arr = [1,2,3,1,2], m = 2, k = 2
Output: false
Explanation: Notice that the pattern (1,2) exists twice but not consecutively, so it doesn't count.


Example 5:

Input: arr = [2,2,2,2], m = 2, k = 3
Output: false
Explanation: The only pattern of length 2 is (2,2) however it's repeated only twice. Notice that we do not count overlapping repetitions.


Constraints:

• 2 <= arr.length <= 100
• 1 <= arr[i] <= 100
• 1 <= m <= 100
• 2 <= k <= 100

class Solution {
public:
bool containsPattern(vector<int>& arr, int m, int k) {
int n = arr.size();
if(m * k > n) return false;
for(int i = 0; i < n; ++i) {
int rep = 0;
for(int j = i; j < n; j += m) {
bool good = true;
for(int u = 0; u < m; ++u) {
if(u + j >= n || arr[u + j] != arr[i + u]) {
good = false;
break;
}
}
if(!good) break;
else ++rep;
}
if(rep >= k) return true;
}
return false;
}
};

# 剑指 Offer 18. 删除链表的节点

输入: head = [4,5,1,9], val = 5



输入: head = [4,5,1,9], val = 1



• 题目保证链表中节点的值互不相同
• 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(head->val == val) return head->next;
ListNode *pre = head, *cur = head;
while(cur != NULL && cur->val != val) {
pre = cur;
cur = cur->next;
}

if(cur->val == val) {
pre->next = cur->next;
}
return head;
}
};

# 剑指 Offer 17. 打印从1到最大的n位数

输入: n = 1



• 用返回一个整数列表来代替打印
• n 为正整数

class Solution {
public:
vector<int> printNumbers(int n) {
vector<int> ans;
int m = pow(10, n) - 1;
for(int i = 1; i <= m; ++i) ans.push_back(i);
return ans;
}
};

# 剑指 Offer 16. 数值的整数次方

输入: 2.00000, 10



输入: 2.10000, 3



输入: 2.00000, -2

• -100.0 < x < 100.0
• n 是 32 位有符号整数，其数值范围是 [−231, 231 − 1] 。

class Solution {
public:
double myPow(double x, int n) {

long long m = n;
if(m < 0) m = -m;

double ans = 1.0;
while(m != 0) {
if(m % 2 == 1) {
ans *= x;
}
x *= x;
m >>= 1;
}
if(n < 0) return 1.0 / ans;
else return ans;
}
};

# 剑指 Offer 15. 二进制中1的个数

输入：00000000000000000000000000001011



输入：00000000000000000000000010000000



输入：11111111111111111111111111111101

class Solution {
public:
int hammingWeight(uint32_t n) {
int ans = 0;
while(n != 0) {
++ans;
n = n & (n - 1);
}
return ans;
}
};

# 剑指 Offer 14- II. 剪绳子 II

输入: 2

输入: 10

• 2 <= n <= 1000

typedef long long LL;

class Solution {
private:
LL FastPow(LL x, LL y) {
LL ans = 1;
while(y != 0) {
if(y % 2 == 1) {
ans = ans * x % 1000000007;
}
x = x * x % 1000000007;
y >>= 1;
}
return ans % 1000000007;
}
public:
int cuttingRope(int n) {
if(n <= 3) return n - 1;
int m = n / 3;
if(n % 3 == 0) {
return FastPow(3, m) % 1000000007;
} else if(n % 3 == 1) {
return (FastPow(3, m - 1) % 1000000007) * 4 % 1000000007;
} else {
return (FastPow(3, m) % 1000000007) * 2 % 1000000007;
}
}
};

# 剑指 Offer 14- I. 剪绳子 LCOF

2 <= n <= 58

class Solution {
public:
int cuttingRope(int n) {
if(n <= 3) return n - 1;
int m = n / 3;
if(n % 3 == 0) {
return pow(3, m);
} else if(n % 3 == 1) {
return pow(3, m - 1) * 4;
} else {
return pow(3, m) * 2;
}
}
};

class Solution {
public:
int cuttingRope(int n) {
vector<int> dp(n + 1, 0);
dp[1] = 1;
for(int i = 2; i <= n; ++i) {
for(int j = 1; j < i; ++j) {
dp[i] = max(dp[i], max(j, dp[j]) * max(i - j, dp[i - j]));
}
}
return dp[n];
}
};

# 剑指 Offer 13. 机器人的运动范围

#### 剑指 Offer 13. 机器人的运动范围

1 <= n,m <= 100
0 <= k <= 20

oaxxx
bcxxx
xxxxx

struct Point {
int x_, y_;
Point(int x, int y) : x_(x), y_(y) {};
};

class Solution {
private:
int SumDigits(int num) {
int ans = 0;
while(num != 0) {
ans += (num % 10);
num /= 10;
}
return ans;
}
bool IsValid(int x, int y, int k) {
return SumDigits(x) + SumDigits(y) <= k;
}
public:
int movingCount(int m, int n, int k) {
vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<vector<int>> visited(m, vector<int>(n, 0));
queue<Point> q;
q.push(Point(0, 0));
int ans = 0;
while(!q.empty()) {
Point cur = q.front();
q.pop();

if(visited[cur.x_][cur.y_] == 1) continue; // 注意！

visited[cur.x_][cur.y_] = 1;
++ans;
for(int i = 0; i < dirs.size(); ++i) {
int u = cur.x_ + dirs[i][0], v = cur.y_ + dirs[i][1];
if(u >= 0 && u < m && v >= 0 && v < n && visited[u][v] == 0 && IsValid(u, v, k)) {
q.push(Point(u, v));
}
}
}
return ans;
}
};

# 剑指 Offer 12. 矩阵中的路径

[[“a”,”b”,”c”,”e”],
[“s”,”f”,”c”,”s”],
[“a”,”d”,”e”,”e”]]

1 <= board.length <= 200
1 <= board[i].length <= 200

class Solution {
private:
bool DFS(vector<vector<char>> &board, vector<vector<int>> &visited, int x, int y, const string &word, int idx) {

if(idx == word.size() - 1) return true;

visited[x][y] = 1;
int m = board.size(), n = board[0].size();

vector<vector<int>> dirs = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
for(int i = 0; i < dirs.size(); ++i) {
int u = x + dirs[i][0], v = y + dirs[i][1];
if(u >= 0 && u < m && v >= 0 && v < n && visited[u][v] == 0 && board[u][v] == word[idx + 1]) {
bool ans = DFS(board, visited, u, v, word, idx + 1);
if(ans) return true;
}
}

visited[x][y] = 0;

return false;
}
public:
bool exist(vector<vector<char>>& board, string word) {
if(word.size() == 0) return true;
int m = board.size(), n = board[0].size();
vector<vector<int>> visited(m, vector<int>(n, 0));
for(int i = 0; i < m; ++i) {
for(int j = 0; j < n; ++j) {
if(board[i][j] == word[0]) {
if(DFS(board, visited, i, j, word, 0)) return true;
}
}
}
return false;
}
};