10000 Greedy algos · rvishureddy/leetcode@25d8855 · GitHub
[go: up one dir, main page]
Skip to content

Commit 25d8855

Browse files
author
viswanatha Ramireddy
committed
Greedy algos
1 parent f9a9e29 commit 25d8855

8 files changed

+865
-0
lines changed

‎.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,3 +2,4 @@
22
algorithms-java/out
33
*.class
44
*.out
5+
*.vscode

‎CppContainersNotes.txt

Lines changed: 241 additions & 0 deletions
7802
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,241 @@
1+
#include <string>
2+
using std::string;
3+
4+
// Declaration & Initialization
5+
string s1; // empty
6+
string s2 = "hello"; // from literal
7+
string s3(5, 'x'); // "xxxxx"
8+
string s4 = s2 + " world"; // concatenation
9+
10+
// Key Operations
11+
s2 += "!"; // append (concatenate)
12+
char c = s2[1]; // index access
13+
14+
string sub = s2.substr(2, 3); // substring from pos=2 len=3
15+
size_t pos = s2.find("lo"); // find substring, returns index or npos
16+
bool empty = s2.empty(); // is empty?
17+
s2.clear(); // clear contents
18+
19+
// Comparison
20+
if (s2 == s4)
21+
{ /* ... */
22+
}
23+
24+
std::string s = "hi";
25+
s.push_back('!'); // hi!
26+
// Note: Can only push one char at a time
27+
s.pop_back()
28+
29+
//Vector
30+
#include <vector>
31+
using std::vector;
32+
33+
// 1D vector
34+
vector<int> v; // empty
35+
vector<int> v2(10); // size=10, default-initialized (0)
36+
vector<int> v3 = {1,2,3,4}; // initializer-list
37+
38+
// 2D vector (matrix/graph adj list)
39+
int rows = 5, cols = 4;
40+
vector<vector<int>> mat(rows, vector<int>(cols, 0));
41+
// or for adjacency list
42+
vector<vector<int>> adj(n);
43+
44+
// Common Ops
45+
v.push_back(42); // append
46+
v.pop_back(); // remove last
47+
int x = v.back(); // access last
48+
v.front(); // first element
49+
50+
v.insert(v.begin()+i, 99);// insert at pos i
51+
v.erase(v.begin()+i); // erase at pos i
52+
v.clear(); // remove all
53+
54+
// Searching & Sorting Helpers
55+
#include <algorithm>
56+
// assumes v sorted
57+
auto it = std::lower_bound(v.begin(), v.end(), target);
58+
auto it2 = std::upper_bound(v.begin(), v.end(), target);
59+
// distance from begin gives index of first ≥ (lower) or > (upper)
60+
61+
//Finding max element in the Vector
62+
int maxVal = *max_element(a.begin(), a.end());
63+
Make sure the vector isn't empty before calling this—otherwise, max_element returns a.end(), and dereferencing that is 👻 undefined behavior.
64+
if (!nums.empty()) {
65+
int maxVal = *max_element(nums.begin(), nums.end());
66+
}
67+
68+
vector<int> nums = {4, 2, 9, 1, 6};
69+
70+
int maxVal = *max_element(nums.begin(), nums.end()); // 9
71+
int minVal = *min_element(nums.begin(), nums.end()); // 1
72+
73+
//Get index of the max element
74+
int maxIdx = max_element(nums.begin(), nums.end()) - nums.begin();
75+
int minIdx = min_element(nums.begin(), nums.end()) - nums.begin();
76+
77+
//Say you have vector<string> and want the longest string:
78+
vector<string> strs = {"cat", "tiger", "lion"};
79+
80+
auto it = max_element(strs.begin(), strs.end(),
81+
[](const string &a, const string &b) {
82+
return a.size() < b.size();
83+
});
84+
85+
string longest = *it; // "tiger"
86+
87+
// With pair<int, int>: Compare on second or custom rule
88+
vector<pair<int, int>> ar 1E0A r = {{1, 10}, {2, 5}, {3, 15}};
89+
90+
// Max by second element
91+
auto maxBySecond = max_element(arr.begin(), arr.end(),
92+
[](auto &a, auto &b) {
93+
return a.second < b.second;
94+
});
95+
// *maxBySecond = {3, 15}
96+
97+
//You can use std::max_element and std::min_element with any
98+
//container that supports iterators, because they operate over
99+
//iterator ranges — not the container itself.
100+
101+
std::list<int> nums = {5, 3, 8, 1};
102+
int maxVal = *std::max_element(nums.begin(), nums.end()); // 8
103+
104+
std::set<int> s = {1, 2, 3, 4};
105+
// max = *s.rbegin(); OR use max_element
106+
int maxVal = *std::max_element(s.begin(), s.end()); // 4
107+
108+
struct Car {
109+
string model;
110+
int speed;
111+
};
112+
113+
vector<Car> cars = {{"A", 100}, {"B", 150}, {"C", 120}};
114+
115+
auto fastest = max_element(cars.begin(), cars.end(), [](const Car& a, const Car& b) {
116+
return a.speed < b.speed;
117+
});
118+
119+
int val = 120;
120+
int clamped = std::clamp(val, 0, 100); // clamped = 100
121+
/*
122+
This means:
123+
124+
"If val is too big, just return the max (100);
125+
If it's too small, return the min (0);
126+
Otherwise, return the value itself."
127+
128+
| Function | Use For |
129+
| ------------------------- | ---------------------------- |
130+
| `std::max(a, b)` | Max of two values |
131+
| `std::min(a, b)` | Min of two values |
132+
| `std::max_element` | Max in a range |
133+
| `std::min_element` | Min in a range |
134+
| `std::clamp(val, lo, hi)` | Bound a value between limits |
135+
*/
136+
137+
138+
#include <list>
139+
using std::list;
140+
141+
list<int> lst; // empty
142+
list<int> lst2(5, 0); // five zeros
143+
144+
// Ops
145+
lst.push_back(1);
146+
lst.push_front(2);
147+
lst.pop_back();
148+
lst.pop_front();
149+
150+
// Splicing, inserting at iterator
151+
auto it = lst.begin();
152+
std::advance(it, 2);
153+
lst.insert(it, 99); // O(1)
154+
lst.erase(it); // O(1)
155+
156+
// Deque
157+
#include <deque>
158+
using std::deque;
159+
160+
deque<int> dq;
161+
dq.push_back(3);
162+
dq.push_front(4);
163+
dq.pop_back();
164+
dq.pop_front();
165+
166+
int a = dq[0]; // random access (slightly slower than vector)
167+
168+
//Sets
169+
170+
#include <set>
171+
using std::set;
172+
173+
set<int> st;
174+
st.insert(5);
175+
st.insert(1);
176+
st.erase(5);
177+
auto sit = st.find(1); // iterator or end()
178+
bool exists = (sit != st.end());
179+
180+
//Unordered Sets
181+
#include <unordered_set>
182+
using std::unordered_set;
183+
184+
unordered_set<string> us;
185+
us.insert("abc");
186+
us.count("def"); // 0 or 1
187+
188+
189+
//Map
190+
191+
#include <map>
192+
using std::map;
193+
194+
map<int,string> mp;
195+
mp[1] = "one"; // insert or overwrite
196+
mp.insert({2, "two"});
197+
mp.erase(1);
198+
auto mit = mp.find(2); // iterator to pair or end()
199+
if (mit != mp.end()) {
200+
int key = mit->first;
201+
string val = mit->second;
202+
}
203+
204+
205+
206+
// Unordered map
207+
#include <unordered_map>
208+
using std::unordered_map;
209+
210+
unordered_map<string,int> ump;
211+
ump["a"] = 10;
212+
ump.count("b"); // 0 or 1
213+
214+
215+
//Queue Stacks
216+
217+
#include <queue>
218+
#include <stack>
219+
220+
std::queue<int> q;
221+
q.push(1);
222+
q.pop();
223+
int front = q.front();
224+
225+
std::stack<int> stck;
226+
stck.push(2);
227+
stck.pop();
228+
int top = stck.top();
229+
230+
231+
//Searching Iteration
232+
// Iterating
233+
for (auto &x : v) { /* ... */ }
234+
for (auto it = mp.begin(); it != mp.end(); ++it) {
235+
// it->first, it->second
236+
}
237+
238+
// Generic find
239+
#include <algorithm>
240+
auto pos = std::find(v.begin(), v.end(), target);
241+
if (pos != v.end()) { /* found */ }

‎myPracticeWithNotes/LargestPalindromeString.cpp

Lines changed: 117 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,117 @@
1+
/*
2+
You are given a string num consisting of digits only.
3+
4+
Return the largest palindromic integer (in the form of a string) that can be formed using digits taken from num. It should not contain leading zeroes.
5+
6+
Notes:
7+
8+
You do not need to use all the digits of num, but you must use at least one digit.
9+
The digits can be reordered.
10+
11+
Example 1:
12+
Input: num = "444947137"
13+
Output: "7449447"
14+
Explanation:
15+
Use the digits "4449477" from "444947137" to form the palindromic integer "7449447".
16+
It can be shown that "7449447" is the largest palindromic integer that can be formed.
17+
18+
Example 2:
19+
Input: num = "00009"
20+
Output: "9"
21+
Explanation:
22+
It can be shown that "9" is the largest palindromic integer that can be formed.
23+
Note that the integer returned should not contain leading zeroes.
24+
25+
Notes:
26+
📌 Key Steps in Your Code:
27+
Count digit frequency using vector<int> freq(10, 0).
28+
29+
***Important: Looping from 9 to 0, build the left side of the palindrome.
30+
31+
Build left side of palindrome from highest digits down.
32+
33+
Add freq[i] / 2 copies of digit i.
34+
35+
Skip leading 0s unless no other digit was used.
36+
37+
Pick middle digit (odd-count) if exists.
38+
39+
Mirror left to create right side.
40+
41+
If no left, but middle is '0' or any digit, return middle.
42+
0099
43+
44+
009
45+
00099
46+
Time: O(N + 10 log 10) ≈ O(N)
47+
Space: O(1) (fixed-size frequency array)
48+
*/
49+
#include <iostream>
50+
#include <string>
51+
#include <vector>
52+
#include <algorithm>
53+
using namespace std;
54+
55+
class Solution
56+
{
57+
public:
58+
string largestPalindromic(string num)
59+
{
60+
// First lets get the frequency of each digit
61+
vector<int> freq(10, 0);
62+
for (char c : num)
63+
{
64+
freq[c - '0']++;
65+
}
66+
67+
// Now let's build the largest palindromic number
68+
string left = "", middle = "";
69+
for (int i = 9; i >= 0; i--)
70+
{
71+
// cout << "Frequency of " << i << ": " << freq[i] << endl;
72+
if (freq[i] % 2 == 1 && middle.empty())
73+
{
74+
middle = to_string(i); // Choose the odd digit for the middle
75+
}
76+
77+
// If we are at digit 0 and no middle digit is set, skip adding leading zeroes
78+
if (left.empty() && i == 0)
79+
{
80+
if (middle.empty())
81+
{
82+
// Special case if we just have "00" as input
83+
// If no other digits are present, we can use 0 as the middle
84+
middle = "0";
85+
}
86+
87+
// If we are at digit 0 and no middle digit is set, skip adding leading zeroes
88+
continue;
89+
}
90+
left += string(freq[i] / 2, '0' + i); // Append half of the even digits
91+
}
92+
// Lets print left, middle here
93+
// cout << "Left part: " << left << endl;
94+
// cout << "Middle part: " << middle << endl;
95+
96+
// If we have a left part, we can form a palindrome
97+
if (!left.empty())
98+
{
99+
// Form the largest palindrome
100+
return left + middle + string(left.rbegin(), left.rend());
101+
}
102+
// If no left part, return the middle digit (if exists)
103+
return middle;
104+
}
105+
};
106+
107+
// Example usage:
108+
int main()
109+
{
110+
Solution solution;
111+
string num = "00099";
112+
string result = solution.largestPalindromic(num);
113+
// Expected output: "90009"
114+
// Print the result
115+
printf("Result:%s\n", result.c_str());
116+
return 0;
117+
}

0 commit comments

Comments
 (0)
0