leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

commit	5d5ee277947c47988f59ee60608c0762f90b98c6
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Mon, 5 Dec 2022 18:17:05 +0100

Initial commit

Diffstat:

A	.clang-format	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0001.cpp	\|	++++++++++++
A	Problems/0002.cpp	\|	+++++++++++++++++++++++
A	Problems/0003.cpp	\|	+++++++++++++
A	Problems/0012.cpp	\|	+++++++++++++++++
A	Problems/0013.cpp	\|	+++++++++++++++++++++++++++++++
A	Problems/0014.cpp	\|	+++++++++++++++
A	Problems/0019.cpp	\|	+++++++++++++++++++
A	Problems/0020.cpp	\|	++++++++++++++++++++++++++++++
A	Problems/0021.cpp	\|	+++++++++++++++++++++++++++++
A	Problems/0024.cpp	\|	++++++++++++++
A	Problems/0026.cpp	\|	++++++++++
A	Problems/0027.cpp	\|	++++++++++
A	Problems/0028.cpp	\|	++++++++++++++++++++++++
A	Problems/0036.cpp	\|	++++++++++++++++++++++
A	Problems/0043.cpp	\|	+++++++++++++++++++++++++++
A	Problems/0054.cpp	\|	++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0059.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++
A	Problems/0061.cpp	\|	+++++++++++++++++++++++++++++
A	Problems/0066.cpp	\|	+++++++++++++++
A	Problems/0067.cpp	\|	+++++++++++++++++
A	Problems/0070.cpp	\|	++++++++++++++++++++++
A	Problems/0083.cpp	\|	++++++++++++
A	Problems/0088.cpp	\|	++++++++++++++++++
A	Problems/0094.cpp	\|	++++++++++++++++++++++++
A	Problems/0100.cpp	\|	+++++++++
A	Problems/0101.cpp	\|	+++++++++++++++++++++++++++++++++
A	Problems/0102.cpp	\|	++++++++++++++++++++++
A	Problems/0103.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0104.cpp	\|	+++++++++++++++++++
A	Problems/0107.cpp	\|	+++++++++++++++++++++++
A	Problems/0111.cpp	\|	++++++++++++++++++++
A	Problems/0112.cpp	\|	++++++++++++++++++++
A	Problems/0114.cpp	\|	+++++++++++++++++++++
A	Problems/0116.cpp	\|	+++++++++++++++++++++
A	Problems/0117.cpp	\|	+++++++++++++++++++++
A	Problems/0118.cpp	\|	++++++++++++++++
A	Problems/0119.cpp	\|	++++++++++++++++
A	Problems/0121.cpp	\|	++++++++++++
A	Problems/0133.cpp	\|	+++++++++++++++++++++++++++++
A	Problems/0138.cpp	\|	++++++++++++++++++++
A	Problems/0141.cpp	\|	+++++++++++++++
A	Problems/0142.cpp	\|	++++++++++++++++++++++
A	Problems/0144.cpp	\|	++++++++++++++++++++
A	Problems/0145.cpp	\|	+++++++++++++++++++++++++++++++++
A	Problems/0150.cpp	\|	++++++++++++++++++++++++++++
A	Problems/0151.cpp	\|	++++++++++++++++++
A	Problems/0160.cpp	\|	++++++++++++++++++++
A	Problems/0167.cpp	\|	++++++++++++++++
A	Problems/0189.cpp	\|	++++++++++++
A	Problems/0199.cpp	\|	++++++++++++++++++++
A	Problems/0200.cpp	\|	+++++++++++++++++++++++++++
A	Problems/0203.cpp	\|	++++++++++++++++
A	Problems/0206.cpp	\|	+++++++++++++++++
A	Problems/0209.cpp	\|	++++++++++++++++++++++++++
A	Problems/0222.cpp	\|	+++++++++++++++++++++++++
A	Problems/0223.cpp	\|	++++++++++++++++++++
A	Problems/0226.cpp	\|	+++++++++++++++++
A	Problems/0234.cpp	\|	++++++++++++++++++++++++++++++++++++++
A	Problems/0236.cpp	\|	++++++++++++++++++++++++++++++
A	Problems/0237.cpp	\|	+++++++
A	Problems/0257.cpp	\|	++++++++++++++++++++++++
A	Problems/0263.cpp	\|	++++++++++
A	Problems/0279.cpp	\|	++++++++++++++++
A	Problems/0283.cpp	\|	++++++++++
A	Problems/0295.cpp	\|	+++++++++++++++++++++++++++++++
A	Problems/0328.cpp	\|	++++++++++++++++++
A	Problems/0338.cpp	\|	++++++++++++
A	Problems/0344.cpp	\|	+++++++
A	Problems/0345.cpp	\|	++++++++++++++++++++
A	Problems/0374.cpp	\|	++++++++++++++++
A	Problems/0383.cpp	\|	+++++++++++++
A	Problems/0387.cpp	\|	++++++++++
A	Problems/0392.cpp	\|	+++++++++
A	Problems/0394.cpp	\|	++++++++++++++++++++++++++++++
A	Problems/0402.cpp	\|	++++++++++++++++++++++++++
A	Problems/0404.cpp	\|	+++++++++++++++++++++++
A	Problems/0412.cpp	\|	+++++++++++++++++++
A	Problems/0414.cpp	\|	+++++++++++++++++++++++++++
A	Problems/0415.cpp	\|	+++++++++++++++++++++
A	Problems/0429.cpp	\|	+++++++++++++++++++++
A	Problems/0430.cpp	\|	++++++++++++++++++++++++++++++++++
A	Problems/0433.cpp	\|	++++++++++++++++++++++++++++++++++++++++++
A	Problems/0445.cpp	\|	++++++++++++++++++++++++++++++++++++++
A	Problems/0448.cpp	\|	++++++++++++++++
A	Problems/0485.cpp	\|	+++++++++++++++
A	Problems/0494.cpp	\|	++++++++++++++++++++++++++++++
A	Problems/0496.cpp	\|	+++++++++++++++++++++
A	Problems/0498.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0503.cpp	\|	++++++++++++++++++++++++
A	Problems/0509.cpp	\|	++++++++++
A	Problems/0542.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0543.cpp	\|	+++++++++++++++++++++++++++++++++++
A	Problems/0547.cpp	\|	++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0556.cpp	\|	++++++++++++++++++++++++
A	Problems/0557.cpp	\|	+++++++++++++++
A	Problems/0559.cpp	\|	++++++++++++++++++
A	Problems/0561.cpp	\|	+++++++++++++++++++++
A	Problems/0563.cpp	\|	++++++++++++++++++
A	Problems/0572.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0589.cpp	\|	+++++++++++++++++
A	Problems/0590.cpp	\|	+++++++++++++++++
A	Problems/0606.cpp	\|	+++++++++++++++++++++++++++++
A	Problems/0617.cpp	\|	+++++++++++++++
A	Problems/0637.cpp	\|	+++++++++++++++++++++++++
A	Problems/0662.cpp	\|	+++++++++++++++++++++++++
A	Problems/0684.cpp	\|	++++++++++++++++++++++++++++++
A	Problems/0707.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0724.cpp	\|	++++++++++++
A	Problems/0733.cpp	\|	++++++++++++++++++++++++++++++++++++++++++
A	Problems/0739.cpp	\|	++++++++++++++++++++
A	Problems/0746.cpp	\|	++++++++++++++++++++
A	Problems/0747.cpp	\|	++++++++++++++++++
A	Problems/0752.cpp	\|	+++++++++++++++++++++++++++++++++++
A	Problems/0797.cpp	\|	+++++++++++++++++++++++++++++++++++++++
A	Problems/0841.cpp	\|	+++++++++++++++++++++
A	Problems/0844.cpp	\|	++++++++++++++++++++++++++++++++++++
A	Problems/0872.cpp	\|	+++++++++++++++++++++++++++
A	Problems/0876.cpp	\|	++++++++++++++
A	Problems/0901.cpp	\|	++++++++++++++++++++
A	Problems/0905.cpp	\|	+++++++++++
A	Problems/0933.cpp	\|	++++++++++
A	Problems/0941.cpp	\|	++++++++++++++++
A	Problems/0947.cpp	\|	+++++++++++++++++++++++++++++++
A	Problems/0950.cpp	\|	++++++++++++++++++++++
A	Problems/0959.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/0965.cpp	\|	+++++++++++++++++++
A	Problems/0977.cpp	\|	++++++++++++++++++++
A	Problems/0989.cpp	\|	+++++++++++++++
A	Problems/0993.cpp	\|	+++++++++++++++++++++++++++++++
A	Problems/0997.cpp	\|	+++++++++++++++++++
A	Problems/1019.cpp	\|	++++++++++++++++++++
A	Problems/102.cpp	\|	++++++++++++++++++++++
A	Problems/1022.cpp	\|	++++++++++++++++++++++
A	Problems/1047.cpp	\|	+++++++++++++++++++
A	Problems/1051.cpp	\|	+++++++++++++
A	Problems/1089.cpp	\|	++++++++++++++++++++++++++
A	Problems/1095.cpp	\|	++++++++++
A	Problems/1099.cpp	\|	++++++++++++
A	Problems/1137.cpp	\|	+++++++++++
A	Problems/1209.cpp	\|	+++++++++++++++++++
A	Problems/1290.cpp	\|	++++++++
A	Problems/1319.cpp	\|	++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/1323.cpp	\|	++++++++++++
A	Problems/1337.cpp	\|	++++++++++++++++++++++++
A	Problems/1342.cpp	\|	++++++++++++++
A	Problems/1346.cpp	\|	++++++++++++++
A	Problems/1367.cpp	\|	+++++++++++++++++++++++++++++++++++
A	Problems/1379.cpp	\|	+++++++++++++++++++++++
A	Problems/144.cpp	\|	++++++++++++++++++
A	Problems/1466.cpp	\|	+++++++++++++++++++++++++++++++
A	Problems/1472.cpp	\|	+++++++++++++++++++++++++++++++
A	Problems/1480.cpp	\|	+++++++++
A	Problems/1544.cpp	\|	++++++++++++++
A	Problems/1557.cpp	\|	++++++++++++++
A	Problems/1584.cpp	\|	++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/1609.cpp	\|	++++++++++++++++++++++++++++
A	Problems/1646.cpp	\|	+++++++++++++++++++
A	Problems/1669.cpp	\|	+++++++++++++
A	Problems/1672.cpp	\|	++++++++
A	Problems/1696.cpp	\|	+++++++++++++++
A	Problems/1700.cpp	\|	+++++++++++++++++++++
A	Problems/1704.cpp	\|	++++++++++++++
A	Problems/1706.cpp	\|	+++++++++++++++++++++++++++++
A	Problems/1791.cpp	\|	++++++++++++++++++
A	Problems/1823.cpp	\|	+++++++++++++++++++++++++
A	Problems/1926.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++
A	Problems/1971.cpp	\|	+++++++++++++++++++++++++++++++++
A	Problems/2073.cpp	\|	++++++++++++
A	Problems/2095.cpp	\|	++++++++++++++++++
A	Problems/2130.cpp	\|	++++++++++++++++++++++++++++++++++
A	Problems/2131.cpp	\|	++++++++++++++++++++++++++
A	Problems/2181.cpp	\|	++++++++++++++++++++
A	Problems/2235.cpp	\|	++++
A	Problems/2236.cpp	\|	++++++
A	Problems/2285.cpp	\|	+++++++++++++++++++++
A	Problems/2326.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++
A	Problems/2331.cpp	\|	++++++++++++
A	Problems/2390.cpp	\|	+++++++++++++++++++
A	Problems/24.cpp	\|	++++++++++++++
A	Problems/2461.cpp	\|	++++++++++++++++++++++++++
A	Problems/2465.cpp	\|	++++++++++++
A	Problems/2466.cpp	\|	++++++++++++++
A	Problems/2467.cpp	\|	++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	Problems/841.cpp	\|	+++++++++++++++++++++
A	README.md	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

186 files changed, 4565 insertions(+), 0 deletions(-)

diff --git a/.clang-format b/.clang-format

@@ -0,0 +1,178 @@

---

Language: Cpp

# BasedOnStyle: LLVM

AccessModifierOffset: -2

AlignAfterOpenBracket: true

AlignArrayOfStructures: Right

AlignConsecutiveMacros: true

AlignConsecutiveAssignments: None

AlignConsecutiveBitFields: None

AlignConsecutiveDeclarations: None

AlignEscapedNewlines: Right

AlignOperands: Align

AlignTrailingComments: true

AllowAllArgumentsOnNextLine: true

AllowAllConstructorInitializersOnNextLine: true

AllowAllParametersOfDeclarationOnNextLine: true

AllowShortEnumsOnASingleLine: true

AllowShortBlocksOnASingleLine: true

AllowShortCaseLabelsOnASingleLine: true

AllowShortFunctionsOnASingleLine: All

AllowShortLambdasOnASingleLine: All

AllowShortIfStatementsOnASingleLine: true

AllowShortLoopsOnASingleLine: true

AlwaysBreakAfterDefinitionReturnType: None

AlwaysBreakAfterReturnType: None

AlwaysBreakBeforeMultilineStrings: false

AlwaysBreakTemplateDeclarations: MultiLine

AttributeMacros:

- __capability

BinPackArguments: true

BinPackParameters: true

BraceWrapping:

AfterCaseLabel: false

AfterClass: false

AfterControlStatement: Never

AfterEnum: false

AfterFunction: false

AfterNamespace: false

AfterObjCDeclaration: false

AfterStruct: false

AfterUnion: false

AfterExternBlock: false

BeforeCatch: false

BeforeElse: false

BeforeLambdaBody: false

BeforeWhile: false

IndentBraces: false

SplitEmptyFunction: true

SplitEmptyRecord: true

SplitEmptyNamespace: true

BreakBeforeBinaryOperators: None

BreakBeforeConceptDeclarations: true

BreakBeforeBraces: Attach

BreakBeforeInheritanceComma: false

BreakInheritanceList: BeforeColon

BreakBeforeTernaryOperators: true

BreakConstructorInitializersBeforeComma: false

BreakConstructorInitializers: BeforeColon

BreakAfterJavaFieldAnnotations: false

BreakStringLiterals: true

ColumnLimit: 80

CommentPragmas: '^ IWYU pragma:'

CompactNamespaces: false

ConstructorInitializerAllOnOneLineOrOnePerLine: false

ConstructorInitializerIndentWidth: 4

ContinuationIndentWidth: 4

Cpp11BracedListStyle: true

DeriveLineEnding: true

DerivePointerAlignment: false

DisableFormat: false

EmptyLineAfterAccessModifier: Never

EmptyLineBeforeAccessModifier: LogicalBlock

ExperimentalAutoDetectBinPacking: false

FixNamespaceComments: true

ForEachMacros:

- foreach

- Q_FOREACH

- BOOST_FOREACH

IfMacros:

- KJ_IF_MAYBE

IncludeBlocks: Preserve

IncludeCategories:

- Regex: '^"(llvm|llvm-c|clang|clang-c)/'

Priority: 2

SortPriority: 0

CaseSensitive: false

- Regex: '^(<|"(gtest|gmock|isl|json)/)'

Priority: 3

SortPriority: 0

CaseSensitive: false

- Regex: '.*'

Priority: 1

SortPriority: 0

CaseSensitive: false

IncludeIsMainRegex: '(Test)?$'

IncludeIsMainSourceRegex: ''

IndentAccessModifiers: false

IndentCaseLabels: false

IndentCaseBlocks: false

IndentGotoLabels: true

IndentPPDirectives: None

IndentExternBlock: AfterExternBlock

IndentRequires: false

IndentWidth: 2

IndentWrappedFunctionNames: false

InsertTrailingCommas: None

JavaScriptQuotes: Leave

JavaScriptWrapImports: true

KeepEmptyLinesAtTheStartOfBlocks: true

LambdaBodyIndentation: Signature

MacroBlockBegin: ''

MacroBlockEnd: ''

MaxEmptyLinesToKeep: 1

NamespaceIndentation: None

ObjCBinPackProtocolList: Auto

ObjCBlockIndentWidth: 2

ObjCBreakBeforeNestedBlockParam: true

ObjCSpaceAfterProperty: false

ObjCSpaceBeforeProtocolList: true

PenaltyBreakAssignment: 2

PenaltyBreakBeforeFirstCallParameter: 19

PenaltyBreakComment: 300

PenaltyBreakFirstLessLess: 120

PenaltyBreakString: 1000

PenaltyBreakTemplateDeclaration: 10

PenaltyExcessCharacter: 1000000

PenaltyReturnTypeOnItsOwnLine: 60

PenaltyIndentedWhitespace: 0

PointerAlignment: Right

PPIndentWidth: -1

ReferenceAlignment: Pointer

ReflowComments: true

ShortNamespaceLines: 1

SortIncludes: CaseSensitive

SortJavaStaticImport: Before

SortUsingDeclarations: true

SpaceAfterCStyleCast: false

SpaceAfterLogicalNot: false

SpaceAfterTemplateKeyword: true

SpaceBeforeAssignmentOperators: true

SpaceBeforeCaseColon: false

SpaceBeforeCpp11BracedList: false

SpaceBeforeCtorInitializerColon: true

SpaceBeforeInheritanceColon: true

SpaceBeforeParens: ControlStatements

SpaceAroundPointerQualifiers: Default

SpaceBeforeRangeBasedForLoopColon: true

SpaceInEmptyBlock: false

SpaceInEmptyParentheses: false

SpacesBeforeTrailingComments: 1

SpacesInAngles: Never

SpacesInConditionalStatement: false

SpacesInContainerLiterals: true

SpacesInCStyleCastParentheses: false

SpacesInLineCommentPrefix:

Minimum: 1

Maximum: -1

SpacesInParentheses: false

SpacesInSquareBrackets: false

SpaceBeforeSquareBrackets: false

BitFieldColonSpacing: Both

Standard: Latest

StatementAttributeLikeMacros:

- Q_EMIT

StatementMacros:

- Q_UNUSED

- QT_REQUIRE_VERSION

TabWidth: 8

UseCRLF: false

UseTab: Never

WhitespaceSensitiveMacros:

- STRINGIZE

- PP_STRINGIZE

- BOOST_PP_STRINGIZE

- NS_SWIFT_NAME

- CF_SWIFT_NAME

...

diff --git a/Problems/0001.cpp b/Problems/0001.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

vector<int> twoSum(vector<int> &nums, int target) {

unordered_map<int, int> um;

for (int i = 0; i < nums.size(); i++)

if (um.find(target - nums[i]) != um.end())

return {um[target - nums[i]], i};

else

um.insert(make_pair(nums[i], i));

return {};

}

};

diff --git a/Problems/0002.cpp b/Problems/0002.cpp

@@ -0,0 +1,23 @@

class Solution {

public:

ListNode *addTwoNumbers(ListNode *list1, ListNode *list2) {

ListNode *head, *t;

t = head = new ListNode();

int add = 0;

while (list1 || list2 || add) {

if (list1) {

add += list1->val;

list1 = list1->next;

}

if (list2) {

add += list2->val;

list2 = list2->next;

}

t = t->next = new ListNode(add % 10);

add /= 10;

}

return head->next;

}

};

diff --git a/Problems/0003.cpp b/Problems/0003.cpp

@@ -0,0 +1,13 @@

class Solution {

public:

int lengthOfLongestSubstring(string s) {

int maxi = 0;

unordered_set<char> us;

for (int i = 0, j = 0; j < size(s); j++) {

while (us.count(s[j])) us.erase(s[i++]);

maxi = max(j - i + 1, maxi);

us.insert(s[j]);

}

return maxi;

}

};

diff --git a/Problems/0012.cpp b/Problems/0012.cpp

@@ -0,0 +1,17 @@

class Solution {

public:

vector<vector<string>> vvs = {

{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},

{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},

{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},

{"", "M", "MM", "MMM", "*", "*", "*", "*", "*", "*"},

};

string intToRoman(int num) {

int exp = 0;

string res = "";

do { res = vvs[exp++][num % 10] + res; } while ((num /= 10) > 0);

return res;

}

};

diff --git a/Problems/0013.cpp b/Problems/0013.cpp

@@ -0,0 +1,31 @@

class Solution {

public:

int value(char c) {

switch (c) {

case 'I': return 1;

case 'V': return 5;

case 'X': return 10;

case 'L': return 50;

case 'C': return 100;

case 'D': return 500;

case 'M': return 1000;

default: return -10000;

}

int romanToInt(string s) {

int size = s.size();

int res = 0;

for (int i = 0; i < size - 1; i++) {

int a = value(s[i]);

int b = value(s[i + 1]);

if (a >= b)

res += a;

else

res -= a;

}

res += value(s[size - 1]);

return res;

}

};

diff --git a/Problems/0014.cpp b/Problems/0014.cpp

@@ -0,0 +1,15 @@

class Solution {

public:

string longestCommonPrefix(vector<string> &strs) {

int mlen = 200;

for (string &s : strs) mlen = min(mlen, (int)s.size());

string res = "";

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

for (int j = 1; j < strs.size(); j++)

if (strs[j][i] != strs[0][i]) return res;

res += strs[0][i];

}

return res;

}

};

diff --git a/Problems/0019.cpp b/Problems/0019.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

ListNode *removeNthFromEnd(ListNode *head, int n) {

ListNode *b = head;

n++;

for (ListNode *a = head; a; a = a->next) {

if (!n)

b = b->next;

else

n--;

}

if (n)

head = head->next;

else

b->next = b->next->next;

return head;

}

};

diff --git a/Problems/0020.cpp b/Problems/0020.cpp

@@ -0,0 +1,30 @@

class Solution {

char is_open(char c) { return c == '(' || c == '[' || c == '{'; }

char get_open_pair(char c) {

switch (c) {

case ')': return '(';

case ']': return '[';

case '}': return '{';

default: return 0;

}

public:

bool isValid(string s) {

stack<char> st;

char t;

for (auto c : s)

if (is_open(c))

st.push(c);

else if ((t = get_open_pair(c)))

if (!st.empty() && st.top() == t)

st.pop();

else

return false;

else

return false;

return st.empty();

}

};

diff --git a/Problems/0021.cpp b/Problems/0021.cpp

@@ -0,0 +1,29 @@

class Solution {

public:

ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {

ListNode *head, *t;

t = head = new ListNode();

while (list1 && list2) {

if (list1->val < list2->val) {

t = t->next = list1;

list1 = list1->next;

} else {

t = t->next = list2;

list2 = list2->next;

}

while (list1) {

t = t->next = list1;

list1 = list1->next;

}

while (list2) {

t = t->next = list2;

list2 = list2->next;

}

return head->next;

}

};

diff --git a/Problems/0024.cpp b/Problems/0024.cpp

@@ -0,0 +1,14 @@

class Solution {

public:

ListNode *swapPairs(ListNode *head) {

ListNode *d = new ListNode(-1, head);

for (ListNode *p = d; p->next && p->next->next;) {

ListNode *t = p->next;

p->next = p->next->next;

t->next = p->next->next;

p->next->next = t;

p = t;

}

return d->next;

}

};

diff --git a/Problems/0026.cpp b/Problems/0026.cpp

@@ -0,0 +1,10 @@

class Solution {

public:

int removeDuplicates(vector<int> &nums) {

int j = 1;

for (int i = 1; i < nums.size(); i++) {

if (nums[i - 1] != nums[i]) nums[j++] = nums[i];

}

return j;

}

};

diff --git a/Problems/0027.cpp b/Problems/0027.cpp

@@ -0,0 +1,10 @@

class Solution {

public:

int removeElement(vector<int> &nums, int val) {

int j = 0;

for (int i = 0; i < nums.size(); i++)

if (nums[i] != val) nums[j++] = nums[i];

return j;

}

};

diff --git a/Problems/0028.cpp b/Problems/0028.cpp

@@ -0,0 +1,24 @@

class Solution {

public:

int strStr(string haystack, string needle) {

vector<int> table(needle.size(), 0);

int m = haystack.size(), n = needle.size();

for (int len = 0, j = 1; j < n;) {

if (needle[j] == needle[len])

table[j++] = ++len;

else if (len)

len = table[len - 1];

else

table[j++] = 0;

}

for (int i = 0, j = 0; i < m;) {

if (haystack[i] == needle[j]) i++, j++;

if (j == n) return i - j;

if (i < m && haystack[i] != needle[j]) j ? j = table[j - 1] : i++;

}

return -1;

}

};

diff --git a/Problems/0036.cpp b/Problems/0036.cpp

@@ -0,0 +1,22 @@

class Solution {

public:

bool isValidSudoku(vector<vector<char>> &board) {

function check = [&board](unordered_set<char> &us, int i, int j) {

if (board[i][j] != '.' && us.count(board[i][j])) return false;

us.insert(board[i][j]);

return true;

};

unordered_set<char> us1, us2, us3;

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

for (int j = 0; j < 9; j++)

if (!check(us1, i, j) || !check(us2, j, i) ||

!check(us3, 3 * (i / 3) + (j / 3), 3 * (i % 3) + (j % 3)))

return false;

us1.clear();

us2.clear();

us3.clear();

}

return true;

}

};

diff --git a/Problems/0043.cpp b/Problems/0043.cpp

@@ -0,0 +1,27 @@

class Solution {

public:

string multiply(string num1, string num2) {

if (num1 == "0" || num2 == "0") return "0";

reverse(num1.begin(), num1.end());

reverse(num2.begin(), num2.end());

string answer(num1.size() + num2.size(), '0');

for (int p2 = 0; p2 < num2.size(); p2++) {

int d2 = num2[p2] - '0';

for (int p1 = 0; p1 < num1.size(); p1++) {

int d1 = num1[p1] - '0';

int numZero = p1 + p2;

int carry = answer[numZero] - '0';

int mul = d1 * d2 + carry;

answer[numZero] = mul % 10 + '0';

answer[numZero + 1] += mul / 10;

}

if (answer.back() == '0') answer.pop_back();

reverse(answer.begin(), answer.end());

return answer;

}

};

diff --git a/Problems/0054.cpp b/Problems/0054.cpp

@@ -0,0 +1,44 @@

class Solution {

pair<int, int> offset[4] = {

{ 0, 1},

{ 1, 0},

{ 0, -1},

{-1, 0}

};

int limit_offset[4] = {1, -1, -1, 1};

int limit[4] = {0, 0, 0, 0};

int &m = limit[2], &n = limit[1];

bool valid(int i, int j) {

return i >= limit[0] && i <= m && j >= limit[3] && j <= n;

}

public:

vector<int> spiralOrder(vector<vector<int>> &matrix) {

vector<int> res;

int direction = 0;

int cnt = 0;

int size;

int i = 0, j = 0;

m = matrix.size() - 1;

n = matrix[0].size() - 1;

size = (m + 1) * (n + 1);

while (true) {

res.push_back(matrix[i][j]);

if (++cnt == size) break;

if (!valid(i + offset[direction].first, j + offset[direction].second)) {

limit[direction] += limit_offset[direction];

direction = (direction + 1) % 4;

}

i += offset[direction].first;

j += offset[direction].second;

}

return res;

}

};

diff --git a/Problems/0059.cpp b/Problems/0059.cpp

@@ -0,0 +1,43 @@

class Solution {

pair<int, int> offset[4] = {

{ 0, 1},

{ 1, 0},

{ 0, -1},

{-1, 0}

};

int limit_offset[4] = {1, -1, -1, 1};

int limit[4] = {0, 0, 0, 0};

int &m = limit[2], &n = limit[1];

bool valid(int i, int j) {

return i >= limit[0] && i <= m && j >= limit[3] && j <= n;

}

public:

vector<vector<int>> generateMatrix(int dim) {

vector<vector<int>> res(dim, vector<int>(dim));

int direction = 0;

int cnt = 0;

int size;

int i = 0, j = 0;

m = n = dim - 1;

size = (m + 1) * (n + 1);

while (true) {

res[i][j] = ++cnt;

if (cnt == size) break;

if (!valid(i + offset[direction].first, j + offset[direction].second)) {

limit[direction] += limit_offset[direction];

direction = (direction + 1) % 4;

}

i += offset[direction].first;

j += offset[direction].second;

}

return res;

}

};

diff --git a/Problems/0061.cpp b/Problems/0061.cpp

@@ -0,0 +1,29 @@

class Solution {

int len(ListNode *head) {

int count = 0;

while (head) {

count++;

head = head->next;

}

return count;

}

public:

ListNode *rotateRight(ListNode *head, int k) {

if (!head) return nullptr;

k %= len(head);

ListNode *p, *t;

t = p = head;

for (; p->next; p = p->next) {

if (k)

k--;

else

t = t->next;

}

p->next = head;

head = t->next;

t->next = nullptr;

return head;

}

};

diff --git a/Problems/0066.cpp b/Problems/0066.cpp

@@ -0,0 +1,15 @@

class Solution {

public:

vector<int> plusOne(vector<int> &digits) {

vector<int> res;

int add = 1;

for (int i = digits.size() - 1; i >= 0 || add; i--) {

if (i >= 0) add += digits[i];

res.push_back(add % 10);

add /= 10;

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/0067.cpp b/Problems/0067.cpp

@@ -0,0 +1,17 @@

class Solution {

public:

string addBinary(string a, string b) {

string res;

int i = a.size() - 1;

int j = b.size() - 1;

int add = 0;

while (i >= 0 || j >= 0 || add) {

if (i >= 0) add += a[i--] - '0';

if (j >= 0) add += b[j--] - '0';

res += to_string(add % 2);

add /= 2;

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/0070.cpp b/Problems/0070.cpp

@@ -0,0 +1,22 @@

class Solution {

public:

int climbStairs(int n) {

vector<int> vec(46);

vec[0] = 1;

vec[1] = 1;

for (int i = 2; i <= n; i++) vec[i] = vec[i - 1] + vec[i - 2];

return vec[n];

}

int climbStairs(int n) {

int first = 1, second = 1;

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

int cnt = first + second;

first = second;

second = cnt;

}

return second;

}

};

diff --git a/Problems/0083.cpp b/Problems/0083.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

ListNode *deleteDuplicates(ListNode *head) {

if (!head) return nullptr;

for (ListNode *p = head; p->next;)

if (p->val == p->next->val)

p->next = p->next->next;

else

p = p->next;

return head;

}

};

diff --git a/Problems/0088.cpp b/Problems/0088.cpp

@@ -0,0 +1,18 @@

class Solution {

public:

void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {

int i = m - 1;

int j = n - 1;

int k = m + n - 1;

while (i >= 0 && j >= 0)

if (nums1[i] > nums2[j])

nums1[k--] = nums1[i--];

else

nums1[k--] = nums2[j--];

while (i >= 0) nums1[k--] = nums1[i--];

while (j >= 0) nums1[k--] = nums2[j--];

}

};

diff --git a/Problems/0094.cpp b/Problems/0094.cpp

@@ -0,0 +1,24 @@

class Solution {

public:

vector<int> inorderTraversal(TreeNode *root) {

vector<int> res;

stack<TreeNode *> st;

while (true) {

while (root) {

st.push(root);

root = root->left;

}

if (!st.empty()) {

root = st.top();

st.pop();

res.push_back(root->val);

root = root->right;

} else

return res;

}

return res;

}

};

diff --git a/Problems/0100.cpp b/Problems/0100.cpp

@@ -0,0 +1,9 @@

class Solution {

public:

bool isSameTree(TreeNode *p, TreeNode *q) {

if (!p && !q) return true;

if (!p || !q) return false;

return p->val == q->val && isSameTree(p->left, q->left) &&

isSameTree(p->right, q->right);

}

};

diff --git a/Problems/0101.cpp b/Problems/0101.cpp

@@ -0,0 +1,33 @@

class Solution {

string preorder(TreeNode *root, bool left) {

if (!root) return "";

string res;

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

if (!root) {

res += "-";

continue;

}

res += root->val;

if (left) {

st.push(root->right);

st.push(root->left);

} else {

st.push(root->left);

st.push(root->right);

}

return res;

}

public:

bool isSymmetric(TreeNode *root) {

if (!root) return false;

return preorder(root->left, true) == preorder(root->right, false);

}

};

diff --git a/Problems/0102.cpp b/Problems/0102.cpp

@@ -0,0 +1,22 @@

class Solution {

public:

vector<vector<int>> levelOrder(TreeNode *root) {

if (!root) return {};

vector<vector<int>> res;

queue<TreeNode *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

res.push_back(vector<int>());

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

res[lvl].push_back(root->val);

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

return res;

}

};

diff --git a/Problems/0103.cpp b/Problems/0103.cpp

@@ -0,0 +1,55 @@

class Solution {

public:

vector<vector<int>> zigzagLevelOrder(TreeNode *root) {

if (!root) return {};

vector<vector<int>> res;

queue<TreeNode *> q;

bool right = true;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

res.push_back(vector<int>());

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

res[lvl].push_back(root->val);

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

if (!right) reverse(res[lvl].begin(), res[lvl].end());

right = !right;

}

return res;

}

vector<vector<int>> zigzagLevelOrder(TreeNode *root) {

if (!root) return {};

vector<vector<int>> res;

deque<TreeNode *> d;

bool right = true;

d.push_front(root);

for (int lvl = 0; !d.empty(); lvl++, right = !right) {

res.push_back(vector<int>());

for (int t = d.size(); t > 0; t--) {

TreeNode *root;

if (right) {

root = d.front();

d.pop_front();

if (root->left) d.push_back(root->left);

if (root->right) d.push_back(root->right);

} else {

root = d.back();

d.pop_back();

if (root->right) d.push_front(root->right);

if (root->left) d.push_front(root->left);

}

res[lvl].push_back(root->val);

}

return res;

}

};

diff --git a/Problems/0104.cpp b/Problems/0104.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

int maxDepth(TreeNode *root) {

if (!root) return 0;

int lvl;

queue<TreeNode *> q;

q.push(root);

for (lvl = 0; !q.empty(); lvl++) {

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

return lvl;

}

};

diff --git a/Problems/0107.cpp b/Problems/0107.cpp

@@ -0,0 +1,23 @@

class Solution {

public:

vector<vector<int>> levelOrderBottom(TreeNode *root) {

if (!root) return {};

vector<vector<int>> res;

queue<TreeNode *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

res.push_back(vector<int>());

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

res[lvl].push_back(root->val);

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/0111.cpp b/Problems/0111.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

int minDepth(TreeNode *root) {

if (!root) return 0;

queue<TreeNode *> q;

q.push(root);

for (int lvl = 1; !q.empty(); lvl++) {

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

if (!root->left && !root->right) return lvl;

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

return -1;

}

};

diff --git a/Problems/0112.cpp b/Problems/0112.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

bool hasPathSum(TreeNode *root, int targetSum) {

if (!root) return false;

stack<pair<TreeNode *, int>> st;

st.push(make_pair(root, 0));

while (!st.empty()) {

TreeNode *root = st.top().first;

int val = st.top().second + root->val;

st.pop();

if (val == targetSum && !root->left && !root->right) return true;

if (root->left) st.push(make_pair(root->left, val));

if (root->right) st.push(make_pair(root->right, val));

}

return false;

}

};

diff --git a/Problems/0114.cpp b/Problems/0114.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

void flatten(TreeNode *root) {

TreeNode *crnt = new TreeNode(-1);

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

crnt->right = root;

while (root) {

crnt = root;

if (root->right) st.push(root->right);

root->right = root->left;

root->left = nullptr;

root = root->right;

}

};

diff --git a/Problems/0116.cpp b/Problems/0116.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

Node *connect(Node *root) {

if (!root) return {};

queue<Node *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

Node *prev = nullptr;

for (int t = q.size(); t > 0; t--) {

Node *root = q.front();

q.pop();

root->next = prev;

prev = root;

if (root->right) q.push(root->right);

if (root->left) q.push(root->left);

}

return root;

}

};

diff --git a/Problems/0117.cpp b/Problems/0117.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

Node *connect(Node *root) {

if (!root) return {};

queue<Node *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

Node *prev = nullptr;

for (int t = q.size(); t > 0; t--) {

Node *root = q.front();

q.pop();

root->next = prev;

prev = root;

if (root->right) q.push(root->right);

if (root->left) q.push(root->left);

}

return root;

}

};

diff --git a/Problems/0118.cpp b/Problems/0118.cpp

@@ -0,0 +1,16 @@

class Solution {

public:

vector<vector<int>> generate(int numRows) {

vector<vector<int>> res;

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

vector<int> row;

row.push_back(1);

for (int j = 1; j < i; j++)

row.push_back(res[i - 1][j - 1] + res[i - 1][j]);

if (i != 0) row.push_back(1);

res.push_back(row);

}

return res;

}

};

diff --git a/Problems/0119.cpp b/Problems/0119.cpp

@@ -0,0 +1,16 @@

class Solution {

public:

vector<int> getRow(int rowIndex) {

vector<vector<int>> res;

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

vector<int> row;

row.push_back(1);

for (int j = 1; j < i; j++)

row.push_back(res[i - 1][j - 1] + res[i - 1][j]);

if (i != 0) row.push_back(1);

res.push_back(row);

}

return res[rowIndex];

}

};

diff --git a/Problems/0121.cpp b/Problems/0121.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

int maxProfit(vector<int> &prices) {

int mini = prices[0];

int profit = 0;

for (int i = 1; i < prices.size(); i++) {

profit = max(prices[i] - mini, profit);

mini = min(prices[i], mini);

}

return profit;

}

};

diff --git a/Problems/0133.cpp b/Problems/0133.cpp

@@ -0,0 +1,29 @@

class Solution {

public:

Node *cloneGraph(Node *node) {

if (!node) return nullptr;

Node *head = new Node(node->val);

unordered_map<Node *, Node *> um({

{node, head}

});

stack<Node *> st;

st.push(node);

while (!st.empty()) {

Node *node = st.top();

st.pop();

for (Node *c : node->neighbors) {

if (um.find(c) != um.end()) {

um[node]->neighbors.push_back(um[c]);

continue;

}

Node *n = new Node(c->val);

um[node]->neighbors.push_back(n);

um.insert(make_pair(c, n));

st.push(c);

}

return head;

}

};

diff --git a/Problems/0138.cpp b/Problems/0138.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

Node *copyRandomList(Node *head) {

if (!head) return nullptr;

unordered_map<Node *, Node *> um;

Node *h, *t;

t = h = new Node(-1);

for (Node *p = head; p; p = p->next) {

t = t->next = new Node(p->val);

um.insert(make_pair(p, t));

}

t = h->next;

for (Node *p = head; p; p = p->next, t = t->next) {

if (p->random != nullptr) t->random = um[p->random];

}

return h->next;

}

};

diff --git a/Problems/0141.cpp b/Problems/0141.cpp

@@ -0,0 +1,15 @@

class Solution {

public:

bool hasCycle(ListNode *head) {

if (!head) return false;

ListNode *slow, *fast;

fast = slow = head;

while (fast->next && fast->next->next) {

fast = fast->next->next;

slow = slow->next;

if (fast == slow) return true;

}

return false;

}

};

diff --git a/Problems/0142.cpp b/Problems/0142.cpp

@@ -0,0 +1,22 @@

class Solution {

public:

ListNode *detectCycle(ListNode *head) {

if (!head) return nullptr;

ListNode *slow, *fast;

fast = slow = head;

while (fast->next && fast->next->next) {

fast = fast->next->next;

slow = slow->next;

if (fast == slow) {

fast = head;

while (fast != slow) {

fast = fast->next;

slow = slow->next;

}

return slow;

}

return nullptr;

}

};

diff --git a/Problems/0144.cpp b/Problems/0144.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

vector<int> preorderTraversal(TreeNode *root) {

if (!root) return {};

vector<int> res;

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

while (root) {

res.push_back(root->val);

if (root->right) st.push(root->right);

root = root->left;

}

return res;

}

};

diff --git a/Problems/0145.cpp b/Problems/0145.cpp

@@ -0,0 +1,33 @@

class Solution {

public:

vector<int> postorderTraversal(TreeNode *root) {

if (!root) return {};

vector<int> res;

unordered_set<TreeNode *> s;

stack<TreeNode *> st;

while (root) {

st.push(root);

root = root->left;

}

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

if (!s.count(root)) {

s.insert(root);

st.push(root);

root = root->right;

while (root) {

st.push(root);

root = root->left;

}

} else {

res.push_back(root->val);

}

return res;

}

};

diff --git a/Problems/0150.cpp b/Problems/0150.cpp

@@ -0,0 +1,28 @@

class Solution {

bool is_op(const string &s) {

return s == "+" || s == "-" || s == "*" || s == "/";

}

public:

int evalRPN(vector<string> &tokens) {

if (tokens.size() == 0) return 0;

stack<long long> st;

for (string &s : tokens) {

if (is_op(s)) {

long long y = st.top();

st.pop();

long long x = st.top();

st.pop();

switch (s[0]) {

case '+': st.push(x + y); break;

case '-': st.push(x - y); break;

case '*': st.push(x * y); break;

case '/': st.push(x / y); break;

}

} else

st.push(stoi(s));

}

return st.top();

}

};

diff --git a/Problems/0151.cpp b/Problems/0151.cpp

@@ -0,0 +1,18 @@

class Solution {

public:

string reverseWords(string s) {

string res = "";

string buff = "";

for (int i = 0; i < s.size(); i++) {

if (s[i] != ' ') {

buff += s[i];

} else if (buff != "") {

res = buff + " " + res;

buff = "";

}

if (buff != "") res = buff + " " + res;

if (res != "") res.pop_back();

return res;

}

};

diff --git a/Problems/0160.cpp b/Problems/0160.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {

if (!headA || !headB) return nullptr;

ListNode *res = nullptr;

for (ListNode *p = headA; p; p = p->next) p->val = -p->val;

for (ListNode *p = headB; p; p = p->next)

if (p->val < 0) {

res = p;

break;

}

for (ListNode *p = headA; p; p = p->next) p->val = -p->val;

return res;

}

};

diff --git a/Problems/0167.cpp b/Problems/0167.cpp

@@ -0,0 +1,16 @@

class Solution {

public:

vector<int> twoSum(vector<int> &numbers, int target) {

int i = 0, j = numbers.size() - 1;

while (i < j) {

int sum = numbers[i] + numbers[j];

if (sum == target)

return {i + 1, j + 1};

else if (sum < target)

i++;

else

j--;

}

return {};

}

};

diff --git a/Problems/0189.cpp b/Problems/0189.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

void rotate(vector<int> &nums, int k) {

k %= nums.size();

vector<int> t(k);

for (int i = 0; i < k; i++) t[i] = nums[nums.size() - k + i];

for (int i = nums.size() - k - 1; i >= 0; i--) nums[i + k] = nums[i];

for (int i = 0; i < k; i++) nums[i] = t[i];

}

};

diff --git a/Problems/0199.cpp b/Problems/0199.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

vector<int> rightSideView(TreeNode *root) {

if (!root) return {};

vector<int> res;

queue<TreeNode *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

res.push_back(q.front()->val);

for (int k = q.size(); k > 0; k--) {

TreeNode *root = q.front();

q.pop();

if (root->right) q.push(root->right);

if (root->left) q.push(root->left);

}

return res;

}

};

diff --git a/Problems/0200.cpp b/Problems/0200.cpp

@@ -0,0 +1,27 @@

class Solution {

public:

int numIslands(vector<vector<char>> &grid) {

queue<pair<int, int>> q;

int cnt = 0;

int m = grid.size(), n = grid[0].size();

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

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

if (grid[i][j] == '0') continue;

q.push(make_pair(i, j));

cnt++;

while (!q.empty()) {

int i = q.front().first;

int j = q.front().second;

q.pop();

if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') continue;

grid[i][j] = '0';

q.push(make_pair(i + 1, j));

q.push(make_pair(i - 1, j));

q.push(make_pair(i, j + 1));

q.push(make_pair(i, j - 1));

}

return cnt;

}

};

diff --git a/Problems/0203.cpp b/Problems/0203.cpp

@@ -0,0 +1,16 @@

class Solution {

public:

ListNode *removeElements(ListNode *head, int val) {

if (!head) return nullptr;

for (ListNode *p = head; p && p->next;)

if (p->next->val == val)

p->next = p->next->next;

else

p = p->next;

if (head->val == val) head = head->next;

return head;

}

};

diff --git a/Problems/0206.cpp b/Problems/0206.cpp

@@ -0,0 +1,17 @@

class Solution {

public:

ListNode *reverseList(ListNode *head) {

ListNode *p, *q, *r;

p = head;

q = nullptr;

while (p) {

r = q;

q = p;

p = p->next;

q->next = r;

}

return q;

}

};

diff --git a/Problems/0209.cpp b/Problems/0209.cpp

@@ -0,0 +1,26 @@

class Solution {

int inf = 100001;

public:

int minSubArrayLen(int target, vector<int> &nums) {

int i = 0, j = 0;

int mini = inf;

int sum = nums[0];

int cnt = 1;

while (true) {

if (sum >= target) {

do {

mini = min(mini, cnt);

sum -= nums[i++];

cnt--;

} while (i < j && sum >= target);

} else {

if (++j >= nums.size()) break;

sum += nums[j];

cnt++;

}

if (mini == inf) return 0;

return mini;

}

};

diff --git a/Problems/0222.cpp b/Problems/0222.cpp

@@ -0,0 +1,25 @@

class Solution {

public:

int countNodes(TreeNode *root) {

if (!root) return 0;

int height = 0;

queue<TreeNode *> q;

q.push(root);

while (!q.empty()) {

TreeNode *root = q.front();

q.pop();

int rh = 0, lh = 0;

for (TreeNode *t = root; t; t = t->left) lh++;

for (TreeNode *t = root; t; t = t->right) rh++;

if (lh == rh)

height += exp2(rh) - 1;

else {

height++;

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

return height;

}

};

diff --git a/Problems/0223.cpp b/Problems/0223.cpp

@@ -0,0 +1,20 @@

class Solution {

int calc_area(int x1, int y1, int x2, int y2) {

return abs(x1 - x2) * abs(y1 - y2);

}

public:

int computeArea(int ax1, int ay1, int ax2, int ay2, int bx1, int by1, int bx2,

int by2) {

int area = calc_area(ax1, ay1, ax2, ay2) + calc_area(bx1, by1, bx2, by2);

int x1, x2, y1, y2;

x1 = max(ax1, bx1);

x2 = min(ax2, bx2);

y1 = max(ay1, by1);

y2 = min(ay2, by2);

if (x2 - x1 > 0 && y2 - y1 > 0)

return area - calc_area(x1, y1, x2, y2);

else

return area;

}

};

diff --git a/Problems/0226.cpp b/Problems/0226.cpp

@@ -0,0 +1,17 @@

class Solution {

public:

TreeNode *invertTree(TreeNode *root) {

if (!root) return nullptr;

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

swap(root->left, root->right);

if (root->left) st.push(root->left);

if (root->right) st.push(root->right);

}

return root;

}

};

diff --git a/Problems/0234.cpp b/Problems/0234.cpp

@@ -0,0 +1,38 @@

class Solution {

public:

ListNode *invert(ListNode *head) {

ListNode *p, *q, *r;

p = head;

q = nullptr;

while (p) {

r = q;

q = p;

p = p->next;

q->next = r;

}

return q;

}

ListNode *first_half_end(ListNode *head) {

ListNode *fast, *slow;

fast = slow = head;

while (fast->next && fast->next->next) {

fast = fast->next->next;

slow = slow->next;

}

return slow;

}

bool isPalindrome(ListNode *head) {

if (!head || !head->next) return true;

ListNode *fhe = first_half_end(head);

ListNode *shs = invert(fhe->next);

for (ListNode *p = head, *tmp = shs; tmp; p = p->next, tmp = tmp->next)

if (p->val != tmp->val) return false;

return true;

}

};

diff --git a/Problems/0236.cpp b/Problems/0236.cpp

@@ -0,0 +1,30 @@

class Solution {

public:

TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q) {

unordered_map<TreeNode *, TreeNode *> um;

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

if (root->left) {

um.insert({root->left, root});

st.push(root->left);

}

if (root->right) {

um.insert({root->right, root});

st.push(root->right);

}

unordered_set<TreeNode *> ans;

while (p) {

ans.insert(p);

p = um[p];

}

while (!ans.count(q)) { q = um[q]; }

return q;

}

};

diff --git a/Problems/0237.cpp b/Problems/0237.cpp

@@ -0,0 +1,7 @@

class Solution {

public:

void deleteNode(ListNode *node) {

node->val = node->next->val;

node->next = node->next->next;

}

};

diff --git a/Problems/0257.cpp b/Problems/0257.cpp

@@ -0,0 +1,24 @@

class Solution {

public:

vector<string> binaryTreePaths(TreeNode *root) {

if (!root) return {};

vector<string> res;

stack<pair<TreeNode *, string>> st;

st.push({root, to_string(root->val)});

while (!st.empty()) {

TreeNode *root = st.top().first;

string s = st.top().second;

st.pop();

if (!root->left && !root->right)

res.push_back(s);

else {

s += "->";

if (root->left) st.push({root->left, s + to_string(root->left->val)});

if (root->right)

st.push({root->right, s + to_string(root->right->val)});

}

return res;

}

};

diff --git a/Problems/0263.cpp b/Problems/0263.cpp

@@ -0,0 +1,10 @@

class Solution {

public:

bool isUgly(int n) {

if (n <= 0) return false;

for (auto i : {2, 3, 5})

while (n % i == 0) n /= i;

return n == 1;

}

};

diff --git a/Problems/0279.cpp b/Problems/0279.cpp

@@ -0,0 +1,16 @@

class Solution {

public:

int numSquares(int n) {

vector<int> dp(n + 1, INT_MAX - 1);

vector<int> primes;

for (int i = 1; i <= sqrt(n); i++) primes.push_back(i * i);

dp[0] = 0;

for (int i = 1; i <= n; i++)

for (int j = 0; j < primes.size() && primes[j] <= i; j++)

dp[i] = min(dp[i], dp[i - primes[j]] + 1);

return dp[n];

}

};

diff --git a/Problems/0283.cpp b/Problems/0283.cpp

@@ -0,0 +1,10 @@

class Solution {

public:

void moveZeroes(vector<int> &nums) {

int j = 0;

for (int i = 0; i < nums.size(); i++)

if (nums[i] != 0) nums[j++] = nums[i];

while (j < nums.size()) nums[j++] = 0;

}

};

diff --git a/Problems/0295.cpp b/Problems/0295.cpp

@@ -0,0 +1,31 @@

class MedianFinder {

priority_queue<int> left;

priority_queue<int, vector<int>, greater<int>> right;

public:

void addNum(int num) {

if (left.empty() || num < left.top())

left.push(num);

else

right.push(num);

if (left.size() < right.size()) {

int temp = right.top();

right.pop();

left.push(temp);

}

if (left.size() - right.size() > 1) {

int temp = left.top();

left.pop();

right.push(temp);

}

double findMedian() {

if (left.size() > right.size())

return left.top();

else

return (left.top() + right.top()) * 0.5;

}

};

diff --git a/Problems/0328.cpp b/Problems/0328.cpp

@@ -0,0 +1,18 @@

class Solution {

public:

ListNode *oddEvenList(ListNode *head) {

if (!head) return nullptr;

ListNode *h, *t, *p;

t = h = new ListNode();

for (p = head; p && p->next;) {

t = t->next = p->next;

p->next = p->next->next;

if (p->next) p = p->next;

}

p->next = h->next;

t->next = nullptr;

return head;

}

};

diff --git a/Problems/0338.cpp b/Problems/0338.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

vector<int> countBits(int n) {

vector<int> res(n + 1);

int offset = 1;

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

if (offset * 2 == i) offset *= 2;

res[i] = (res[i - offset]) + 1;

}

return res;

}

};

diff --git a/Problems/0344.cpp b/Problems/0344.cpp

@@ -0,0 +1,7 @@

class Solution {

public:

void reverseString(vector<char> &s) {

int i = 0, j = (int)s.size() - 1;

while (i < j) swap(s[i++], s[j--]);

}

};

diff --git a/Problems/0345.cpp b/Problems/0345.cpp

@@ -0,0 +1,20 @@

class Solution {

bool is_vowel(char c) {

c = tolower(c);

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

}

public:

string reverseVowels(string s) {

int i = 0, j = size(s) - 1;

while (i < j) {

while (i < j && !is_vowel(s[i])) i++;

while (i < j && !is_vowel(s[j])) j--;

if (i >= j) break;

swap(s[i], s[j]);

i++;

j--;

}

return s;

}

};

diff --git a/Problems/0374.cpp b/Problems/0374.cpp

@@ -0,0 +1,16 @@

class Solution {

public:

int guessNumber(int n) {

int low = 1, high = n;

while (true) {

int mid = low + (high - low) / 2;

switch (guess(mid)) {

case 0: return mid;

case 1: low = mid + 1; break;

case -1: high = mid - 1; break;

default: return -1;

}

return -1;

}

};

diff --git a/Problems/0383.cpp b/Problems/0383.cpp

@@ -0,0 +1,13 @@

class Solution {

public:

bool canConstruct(string ransomNote, string magazine) {

unordered_map<char, int> us;

for (char c : magazine) us[c]++;

for (char c : ransomNote)

if (!us[c]--) return false;

return true;

}

};

diff --git a/Problems/0387.cpp b/Problems/0387.cpp

@@ -0,0 +1,10 @@

class Solution {

public:

int firstUniqChar(string s) {

vector<int> um(26, 0);

for (char c : s) um[c - 'a']++;

for (int i = 0; i < s.size(); i++)

if (um[s[i] - 'a'] == 1) return i;

return -1;

}

};

diff --git a/Problems/0392.cpp b/Problems/0392.cpp

@@ -0,0 +1,9 @@

class Solution {

public:

bool isSubsequence(string s, string t) {

int j = 0;

for (int i = 0; i < t.size() && j < s.size(); i++)

if (t[i] == s[j]) j++;

return j == s.size();

}

};

diff --git a/Problems/0394.cpp b/Problems/0394.cpp

@@ -0,0 +1,30 @@

class Solution {

public:

string decodeString(string s) {

stack<int> is;

stack<string> ss;

ss.push("");

for (int i = 0; i < s.size(); i++) {

if (isdigit(s[i])) {

int res = 0;

do {

res *= 10;

res += s[i] - '0';

} while (isdigit(s[++i]));

is.push(res);

ss.push("");

} else if (s[i] == ']') {

string res = "";

while (is.top()--) res += ss.top();

is.pop();

ss.pop();

ss.top() += res;

} else {

ss.top() += s[i];

}

return ss.top();

}

};

diff --git a/Problems/0402.cpp b/Problems/0402.cpp

@@ -0,0 +1,26 @@

class Solution {

public:

string removeKdigits(string num, int k) {

stack<char> st;

for (char c : num) {

while (k && !st.empty() && c < st.top()) {

k--;

st.pop();

}

if (st.empty() && c == '0') continue;

st.push(c);

}

string res = "";

while (!st.empty() && k--) st.pop();

while (!st.empty()) {

res = st.top() + res;

st.pop();

}

if (res == "") return "0";

return res;

}

};

diff --git a/Problems/0404.cpp b/Problems/0404.cpp

@@ -0,0 +1,23 @@

class Solution {

public:

int sumOfLeftLeaves(TreeNode *root) {

if (!root) return 0;

int res = 0;

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

if (root->left) {

if (!root->left->left && !root->left->right)

res += root->left->val;

else

st.push(root->left);

}

if (root->right) st.push(root->right);

}

return res;

}

};

diff --git a/Problems/0412.cpp b/Problems/0412.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

vector<string> fizzBuzz(int n) {

vector<string> res;

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

string s = "";

if (i % 3 == 0) s += "Fizz";

if (i % 5 == 0) s += "Buzz";

if (s == "") s = to_string(i);

res.push_back(s);

}

return res;

}

};

diff --git a/Problems/0414.cpp b/Problems/0414.cpp

@@ -0,0 +1,27 @@

class Solution {

public:

int thirdMax(vector<int> &nums) {

long long firstMax = numeric_limits<long long>::min();

long long secondMax = numeric_limits<long long>::min();

long long thirdMax = numeric_limits<long long>::min();

for (int &num : nums) {

if (firstMax == num || secondMax == num || thirdMax == num) { continue; }

if (firstMax <= num) {

thirdMax = secondMax;

secondMax = firstMax;

firstMax = num;

} else if (secondMax <= num) {

thirdMax = secondMax;

secondMax = num;

} else if (thirdMax <= num) {

thirdMax = num;

}

if (thirdMax == numeric_limits<long long>::min()) return firstMax;

return thirdMax;

}

};

diff --git a/Problems/0415.cpp b/Problems/0415.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

string addStrings(string num1, string num2) {

if (num1 == "0" && num2 == "0") return "0";

string res = "";

int i = num1.size() - 1;

int j = num2.size() - 1;

int add = 0;

while (i >= 0 || j >= 0 || add) {

if (i >= 0) add += num1[i--] - '0';

if (j >= 0) add += num2[j--] - '0';

res += to_string(add % 10);

add /= 10;

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/0429.cpp b/Problems/0429.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

vector<vector<int>> levelOrder(Node *root) {

if (!root) return {};

vector<vector<int>> res;

queue<Node *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

res.push_back(vector<int>());

for (int t = q.size(); t > 0; t--) {

Node *root = q.front();

q.pop();

res[lvl].push_back(root->val);

for (Node *c : root->children) q.push(c);

}

return res;

}

};

diff --git a/Problems/0430.cpp b/Problems/0430.cpp

@@ -0,0 +1,34 @@

class Solution {

void insert_after(Node **t, Node *n) {

n->prev = *t;

n->child = nullptr;

(*t) = (*t)->next = n;

}

public:

Node *flatten(Node *head) {

if (!head) return nullptr;

stack<Node *> s;

s.push(head);

Node *h, *t;

t = h = new Node();

while (!s.empty()) {

Node *self = s.top();

s.pop();

if (self->next) s.push(self->next);

Node *child = self->child;

insert_after(&t, self);

while (child) {

self = child;

child = self->child;

insert_after(&t, self);

if (self->next) s.push(self->next);

}

t->next = nullptr;

h->next->prev = nullptr;

return h->next;

}

};

diff --git a/Problems/0433.cpp b/Problems/0433.cpp

@@ -0,0 +1,42 @@

class Solution {

bool mutation(const string &s1, const string &s2) {

int cnt = 0;

for (int i = 0; i < size(s1); i++)

if (s1[i] != s2[i]) cnt++;

return cnt == 1;

}

public:

int minMutation(string startGene, string endGene, vector<string> &bank) {

/* unordered_map<string, vector<string>> um; */

/* if (find(bank.begin(), bank.end(), startGene) == bank.end()) */

/* bank.push_back(startGene); */

/* for (int i = 0; i < size(bank); i++) { */

/* for (int j = i + 1; j < size(bank); j++) */

/* if (mutation(bank[i], bank[j])) { */

/* um[bank[i]].push_back(bank[j]); */

/* um[bank[j]].push_back(bank[i]); */

/* } */

int mini = INT_MAX;

unordered_set<string> visited;

queue<pair<string, int>> st;

st.push({startGene, 0});

while (!st.empty()) {

string root = st.front().first;

int count = st.front().second;

st.pop();

visited.insert(root);

if (root == endGene) return count;

/* for (string &s : um[root]) */

/* if (visited.find(s) == visited.end()) st.push({s, count + 1}); */

for (string &s : bank)

if (visited.find(s) == visited.end() && mutation(root, s))

st.push({s, count + 1});

}

return -1;

}

};

diff --git a/Problems/0445.cpp b/Problems/0445.cpp

@@ -0,0 +1,38 @@

class Solution {

public:

string addStrings(string num1, string num2) {

if (num1 == "0" && num2 == "0") return "0";

string res = "";

int i = num1.size() - 1;

int j = num2.size() - 1;

int add = 0;

while (i >= 0 || j >= 0 || add) {

if (i >= 0) add += num1[i--] - '0';

if (j >= 0) add += num2[j--] - '0';

res += to_string(add % 10);

add /= 10;

}

reverse(res.begin(), res.end());

return res;

}

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {

if (!l1 || !l2) return nullptr;

string s1 = "", s2 = "";

for (ListNode *p = l1; p; p = p->next) s1 += '0' + p->val;

for (ListNode *p = l2; p; p = p->next) s2 += '0' + p->val;

string s = addStrings(s1, s2);

ListNode *h, *t;

t = h = new ListNode();

for (char c : s) t = t->next = new ListNode(c - '0');

return h->next;

}

};

diff --git a/Problems/0448.cpp b/Problems/0448.cpp

@@ -0,0 +1,16 @@

class Solution {

public:

vector<int> findDisappearedNumbers(vector<int> &nums) {

vector<int> res;

for (int i = 0; i < nums.size(); i++) {

int index = abs(nums[i]) - 1;

if (nums[index] > 0) nums[index] = -nums[index];

}

for (int i = 0; i < nums.size(); i++)

if (nums[i] > 0) res.push_back(i + 1);

return res;

}

};

diff --git a/Problems/0485.cpp b/Problems/0485.cpp

@@ -0,0 +1,15 @@

class Solution {

public:

int findMaxConsecutiveOnes(vector<int> &nums) {

int maxi = 0;

int cnt = 0;

for (int i : nums)

if (i)

maxi = max(maxi, ++cnt);

else

cnt = 0;

return maxi;

}

};

diff --git a/Problems/0494.cpp b/Problems/0494.cpp

@@ -0,0 +1,30 @@

class Solution {

public:

int findTargetSumWays(vector<int> &nums, int target) {

queue<int> st;

st.push(0);

int zc = 0;

for (int i = 0; i != nums.size(); ++i) {

if (!nums[i]) {

zc++;

continue;

}

for (int j = st.size(); j > 0; --j) {

int n = st.front();

st.pop();

st.push(n - nums[i]);

st.push(n + nums[i]);

}

int count = 0;

while (!st.empty()) {

if (st.front() == target) count++;

st.pop();

}

return count * exp2(zc);

}

};

diff --git a/Problems/0496.cpp b/Problems/0496.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

vector<int> nextGreaterElement(vector<int> &nums1, vector<int> &nums2) {

vector<int> res(nums1.size(), -1);

unordered_map<int, int> um;

stack<int> st;

for (int i = 0; i < nums2.size(); i++) {

while (!st.empty() && nums2[i] > st.top()) {

um.insert(make_pair(st.top(), nums2[i]));

st.pop();

}

st.push(nums2[i]);

}

for (int i = 0; i < nums1.size(); i++)

if (um.find(nums1[i]) != um.end()) res[i] = um[nums1[i]];

return res;

}

};

diff --git a/Problems/0498.cpp b/Problems/0498.cpp

@@ -0,0 +1,45 @@

class Solution {

public:

bool valid(int i, int m, int j, int n) {

return i >= 0 && i <= m && j >= 0 && j <= n;

}

void quick_adjust(int &i, int &j, bool &up) {

if (up)

i++;

else

j++;

up = !up;

}

void move(int &i, int &j, bool &up) {

if (up) {

i--;

j++;

} else {

i++;

j--;

}

vector<int> findDiagonalOrder(vector<vector<int>> &mat) {

vector<int> res;

bool up = true;

int i = 0, j = 0;

int m = mat.size() - 1, n = mat[0].size() - 1;

while (true) {

res.push_back(mat[i][j]);

if (i == m && j == n) break;

move(i, j, up);

if (!valid(i, m, j, n)) {

quick_adjust(i, j, up);

while (!valid(i, m, j, n)) move(i, j, up);

}

return res;

}

};

diff --git a/Problems/0503.cpp b/Problems/0503.cpp

@@ -0,0 +1,24 @@

class Solution {

public:

vector<int> nextGreaterElements(vector<int> &nums) {

vector<int> res(nums.size(), -1);

stack<int> st;

for (int i = 0; i < nums.size(); i++) {

while (!st.empty() && nums[i] > nums[st.top()]) {

res[st.top()] = nums[i];

st.pop();

}

st.push(i);

}

for (int i = 0; !st.empty() && i < nums.size(); i++) {

while (!st.empty() && nums[i] > nums[st.top()]) {

res[st.top()] = nums[i];

st.pop();

}

return res;

}

};

diff --git a/Problems/0509.cpp b/Problems/0509.cpp

@@ -0,0 +1,10 @@

class Solution {

public:

int fib(int n) {

vector<int> f(31);

f[0] = 0;

f[1] = 1;

for (int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];

return f[n];

}

};

diff --git a/Problems/0542.cpp b/Problems/0542.cpp

@@ -0,0 +1,53 @@

class Solution {

queue<pair<int, int>> q;

int m, n;

typedef vector<vector<int>> vvi;

int valid(int sr, int sc) { return sr >= 0 && sr < m && sc >= 0 && sc < n; }

void add(vvi &mat, int sr, int sc) {

cout << sr << " " << sc << " valid is: " << valid(sr, sc) << endl;

if (valid(sr, sc) && mat[sr][sc] != 0) q.push(make_pair(sr, sc));

}

void ff(vvi &mat, vvi &res, int sr, int sc) {

q.push(make_pair(sr, sc));

for (int lvl = 0; !q.empty(); lvl++) {

for (int t = q.size(); t > 0; t--) {

int sr = q.front().first;

int sc = q.front().second;

cout << "lvl" << lvl << ": " << sr << " " << sc << endl;

q.pop();

if (!res[sr][sc] || res[sr][sc] > lvl)

res[sr][sc] = lvl;

else

continue;

cout << "adding" << endl;

add(mat, sr + 1, sc);

add(mat, sr - 1, sc);

add(mat, sr, sc + 1);

add(mat, sr, sc - 1);

}

cout << "end FF" << endl;

}

public:

vector<vector<int>> updateMatrix(vvi &mat) {

m = mat.size();

n = mat[0].size();

cout << m << " " << n << endl;

vvi res(m, vector<int>(n, 0));

for (int i = 0; i < m; i++)

for (int j = 0; j < n; j++)

if (mat[i][j] == 0) ff(mat, res, i, j);

return res;

}

};

diff --git a/Problems/0543.cpp b/Problems/0543.cpp

@@ -0,0 +1,35 @@

class Solution {

public:

int diameterOfBinaryTree(TreeNode *root) {

unordered_map<TreeNode *, int> um;

stack<TreeNode *> st;

int res = 0;

while (root) {

st.push(root);

root = root->left;

}

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

if (um.find(root) == um.end()) {

um.insert({root, 1});

st.push(root);

root = root->right;

while (root) {

st.push(root);

root = root->left;

}

} else {

if (!root->left && !root->right) continue;

int l = um[root->left];

int r = um[root->right];

res = max(l + r, res);

um[root] = 1 + max(l, r);

}

return res;

}

};

diff --git a/Problems/0547.cpp b/Problems/0547.cpp

@@ -0,0 +1,44 @@

class UnionFind {

vector<int> root, rank;

int n;

public:

UnionFind(int n) : n(n), root(n), rank(n, 1) {

iota(root.begin(), root.end(), 0);

}

int find(int x) {

while (x != root[x]) x = root[x] = root[root[x]];

return x;

}

void join(int x, int y) {

x = find(x), y = find(y);

if (x != y) {

if (rank[x] > rank[y]) swap(x, y);

root[x] = y;

rank[y] += rank[x];

}

int count() {

int cnt = 0;

for (int i = 0; i < n; i++) cnt += root[i] == i;

return cnt;

}

};

class Solution {

public:

int findCircleNum(vector<vector<int>> &isConnected) {

int n = isConnected.size();

UnionFind uf(n);

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

for (int j = i + 1; j < n; j++)

if (isConnected[i][j]) uf.join(i, j);

return uf.count();

}

};

diff --git a/Problems/0556.cpp b/Problems/0556.cpp

@@ -0,0 +1,24 @@

class Solution {

public:

int nextGreaterElement(int n) {

string nums = to_string(n);

int prev = 0;

stack<int> st;

for (int i = nums.size() - 1; i >= 0; i--) {

if (!st.empty() && nums[i] < nums[st.top()]) {

while (!st.empty() && nums[i] < nums[st.top()]) {

prev = st.top();

st.pop();

}

swap(nums[i], nums[prev]);

reverse(nums.begin() + i + 1, nums.end());

break;

}

st.push(i);

}

long long res = stoll(nums);

return (res > INT_MAX || (int)res == n) ? -1 : (int)res;

}

};

diff --git a/Problems/0557.cpp b/Problems/0557.cpp

@@ -0,0 +1,15 @@

class Solution {

public:

string reverseWords(string s) {

int last = -1;

for (int k = 0; k <= s.size(); k++) {

if (k == s.size() || s[k] == ' ') {

int i = last + 1;

int j = k - 1;

while (i < j) swap(s[i++], s[j--]);

last = k;

}

return s;

}

};

diff --git a/Problems/0559.cpp b/Problems/0559.cpp

@@ -0,0 +1,18 @@

class Solution {

public:

int maxDepth(Node *root) {

if (!root) return 0;

int lvl;

queue<Node *> q;

q.push(root);

for (lvl = 0; !q.empty(); lvl++) {

for (int t = q.size(); t > 0; t--) {

Node *root = q.front();

q.pop();

for (Node *c : root->children) q.push(c);

}

return lvl;

}

};

diff --git a/Problems/0561.cpp b/Problems/0561.cpp

@@ -0,0 +1,21 @@

class Solution {

const static int length = 20001;

public:

int arrayPairSum(vector<int> &nums) {

int arr[length] = {0};

for (int i : nums) arr[i + 10000]++;

int res = 0;

int sub = 0;

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

if (!arr[i]) continue;

arr[i] -= sub;

res += (arr[i] / 2 + arr[i] % 2) * (i - 10000);

sub = arr[i] % 2;

}

return res;

}

};

diff --git a/Problems/0563.cpp b/Problems/0563.cpp

@@ -0,0 +1,18 @@

class Solution {

int res = 0;

int sum_adding_tilt(TreeNode *root) {

if (!root) return 0;

int l = sum_adding_tilt(root->left);

int r = sum_adding_tilt(root->right);

res += abs(l - r);

return l + r + root->val;

}

public:

int findTilt(TreeNode *root) {

res = 0;

sum_adding_tilt(root);

return res;

}

};

diff --git a/Problems/0572.cpp b/Problems/0572.cpp

@@ -0,0 +1,47 @@

class Solution {

bool strStr(string haystack, string needle) {

int m = haystack.size(), n = needle.size();

vector<int> table(needle.size(), 0);

for (int len = 0, j = 1; j < n;) {

if (needle[j] == needle[len])

table[j++] = ++len;

else if (len)

len = table[len - 1];

else

table[j++] = 0;

}

for (int i = 0, j = 0; i < m;) {

if (haystack[i] == needle[j]) i++, j++;

if (j == n) return true;

if (i < m && haystack[i] != needle[j]) j ? j = table[j - 1] : i++;

}

return false;

}

string tree_preorder_string(TreeNode *root) {

if (!root) return "";

string res = "";

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

res += root ? "_" + to_string(root->val) : "#";

if (!root) continue;

st.push(root->right);

st.push(root->left);

}

return res;

}

public:

bool isSubtree(TreeNode *root, TreeNode *subRoot) {

string tree = tree_preorder_string(root);

string sub = tree_preorder_string(subRoot);

return strStr(tree, sub);

}

};

diff --git a/Problems/0589.cpp b/Problems/0589.cpp

@@ -0,0 +1,17 @@

class Solution {

public:

vector<int> preorder(Node *root) {

if (!root) return {};

vector<int> res;

stack<Node *> st;

st.push(root);

while (!st.empty()) {

Node *root = st.top();

st.pop();

res.push_back(root->val);

reverse(root->children.begin(), root->children.end());

for (Node *c : root->children) st.push(c);

}

return res;

}

};

diff --git a/Problems/0590.cpp b/Problems/0590.cpp

@@ -0,0 +1,17 @@

class Solution {

public:

vector<int> postorder(Node *root) {

if (!root) return {};

vector<int> res;

stack<Node *> st;

st.push(root);

while (!st.empty()) {

Node *root = st.top();

st.pop();

for (Node *c : root->children) st.push(c);

res.push_back(root->val);

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/0606.cpp b/Problems/0606.cpp

@@ -0,0 +1,29 @@

class Solution {

public:

string tree2str(TreeNode *root) {

if (!root) return "";

string res = "";

stack<TreeNode *> st;

unordered_set<TreeNode *> us;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

if (us.find(root) != us.end()) {

res += ")";

st.pop();

} else {

us.insert(root);

res += "(" + to_string(root->val);

if (!root->left && !root->right) continue;

if (root->right) st.push(root->right);

if (root->left)

st.push(root->left);

else

res += "()";

}

return res.substr(1, res.size() - 2);

}

};

diff --git a/Problems/0617.cpp b/Problems/0617.cpp

@@ -0,0 +1,15 @@

class Solution {

public:

TreeNode *mergeTrees(TreeNode *root1, TreeNode *root2) {

if (!root1 && !root2) return nullptr;

if (!root2)

return new TreeNode(root1->val, mergeTrees(root1->left, nullptr),

mergeTrees(root1->right, nullptr));

if (!root1)

return new TreeNode(root2->val, mergeTrees(nullptr, root2->left),

mergeTrees(nullptr, root2->right));

return new TreeNode(root1->val + root2->val,

mergeTrees(root1->left, root2->left),

mergeTrees(root1->right, root2->right));

}

};

diff --git a/Problems/0637.cpp b/Problems/0637.cpp

@@ -0,0 +1,25 @@

class Solution {

public:

vector<double> averageOfLevels(TreeNode *root) {

if (!root) return {};

vector<double> res;

queue<TreeNode *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

int cnt = 0;

double sum = 0;

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

sum += root->val;

cnt++;

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

res.push_back(sum / cnt);

}

return res;

}

diff --git a/Problems/0662.cpp b/Problems/0662.cpp

@@ -0,0 +1,25 @@

class Solution {

public:

int widthOfBinaryTree(TreeNode *root) {

int maxi = 0;

queue<TreeNode *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

int first = -1, last = -1;

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

if (root) {

if (first == -1) first = t;

last = t;

}

if (!root) continue;

q.push(root->left);

q.push(root->right);

}

maxi = max(maxi, first - last);

}

return maxi;

}

};

diff --git a/Problems/0684.cpp b/Problems/0684.cpp

@@ -0,0 +1,30 @@

class Solution {

public:

int minReorder(int n, vector<vector<int>> &connections) {

vector<vector<int>> adj(n, vector<int>());

vector<bool> visited(n, false);

stack<int> st;

int res = 0;

for (auto &e : connections) {

adj[e[0]].push_back(e[1]);

adj[e[1]].push_back(-e[0]);

}

st.push(0);

visited[0] = true;

while (!st.empty()) {

int root = st.top();

st.pop();

for (auto c : adj[root]) {

int ac = abs(c);

if (!visited[ac]) {

res += c > 0;

visited[ac] = true;

st.push(ac);

}

return res;

}

};

diff --git a/Problems/0707.cpp b/Problems/0707.cpp

@@ -0,0 +1,77 @@

class MyLinkedList {

struct Node {

int val;

Node *next;

Node(int val, Node *next = nullptr) : val(val), next(next) {}

};

Node *head = nullptr, *tail = nullptr;

int size = 0;

public:

MyLinkedList() {}

int get(int index) {

if (index >= size) return -1;

Node *p = head;

while (index--) p = p->next;

return p->val;

}

void addAtHead(int val) {

if (!head)

head = tail = new Node(val);

else

head = new Node(val, head);

size++;

}

void addAtTail(int val) {

if (!head)

head = tail = new Node(val);

else

tail = tail->next = new Node(val);

size++;

}

void addAtIndex(int index, int val) {

if (index > size) return;

Node *p = head;

size++;

if (index == 0) {

addAtHead(val);

return;

}

while (--index) p = p->next;

p->next = new Node(val, p->next);

if (p == tail) tail = p->next;

}

void deleteAtIndex(int index) {

if (index >= size) return;

Node *t, *p;

size--;

if (index == 0) {

cout << "head" << endl;

t = head;

head = head->next;

delete t;

return;

}

p = head;

while (--index) p = p->next;

t = p->next;

p->next = p->next->next;

if (t == tail) tail = p;

delete t;

}

};

diff --git a/Problems/0724.cpp b/Problems/0724.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

int pivotIndex(vector<int> &nums) {

int left = 0;

int right = accumulate(nums.begin(), nums.end(), 0);

for (int i = 0; i < nums.size(); left += nums[i++]) {

right -= nums[i];

if (left == right) return i;

}

return -1;

}

};

diff --git a/Problems/0733.cpp b/Problems/0733.cpp

@@ -0,0 +1,42 @@

class Solution {

int m, n, src, color;

vector<vector<int>> *image;

queue<pair<int, int>> q;

int valid(int sr, int sc) { return sr >= 0 && sr < m && sc >= 0 && sc < n; }

void add(int sr, int sc) {

if (valid(sr, sc) && (*image)[sr][sc] == src) {

(*image)[sr][sc] = color;

q.push(make_pair(sr, sc));

}

public:

vector<vector<int>> floodFill(vector<vector<int>> &image, int sr, int sc,

int color) {

src = image[sr][sc];

if (src == color) return image;

m = image.size();

n = image[0].size();

this->color = color;

this->image = &image;

q.push(make_pair(sr, sc));

image[sr][sc] = color;

while (!q.empty()) {

int sr = q.front().first;

int sc = q.front().second;

q.pop();

add(sr + 1, sc);

add(sr - 1, sc);

add(sr, sc + 1);

add(sr, sc - 1);

}

return image;

}

};

diff --git a/Problems/0739.cpp b/Problems/0739.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

vector<int> dailyTemperatures(vector<int> &temps) {

stack<int> st({0});

for (int i = 1; i < temps.size(); ++i) {

while (!st.empty() && temps[i] > temps[st.top()]) {

temps[st.top()] = i - st.top();

st.pop();

}

st.push(i);

}

while (!st.empty()) {

temps[st.top()] = 0;

st.pop();

}

return temps;

}

};

diff --git a/Problems/0746.cpp b/Problems/0746.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

int minCostClimbingStairs(vector<int> &cost) {

vector<int> vec(cost.size() + 2);

for (int i = 2; i <= cost.size(); i++)

vec[i] = min(vec[i - 1] + cost[i - 1], vec[i - 2] + cost[i - 2]);

return vec[cost.size()];

}

int minCostClimbingStairs(vector<int> &cost) {

int first = cost[0], second = cost[1];

if (cost.size() <= 2) return min(first, second);

for (int i = 2; i < cost.size(); i++) {

int cur = cost[i] + min(first, second);

first = second;

second = cur;

}

return min(first, second);

}

};

diff --git a/Problems/0747.cpp b/Problems/0747.cpp

@@ -0,0 +1,18 @@

class Solution {

public:

int dominantIndex(vector<int> &nums) {

int max1, max2, index;

max1 = max2 = index = 0;

for (int i = 0; i < nums.size(); i++) {

if (nums[i] > max1) {

index = i;

max2 = max1;

max1 = nums[i];

} else if (nums[i] > max2) {

max2 = nums[i];

}

return 2 * max2 <= max1 ? index : -1;

}

};

diff --git a/Problems/0752.cpp b/Problems/0752.cpp

@@ -0,0 +1,35 @@

class Solution {

public:

vector<string> neighbours(const string &code) {

vector<string> res;

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

for (int j = -1; j <= 1; j += 2) {

string s = code;

s[i] = (code[i] - '0' + j + 10) % 10 + '0';

res.push_back(s);

}

return res;

}

int openLock(vector<string> &deadends, string target) {

unordered_set<string> um(deadends.begin(), deadends.end());

if (um.count("0000")) return -1;

queue<string> q({"0000"});

for (int cnt = 0; !q.empty(); ++cnt) {

for (int i = q.size(); i > 0; --i) {

string s = q.front();

q.pop();

if (s == target) return cnt;

for (string &s : neighbours(s)) {

if (um.count(s)) continue;

um.insert(s);

q.push(s);

}

return -1;

}

};

diff --git a/Problems/0797.cpp b/Problems/0797.cpp

@@ -0,0 +1,39 @@

class Solution {

public:

vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {

int n = graph.size();

vector<vector<int>> res;

unordered_set<int> visited;

vector<int> path;

stack<int> st;

st.push(0);

while (!st.empty()) {

int root = st.top();

st.pop();

if (root == n - 1) {

path.push_back(root);

res.push_back(path);

path.pop_back();

continue;

}

if (visited.count(root)) {

visited.erase(root);

path.pop_back();

continue;

}

path.push_back(root);

visited.insert(root);

st.push(root);

for (int n : graph[root])

if (!visited.count(n)) st.push(n);

}

return res;

}

};

diff --git a/Problems/0841.cpp b/Problems/0841.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

bool canVisitAllRooms(vector<vector<int>> &rooms) {

unordered_set<int> us;

queue<int> q;

q.push(0);

us.insert(0);

while (!q.empty()) {

int room = q.front();

q.pop();

for (int key : rooms[room]) {

if (!us.count(key)) {

us.insert(key);

q.push(key);

}

return us.size() == rooms.size();

}

};

diff --git a/Problems/0844.cpp b/Problems/0844.cpp

@@ -0,0 +1,36 @@

class Solution {

public:

bool backspaceCompare(string s, string t) {

int i = s.size() - 1, j = t.size() - 1;

int skipS = 0, skipT = 0;

while (i >= 0 || j >= 0) {

while (i >= 0) {

if (s[i] == '#') {

skipS++, i--;

} else if (skipS > 0) {

skipS--;

i--;

} else

break;

}

while (j >= 0) {

if (t[j] == '#') {

skipT++, j--;

} else if (skipT > 0) {

skipT--;

j--;

} else

break;

}

if (i >= 0 && j >= 0 && s[i] != t[j]) return false;

if ((i >= 0) != (j >= 0)) return false;

i--;

j--;

}

return true;

}

};

diff --git a/Problems/0872.cpp b/Problems/0872.cpp

@@ -0,0 +1,27 @@

class Solution {

vector<int> sequence(TreeNode *root) {

if (!root) return {};

vector<int> res;

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

if (!root->left && !root->right) {

res.push_back(root->val);

continue;

}

if (root->left) st.push(root->left);

if (root->right) st.push(root->right);

}

return res;

}

public:

bool leafSimilar(TreeNode *root1, TreeNode *root2) {

return sequence(root1) == sequence(root2);

}

};

diff --git a/Problems/0876.cpp b/Problems/0876.cpp

@@ -0,0 +1,14 @@

class Solution {

public:

ListNode *middleNode(ListNode *head) {

ListNode *fast, *slow;

fast = slow = head;

while (fast->next && fast->next->next) {

fast = fast->next->next;

slow = slow->next;

}

if (fast->next) slow = slow->next;

return slow;

}

};

diff --git a/Problems/0901.cpp b/Problems/0901.cpp

@@ -0,0 +1,20 @@

class StockSpanner {

static const int length = 10001;

int size = 0;

pair<int, int> stocks[length];

public:

StockSpanner() {}

int next(int price) {

int index = size - 1;

while (index >= 0)

if (price >= stocks[index].first)

index -= stocks[index].second;

else

break;

int span = size - index;

stocks[size++] = make_pair(price, span);

return span;

}

};

diff --git a/Problems/0905.cpp b/Problems/0905.cpp

@@ -0,0 +1,11 @@

class Solution {

public:

vector<int> sortArrayByParity(vector<int> &nums) {

vector<int> res;

for (int i : nums)

if (i % 2 == 0) res.push_back(i);

for (int i : nums)

if (i % 2 == 1) res.push_back(i);

return res;

}

};

diff --git a/Problems/0933.cpp b/Problems/0933.cpp

@@ -0,0 +1,10 @@

class RecentCounter {

queue<int> q;

public:

int ping(int t) {

q.push(t);

while (t - 3000 > q.front()) q.pop();

return q.size();

}

};

diff --git a/Problems/0941.cpp b/Problems/0941.cpp

@@ -0,0 +1,16 @@

class Solution {

public:

bool validMountainArray(vector<int> &arr) {

int i = 0;

while (i < arr.size() - 1 && arr[i] < arr[i + 1]) i++;

if (i == 0) return false;

int j = i;

while (i < arr.size() - 1 && arr[i] > arr[i + 1]) i++;

if (i == j) return false;

return i == arr.size() - 1;

}

};

diff --git a/Problems/0947.cpp b/Problems/0947.cpp

@@ -0,0 +1,31 @@

class Solution {

public:

int removeStones(vector<vector<int>> &stones) {

unordered_map<int, vector<int>> rows, cols;

unordered_set<int> seen;

for (int s = 0; s < size(stones); ++s)

rows[stones[s][0]].push_back(s), cols[stones[s][1]].push_back(s);

int c = 0;

stack<int> st;

for (int s = 0; s < size(stones); ++s) {

if (seen.count(s)) continue;

st.push(s);

while (!st.empty()) {

int s = st.top();

st.pop();

if (seen.count(s)) continue;

seen.insert(s);

int r = stones[s][0], c = stones[s][1];

for (auto ss : rows[r])

if (!seen.count(ss)) st.push(ss);

for (auto ss : cols[c])

if (!seen.count(ss)) st.push(ss);

}

c++;

}

return size(stones) - c;

}

};

diff --git a/Problems/0950.cpp b/Problems/0950.cpp

@@ -0,0 +1,22 @@

class Solution {

public:

vector<int> deckRevealedIncreasing(vector<int> &deck) {

sort(deck.begin(), deck.end(),

[](const int a, const int b) { return a > b; });

deque<int> q;

vector<int> res;

for (int i = 0; i < deck.size() - 1; i++) {

q.push_back(deck[i]);

q.push_back(q.front());

q.pop_front();

}

q.push_back(deck[deck.size() - 1]);

while (!q.empty()) {

res.push_back(q.back());

q.pop_back();

}

return res;

}

};

diff --git a/Problems/0959.cpp b/Problems/0959.cpp

@@ -0,0 +1,81 @@

class UnionFind {

vector<int> root, rank;

int n;

public:

UnionFind(int n) : n(n), root(n), rank(n, 1) {

iota(root.begin(), root.end(), 0);

}

int find(int x) {

while (x != root[x]) x = root[x] = root[root[x]];

return x;

}

void join(int x, int y) {

x = find(x), y = find(y);

if (x != y) {

if (rank[x] > rank[y]) swap(x, y);

root[x] = y;

rank[y] += rank[x];

}

int count() {

int cnt = 0;

for (int i = 0; i < n; i++) cnt += root[i] == i;

return cnt;

}

void set_invalid(int x) { root[x] = -1; }

};

class Solution {

int n;

int get_base_index(int x, int y) { return (n * x + y) * 2; }

bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }

int get_start_offset(char c, int k) {

if (c == '/')

return (k % 2 == 0) ? 1 : 0;

else

return (k == 0 || k == 3) ? 1 : 0;

}

int get_index(char c, int k, int x, int y, bool dest) {

int offset = get_start_offset(c, k);

if (dest) offset = !offset;

return get_base_index(x, y) + (c != ' ') * offset;

}

public:

int regionsBySlashes(vector<string> &grid) {

n = grid.size();

UnionFind uf(2 * n * n);

vector<pair<int, int>> offset = {

{ 0, 1},

{ 0, -1},

{ 1, 0},

{-1, 0}

};

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

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

for (int k = 0; k < 4; k++) {

int nx = x + offset[k].first, ny = y + offset[k].second;

if (!valid(nx, ny)) continue;

int index = get_index(grid[x][y], k, x, y, 0);

int nindex = get_index(grid[nx][ny], k, nx, ny, 1);

uf.join(index, nindex);

}

if (grid[x][y] == ' ') uf.set(get_base_index(x, y) + 1);

}

return uf.count();

}

};

diff --git a/Problems/0965.cpp b/Problems/0965.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

bool isUnivalTree(TreeNode *root) {

if (!root) return true;

int val = root->val;

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

if (root->val != val) return false;

if (root->left) st.push(root->left);

if (root->right) st.push(root->right);

}

return true;

}

};

diff --git a/Problems/0977.cpp b/Problems/0977.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

vector<int> sortedSquares(vector<int> &nums) {

vector<int> res;

int i = 0, j = nums.size() - 1;

while (i <= j) {

int n1 = nums[i] * nums[i];

int n2 = nums[j] * nums[j];

if (n1 > n2) {

res.push_back(n1);

i++;

} else {

res.push_back(n2);

j--;

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/0989.cpp b/Problems/0989.cpp

@@ -0,0 +1,15 @@

class Solution {

public:

vector<int> addToArrayForm(vector<int> &num, int k) {

vector<int> res;

for (int i = num.size() - 1; i >= 0 || k; i--) {

if (i >= 0) k += num[i];

res.push_back(k % 10);

k /= 10;

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/0993.cpp b/Problems/0993.cpp

@@ -0,0 +1,31 @@

class Solution {

public:

bool isCousins(TreeNode *root, int x, int y) {

if (!root) return {};

bool fx = false, fy = false;

queue<TreeNode *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

if (root->left && root->right)

if ((root->left->val == x && root->right->val == y) ||

(root->left->val == y && root->right->val == x))

return false;

if (root->val == x) fx = true;

if (root->val == y) fy = true;

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

if (fx && fy) return true;

if (fx || fy) return false;

}

return false;

}

};

diff --git a/Problems/0997.cpp b/Problems/0997.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

int findJudge(int n, vector<vector<int>> &trust) {

if (n == 1 && trust.empty()) return 1;

vector<int> trusted(n + 1, 0);

unordered_set<int> trusting;

for (auto &p : trust) {

trusting.insert(p[0]);

trusted[p[1]]++;

}

for (int i = 1; i <= n; i++)

if (trusted[i] == n - 1 && !trusting.count(i)) return i;

return -1;

}

};

diff --git a/Problems/1019.cpp b/Problems/1019.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

vector<int> nextLargerNodes(ListNode *head) {

if (!head) return {};

int len = 0, i = 0;

vector<int> res;

stack<pair<int, int>> st;

for (ListNode *p = head; p; p = p->next, i++) {

res.push_back(0);

while (!st.empty() && p->val > st.top().first) {

res[st.top().second] = p->val;

st.pop();

}

st.push({p->val, i});

}

return res;

}

};

diff --git a/Problems/102.cpp b/Problems/102.cpp

@@ -0,0 +1,22 @@

class Solution {

public:

vector<vector<int>> levelOrder(TreeNode *root) {

if (!root) return {};

vector<vector<int>> res;

queue<TreeNode *> q;

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

res.push_back(vector<int>());

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

res[lvl].push_back(root->val);

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

return res;

}

};

diff --git a/Problems/1022.cpp b/Problems/1022.cpp

@@ -0,0 +1,22 @@

class Solution {

public:

int sumRootToLeaf(TreeNode *root) {

if (!root) return 0;

stack<pair<TreeNode *, int>> st;

int sum = 0;

st.push({root, 0});

while (!st.empty()) {

TreeNode *root = st.top().first;

int val = (st.top().second << 1) | root->val;

st.pop();

if (!root->left && !root->right) {

sum += val;

continue;

}

if (root->left) st.push({root->left, val});

if (root->right) st.push({root->right, val});

}

return sum;

}

};

diff --git a/Problems/1047.cpp b/Problems/1047.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

string removeDuplicates(string s) {

stack<char> st;

for (char c : s)

if (st.empty() || c != st.top())

st.push(c);

else

st.pop();

string res = "";

while (!st.empty()) {

res += st.top();

st.pop();

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/1051.cpp b/Problems/1051.cpp

@@ -0,0 +1,13 @@

class Solution {

public:

int heightChecker(vector<int> &heights) {

int count = 0;

vector<int> exp = heights;

sort(exp.begin(), exp.end());

for (int i = 0; i < heights.size(); i++)

if (heights[i] != exp[i]) count++;

return count;

}

};

diff --git a/Problems/1089.cpp b/Problems/1089.cpp

@@ -0,0 +1,26 @@

class Solution {

public:

void duplicateZeros(vector<int> &arr) {

int cnt = 0;

int len = arr.size() - 1;

for (int i = 0; i + cnt <= len; i++)

if (arr[i] == 0) {

if (i + cnt == len) {

arr[len] = 0;

len -= 1;

break;

}

cnt++;

}

for (int i = len - cnt; i >= 0; i--) {

if (arr[i] == 0) {

arr[i + cnt] = 0;

cnt--;

arr[i + cnt] = 0;

} else {

arr[i + cnt] = arr[i];

}

};

diff --git a/Problems/1095.cpp b/Problems/1095.cpp

@@ -0,0 +1,10 @@

#include <cmath>

class Solution {

public:

int findNumbers(vector<int> &nums) {

int res = 0;

for (int i : nums)

if (int(log10(i) + 1) % 2 == 0) res++;

return res;

}

};

diff --git a/Problems/1099.cpp b/Problems/1099.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

vector<int> replaceElements(vector<int> &arr) {

int maxi = -1;

for (int i = arr.size() - 1; i >= 0; i--) {

int tmp = arr[i];

arr[i] = maxi;

maxi = max(maxi, tmp);

}

return arr;

}

};

diff --git a/Problems/1137.cpp b/Problems/1137.cpp

@@ -0,0 +1,11 @@

class Solution {

public:

int tribonacci(int n) {

vector<int> f(38);

f[0] = 0;

f[1] = 1;

f[2] = 1;

for (int i = 3; i <= n; i++) f[i] = f[i - 1] + f[i - 2] + f[i - 3];

return f[n];

}

};

diff --git a/Problems/1209.cpp b/Problems/1209.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

string removeDuplicates(string s, int k) {

stack<pair<char, int>> st;

for (char c : s)

if (!st.empty() && st.top().first == c) {

if (++st.top().second == k) st.pop();

} else

st.push(make_pair(c, 1));

string res = "";

while (!st.empty()) {

res += string(st.top().second, st.top().first);

st.pop();

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/1290.cpp b/Problems/1290.cpp

@@ -0,0 +1,8 @@

class Solution {

public:

int getDecimalValue(ListNode *head) {

int res = 0;

for (; head; head = head->next) res = res * 2 + head->val;

return res;

}

};

diff --git a/Problems/1319.cpp b/Problems/1319.cpp

@@ -0,0 +1,46 @@

class UnionFind {

int n;

vector<int> root, rank;

public:

UnionFind(int n) : n(n), root(n), rank(n, 1) {

iota(root.begin(), root.end(), 0);

}

int find(int x) {

while (x != root[x]) x = root[x] = root[root[x]];

return x;

}

void join(int x, int y) {

x = find(x), y = find(y);

if (x != y) {

if (rank[x] > rank[y]) swap(x, y);

root[x] = y;

rank[y] += rank[x];

}

int count() {

int cnt = 0;

for (int i = 0; i < n; i++) cnt += root[i] == i;

return cnt;

}

};

class Solution {

public:

int makeConnected(int n, vector<vector<int>> &connections) {

int count = 0;

UnionFind uf(n);

for (auto &edge : connections) {

if (uf.find(edge[0]) == uf.find(edge[1]))

count++;

else

uf.join(edge[0], edge[1]);

}

return count < uf.count() - 1 ? -1 : uf.count() - 1;

}

};

diff --git a/Problems/1323.cpp b/Problems/1323.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

int maximum69Number(int num) {

string s = to_string(num);

for (int i = 0; i < size(s); i++) {

if (s[i] == '9') continue;

s[i] = '9';

return stoi(s);

}

return num;

}

};

diff --git a/Problems/1337.cpp b/Problems/1337.cpp

@@ -0,0 +1,24 @@

class Solution {

public:

typedef pair<int, int> ii;

vector<int> kWeakestRows(vector<vector<int>> &mat, int k) {

vector<ii> vp;

int i = 0;

for (auto &v : mat)

vp.push_back(make_pair(i++, accumulate(v.begin(), v.end(), 0)));

sort(vp.begin(), vp.end(), [](const ii &a, const ii &b) -> bool {

return a.second < b.second || (a.second == b.second && a.first < b.first);

});

vector<int> res;

for (auto &p : vp)

if (k--)

res.push_back(p.first);

else

break;

return res;

}

};

diff --git a/Problems/1342.cpp b/Problems/1342.cpp

@@ -0,0 +1,14 @@

class Solution {

public:

int numberOfSteps(int num) {

int res = 0;

while (num) {

res++;

if (num % 2 == 0)

num /= 2;

else

num--;

}

return res;

}

};

diff --git a/Problems/1346.cpp b/Problems/1346.cpp

@@ -0,0 +1,14 @@

class Solution {

public:

bool checkIfExist(vector<int> &arr) {

unordered_set<int> us;

for (int i : arr)

if ((i % 2 == 0 && us.find(i / 2) != us.end()) ||

us.find(i * 2) != us.end())

return true;

else

us.insert(i);

return false;

}

};

diff --git a/Problems/1367.cpp b/Problems/1367.cpp

@@ -0,0 +1,35 @@

class Solution {

vector<int> needle, lps;

void computeKMPTable(vector<int> needle) {

lps.resize(needle.size(), 0);

for (int len = 0, j = 1; j < size(needle);) {

if (needle[j] == needle[len])

lps[j++] = ++len;

else if (len)

len = lps[len - 1];

else

lps[j++] = 0;

}

bool kmpSearch(TreeNode *root, int j) {

if (j == size(needle)) return true;

if (!root) return false;

while (j > 0 && root->val != needle[j]) j = lps[j - 1];

if (root->val == needle[j]) j++;

return kmpSearch(root->left, j) || kmpSearch(root->right, j);

}

public:

bool isSubPath(ListNode *head, TreeNode *root) {

if (!head || !root) return false;

needle.resize(0);

for (ListNode *t = head; t; t = t->next) needle.push_back(t->val);

computeKMPTable(needle);

return kmpSearch(root, 0);

}

};

diff --git a/Problems/1379.cpp b/Problems/1379.cpp

@@ -0,0 +1,23 @@

class Solution {

public:

TreeNode *getTargetCopy(TreeNode *original, TreeNode *cloned,

TreeNode *target) {

if (!original || !cloned || !target) return nullptr;

stack<pair<TreeNode *, TreeNode *>> st;

st.push({original, cloned});

while (!st.empty()) {

TreeNode *original = st.top().first;

TreeNode *cloned = st.top().second;

st.pop();

if (original == target) return cloned;

if (original->left) st.push({original->left, cloned->left});

if (original->right) st.push({original->right, cloned->right});

}

return nullptr;

}

};

diff --git a/Problems/144.cpp b/Problems/144.cpp

@@ -0,0 +1,18 @@

class Solution {

public:

vector<int> preorderTraversal(TreeNode *root) {

if (!root) return {};

vector<int> res;

stack<TreeNode *> st;

st.push(root);

while (!st.empty()) {

TreeNode *root = st.top();

st.pop();

res.push_back(root->val);

if (root->right) st.push(root->right);

if (root->left) st.push(root->left);

}

return res;

}

};

diff --git a/Problems/1466.cpp b/Problems/1466.cpp

@@ -0,0 +1,31 @@

class Solution {

public:

int minReorder(int n, vector<vector<int>> &connections) {

unordered_set<string> us;

vector<bool> visited(n, false);

vector<vector<int>> adj(n, vector<int>());

for (auto &e : connections) {

us.insert(to_string(e[0]) + " " + to_string(e[1]));

adj[e[0]].push_back(e[1]);

adj[e[1]].push_back(e[0]);

}

int res = 0;

stack<int> st;

st.push(0);

visited[0] = true;

while (!st.empty()) {

int root = st.top();

st.pop();

for (auto c : adj[root])

if (!visited[c]) {

if (!us.count(to_string(c) + " " + to_string(root))) res++;

visited[c] = true;

st.push(c);

}

return res;

}

};

diff --git a/Problems/1472.cpp b/Problems/1472.cpp

@@ -0,0 +1,31 @@

class BrowserHistory {

struct Node {

Node *next, *prev;

string val;

Node(string val = "#", Node *prev = nullptr, Node *next = nullptr)

: val(val), prev(prev), next(next) {}

};

Node *head = nullptr, *tail = nullptr, *crnt = nullptr;

public:

BrowserHistory(string homepage) { crnt = head = tail = new Node(homepage); }

void visit(string url) {

for (Node *t = tail->next; t;) {

Node *tmp = t;

t = t->next;

delete tmp;

}

crnt = tail = tail->next = new Node(url, tail, nullptr);

}

string back(int steps) {

while (steps-- && crnt->prev) tail = crnt = crnt->prev;

return crnt->val;

}

string forward(int steps) {

while (steps-- && crnt->next) tail = crnt = crnt->next;

return crnt->val;

}

};

diff --git a/Problems/1480.cpp b/Problems/1480.cpp

@@ -0,0 +1,9 @@

class Solution {

public:

vector<int> runningSum(vector<int> &nums) {

vector<int> res;

int acc = 0;

for (auto i : nums) res.push_back(acc += i);

return res;

}

};

diff --git a/Problems/1544.cpp b/Problems/1544.cpp

@@ -0,0 +1,14 @@

class Solution {

public:

string makeGood(string s) {

int i = 0;

while (i < s.size())

if (s[i] != s[i + 1] && toupper(s[i]) == toupper(s[i + 1])) {

s.erase(i, 2);

i = max(0, i - 1);

} else {

i++;

}

return s;

}

};

diff --git a/Problems/1557.cpp b/Problems/1557.cpp

@@ -0,0 +1,14 @@

class Solution {

public:

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>> &edges) {

vector<int> root(n), res;

iota(root.begin(), root.end(), 0);

for (auto &p : edges) root[p[1]] = p[0];

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

if (i == root[i]) res.push_back(i);

return res;

}

};

diff --git a/Problems/1584.cpp b/Problems/1584.cpp

@@ -0,0 +1,58 @@

class UnionFind {

vector<int> root, rank;

public:

UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }

int find(int x) {

while (x != root[x]) x = root[x] = root[root[x]];

return x;

}

void join(int x, int y) {

x = find(x), y = find(y);

if (x != y) {

if (rank[x] > rank[y]) swap(x, y);

root[x] = y;

rank[y] += rank[x];

}

};

struct edge {

int p1, p2;

int cost;

edge(int p1 = -1, int p2 = -1, int cost = INT_MAX)

: p1(p1), p2(p2), cost(cost) {}

bool operator()(const edge &e1, const edge &e2) { return e1.cost > e2.cost; }

};

class Solution {

int distance(vector<int> &p1, vector<int> &p2) {

return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1]);

}

public:

int minCostConnectPoints(vector<vector<int>> &points) {

UnionFind uf(points.size() * (points.size() + 1) / 2);

priority_queue<edge, vector<edge>, edge> pq;

for (int i = 0; i < points.size(); i++)

for (int j = i + 1; j < points.size(); j++)

pq.push(edge(i, j, distance(points[i], points[j])));

int num = 1, res = 0;

while (num < points.size()) {

edge e = pq.top();

pq.pop();

if (uf.find(e.p1) != uf.find(e.p2)) {

res += e.cost;

uf.join(e.p1, e.p2);

num++;

}

return res;

}

};

diff --git a/Problems/1609.cpp b/Problems/1609.cpp

@@ -0,0 +1,28 @@

class Solution {

public:

bool isEvenOddTree(TreeNode *root) {

if (!root) return false;

queue<TreeNode *> q;

TreeNode *de = new TreeNode(0);

TreeNode *dd = new TreeNode(INT_MAX);

q.push(root);

for (int lvl = 0; !q.empty(); lvl++) {

TreeNode *p = (lvl % 2 == 0) ? de : dd;

for (int t = q.size(); t > 0; t--) {

TreeNode *root = q.front();

q.pop();

if (lvl % 2 == 0) {

if (root->val % 2 != 1 || root->val <= p->val) return false;

} else {

if (root->val % 2 != 0 || root->val >= p->val) return false;

}

p = root;

if (root->left) q.push(root->left);

if (root->right) q.push(root->right);

}

return true;

}

};

diff --git a/Problems/1646.cpp b/Problems/1646.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

int getMaximumGenerated(int n) {

if (n == 0) return 0;

if (n == 1) return 1;

vector<int> vec(n + 1);

vec[0] = 0;

vec[1] = 1;

int maxi = 0;

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

vec[i] = vec[i / 2];

if (i % 2) vec[i] += vec[i / 2 + 1];

maxi = max(vec[i], maxi);

}

return maxi;

}

};

diff --git a/Problems/1669.cpp b/Problems/1669.cpp

@@ -0,0 +1,13 @@

class Solution {

public:

ListNode *mergeInBetween(ListNode *list1, int a, int b, ListNode *list2) {

ListNode *ap, *bp;

a--;

for (ap = list1; a; a--, b--) ap = ap->next;

for (bp = ap; b; b--) bp = bp->next;

ap->next = list2;

while (ap->next) ap = ap->next;

ap->next = bp->next;

return list1;

}

};

diff --git a/Problems/1672.cpp b/Problems/1672.cpp

@@ -0,0 +1,8 @@

class Solution {

public:

int maximumWealth(vector<vector<int>> &accounts) {

vector<int> w;

for (auto &v : accounts) w.push_back(accumulate(v.begin(), v.end(), 0));

return *max_element(w.begin(), w.end());

}

};

diff --git a/Problems/1696.cpp b/Problems/1696.cpp

@@ -0,0 +1,15 @@

class Solution {

public:

int maxResult(vector<int> &nums, int k) {

vector<int> dp(size(nums));

dp[0] = nums[0];

deque<int> q{0};

for (int i = 1; i < size(nums); i++) {

if (q.front() < i - k) q.pop_front();

dp[i] = nums[i] + dp[q.front()];

while (!q.empty() && dp[q.back()] <= dp[i]) q.pop_back();

q.push_back(i);

}

return dp.back();

}

};

diff --git a/Problems/1700.cpp b/Problems/1700.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

int countStudents(vector<int> &students, vector<int> &sandwiches) {

vector<int> count(2, 0);

queue<int> q;

for (int s : students) {

q.push(s);

count[s]++;

}

for (int i = 0; i < sandwiches.size() && count[sandwiches[i]] != 0; q.pop())

if (q.front() == sandwiches[i]) {

count[sandwiches[i]]--;

i++;

} else

q.push(q.front());

return q.size();

}

};

diff --git a/Problems/1704.cpp b/Problems/1704.cpp

@@ -0,0 +1,14 @@

class Solution {

bool is_vowel(char c) {

return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';

}

public:

bool halvesAreAlike(string s) {

int i = 0, j = s.size() / 2, count = 0;

while (j < s.size())

count += is_vowel(tolower(s[i++])) - is_vowel(tolower(s[j++]));

;

return !count;

}

};

diff --git a/Problems/1706.cpp b/Problems/1706.cpp

@@ -0,0 +1,29 @@

class Solution {

int m, n;

bool valid_column(int column) { return column >= 0 && column < n; }

int simulate(int column, vector<vector<int>> &grid) {

int row = 0;

while (row < m) {

int type = grid[row][column];

int nextc = column + type;

if (valid_column(nextc) && grid[row][nextc] == type) {

row++;

column = nextc;

} else

return -1;

}

return column;

}

public:

vector<int> findBall(vector<vector<int>> &grid) {

m = grid.size();

n = grid[0].size();

vector<int> res;

for (int i = 0; i < n; i++) res.push_back(simulate(i, grid));

return res;

}

};

diff --git a/Problems/1791.cpp b/Problems/1791.cpp

@@ -0,0 +1,18 @@

class Solution {

public:

int findCenter(vector<vector<int>> &edges) {

unordered_set<int> us;

for (auto &p : edges) {

if (us.count(p[0]))

return p[0];

else

us.insert(p[0]);

if (us.count(p[1]))

return p[1];

else

us.insert(p[1]);

}

return -1;

}

};

diff --git a/Problems/1823.cpp b/Problems/1823.cpp

@@ -0,0 +1,25 @@

class Solution {

struct Node {

Node *next;

int val;

Node(int val = -1, Node *next = nullptr) : val(val), next(next) {}

};

public:

int findTheWinner(int n, int k) {

Node *h, *t;

t = h = new Node();

for (int i = 1; i <= n; i++) t = t->next = new Node(i);

t->next = h->next;

delete h;

while (t != t->next) {

for (int c = k - 1; c; c--) t = t->next;

h = t->next;

t->next = t->next->next;

delete h;

}

return t->val;

}

};

diff --git a/Problems/1926.cpp b/Problems/1926.cpp

@@ -0,0 +1,43 @@

class Solution {

int m, n;

vector<int> ox = {-1, 1, 0, 0};

vector<int> oy = {0, 0, -1, 1};

bool is_valid(int x, int y) { return x >= 0 && x < m && y >= 0 && y < n; }

bool is_exit(int x, int y) {

return x == 0 || x == m - 1 || y == 0 || y == n - 1;

}

public:

int nearestExit(vector<vector<char>> &maze, vector<int> &entrance) {

m = maze.size();

n = maze[0].size();

queue<pair<int, int>> q;

q.push({entrance[0], entrance[1]});

for (int lvl = 0; !q.empty(); lvl++) {

for (int t = q.size(); t > 0; t--) {

int x = q.front().first;

int y = q.front().second;

q.pop();

// cout << x << " " << y << endl;

if (maze[x][y] == '+') continue;

if ((x != entrance[0] || y != entrance[1]) && is_exit(x, y)) return lvl;

maze[x][y] = '+';

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

int nx = x + ox[i];

int ny = y + oy[i];

if (is_valid(nx, ny) && maze[nx][ny] != '+') q.push({nx, ny});

}

return -1;

}

};

diff --git a/Problems/1971.cpp b/Problems/1971.cpp

@@ -0,0 +1,33 @@

class UnionFind {

vector<int> root, rank;

public:

UnionFind(int n) : root(n), rank(n, 1) { iota(root.begin(), root.end(), 0); }

int find(int x) {

while (x != root[x]) x = root[x] = root[root[x]];

return x;

}

void join(int x, int y) {

x = find(x), y = find(y);

if (x != y) {

if (rank[x] > rank[y]) swap(x, y);

root[x] = y;

rank[y] += rank[x];

}

};

class Solution {

public:

bool validPath(int n, vector<vector<int>> &edges, int source,

int destination) {

UnionFind uf(n);

for (auto &p : edges) uf.join(p[0], p[1]);

return uf.find(source) == uf.find(destination);

}

};

diff --git a/Problems/2073.cpp b/Problems/2073.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

int timeRequiredToBuy(vector<int> &tickets, int k) {

int time = 0;

for (int i = 0; i < tickets.size(); i++)

if (tickets[i] >= tickets[k])

time += tickets[k] - (i > k);

else

time += tickets[i];

return time;

}

};

diff --git a/Problems/2095.cpp b/Problems/2095.cpp

@@ -0,0 +1,18 @@

class Solution {

ListNode *pre_mid(ListNode *head) {

ListNode *slow = head, *fast = head->next;

while (fast && fast->next && fast->next->next) {

slow = slow->next;

fast = fast->next->next;

}

return slow;

}

public:

ListNode *deleteMiddle(ListNode *head) {

if (!head || !head->next) return nullptr;

ListNode *pre = pre_mid(head);

pre->next = pre->next->next;

return head;

}

};

diff --git a/Problems/2130.cpp b/Problems/2130.cpp

@@ -0,0 +1,34 @@

class Solution {

ListNode *pre_mid(ListNode *head) {

ListNode *slow = head, *fast = head;

while (fast->next && fast->next->next) {

slow = slow->next;

fast = fast->next->next;

}

return slow;

}

ListNode *reverse(ListNode *head) {

ListNode *p = head, *q = nullptr, *r = nullptr;

while (p) {

r = q;

q = p;

p = p->next;

q->next = r;

}

return q;

}

public:

int pairSum(ListNode *head) {

ListNode *pre = pre_mid(head);

ListNode *head2 = reverse(pre->next);

int maxi = INT_MIN;

for (ListNode *p = head, *q = head2; q; p = p->next, q = q->next)

maxi = max(p->val + q->val, maxi);

pre->next = reverse(head2);

return maxi;

}

};

diff --git a/Problems/2131.cpp b/Problems/2131.cpp

@@ -0,0 +1,26 @@

class Solution {

public:

int longestPalindrome(vector<string> &words) {

unordered_map<string, int> um;

for (string &w : words) um[w]++;

bool odd = false;

int res = 0;

for (const auto &[s, count] : um) {

if (!count) continue;

if (s[0] == s[1]) {

if (count % 2 == 0) {

res += count;

} else {

res += count - 1;

odd = true;

}

} else if (s[0] < s[1] && um.count({s[1], s[0]})) {

res += min(count, um[{s[1], s[0]}]) * 2;

}

if (odd) res++;

return res * 2;

}

};

diff --git a/Problems/2181.cpp b/Problems/2181.cpp

@@ -0,0 +1,20 @@

class Solution {

public:

ListNode *mergeNodes(ListNode *head) {

if (!head) return nullptr;

for (ListNode *p = head; p->next->next;)

if (p->val == 0 && p->next->val != 0 && p->next->next->val != 0) {

p->next->next->val += p->next->val;

p->next = p->next->next;

} else

p = p->next;

for (ListNode *p = head; p->next;)

if (!p->next->val)

p->next = p->next->next;

else

p = p->next;

return head->val ? head : head->next;

}

};

diff --git a/Problems/2235.cpp b/Problems/2235.cpp

@@ -0,0 +1,4 @@

class Solution {

public:

int sum(int num1, int num2) { return num1 + num2; }

};

diff --git a/Problems/2236.cpp b/Problems/2236.cpp

@@ -0,0 +1,6 @@

class Solution {

public:

bool checkTree(TreeNode *root) {

return root->val == root->left->val + root->right->val;

}

};

diff --git a/Problems/2285.cpp b/Problems/2285.cpp

@@ -0,0 +1,21 @@

class Solution {

typedef pair<int, int> pii;

public:

long long maximumImportance(int n, vector<vector<int>> &roads) {

vector<int> count(n, 0);

for (auto &e : roads) {

count[e[0]]++;

count[e[1]]++;

}

sort(count.begin(), count.end());

long long res = 0ll;

for (int i = 0; i < n; i++) res += (i + 1ll) * count[i];

return res;

}

};

diff --git a/Problems/2326.cpp b/Problems/2326.cpp

@@ -0,0 +1,45 @@

class Solution {

pair<int, int> offset[4] = {

{ 0, 1},

{ 1, 0},

{ 0, -1},

{-1, 0}

};

int limit_offset[4] = {1, -1, -1, 1};

int limit[4] = {0, 0, 0, 0};

int &m = limit[2], &n = limit[1];

bool valid(int i, int j) {

return i >= limit[0] && i <= m && j >= limit[3] && j <= n;

}

public:

vector<vector<int>> spiralMatrix(int dm, int dn, ListNode *head) {

vector<vector<int>> res(dm, vector<int>(dn, -1));

int direction = 0;

int cnt = 0;

int size;

int i = 0, j = 0;

m = dm - 1;

n = dn - 1;

size = (m + 1) * (n + 1);

while (true) {

res[i][j] = head->val;

head = head->next;

if (!head || ++cnt == size) break;

if (!valid(i + offset[direction].first, j + offset[direction].second)) {

limit[direction] += limit_offset[direction];

direction = (direction + 1) % 4;

}

i += offset[direction].first;

j += offset[direction].second;

}

return res;

}

};

diff --git a/Problems/2331.cpp b/Problems/2331.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

bool evaluateTree(TreeNode *root) {

switch (root->val) {

case 0:

case 1: return root->val;

case 2: return evaluateTree(root->left) || evaluateTree(root->right);

case 3: return evaluateTree(root->left) && evaluateTree(root->right);

default: return false;

}

};

diff --git a/Problems/2390.cpp b/Problems/2390.cpp

@@ -0,0 +1,19 @@

class Solution {

public:

string removeStars(string s) {

stack<char> st;

for (char c : s)

if (c == '*')

st.pop();

else

st.push(c);

string res = "";

while (!st.empty()) {

res += st.top();

st.pop();

}

reverse(res.begin(), res.end());

return res;

}

};

diff --git a/Problems/24.cpp b/Problems/24.cpp

@@ -0,0 +1,14 @@

class Solution {

public:

ListNode *swapPairs(ListNode *head) {

ListNode *d = new ListNode(-1, head);

for (ListNode *p = d; p->next && p->next->next;) {

ListNode *t = p->next;

p->next = p->next->next;

t->next = p->next->next;

p->next->next = t;

p = t;

}

return d->next;

}

};

diff --git a/Problems/2461.cpp b/Problems/2461.cpp

@@ -0,0 +1,26 @@

class Solution {

public:

long long maximumSubarraySum(vector<int> &nums, int k) {

long long maxi = LLONG_MIN;

unordered_set<int> us;

int i = 0;

long long sum = 0ll;

for (int j = 0; j <= size(nums);) {

while (us.find(nums[j]) != us.end()) {

sum -= nums[i];

us.erase(nums[i++]);

}

if (j - i < k) {

sum += nums[j];

us.insert(nums[j++]);

}

if (j > size(nums)) break;

if (j - i == k) {

maxi = max(sum, maxi);

sum -= nums[i];

us.erase(nums[i++]);

}

return maxi == LLONG_MIN ? 0 : maxi;

}

};

diff --git a/Problems/2465.cpp b/Problems/2465.cpp

@@ -0,0 +1,12 @@

class Solution {

public:

int distinctAverages(vector<int> &nums) {

unordered_set<int> us;

sort(nums.begin(), nums.end());

for (int i = 0, j = nums.size() - 1; i < j; i++, j--)

us.insert(nums[i] + nums[j]);

return us.size();

}

};

diff --git a/Problems/2466.cpp b/Problems/2466.cpp

@@ -0,0 +1,14 @@

class Solution {

public:

int countGoodStrings(int low, int high, int zero, int one) {

vector<int> dp(high + 1, 0);

dp[0] = 1;

int res = 0, mod = 1e9 + 7;

for (int i = 1; i <= high; i++) {

if (i >= zero) dp[i] = (dp[i] + dp[i - zero]) % mod;

if (i >= one) dp[i] = (dp[i] + dp[i - one]) % mod;

if (i >= low) res = (res + dp[i]) % mod;

}

return res;

}

};

diff --git a/Problems/2467.cpp b/Problems/2467.cpp

@@ -0,0 +1,72 @@

class Solution {

vector<vector<int>> adj;

vector<bool> visited;

vector<int> distance, parent;

void distance_parent(int start) {

stack<pair<int, int>> st;

st.push({start, 0});

parent[start] = 0;

while (!st.empty()) {

int p = st.top().first;

int d = st.top().second;

st.pop();

distance[p] = d;

for (int c : adj[p])

if (distance[c] == -1) {

parent[c] = p;

st.push({c, d + 1});

}

int profit(int start, vector<int> &amount) {

stack<pair<int, int>> st;

st.push({start, 0});

int maxi = INT_MIN;

while (!st.empty()) {

int count = 0;

int root = st.top().first;

int value = st.top().second + amount[root];

st.pop();

visited[root] = true;

for (int c : adj[root])

if (!visited[c]) {

count++;

st.push({c, value});

}

if (!count) maxi = max(value, maxi);

}

return maxi;

}

public:

int mostProfitablePath(vector<vector<int>> &edges, int bob,

vector<int> &amount) {

int size = amount.size();

adj.resize(size, vector<int>());

distance.resize(size, -1);

parent.resize(size, -1);

visited.resize(size, false);

for (auto &e : edges) {

adj[e[0]].push_back(e[1]);

adj[e[1]].push_back(e[0]);

}

distance_parent(0);

for (int current = bob, bob_distance = 0; current; bob_distance++) {

if (distance[current] > bob_distance)

amount[current] = 0;

else if (distance[current] == bob_distance)

amount[current] /= 2;

current = parent[current];

}

return profit(0, amount);

}

};

diff --git a/Problems/841.cpp b/Problems/841.cpp

@@ -0,0 +1,21 @@

class Solution {

public:

bool canVisitAllRooms(vector<vector<int>> &rooms) {

unordered_set<int> us;

queue<int> q;

q.push(0);

us.insert(0);

while (!q.empty()) {

int room = q.front();

q.pop();

for (int key : rooms[room]) {

if (!us.count(key)) {

us.insert(key);

q.push(key);

}

return us.size() == rooms.size();

}

};

diff --git a/README.md b/README.md

@@ -0,0 +1,189 @@

# Leetcode

# Problems

0001. (Easy) [Two Sum](Problems/0001.cpp)

0002. (Medium) [Add Two Numbers](Problems/0002.cpp)

0003. (Mecium) [Longest Substring Without Repeating Characters](Problems/0003.cpp)

0012. (Medium) [Integer to Roman](Problems/0012.cpp)

0013. (Easy) [Roman to Integer](Problems/0013.cpp)

0014. (Easy) [Longest Common Prefix](Problems/0014.cpp)

0019. (Medium) [Remove Nth Node From the End of List](Problems/0019.cpp)

0020. (Easy) [Valid Parentheses](Problems/0020.cpp)

0021. (Easy) [Merge Two Sorted Lists](Problems/0021.cpp)

0024. (Medium) [Swap Nodes in Pairs](Problems/0024.cpp)

0026. (Easy) [Remove Duplicates from Sorted Array](Problems/0026.cpp)

0027. (Easy) [Remove Element](Problems/0027.cpp)

0028. (Medium) [Find the Index of the First Occurrence in a String](Problems/0028.cpp)

0036. (Mecium) [Valid Sudoku](Problems/0036.cpp)

0043. (Medium) [Multiply Strings](Problems/0043.cpp)

0054. (Medium) [Spiral Matrix](Problems/0054.cpp)

0059. (Medium) [Spiral Matrix II](Problems/0059.cpp)

0061. (Medium) [Rotate List](Problems/0061.cpp)

0066. (Easy) [Plus One](Problems/0066.cpp)

0067. (Easy) [Add Binary](Problems/0067.cpp)

0070. (Easy) [Climbing Stairs](Problems/0070.cpp)

0083. (Easy) [Remove Duplicates from Sorted List](Problems/0083.cpp)

0088. (Easy) [Merge Sorted Array](Problems/0088.cpp)

0094. (Easy) [Binary Tree Inorder Traversal](Problems/0094.cpp)

0100. (Easy) [Same Tree](Problems/0100.cpp)

0101. (Easy) [Symmetric Tree](Problems/0101.cpp)

0102. (Medium) [Binary Tree Level Order Traversal](Problems/0102.cpp)

0103. (Medium) [Binary Tree Zigzag Level Order Traversal](Problems/0103.cpp)

0104. (Easy) [Maximum Depth of Binary Tree](Problems/0104.cpp)

0107. (Medium) [Binary Tree Level Order Traversal II](Problems/0107.cpp)

0111. (Easy) [Minimum Depth of Binary Tree](Problems/0111.cpp)

0112. (Easy) [Path Sum](Problems/0112.cpp)

0114. (Medium) [Flatten Binary Tree to Linked List](Problems/0114.cpp)

0116. (Medium) [Populating Next Right Pointers in Each Node](Problems/0116.cpp)

0117. (Medium) [Populating Next Right Pointers in Each Node II](Problems/0117.cpp)

0118. (Easy) [Pascal's Triangle](Problems/0118.cpp)

0119. (Easy) [Pascal's Triangle II](Problems/0119.cpp)

0121. (Easy) [Best Time to Buy and Sell Stock](Problems/0121.cpp)

0133. (Medium) [Clone Graph](Problems/0133.cpp)

0138. (Medium) [Copy List with Random Pointer](Problems/0138.cpp)

0141. (Easy) [Linked List Cycle](Problems/0141.cpp)

0142. (Medium) [Linked List Cycle II](Problems/0142.cpp)

0144. (Medium) [Binary Tree Preorder Traversal](Problems/0144.cpp)

0145. (Easy) [Binary Tree Postorder Traversal](Problems/0145.cpp)

0150. (Medium) [Evaluate Reverse Polish Notation](Problems/0150.cpp)

0151. (Medium) [Reverse Words in a String](Problems/0151.cpp)

0160. (Easy) [Intersection of Two Linked Lists](Problems/0160.cpp)

0167. (Medium) [Two Sum II - Input Array Is Sorted](Problems/0167.cpp)

0189. (Medium) [Rotate Array](Problems/0189.cpp)

0199. (Medium) [Binary Tree Right Side View](Problems/0199.cpp)

0200. (Medium) [Number of Islands](Problems/0200.cpp)

0203. (Easy) [Remove Linked List Elements](Problems/0203.cpp)

0206. (Easy) [Reverse Linked List](Problems/0206.cpp)

0209. (Medium) [Minimum Size Subarray Sum](Problems/0209.cpp)

0222. (Medium) [Count Complete Tree Nodes](Problems/0222.cpp)

0223. (Mecium) [Rectangle Area](Problems/0223.cpp)

0226. (Easy) [Invert Binary Tree](Problems/0226.cpp)

0234. (Easy) [Palindrome Linked List](Problems/0234.cpp)

0236. (Medium) [Lowest Common Ancestor of a Binary Tree](Problems/0236.cpp)

0237. (Medium) [Delete Node in a Linked List](Problems/0237.cpp)

0257. (Easy) [Binary Tree Paths](Problems/0257.cpp)

0263. (Easy) [Ugly Number](Problems/0263.cpp)

0279. (Mecium) [Perfect Squares](Problems/0279.cpp)

0283. (Easy) [Move Zeroes](Problems/0283.cpp)

0328. (Medium) [Odd Even Linked List](Problems/0328.cpp)

0338. (Easy) [Counting Bits](Problems/0338.cpp)

0344. (Easy) [Reverse String](Problems/0344.cpp)

0345. (Easy) [Reverse Vowels of a String](Problems/0345.cpp)

0374. (Easy) [Guess Number Higher or Lower](Problems/0374.cpp)

0383. (Easy) [Ransom Note](Problems/0383.cpp)

0387. (Easy) [First Unique Character in a String](Problems/0387.cpp)

0392. (Easy) [Is Subsequence](Problems/0392.cpp)

0394. (Medium) [Decode String](Problems/0394.cpp)

0404. (Easy) [Sum of Left Leaves](Problems/0404.cpp)

0412. (Easy) [Fizz Buzz](Problems/0412.cpp)

0414. (Easy) [Third Maximum Number](Problems/0414.cpp)

0415. (Easy) [Add Strings](Problems/0415.cpp)

0429. (Medium) [N-ary Tree Level Order Traversal](Problems/0429.cpp)

0430. (Medium) [Flatten a Multilevel Doubly Linked list](Problems/0430.cpp)

0433. (Medium) [Minimum Genetic Mutation](Problems/0433.cpp)

0445. (Medium) [Add Two Numbers II](Problems/0445.cpp)

0448. (Easy) [Find All Numbers Disappeared in an Array](Problems/0448.cpp)

0485. (Easy) [Max Consecutive Ones](Problems/0485.cpp)

0496. (Medium) [Next Greater Element I](Problems/0496.cpp)

0498. (Medium) [Diagonal Traverse](Problems/0498.cpp)

0503. (Medium) [Next Greater Element II](Problems/0503.cpp)

0509. (Easy) [Fibonacci Number](Problems/0509.cpp)

0543. (Easy) [Diameter of Binary Tree](Problems/0543.cpp)

0547. (Mecium) [Number of Provinces](Problems/0547.cpp)

0557. (Easy) [Reverse Words in a String III](Problems/0557.cpp)

0559. (Easy) [Maximum Depth of N-ary Tree](Problems/0559.cpp)

0561. (Easy) [Array Partition](Problems/0561.cpp)

0563. (Easy) [Binary Tree Tilt](Problems/0563.cpp)

0572. (Easy) [Subtree of Another Tree](Problems/0572.cpp)

0589. (Easy) [N-ary Tree Preorder Traversal](Problems/0589.cpp)

0590. (Easy) [N-ary Tree Postorder Traversal](Problems/0590.cpp)

0606. (Easy) [Construct String from Binary Tree ](Problems/0606.cpp)

0617. (Easy) [Merge Two Binary Trees](Problems/0617.cpp)

0637. (Easy) [Average of Levels in Binary Tree](Problems/0637.cpp)

0684. (Mecium) [Redundant Connection](Problems/0684.cpp)

0707. (Medium) [Design Linked List](Problems/0707.cpp)

0724. (Easy) [Find Pivot Index](Problems/0724.cpp)

0733. (Easy) [Flood Fill](Problems/0733.cpp)

0739. (Medium) [Daily Temperatures](Problems/0739.cpp)

0746. (Easy) [Min Cost Climbing Stairs](Problems/0746.cpp)

0747. (Easy) [Largest Number At Least Twice of Others](Problems/0747.cpp)

0752. (Medium) [Open the Lock](Problems/0752.cpp)

0797. (Mecium) [All Paths From Source to Target](Problems/0797.cpp)

0841. (Medium) [Keys and Rooms](Problems/0841.cpp)

0844. (Easy) [Backspace String Compare](Problems/0844.cpp)

0872. (Easy) [Leaf-Similar Trees](Problems/0872.cpp)

0876. (Easy) [Middle of the Linked List](Problems/0876.cpp)

0901. (Medium) [Online Stock Span](Problems/0901.cpp)

0905. (Easy) [Sort Array By Parity](Problems/0905.cpp)

0933. (Easy) [Number of Recent Calls](Problems/0933.cpp)

0941. (Easy) [Valid Mountain Array](Problems/0941.cpp)

0947. (Medium) [Most Stones Removed with Same Row or Column](Problems/0947.cpp)

0950. (Medium) [Reveal Cards In Increasing Order](Problems/0950.cpp)

0959. (Mecium) [Regions Cut By Slashes](Problems/0959.cpp)

0965. (Easy) [Univalued Binary Tree](Problems/0965.cpp)

0977. (Easy) [Squares of a Sorted Array](Problems/0977.cpp)

0989. (Easy) [Add to Array-Form of Integer](Problems/0989.cpp)

0993. (Easy) [Cousins in Binary Tree](Problems/0993.cpp)

0997. (Easy) [Find the Town Judge](Problems/0997.cpp)

1019. (Medium) [Next Greater Node In Linked List](Problems/1019.cpp)

1022. (Easy) [Sum of Root To Leaf Binary Numbers](Problems/1022.cpp)

1047. (Easy) [Remove All Adjacent Duplicates In String](Problems/1047.cpp)

1051. (Easy) [Height Checker](Problems/1051.cpp)

1089. (Easy) [Duplicate Zeros](Problems/1089.cpp)

1095. (Easy) [Find Numbers with Even Number of Digits](Problems/1095.cpp)

1099. (Easy) [Replace Elements with Greatest Element on Right Side](Problems/1099.cpp)

1137. (Easy) [N-th Tribonacci Number](Problems/1137.cpp)

1209. (Medium) [Remove All Adjacent Duplicates in String II](Problems/1209.cpp)

1290. (Easy) [Convert Binary Number in a Linked List to Integer](Problems/1290.cpp)

1319. (Mecium) [Number of Operations to Make Network Connected](Problems/1319.cpp)

1323. (Easy) [Maximum 69 Number](Problems/1323.cpp)

1337. (Easy) [The K Weakest Rows in a Matrix](Problems/1337.cpp)

1342. (Easy) [Number of Steps to Reduce a Number to Zero](Problems/1342.cpp)

1346. (Easy) [Check if N and Its Double Exist](Problems/1346.cpp)

1379. (Easy) [Find a Corresponding Node of a Binary Tree in a Clone of That Tree ](Problems/1379.cpp)

1466. (Mecium) [Reorder Routes to Make All Paths Lead to the City Zero](Problems/1466.cpp)

1472. (Medium) [Design Browser History ](Problems/1472.cpp)

1480. (Easy) [Running Sum of 1d Array](Problems/1480.cpp)

1544. (Easy) [Make The String Great](Problems/1544.cpp)

1557. (Mecium) [Minimum Number of Vertices to Reach All Nodes](Problems/1557.cpp)

1584. (Mecium) [Min Cost to Connect All Points](Problems/1584.cpp)

1609. (Medium) [Even Odd Tree](Problems/1609.cpp)

1646. (Easy) [Get Maximum in Generated Array](Problems/1646.cpp)

1669. (Medium) [Merge In Between Linked Lists](Problems/1669.cpp)

1672. (Easy) [Richest Customer Wealth](Problems/1672.cpp)

1696. (Medium) [Jump Game VI](Problems/1696.cpp)

1700. (Easy) [Number of Students Unable to Eat Lunch](Problems/1700.cpp)

1704. (Easy) [Determine if String Halves Are Alike](Problems/1704.cpp)

1706. (Medium) [Where Will the Ball Fall](Problems/1706.cpp)

1791. (Easy) [Find Center of Star Graph](Problems/1791.cpp)

1823. (Medium) [Find the Winner of the Circular Game](Problems/1823.cpp)

1926. (Mecium) [Nearest Exit from Entrance in Maze](Problems/1926.cpp)

1971. (Easy) [Find if Path Exists in Graph](Problems/1971.cpp)

2073. (Easy) [Time Needed to Buy Tickets](Problems/2073.cpp)

2095. (Medium) [Delete the Middle Node of a Linked List](Problems/2095.cpp)

2130. (Medium) [Maximum Twin Sum of a Linked List](Problems/2130.cpp)

2131. (Medium) [Longest Palindrome by Concatenating Two Letter Words](Problems/2131.cpp)

2181. (Medium) [Merge Nodes in Between Zeros](Problems/2181.cpp)

2235. (Easy) [Add Two Integers](Problems/2235.cpp)

2236. (Easy) [Root Equals Sum of Children](Problems/2236.cpp)

2285. (Mecium) [Maximum Total Importance of Roads](Problems/2285.cpp)

2326. (Medium) [Spiral Matrix IV](Problems/2326.cpp)

2331. (Easy) [Evaluate Boolean Binary Tree](Problems/2331.cpp)

2390. (Medium) [Removing Stars From a String](Problems/2390.cpp)

2465. (Easy) [Number of Distinct Averages](Problems/2465.cpp)

2466. (Medium) [Count Ways To Build Good Strings](Problems/2466.cpp)

2467. (Medium) [Most Profitable Path in a Tree](Problems/2467.cpp)

2469. (Hard) [Find Median from Data Stream](Problems/0295.cpp)

1367. (Medium) [Linked List in Binary Tree ](Problems/1367.cpp)

0556. (Medium) [Next Greater Element III](Problems/0556.cpp)

DNF:

0494. (Medium) [Target Sum](Problems/0494.cpp)

0402. (Medium) [Remove K Digits](Problems/0402.cpp)

0129. (Medium) [Sum Root to Leaf Numbers](Problems/0129.cpp)

0542. (Medium) [01 Matrix](Problems/0542.cpp)

0662. (Medium) [Maximum Width of Binary Tree](Problems/0662.cpp)

1438. (Medium) [Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit](Problems/0143.cpp)

2461. (Medium) [Maximum Sum of Distinct Subarrays With Length K](Problems/2461.cpp)