Cheat sheet Question List
Below are the must-known data structures with all basic functions of any programming language given. Here I am currently listing the c++ based functions for below mentioned Data Structures.
Topics Mentioned below
A.) String
B.) XOR operations
C.) Topological Sort
D.) Buy & Sell
E.) Binary Search
F.) Maximum Sum in Array/Tress: Not Adjacent indexes
G.) Interval
H.) Coin Change
I.) Reverse Linked List
J.) Trees
String Functions Code Block
string a = "123"; string b = "123 456"; string c= " 123 "; string d = " 123 a23"; string e = " a 5432"; cout<
int a = 123; char b = 'A'; cout<
char a = 'T'; cout<< std:string(1,a) ; // "T"
//istringstream (use for input stream), ostringstream (use for output stream), stringstream(use for input/output both) string str = " bitsofjarvis ! # #$% blog is gooood "; istringstream ss(str); string word; while(ss >> word){ cout<whereas you where waiting a write only object, you will not be happy ;-) source : stackoverflow
string A = "I AM GOOD" , B = "YES I AM"; istringstream combined(A + " " + B); string word; while (getline(combined, word, ' ')){ cout<
tolower(c); OR for(auto &c : str) c = tolower(c);
str.substr(startIndex , length);
str.find("@gmail.com"); OR std::string str ("There are two needles in this haystack with needles."); std::string str2 ("needle"); // different member versions of find in the same order as above: std::size_t found = str.find(str2); if (found!=std::string::npos) std::cout << "first 'needle' found at: " << found << '\n'; found=str.find("needles are small",found+1,6); if (found!=std::string::npos) std::cout << "second 'needle' found at: " << found << '\n'; found=str.find("haystack"); if (found!=std::string::npos) std::cout << "'haystack' also found at: " << found << '\n'; found=str.find('.'); if (found!=std::string::npos) std::cout << "Period found at: " << found << '\n'; // let's replace the first needle: str.replace(str.find(str2),str2.length(),"preposition"); std::cout << str << '\n'; //output : to be, or not to be: that is the question...
str.erase (10,8); OR str.erase (str.begin()+5, str.end()-9);
std::string str="to be question"; std::string str2="the "; std::string str3="or not to be"; std::string::iterator it; // used in the same order as described above: str.insert(6,str2); // to be (the )question str.insert(6,str3,3,4); // to be (not )the question str.insert(10,"that is cool",8); // to be not (that is )the question str.insert(10,"to be "); // to be not (to be )that is the question str.insert(15,1,':'); // to be not to be(:) that is the question it = str.insert(str.begin()+5,','); // to be(,) not to be: that is the question str.insert (str.end(),3,'.'); // to be, not to be: that is the question(...) str.insert (it+2,str3.begin(),str3.begin()+3); // (or ) std::cout << str << '\n'; //output:to be, or not to be: that is the question...
sort(s.begin() , s.end());
string sentence = " This site is Awsm GOOOD "; stringstream ss(sentence); string words; while(ss >> words){ cout<
Stack Functions
#include <iostream> // std::cout #include <stack> // std::stack int main () { std::stack<int> mystack; for (int i=0; i<5; ++i){ mystack.push(i); } std::cout << "Popping out elements..."; while (!mystack.empty()) { std::cout << ' ' << mystack.top(); mystack.pop(); } std::cout << '\n'; return 0; }
// stack::push/pop #include <iostream> // std::cout #include <stack> // std::stack int main () { std::stack<int> mystack; for (int i=0; i<5; ++i) mystack.push(i); std::cout << "Popping out elements..."; while (!mystack.empty()) { std::cout << ' ' << mystack.top(); mystack.pop(); } std::cout << '\n'; return 0; }
Queue Functions
// queue::push/pop #include// std::cin, std::cout #include // std::queue int main () { std::queue myqueue; int myint; std::cout << "Please enter some integers (enter 0 to end):\n"; do { std::cin >> myint; myqueue.push (myint); } while (myint); std::cout << "myqueue contains: "; while (!myqueue.empty()) { std::cout << ' ' << myqueue.front(); myqueue.pop(); } std::cout << '\n'; return 0; }
// queue::push/pop #include// std::cin, std::cout #include // std::queue int main () { std::queue myqueue; int myint; std::cout << "Please enter some integers (enter 0 to end):\n"; do { std::cin >> myint; myqueue.push (myint); } while (myint); std::cout << "myqueue contains: "; while (!myqueue.empty()) { std::cout << ' ' << myqueue.front(); myqueue.pop(); } std::cout << '\n'; return 0; }
// queue::front #include// std::cout #include // std::queue int main () { std::queue myqueue; myqueue.push(77); myqueue.push(16); myqueue.front() -= myqueue.back(); // 77-16=61 std::cout << "myqueue.front() is now " << myqueue.front() << '\n'; return 0; }
// queue::back #include// std::cout #include // std::queue int main () { std::queue myqueue; myqueue.push(12); myqueue.push(75); // this is now the back myqueue.back() -= myqueue.front(); std::cout << "myqueue.back() is now " << myqueue.back() << '\n'; return 0; }
Map Functions
map<string , int> phoneNum; phoneNum.insert( pair<string , int>("zunglee", 530-7972));
map<string , int> phoneNum; phoneNum.insert( pair<string , int>("zunglee", 530-7972)); for(pair<string , int> p : phoneNum){ cout<<"Contact Name :" <<p.first; cout<<"Contact number :" <<p.second; }
//1.) COPY to vector and sort; map<string , int> phoneNum; .. .. .. vector<pair<string , int>> vecData; for(auto &it : phoneNum){ vecData.push_back(it); } sort(vecData.begin() , vecData.end() , []( pair<string,int> a , pair<string,int> b ){ return a.second < b.second; });
map<string , int> phoneNum; .. .. .. struct comp { template <typename T> // Comparator function bool operator()(const T& l, const T& r) const { if (l.second != r.second) { return l.second < r.second; } return l.first < r.first; } }; set<pair<string , int> , comp> setData(phoneNum.begin() , phoneNum.end());
map<string , int> phoneNum; .. .. .. sortMap(phoneNum); void sortMap(map<string , int> &M){ multimap<int, string> MM; for (auto& it : M) { MM.insert({ it.second, it.first }); } }
Set Functions
set<int> myset; myset.insert(7); int arr[]= {5,10,15}; myset.insert(arr , arr+2);
//final : 7 , 5 , 10 (****15 is not included)
//1.) Advance eg : set<string> s ; s.insert("zunglee"); s.insert("bits"); s.insert("of"); s.insert("jarvis"); auto first = s.begin(); // get iterator to 1st element std::advance(first, 1); // advance by 1 std::cout << *first; // first element //2.) std::next auto it = std::next(myset.begin(), 5); std::cout << *it; std::advance modifies its argument returns nothing works on input iterators or better (or bi-directional iterators if a negative distance is given) std::next leaves its argument unmodified returns a copy of the argument, advanced by the specified amount works on forward iterators or better (or bi-directional iterators if a negative distance is given))
Heap Function
struct comparator { bool operator()(int a, int b) { return a > b; } }; priority_queue<int, vector<int>, comp> minHeap; minHeap.push(12); minHeap.push(8); minHeap.push(15); while (!minHeap.empty()) { cout<<minHeap.top()<<" "; minHeap.pop(); }
priority_queue <int> pq; pq.push(5); pq.push(1); pq.push(10); while (pq.empty() == false) { cout << pq.top() << " "; pq.pop(); }
Here I am going to List by Topic wise:
A.) String :
1446. Consecutive Characters: https://leetcode.com/problems/consecutive-characters/submissions/
459. Repeated Substring Pattern
1759. Count Number of Homogenous Substrings
884. Uncommon Words from Two Sentences
890. Find and Replace Pattern (idea to normalize sol1 )
To-do :
1763. Longest Nice Substring
B.) XOR operations
- Missing Number: https://leetcode.com/problems/missing-number/
- Bitwise ORs of Subarrays: https://leetcode.com/problems/bitwise-ors-of-subarrays/
- XOR Queries of a Subarray: https://leetcode.com/problems/xor-queries-of-a-subarray/
- Minimum Flips to Make a OR b Equal to c: https://leetcode.com/problems/minimum-flips-to-make-a-or-b-equal-to-c/
- Count Triplets That Can Form Two Arrays of Equal XOR: https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/
- Bitwise AND of Numbers Range: https://leetcode.com/problems/bitwise-and-of-numbers-range/
- Decode XORed Permutation: https://leetcode.com/problems/decode-xored-permutation/
1. (a|b) = (a+b) - (a&b) This is helpful when we want to related AND/OR operations with sum. 2. (a+b) = (a^b) + 2*(a&b) This one is a very special relation which can be used to solve some seemingly very tough questions. 3. The popcount function is a C++ 20 standard builtin function that counts set bits. LeetCode uses g++ compiler with the C++17 standard so we can use __builtin_popcount instead popcount(6) => 2 4. Setting K-th Bit: n | 1 ≪ (K – 1) 5. Clearing K-th Bit : n & ~(1 ≪ K – 1) 6. Toggling K-th Bit : n ^(1 ≪ K – 1) 7. Toggling Rightmost One Bit : n & n – 1 8. Isolating Rightmost Zero Bit : ~n & n + 1 9. Checking Whether Number is Power of 2 or Not : if(n & n – 1 == 0) 10. Multiplying by 2 : n ≪ 1 11. Divinding by 2: n >> 1
C,) Topological Sort
- 207 .Course Schedule : https://leetcode.com/problems/course-schedule/
- 210. Course Schedule II : https://leetcode.com/problems/course-schedule-ii/
- 269. Alien Dictionary : https://leetcode.com/problems/alien-dictionary/
- 329. Longest Increasing Path in a Matrix : https://leetcode.com/problems/longest-increasing-path-in-a-matrix/
- 444. Sequence Reconstruction : https://leetcode.com/problems/sequence-reconstruction/
- 1203. Sort Items by Groups Respecting Dependencies : https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/
- 913. Cat & mouse : https://leetcode.com/problems/cat-and-mouse/
D.) Buy & Sell
E.)Binary Search
- 1283. Smallest Divisor Given a Threshold : https://leetcode.com/problems/find-the-smallest-divisor-given-a-threshold/
- 1231. Divide Chocolate : https://leetcode.com/problems/divide-chocolate/discuss/408503/Python-Binary-Search
- 1011. Capacity To Ship Packages In N Days : https://leetcode.com/problems/koko-eating-bananas/discuss/152324/C++JavaPython-Binary-Search
- 875. Koko Eating Bananas : https://leetcode.com/problems/koko-eating-bananas/discuss/152324/C++JavaPython-Binary-Search
- 774. Minimize Max Distance to Gas Station: https://leetcode.com/problems/minimize-max-distance-to-gas-station/discuss/113633/Easy-and-Concise-Solution-using-Binary-Search-C++JavaPython
- 410. Split Array Largest Sum: https://leetcode.com/problems/split-array-largest-sum/
- 1482 . Minimum Number of Days to Make m Bouquets
F.) Maximum Sum in Array/Tress: Not Adjacent indexes
G.) Interval
56. Merge Intervals (sol1 , sol2 )
252 Meeting Rooms
253 Meeting Rooms II
435 Non-overlapping Intervals (sol1 , sol2)
452. Minimum Number of Arrows to Burst Balloons ()
https://leetcode.com/problems/insert-interval/
436. Find Right Interval (sol1)
986. Interval List Intersections
H,) Coin Change
518. Coin Change 2
377. Combination Sum IV
I.) Reverse Linked List
206. Reverse Linked List
92. Reverse Linked List II
25. Reverse Nodes in k-Group
** Alternate K-group reverse
J.) Tree
Preorder , Inorder , Postoder traversal
https://leetcode.com/problems/binary-tree-right-side-view/
J.) Tree
Preorder , Inorder , Postoder traversal
https://leetcode.com/problems/binary-tree-right-side-view/
J.) Tree
Preorder , Inorder , Postoder traversal
https://leetcode.com/problems/binary-tree-right-side-view/
https://leetcode.com/problems/boundary-of-binary-tree/
Stack
- 1425. Constrained Subsequence Sum
- 1130. Minimum Cost Tree From Leaf Values
- 907. Sum of Subarray Minimums
- 901. Online Stock Span
- 856. Score of Parentheses
- 503. Next Greater Element II
- 496. Next Greater Element I
- 84. Largest Rectangle in Histogram
- 42. Trapping Rain Water
Sliding Window
- 1425. Constrained Subsequence Sum
- 1358. Number of Substrings Containing All Three Characters
- 1248. Count Number of Nice Subarrays
- 1234. Replace the Substring for Balanced String
- 1004. Max Consecutive Ones III
- 930. Binary Subarrays With Sum
- 992. Subarrays with K Different Integers
- 904. Fruit Into Baskets
- 862. Shortest Subarray with Sum at Least K
- 209. Minimum Size Subarray Sum
Binary Search
- 1482. Minimum Number of Days to Make m Bouquets
- 1283. Find the Smallest Divisor Given a Threshold
- 1231. Divide Chocolate
- 1011. Capacity To Ship Packages In N Days
- 875. Koko Eating Bananas
- 774. Minimize Max Distance to Gas Station
- 410. Split Array Largest Sum
Bonus (Monotone Stack)
Linked List: [8]
https://leetcode.com/problems/add-two-numbers/
https://leetcode.com/problems/merge-two-sorted-lists/
https://leetcode.com/problems/reverse-nodes-in-k-group/
https://leetcode.com/problems/copy-list-with-random-pointer/
https://leetcode.com/problems/sort-list/
https://leetcode.com/problems/palindrome-linked-list/
https://leetcode.com/problems/linked-list-cycle-ii/
https://leetcode.com/problems/intersection-of-two-linked-lists/
Array: [8]
https://leetcode.com/problems/two-sum/
https://leetcode.com/problems/search-insert-position/
https://leetcode.com/problems/spiral-matrix/
https://leetcode.com/problems/sort-colors/
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
https://leetcode.com/problems/majority-element-ii/
https://leetcode.com/problems/insert-delete-getrandom-o1/
https://leetcode.com/problems/task-scheduler/
HashMap: [9]
https://leetcode.com/problems/longest-substring-without-repeating-characters/
https://leetcode.com/problems/group-anagrams/
https://leetcode.com/problems/bulls-and-cows/
https://leetcode.com/problems/sort-characters-by-frequency/
https://leetcode.com/problems/subarray-sum-equals-k/
https://leetcode.com/problems/valid-sudoku/
https://leetcode.com/problems/subarray-sums-divisible-by-k/
Ordered Map:
https://leetcode.com/problems/my-calendar-ii/
https://leetcode.com/problems/my-calendar-iii/
String: [5]
https://leetcode.com/problems/longest-palindromic-substring/
https://leetcode.com/problems/reverse-words-in-a-string/
https://leetcode.com/problems/compare-version-numbers/
https://leetcode.com/problems/longest-common-prefix/
https://leetcode.com/problems/long-pressed-name/
Stack: [5]
https://leetcode.com/problems/valid-parentheses/
https://leetcode.com/problems/simplify-path/
https://leetcode.com/problems/implement-stack-using-queues/
https://leetcode.com/problems/next-greater-element-i/
https://leetcode.com/problems/min-stack/
Queue: [3]
https://leetcode.com/problems/number-of-recent-calls/
https://leetcode.com/problems/design-circular-queue/
https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
Heap: [3]
https://leetcode.com/problems/top-k-frequent-elements/
https://leetcode.com/problems/find-median-from-data-stream/
https://leetcode.com/problems/last-stone-weight/
Two Pointers: [3]
https://leetcode.com/problems/3sum/
https://leetcode.com/problems/boats-to-save-people/
https://leetcode.com/problems/container-with-most-water/
Binary Search: [4]
https://leetcode.com/problems/first-bad-version/
https://leetcode.com/problems/search-in-rotated-sorted-array/
https://leetcode.com/problems/powx-n/
https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
Bit Manipulation: [5]
https://leetcode.com/problems/single-number-ii/
https://leetcode.com/problems/power-of-two/
https://leetcode.com/problems/single-number-iii/
https://leetcode.com/problems/sum-of-two-integers/
https://leetcode.com/problems/counting-bits/
Tree: [12]
https://leetcode.com/problems/binary-tree-inorder-traversal/
https://leetcode.com/problems/validate-binary-search-tree/
https://leetcode.com/problems/binary-tree-level-order-traversal/
https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/
https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
https://leetcode.com/problems/balanced-binary-tree/
https://leetcode.com/problems/binary-tree-right-side-view/
https://leetcode.com/problems/serialize-and-deserialize-binary-tree/
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
https://leetcode.com/problems/find-largest-value-in-each-tree-row/
https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree/
https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
Graph: [8]
Topological Sort:
https://leetcode.com/problems/course-schedule-ii/
DFS:
https://leetcode.com/problems/number-of-islands/
https://leetcode.com/problems/number-of-closed-islands/
https://leetcode.com/problems/number-of-enclaves/
BFS:
https://leetcode.com/problems/rotting-oranges/
https://leetcode.com/problems/01-matrix/
Union Find:
https://leetcode.com/problems/redundant-connection/
https://leetcode.com/problems/friend-circles/
Trie: [2]
https://leetcode.com/problems/implement-trie-prefix-tree/
https://leetcode.com/problems/design-add-and-search-words-data-structure/
Sort: [2]
https://leetcode.com/problems/merge-intervals/
https://leetcode.com/problems/rank-teams-by-votes/
Divide and Conquer: [1]
https://leetcode.com/problems/median-of-two-sorted-arrays/
Dynamic Programming: [8]
https://leetcode.com/problems/climbing-stairs/
https://leetcode.com/problems/house-robber/
https://leetcode.com/problems/perfect-squares/
https://leetcode.com/problems/coin-change/
https://leetcode.com/problems/longest-increasing-subsequence/
https://leetcode.com/problems/russian-doll-envelopes/
https://leetcode.com/problems/ugly-number-ii/
https://leetcode.com/problems/range-sum-query-2d-immutable/
Greedy: [4]
https://leetcode.com/problems/gas-station/
https://leetcode.com/problems/assign-cookies/
https://leetcode.com/problems/lemonade-change/
https://leetcode.com/problems/jump-game/
Design: [4]
https://leetcode.com/problems/lru-cache/
https://leetcode.com/problems/implement-queue-using-stacks/
https://leetcode.com/problems/design-twitter/
https://leetcode.com/problems/kth-largest-element-in-a-stream/
Math: [2]
https://leetcode.com/problems/rectangle-area/
https://leetcode.com/problems/excel-sheet-column-title/
Sliding window: [3]
https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/
https://leetcode.com/problems/sliding-window-maximum/
https://leetcode.com/problems/max-consecutive-ones-iii/