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

给一个数组,包含正数、负数和0,问最长连乘结果为正的长度是多少。

本题与LeetCode Maximum Product Subarray类似,要注意负负得正的情况。首先是传统DP好理解方法:设置dp_pos和dp_neg两个数组,分别表示遍历到i时,当前的最长连乘为正的长度和最长连乘为负的长度。则对于第i个位置,如果nums[i]是正数,则dp_pos直接+1;对于dp_neg,如果前一刻已经是连乘为负,即dp_neg[i-1]>0,则在前一刻基础上再乘以nums[i]还是负,所以负数长度可变长,即dp_neg+1;如果前一刻没有连乘为负,则增加一个正数也不会使连乘为负的长度增加,所以dp_neg=0。类似的可以讨论num[i]为负数的情况。如果nums[i]==0,则dp_pos和dp_neg都重置为0。

完整代码如下:

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;
    }
};

本代码提交AC,用时268MS。

因为DP只用到上一刻的状态,所以不用数组存储也可以,节省内存版本如下,不过需要注意tmp=pos_len保存上一刻的pos_len状态。

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;
    }
};

本代码提交AC,用时368MS。

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

给定一个数组,为是否存在长度为m的子数组,这个子数组重复了至少k词。

观察数据范围,数据量很小,直接暴力求解,代码如下:

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;
    }
};

本代码提交AC,用时4MS。

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

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

给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。

返回删除后的链表的头节点。

注意:此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.

说明:

  • 题目保证链表中节点的值互不相同
  • 若使用 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;
    }
};

本代码提交AC,用时12MS。

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

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

输入数字 n,按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3,则打印出 1、2、3 一直到最大的 3 位数 999。

示例 1:

输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明:

  • 用返回一个整数列表来代替打印
  • 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;
    }
};

本代码提交AC,用时12MS。

如果只是这么解的话,就太easy了。这题是要考察大数越界的问题,这就需要用到string来表示数字了,然后使用递归的方法求解,具体可以看题解: https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/

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

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

实现函数double Power(double base, int exponent),求base的exponent次方。不得使用库函数,同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000

示例 2:

输入: 2.10000, 3
输出: 9.26100

示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2 = 1/22 = 1/4 = 0.25

说明:

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

注意:本题与主站 50 题相同:https://leetcode-cn.com/problems/powx-n/


实现函数pow(x,n),与LeetCode Pow(x, n)相同,快速幂。完整代码如下:

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;
    }
};

本代码提交AC,用时0MS。

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

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

请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。

示例 1:

输入:00000000000000000000000000001011
输出:3
解释:输入的二进制串 00000000000000000000000000001011 中,共有三位为 '1'。

示例 2:

输入:00000000000000000000000010000000
输出:1
解释:输入的二进制串 00000000000000000000000010000000 中,共有一位为 '1'。

示例 3:

输入:11111111111111111111111111111101
输出:31
解释:输入的二进制串 11111111111111111111111111111101 中,共有 31 位为 '1'。

注意:本题与主站 191 题相同:https://leetcode-cn.com/problems/number-of-1-bits/


统计无符号int的二进制中1的个数。简单题,n&(n-1)能把最后一个1消掉,直到为0。与LeetCode Number of 1 Bits相同,完整代码如下:

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

本代码提交AC,用时4MS。

剑指 Offer 14- II. 剪绳子 II

剑指 Offer 14- II. 剪绳子 II

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问 k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

提示:

  • 2 <= n <= 1000

注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/


本题是上一题(剑指 Offer 14- I. 剪绳子 LCOF)的升级版,即n的范围变大了,导致次方超过int和long long的范围,需要在求pow的过程中取mod。使用快速幂的方法,代码如下:

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;
        }
    }
};

本代码提交AC,用时0MS。

剑指 Offer 14- I. 剪绳子 LCOF

剑指 Offer 14- I. 剪绳子 LCOF

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]…k[m-1] 。请问 k[0]k[1]…*k[m-1] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

示例 1:

输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:

输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示:

2 <= n <= 58
注意:本题与主站 343 题相同:https://leetcode-cn.com/problems/integer-break/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一根长为n的绳子,剪成m段,使得m段长度的乘积最大。问最大乘积是多少。

看题解,把长度切分为3,乘积最大。需要用到算术几何平均不等式,以及求导求极值等数学知识。

完整代码如下:

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;
        }
    }
};

本代码提交AC,用时0MS。

另一个通用解法是DP,假设dp[i]是长度为i,切分之后的最大乘积。则对于dp[j],可以把[1,…,j]切分为[1,…,k]和[k+1,…,j],因为切分之后两段的长度都小于j,所以之前已经求解过了,可直接得到乘积。题解如下: https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/shu-xue-zhi-shi-he-dong-tai-gui-hua-liang-chong-fa/ 。完整代码如下:

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];
    }
};

本代码提交AC,用时4MS。

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

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

地上有一个m行n列的方格,从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动,它每次可以向左、右、上、下移动一格(不能移动到方格外),也不能进入行坐标和列坐标的数位之和大于k的格子。例如,当k为18时,机器人能够进入方格 [35, 37] ,因为3+5+3+7=18。但它不能进入方格 [35, 38],因为3+5+3+8=19。请问该机器人能够到达多少个格子?

示例 1:

输入:m = 2, n = 3, k = 1
输出:3
示例 2:

输入:m = 3, n = 1, k = 0
输出:1
提示:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个m*n的矩阵,要求从(0,0)开始移动,不能移动到坐标数字的位数之和超过k的位置,问最多有多少个可以走的格子。

简单的BFS的题,需要注意的是,BFS出队列的时候,检查一下这个点之前有没有被访问过。比如下图,最开始访问o点,然后会把a和b都进队列,接着a会把c进队列,但b也会把c进队列,导致c被进了两次,所以需要判断一下之前是否被访问。

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;
    }
};

本代码提交AC,用时8MS。

剑指 Offer 12. 矩阵中的路径

剑指 Offer 12. 矩阵中的路径

请设计一个函数,用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始,每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格,那么该路径不能再次进入该格子。例如,在下面的3×4的矩阵中包含一条字符串“bfce”的路径(路径中的字母用加粗标出)。

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

但矩阵中不包含字符串“abfb”的路径,因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后,路径不能再次进入这个格子。

示例 1:

输入:board = [[“A”,”B”,”C”,”E”],[“S”,”F”,”C”,”S”],[“A”,”D”,”E”,”E”]], word = “ABCCED”
输出:true
示例 2:

输入:board = [[“a”,”b”],[“c”,”d”]], word = “abcd”
输出:false
提示:

1 <= board.length <= 200
1 <= board[i].length <= 200
注意:本题与主站 79 题相同:https://leetcode-cn.com/problems/word-search/

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个字符矩阵,问矩阵中是否能走出一条路径,这条路径上的字符串起来和target字符串相等。

典型的DFS题,首先找到第一个字符开始的位置,然后DFS,完整代码如下:

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;
    }
};

本代码提交AC,用时624MS。