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 pivotInteger(int n) {
int left = 2;
int right= n-1;
if (n < 2)
return n;
int leftSum = 1;
int rightSum = n;
int totalSum = (n * (n + 1)) /2;
while(leftSum < totalSum && rightSum < totalSum && left < right){
if (leftSum < rightSum){
leftSum += left;
left++;
}else{
rightSum += right;
right--;
}
}
if (leftSum == rightSum)
return left;
else
return -1;
}
};
class Solution{
public:
vector matrixDiagonally(vector>&mat)
{
int n=mat.size();
vector ans(n*n,0);
int k=0;
bool up=true;
int r=0,c=0;
while(r0 && c0 && r
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
ListNode* dummy = new ListNode(0), *cur = dummy;
dummy->next = head;
int prefix = 0;
map m;
while (cur) {
prefix += cur->val;
if (m.count(prefix)) {
cur = m[prefix]->next;
int p = prefix + cur->val;
while (p != prefix) {
m.erase(p);
cur = cur->next;
p += cur->val;
}
m[prefix]->next = cur->next;
} else {
m[prefix] = cur;
}
cur = cur->next;
}
return dummy->next;
}
};
class Solution {
private:
vector> mat;
vector> res;
void multiply(vector>& res, const vector>& mat, long long m) {
vector> res1(3, vector(3, 0));
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
for (int k = 0; k < 3; ++k) {
res1[i][j] += (res[i][k] * mat[k][j]) % m;
res1[i][j] %= m;
}
}
}
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
res[i][j] = res1[i][j];
}
}
}
void matrixExponentiation(long long n, long long m) {
while (n > 0) {
if (n & 1) {
multiply(res, mat, m);
}
multiply(mat, mat, m);
n /= 2;
}
}
public:
long long genFibNum(long long a, long long b, long long c, long long n, long long m) {
res = vector>(3, vector(3, 0));
res[0][0] = res[1][1] = res[2][2] = 1;
mat = vector>(3, vector(3, 0));
mat[0][0] = a;
mat[0][1] = b;
mat[0][2] = mat[1][0] = mat[2][2] = 1;
mat[1][1] = mat[1][2] = mat[2][0] = mat[2][1] = 0;
if (n <= 2) {
return 1 % m;
} else {
matrixExponentiation(n - 2, m);
return (res[0][0] + res[0][1] + c * res[0][2]) % m;
}
}
};
class Solution {
public:
string customSortString(string order, string s) {
string ret = "";
for (char c : order) {
for (size_t i = 0U; i < s.size(); ++i) {
if (c == s[i]) {
ret += s[i];
s[i] = ';';
}
}
}
for (char c : s) {
if (c != ';')
ret += c;
}
return ret;
}
};
class Solution{
public:
bool check(vector> &mat2, int n, int x){
int i = 0;
int j = n-1;
while(i >= 0 && i < n && j >= 0 && j < n){
if(mat2[i][j] == x){
return true;
}
else if(mat2[i][j] < x){
i++;
}
else j--;
}
return false;
}
int countPairs(vector> &mat1, vector> &mat2, int n, int x)
{
// Your code goes here
int cnt = 0;
for(int i = 0;i < n;i++){
for(int j = 0;j < n;j++){
int c = x - mat1[i][j];
if(check(mat2,n,c)){
cnt++;
}
}
}
return cnt;
}
};
class Solution {
public:
vector intersection(vector& a1, vector& a2) {
set s1(a1.begin(), a1.end());
set s2(a2.begin(), a2.end());
set s;
set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
inserter(s, s.begin()));
vector res(s.begin(), s.end());
return res;
}
};
class Solution{
public:
string removeDuplicates(string str) {
vector v1(26,0),v2(26,0);
string s="";
for(char& ch:str){
if(ch>='A'&&ch<='Z'){
if(v1[ch-'A']==0){
s.push_back(ch);
}
v1[ch-'A']++;
}
if(ch>='a'&&ch<='z'){
if(v2[ch-'a']==0){
s.push_back(ch);
}
v2[ch-'a']++;
}
}
return s;
}
};
class Solution {
public:
int getCommon(vector& nums1, vector& nums2) {
int i=0, j=0;
int m = nums1.size();
int n = nums2.size();
while(inums2[j]){
j++;
}
else{
i++;
}
}
return -1;
}
};
class Solution{
public:
char nthCharacter(string s, int r, int n) {
string temp = s;
for (int i = 0;i < r; i++) {
string ans = "";
for (auto j :temp) {
if (j == '1') ans += "10";
else ans += "01";
if (ans.size()>n) break;
}
temp = ans;
}
return temp[n];
}
};
