LeetCode, GeeksForGeeks Problem of the day solution
前往频道在 Telegram
Complete daily challenges from LeetCode, GeeksForGeeks and redeem their rewards Channel link : https://t.me/leetcode_gfg_potd
显示更多1 250
订阅者
+224 小时
+147 天
+2930 天
帖子存档
class Solution {
public:
int minFallingPathSum(vector>& matrix) {
int m=matrix.size();
int n=matrix[0].size();
vector> dp(m, vector(n, 0));
for(int i=0;i=0){
ld = dp[i-1][j-1];
}
int pr = dp[i-1][j];
int rd = 1e9;
if(j+1
class Solution {
public:
vector> kTop(vector& arr, int N, int K) {
vector top(K + 1);
vector> ans;
unordered_map m;
for (int i = 0; i < N; i++) {
vectortemp;
m[arr[i]]++;
top[K] = arr[i];
auto it = find(top.begin(), top.end() - 1, arr[i]);
for (int j = distance(top.begin(), it) - 1; j >= 0; --j) {
if (m[top[j]] < m[top[j + 1]])
swap(top[j], top[j + 1]);
else if ((m[top[j]] == m[top[j + 1]]) && (top[j] > top[j+1]))
swap(top[j], top[j + 1]);
else
break;
}
for (int i = 0; i < K && top[i] != 0; ++i)
temp.push_back(top[i]);
ans.push_back(temp);
}
return ans;
}
};
class Solution {
public:
int climbStairs(int n) {
int arr[46]={0};
arr[0] = 1;
arr[1] = 1;
for(int i=2;i<=45;i++){
arr[i] = arr[i-1]+arr[i-2];
}
return arr[n];
}
};
class Solution{
public:
int min_sprinklers(int gallery[], int n)
{
// code here
vector jump(n, -1);
for(int i = 0; i < n; i++){
long long int x = max(0, i-gallery[i]), y = min(n-1, i+gallery[i]);
jump[x] = max(jump[x], y);
}
int res = 0;
long long int max_reachable = -1;
for(int i = 0; i < n; res += 1){
long long int dist = max(jump[i], max_reachable);
if(dist < 0 or res > n) return -1;
if(dist >= n) return res;
for(; i <= dist and i < n; i++){
if(jump[i] > 0) max_reachable = max(max_reachable, jump[i]);
}
dist = max_reachable;
}
return res;
}
};
class Solution {
public:
bool uniqueOccurrences(vector& arr) {
int k=1000;
vector freq(2*k + 1);
for(auto it:arr){
freq[it+k]++;
}
sort(freq.begin(), freq.end());
for(int i=1;i<=2*k;i++){
if(freq[i]!=0 && freq[i]==freq[i-1]){
return false;
}
}
return true;
}
};
class Solution {
public:
vector> uniquePerms(vector &arr ,int n) {
vector>ans;
set>st;
solve(arr,0,n,st);
for(auto it:st){
ans.push_back(it);
}
return ans;
}
void solve(vector&a,int idx, int n,set>&st){
if(idx==n){
st.insert(a);return;
}
for(int i=idx;i
class RandomizedSet {
public:
vector vec;
unordered_map indexMap;
RandomizedSet() {
}
bool insert(int val) {
if(indexMap.find(val) != indexMap.end()){
return false;
}
vec.push_back(val);
indexMap[val] = vec.size()-1;
return true;
}
bool remove(int val) {
if(indexMap.find(val)==indexMap.end()){
return false;
}
int lastEle = vec.back();
indexMap[lastEle] = indexMap[val];
vec[indexMap[lastEle]] = lastEle;
vec.pop_back();
indexMap.erase(val);
return true;
}
int getRandom() {
return vec[rand()%vec.size()];
}
};
class Solution{
public:
vector> dp;
int sequence(int it , int n , int m){
if(n==0)return 1;
if(it > m)return 0;
if(dp[it][n] != -1)return dp[it][n];
return dp[it][n] = sequence(it*2 , n-1 , m) + sequence(it+1 , n , m);
}
int numberSequence(int m, int n){
// code here
dp = vector>(m+1 , vector(n+1 , -1));
return sequence(1, n ,m);
}
};
class Solution {
public:
vector> findWinners(vector>& matches) {
unordered_set u;
map m;
int n=matches.size();
for(int i=0;i> ans(2);
n=u.size();
for(auto i=u.begin();i!=u.end();i++){
if(!m.count(*i)) ans[0].push_back(*i);
else if(m[*i]==1) ans[1].push_back(*i);
}
sort(ans[1].begin(),ans[1].end());
sort(ans[0].begin(),ans[0].end());
return ans;
}
};
class Solution{
public:
int solve(int index, int total, vector &cost, vector> &dp)
{
if(index == cost.size()) return 0;
if(dp[index][total] != -1) return dp[index][total] ;
int take = 0, not_take = 0;
if(total >= cost[index])
take = 1 + solve(index+1, total - 0.1*cost[index], cost, dp);
not_take = solve(index+1, total, cost, dp);
return dp[index][total] = max(take, not_take);
}
int max_courses(int n, int total, vector &cost)
{
vector> dp(n, vector (total+1, -1));
return solve(0, total, cost, dp);
}
};
