JAVA CODE-
class Solution {
public int search(int[] nums, int target) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
int num = nums[mid];
if (num == target)
return mid;
else if (num > target)
high = mid - 1;
else
low = mid + 1;
}
return -1;
}
}
class Solution {
public:
int ways(vector<string>& pizza, int k) {
const int M = pizza.size();
const int N = pizza[0].size();
// dp[m][n][k] := # of ways to cut pizza[m:M][n:N] w/ k cuts
dp.resize(M, vector<vector<int>>(N, vector<int>(k, -1)));
prefix.resize(M + 1, vector<int>(N + 1));
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
prefix[i + 1][j + 1] = (pizza[i][j] == 'A') + prefix[i][j + 1] +
prefix[i + 1][j] - prefix[i][j];
return ways(0, 0, k - 1, M, N);
}
private:
static constexpr int kMod = 1'000'000'007;
vector<vector<vector<int>>> dp;
vector<vector<int>> prefix;
// HasApple of pizza[row1..row2)[col1..col2)
bool hasApple(int row1, int row2, int col1, int col2) {
return (prefix[row2][col2] - prefix[row1][col2] - prefix[row2][col1] +
prefix[row1][col1]) > 0;
};
int ways(int m, int n, int k, const int M, const int N) {
if (k == 0)
return 1;
if (dp[m][n][k] >= 0)
return dp[m][n][k];
dp[m][n][k] = 0;
for (int i = m + 1; i < M; ++i) // Cut horizontally
if (hasApple(m, i, n, N) && hasApple(i, M, n, N))
dp[m][n][k] = (dp[m][n][k] + ways(i, n, k - 1, M, N)) % kMod;
for (int j = n + 1; j < N; ++j) // Cut vertically
if (hasApple(m, M, n, j) && hasApple(m, M, j, N))
dp[m][n][k] = (dp[m][n][k] + ways(m, j, k - 1, M, N)) % kMod;
return dp[m][n][k];
}
};
87. Scramble String [Daily Coding Challenge] 30/03/2023
We can scramble a string s to get a string t using the following algorithm:
If the length of the string is 1, stop.
If the length of the string is > 1, do the following:
Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
Apply step 1 recursively on each of the two substrings x and y.
Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.
Example 1:
Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.
Example 2:
Input: s1 = "abcde", s2 = "caebd"
Output: false
Example 3:
Input: s1 = "a", s2 = "a"
Output: true
Constraints:
s1.length == s2.length
1 <= s1.length <= 30
s1 and s2 consist of lowercase English letters.
SOLUTION IN C++
class Solution {
public:
bool isScramble(string s1, string s2) {
if (s1 == s2)
return true;
if (s1.length() != s2.length())
return false;
const string hashedKey = s1 + '+' + s2;
if (memo.count(hashedKey))
return memo[hashedKey];
vector<int> count(128);
for (int i = 0; i < s1.length(); ++i) {
++count[s1[i]];
--count[s2[i]];
}
if (any_of(begin(count), end(count), [](int c) { return c != 0; }))
return memo[hashedKey] = false;
for (int i = 1; i < s1.length(); ++i) {
if (isScramble(s1.substr(0, i), s2.substr(0, i)) &&
isScramble(s1.substr(i), s2.substr(i)))
return memo[hashedKey] = true;
if (isScramble(s1.substr(0, i), s2.substr(s2.length() - i)) &&
isScramble(s1.substr(i), s2.substr(0, s2.length() - i)))
return memo[hashedKey] = true;
}
return memo[hashedKey] = false;
}
private:
unordered_map<string, bool> memo;
};
The founder of LeetCode is Huahua (Yi) Zhang. He is a former software engineer at Google, Facebook, and several other companies. Zhang started LeetCode in 2015 with the goal of providing a platform for developers to practice coding interview questions and improve their problem-solving skills. Since then, LeetCode has grown to become one of the most popular platforms for technical interview preparation, with a large community of users and a vast library of coding problems. Today, Zhang continues to be involved with LeetCode as the company's CEO and chief architect.
A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.
Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level i.e. time[i] * satisfaction[i].
Return the maximum sum of like-time coefficient that the chef can obtain after dishes preparation.
Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.
Example 1:
Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14).
Each dish is prepared in one unit of time.
Example 2:
Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)
Example 3:
Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People do not like the dishes. No dish is prepared.
Constraints:
n == satisfaction.length
1 <= n <= 500
-1000 <= satisfaction[i] <= 1000
SOLUTION
