O(n) – Page 8 – Huahua’s Tech Road

Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below. [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ]

Solution: DFS

Time complexity: O(n!)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int totalNQueens(int n) {

vector<int> cols(n);

vector<int> diag1(2 * n - 1);

vector<int> diag2(2 * n - 1);

int ans = 0;

function<void(int)> dfs = [&](int r) {

if (r == n) {

++ans;

return;

}

for (int i = 0; i < n; i++) {

int& c = cols[i];

int& d1 = diag1[r + i];

int& d2 = diag2[r - i + n - 1];

if (c || d1 || d2) continue;

c = d1 = d2 = 1;

dfs(r + 1);

c = d1 = d2 = 0;

}

};

dfs(0);

return ans;

}

};

Given an integer array arr and an integer k, modify the array by repeating it k times.

For example, if arr = [1, 2] and k = 3 then the modified array will be [1, 2, 1, 2, 1, 2].

Return the maximum sub-array sum in the modified array. Note that the length of the sub-array can be 0 and its sum in that case is 0.

As the answer can be very large, return the answer modulo 10^9 + 7.

Example 1:

Input: arr = [1,2], k = 3
Output: 9

Example 2:

Input: arr = [1,-2,1], k = 5
Output: 2

Example 3:

Input: arr = [-1,-2], k = 7
Output: 0

Constraints:

1 <= arr.length <= 10^5
1 <= k <= 10^5
-10^4 <= arr[i] <= 10^4

Solution: DP

This problem can be reduced to maxSubarray.
If k < 3: return maxSubarray(arr * k)
ans1 = maxSubarray(arr * 1)
ans2 = maxSubarray(arr * 2)
ans = max([ans1, ans2, ans2 + sum(arr) * (k – 2)])

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int kConcatenationMaxSum(vector<int>& arr, int k) {

constexpr int kMod = 1e9 + 7;

auto maxSum = [&arr](int r) {

long sum = 0;

long ans = 0;

for (int i = 0; i < r; ++i) {

for (long a : arr) {

sum = max(0L, sum += a);

ans = max(ans, sum);

}

return ans;

};

if (k < 3) return maxSum(k) % kMod;

long ans1 = maxSum(1);

long ans2 = maxSum(2);

long sum = accumulate(begin(arr), end(arr), 0L);

return max({ans1, ans2, ans2 + sum * (k - 2)}) % kMod;

}

};

Posts tagged as “O(n)”

花花酱 LeetCode 52. N-Queens II

Solution: DFS

C++

Related Problems

花花酱 LeetCode 1191. K-Concatenation Maximum Sum

Solution: DP

C++