GeeksForGeeks - POTD | GFG POTD Answer
关闭频道
1 218
订阅者
无数据24 小时
-97 天
-5730 天
帖子存档
class Solution {
public:
int findMoves(int n, vector chairs, vector passengers) {
sort(chairs.begin(),chairs.end());
sort(passengers.begin(),passengers.end());
int res=0;
for(int i=0 ; i
class Solution {
public:
bool isStraightHand(int N, int groupSize, vector &hand) {
multiset s(hand.begin(),hand.end());
while(s.size()>0)
{
int x = *s.begin();
for(int i=x;i
class Solution{
public:
vectorkthSmallestNum(int n, vector>&range, int q, vectorqueries){
sort(range.begin(),range.end());
for(int i = 1; i < n; i++)
{
range[i][0] = max(range[i][0],range[i-1][1]);
range[i][1] = max(range[i][1],range[i-1][1]);
}
vector ans;
for(auto it : queries)
{
int prev = 0,flag = 0;
for(int i = 0; i < n; i++)
{
if(i != 0)
{
if(range[i-1][1] == range[i][0])
{
range[i][0]++;
}
}
int diff = prev + range[i][1] - range[i][0] + 1;
if(it <= diff)
{
int x = it - prev - 1;
ans.push_back(x + range[i][0]);
flag = 1;
break;
}
prev = diff;
}
if(!flag)
{
ans.push_back(-1);
}
}
return ans;
}
};
class Solution {
private:
void dfs(int i, int j, vector<vector<int>> &matrix) {
if(i < 0 i == matrix.size() j < 0 j == matrix[0].size() matrix[i][j] == 0) {
return;
}
matrix[i][j] = 0;
dfs(i+1, j, matrix);
dfs(i-1, j, matrix);
dfs(i, j+1, matrix);
dfs(i, j-1, matrix);
}
public:
int closedIslands(vector<vector<int>>& matrix, int N, int M) {
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if((i == 0 i == N-1 j == 0 || j == M-1) && matrix[i][j] == 1) {
dfs(i, j, matrix);
}
}
}
int ans = 0;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
if(matrix[i][j] == 1) {
ans++;
dfs(i, j, matrix);
}
}
}
return ans;
}
};
class Solution{
public:
int isPossible(int n, int m, string s)
{
int lowr = 0, lowc = 0, highr = 0, highc = 0, r=0,c=0;
for (auto it:s)
{
if (it=='L')
c--;
if (it=='R')
c++;
if (it=='U')
r--;
if (it=='D')
r++;
lowr = min(lowr, r);
lowc = min(lowc,c);
highr = max(highr,r);
highc = max(highc,c);
}
if (highr-lowr
class Solution {
public:
bool isPowerOfFive(string s) {
int n = s.length();
if (n == 0) return false;
if (s[0] == '0') return false;
long long num = 0;
for (int i = 0; i < n; i++) {
num = num * 2 + (s[i] - '0');
}
if (num == 0) return false;
while (num > 1) {
if (num % 5 != 0) return false;
num /= 5;
}
return true;
}
int cuts(string s) {
int n = s.length();
if (n == 0 || s[0] == '0')
return -1;
if (isPowerOfFive(s))
return 1;
int minCuts = INT_MAX;
for (int i = 1; i < n; i++) {
string left = s.substr(0, i);
string right = s.substr(i);
if (isPowerOfFive(left)) {
int cutsRight = cuts(right);
if (cutsRight != -1)
minCuts = min(minCuts, 1 + cutsRight);
}
}
if (minCuts != INT_MAX)
return minCuts;
return -1;
}
};
class Solution {
public:
int countBitsUtil(int n) {
int bits = 0;
int powerOfTwo = 1;
while (powerOfTwo <= n) {
int pairsOfOnes = (n + 1) / (powerOfTwo * 2) * powerOfTwo;
int extraOnes = max(0, (n + 1) % (powerOfTwo * 2) - powerOfTwo);
bits += pairsOfOnes + extraOnes;
powerOfTwo <<= 1;
}
return bits;
}
long long countBits(long long N) {
return countBitsUtil(N);
}
};
class Solution {
public:
long long findMaxSubsetSum(int N, vector &A) {
long long curr,next = 0,nextNext = 0;
for(int i=N-1;i>=0;i--){
curr = max(next,nextNext) + A[i];
nextNext = next;
next = curr;
}
return max(next,nextNext);
}
};
class Solution {
public:
int bitMagic(int n, vector &arr) {
int ans=0;
for(int i=0;i
class Solution {
public:
int arrayOperations(int n, vector &arr) {
// code here
bool f = false;
int cntZero = count(arr.begin(), arr.end(), 0);
if(cntZero == 0)
return -1;
int cnt = 0;
for(int i = 0; i < n; i++){
if( f == false && arr[i] != 0){
cnt++;
f = true;
}
else if( arr[i] == 0){
f = false;
}
}
return cnt;
}
};
