8000 todo AddTwoNumbersRepresentedByLinkedList · jacobklo/jalgorithmCPP@ad4673f · GitHub
[go: up one dir, main page]
Skip to content

Commit ad4673f

Browse files
jacobklojacobklo
committed
todo AddTwoNumbersRepresentedByLinkedList
1 parent 10e2e44 commit ad4673f

File tree

7 files changed

+156
-25
lines changed

7 files changed

+156
-25
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ unlike normal projects.
2323
#### Backtrack
2424
* [MostEleganceString - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/MostEleganceString.h)
2525
* [Davis' Staircase - Hackerrank](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/DavisStaircase.h)
26+
* [Add two numbers represented by linked lists - GeeksForGeeks](https://github.com/jljacoblo/jalgorithmCPP/blob/master/src/Backtrack/AddTwoNumbers.h)
2627
***
2728

2829
#### DataStructure

‎src/Backtrack/AddTwoNumbers.h

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
//
2+
// Created by Jacob Lo on 10/21/18.
3+
//
4+
5+
/*
6+
* EASY
7+
* https://www.geeksforgeeks.org/sum-of-two-linked-lists/
8+
* Given two numbers represented by two linked lists, write a function that returns sum list. The sum list is linked list representation of addition of two input numbers. It is not allowed to modify the lists. Also, not allowed to use explicit extra space (Hint: Use Recursion).
9+
10+
Example
11+
12+
Input:
13+
First List: 5->6->3 // represents number 563
14+
Second List: 8->4->2 // represents number 842
15+
Output
16+
Resultant list: 1->4->0->5 // represents number 1405
17+
*/
18+
#pragma once
19+
20+
#include <string>
21+
#include <climits>
22+
23+
using namespace std;
24+
25+
namespace AddTwoNumbers {
26+
struct Node {
27+
int data;
28+
Node* next = nullptr;
29+
30+
Node(int d) { data = d; }
31+
};
32+
33+
string nodeToString(Node* root) {
34+
string result = "";
35+
while(root != nullptr) {
36+
result += to_string(root->data);
37+
root = root->next;
38+
}
39+
return result;
40+
}
41+
42+
void add(Node& result, Node* a, Node* b) {
43+
44+
/// if both a and b is last node
45+
if ( a->next == nullptr && b->next == nullptr ) {
46+
int added = a->data + b->data;
47+
Node* newNode = new Node( ( added > 10 ? added - 10: added ) );
48+
result.data = ( added > 10 ? 1 : 0 );
49+
result.next = newNode;
50+
return;
51+
}
52+
53+
// TODO : test case 123 + 10 wrong!
54+
result.next = new Node(INT_MIN);
55+
Node* ANextNodeOrLast = ( a->next != nullptr ? a->next : a );
56+
Node* BNextNodeOrLast = ( b->next != nullptr ? b->next : b );
57+
58+
add( *(result.next), ANextNodeOrLast, BNextNodeOrLast);
59+
int added = result.next->data;
60+
// if current a is not the last node, which means we need to handle current a,
61+
// if it is last node already, then recursive already added, no need to handle
62+
// Think of a == 1[2]3, where [] is current
63+
// b == [6]
64+
67E6 // we recursive call add, where recursive-current of a == 12[3], and b == [6].
65+
// if this current recurion, it should be a == 1[2]3, b == [0]6
66+
if ( a->next != nullptr ) {
67+
added += a->data;
68+
}
69+
if ( b->next != nullptr ) {
70+
added += b->data;
71+
}
72+
result.next->data = ( added > 10 ? added - 10: added );
73+
result.data = ( added > 10 ? 1 : 0 );
74+
return;
75+
76+
}
77+
}

‎src/CMakeLists.txt

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,5 +41,7 @@ add_executable(jalgorithmCPP
4141
DynamicProgramming/MaxSubsetSum.h
4242
Backtrack/DavisStaircase.h
4343
DataStructure/QueueUsingTwoStack.h
44+
Search/TripleSum.h
45+
Backtrack/AddTwoNumbers.h
4446
)
4547

‎src/Sort/FraudulentActivityNotifications.h

Lines changed: 34 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -13,41 +13,55 @@
1313
#pragma once
1414

1515
#include <vector>
16-
#include <set>
17-
#include <functional>
1816
#include <queue>
17+
#include <algorithm>
18+
#include <set>
1919

2020
using namespace std;
2121

2222
namespace FraudulentActivityNotifications {
2323

24-
// TODO
24+
double calcMedian(const multiset<int>& set) {
25+
auto middle = set.begin();
26+
for ( int i = 0 ; i < (set.size()-1) / 2 ; i++, ++middle) {}
27+
28+
double median = *middle;
29+
if ( set.size() % 2 == 0) {
30+
median = ( median + (*middle+1) ) / 2;
31+
}
32+
33+
return median;
34+
}
35+
2536
int activityNotifications(vector<int> expenditure, int d) {
2637

27-
int notices;
28-
multiset<int> dmap;
29-
/// loop through expenditure, update BST to max d num of elements, find if i is bigger than median
30-
for ( int i = 0 ; i < expenditure.size() ; i++ ){
38+
int notices = 0;
39+
vector<int> lastElements;
40+
multiset<int> lastElementsSorted;
3141

32-
/// check if BST has enough elements. if num of elements smaller than d, append and continue
33-
if ( dmap.size() < d ) {
34-
dmap.insert( expenditure[i] );
35-
continue;
36-
}
42+
/// check if BST has enough elements. if num of elements smaller than d, append and continue
43+
for ( int i = 0 ; i < d && i < expenditure.size(); i++ ) {
44+
lastElements.push_back(expenditure[i]);
45+
lastElementsSorted.insert(expenditure[i]);
46+
}
3747

38-
/// check if median is smaller than i expends, if so, add notice
39-
multiset<int>::iterator it = dmap.begin();
40-
// find median node
41-
for ( int j = 0 ; j < dmap.size() / 2 ; j++, ++it ) {}
48+
/// loop through expenditure, update BST to max d num of elements, find if i is bigger than median
49+
for ( int i = d ; i < expenditure.size() ; i++ ){
4250

43-
// check median < i expends
44-
if ( (*it) < expenditure[i] ) {
51+
/// check if median is smaller than i expends, if so, add notice
52+
double median = calcMedian(lastElementsSorted);
53+
if ( 2*median <= expenditure[i] ) {
4554
notices++;
4655
}
4756

4857
/// update BST
49-
dmap.erase( dmap.begin() );
50-
dmap.insert( expenditure[i] );
58+
// REMEMBER : cannot do this, it will remove all number that has the same value!
59+
// dmap.erase( );
60+
auto toRemoveOldestItr = lastElementsSorted.find( lastElements[0] );
61+
lastElementsSorted.erase( toRemoveOldestItr );
62+
lastElements.erase( lastElements.begin());
63+
lastElementsSorted.insert( expenditure[i] );
64+
lastElements.push_back( expenditure[i] );
5165
}
5266

5367
return notices;

‎src/main.cpp

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -5,16 +5,17 @@
55
#include <iostream>
66
#include <random>
77
#include <vector>
8+
#include <string>
9+
#include <climits>
810

911
#include "String/ContainersToString.h"
1012

11-
#include "DynamicProgramming/MaxSubsetSum.h"
13+
#include "Backtrack/AddTwoNumbers.h"
1214

1315
using namespace std;
16+
using namespace AddTwoNumbers;
17+
1418

1519
int main() {
16-
vector<int> arr{3,7,4,6,5};
17-
vector<int> arr2{3,5,-7,8,10};
18-
int result = MaxSubsetSum::maxSubsetSum(arr);
19-
cout << result;
20+
2021
}

‎test/Backtrack/AddTwoNumbersTest.cpp

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
//
2+
// Created by Jacob Lo on 10/21/18.
3+
//
4+
5+
#include "catch.hpp"
6+
#include "Backtrack/AddTwoNumbers.h"
7+
8+
using namespace AddTwoNumbers;
9+
10+
TEST_CASE( "Test Add Two Numbers Represented Linked Lists", "[TestAddTwoNumbers]" ) {
11+
Node* hundard = new Node(1);
12+
hundard->next = new Node(2);
13+
hundard->next->next = new Node(3);
14+
15+
Node* ten = new Node(1);
16+
ten->next = new Node(0);
17+
18+
Node* o = new Node(1);
19+
Node* t = new Node(2);
20+
21+
// Node result = Node(INT_MIN);
22+
// add(result, hundard, o);
23+
// REQUIRE(string("0124") == nodeToString( &result ) );
24+
//
25+
// Node result2 = Node(INT_MIN);
26+
// add(result2, hundard, hundard);
27+
// REQUIRE(string("0246") == nodeToString( &result2 ) );
28+
29+
Node result3 = Node(INT_MIN);
30+
add(result3, hundard, ten);
31+
REQUIRE(string("0133") == nodeToString( &result3 ) );
32+
33+
34+
}

‎test/CMakeLists.txt

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -52,6 +52,8 @@ add_executable(jalgorithmCPP_Test
5252
../src/DynamicProgramming/MaxSubsetSum.h
5353
Backtrack/DavisStaircaseTest.cpp
5454
../src/Backtrack/DavisStaircase.h
55+
Backtrack/AddTwoNumbersTest.cpp
56+
../src/Backtrack/AddTwoNumbers.h
5557
../src/String/ContainersToString.h
5658
)
5759

0 commit comments

Comments
 (0)
0