Skip to content

Commit c60307c

Browse files
slightbugslightbug
committed
LeetCode initial
1 parent 20ad1de commit c60307c

10 files changed

+494
-0
lines changed

‎LeetCode/Hash Table/README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,4 @@
1+
# | Problem | Solution
2+
-----|---------------- | ---------------
3+
138|[Copy List with Random Pointer]()|[track the location to set random](https://github.com/slightbug/Coding/blob/master/LinkedList/CopyListwithRandomPointer.java)
4+
?|[]()|[]()

‎LeetCode/LinkedList/AddTwoNumbers.java

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
/*
2+
2. Add Two Numbers
3+
4+
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
5+
6+
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
7+
Output: 7 -> 0 -> 8
8+
9+
*/
10+
11+
/*
12+
Similar to String case: start from least signification digit, if null then use 0
13+
*/
14+
15+
/**
16+
* Definition for singly-linked list.
17+
* public class ListNode {
18+
* int val;
19+
* ListNode next;
20+
* ListNode(int x) { val = x; }
21+
* }
22+
*/
23+
public class Solution {
24+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
25+
ListNode itr1 = l1, itr2 = l2, dummy = new ListNode(0), cur = dummy;
26+
int carry = 0, d1, d2, sum;
27+
28+
while(itr1 != null || itr2 != null || carry == 1) {
29+
d1 = 0;
30+
d2 = 0;
31+
if(itr1 != null) {
32+
d1 = itr1.val;
33+
itr1 = itr1.next;
34+
}
35+
if(itr2 != null) {
36+
d2 = itr2.val;
37+
itr2 = itr2.next;
38+
}
39+
40+
sum = d1 + d2 + carry;
41+
cur.next = new ListNode(sum % 10);
42+
cur = cur.next;
43+
44+
carry = sum / 10;
45+
}
46+
47+
return dummy.next;
48+
}
49+
}

‎LeetCode/LinkedList/AddTwoNumbersII.java

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
/*
2+
445. Add Two Numbers II
3+
4+
You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
5+
6+
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
7+
8+
Follow up:
9+
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
10+
11+
Example:
12+
13+
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
14+
Output: 7 -> 8 -> 0 -> 7
15+
16+
*/
17+
18+
/*
19+
Similar to I, but use two stacks to store the numbers.
20+
1. Carry can be directly recorded by sum/10 in next iteration.
21+
2. Need one node to keep the new head.
22+
23+
*/
24+
25+
/**
26+
* Definition for singly-linked list.
27+
* public class ListNode {
28+
* int val;
29+
* ListNode next;
30+
* ListNode(int x) { val = x; }
31+
* }
32+
*/
33+
34+
35+
public class Solution {
36+
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
37+
LinkedList<Integer> stack1 = new LinkedList<>();
38+
LinkedList<Integer> stack2 = new LinkedList<>();
39+
int d1, d2, sum, carry = 0;
40+
ListNode dummy = new ListNode(0), itr;
41+
42+
itr = l1;
43+
while(itr != null) {
44+
stack1.push(itr.val);
45+
itr = itr.next;
46+
}
47+
48+
itr = l2;
49+
while(itr != null) {
50+
stack2.push(itr.val);
51+
itr = itr.next;
52+
}
53+
54+
while(!stack1.isEmpty() || !stack2.isEmpty() || carry == 1) {
55+
d1 = !stack1.isEmpty() ? stack1.pop() : 0;
56+
d2 = !stack2.isEmpty() ? stack2.pop() : 0;
57+
sum = d1 + d2 + carry;
58+
itr = new ListNode(sum % 10);
59+
itr.next = dummy.next;
60+
dummy.next = itr;
61+
carry = sum / 10;
62+
}
63+
64+
return dummy.next;
65+
}
66+
}

‎LeetCode/LinkedList/CopyListwithRandomPointer.java

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
/*
2+
138. Copy List with Random Pointer
3+
4+
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
5+
6+
Return a deep copy of the list.
7+
8+
*/
9+
10+
/*
11+
Idea:
12+
M1:
13+
1. Using a hashmap to keep new node (value) corresponding to original node (key)
14+
2. Traverse again, and set the random and next: dict.get(*).next = dict.get(*.next);
15+
16+
M2:
17+
1. Since we need to know the node location when we set random for cloned list,
18+
then we can insert the copied node after the original node
19+
2. Traverse again, and set the random: check null before every *.next
20+
3. Seperate the new list from the original list: using a dummy header
21+
22+
*/
23+
24+
/**
25+
* Definition for singly-linked list with a random pointer.
26+
* class RandomListNode {
27+
* int label;
28+
* RandomListNode next, random;
29+
* RandomListNode(int x) { this.label = x; }
30+
* };
31+
*/
32+
public class Solution {
33+
/*public RandomListNode copyRandomList(RandomListNode head) {
34+
// Assume:
35+
// 1. no cycle. 2. No additional nodes linked through random.
36+
// 3. RnadomListNode class has funtions of hasCode() and overrided equals():
37+
// if not, maintain an integer count to identify that node and use this integer as key for HashMap
38+
39+
Map<RandomListNode, RandomListNode> dict = new HashMap<>();
40+
41+
RandomListNode cur = head;
42+
43+
while(cur != null) {
44+
dict.put(cur, new RandomListNode(cur.label));
45+
cur = cur.next;
46+
}
47+
48+
cur = head;
49+
while(cur != null) { // there has to be another round to link random: can't link before create these nodes
50+
dict.get(cur).next = dict.get(cur.next); // key
51+
dict.get(cur).random = dict.get(cur.random);
52+
cur = cur.next;
53+
}
54+
55+
return head == null ? null : dict.get(head);
56+
}*/
57+
58+
// high vote solution:
59+
// https://discuss.leetcode.com/topic/7594/a-solution-with-constant-space-complexity-o-1-and-linear-time-complexity-o-n
60+
61+
public RandomListNode copyRandomList(RandomListNode head) {
62+
RandomListNode dummy = new RandomListNode(0);
63+
RandomListNode cur = head, res, temp;
64+
65+
while(cur != null) {
66+
temp = new RandomListNode(cur.label);
67+
temp.next = cur.next;
68+
cur.next = temp;
69+
cur = cur.next.next;
70+
}
71+
72+
cur = head;
73+
while(cur != null) {
74+
if(cur.random != null) {
75+
cur.next.random = cur.random.next; // key
76+
}
77+
78+
cur = cur.next.next;
79+
}
80+
81+
cur = head;
82+
temp = dummy;
83+
while(cur != null) {
84+
temp.next = cur.next;
85+
temp = temp.next;
86+
cur.next = cur.next.next;
87+
cur = cur.next;
88+
}
89+
90+
return dummy.next;
91+
}
92+
}

‎LeetCode/LinkedList/Design Phone Directory.java

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
/*
2+
379. Design Phone Directory
3+
4+
Design a Phone Directory which supports the following operations:
5+
6+
get: Provide a number which is not assigned to anyone.
7+
check: Check if a number is available or not.
8+
release: Recycle or release a number.
9+
10+
Example:
11+
12+
// Init a phone directory containing a total of 3 numbers: 0, 1, and 2.
13+
PhoneDirectory directory = new PhoneDirectory(3);
14+
15+
// It can return any available phone number. Here we assume it returns 0.
16+
directory.get();
17+
18+
// Assume it returns 1.
19+
directory.get();
20+
21+
// The number 2 is available, so return true.
22+
directory.check(2);
23+
24+
// It returns 2, the only number that is left.
25+
directory.get();
26+
27+
// The number 2 is no longer available, so return false.
28+
directory.check(2);
29+
30+
// Release number 2 back to the pool.
31+
directory.release(2);
32+
33+
// Number 2 is available again, return true.
34+
directory.check(2);
35+
36+
*/
37+
/*
38+
M1:
39+
Using one list for available, and one boolean array for all data
40+
41+
M2:
42+
BitSet: https://discuss.leetcode.com/topic/53102/java-ac-solution-with-bitset-and-efficient-get-comments
43+
44+
*/
45+
public class PhoneDirectory {
46+
47+
/** Initialize your data structure here
48+
@param maxNumbers - The maximum numbers that can be stored in the phone directory. */
49+
50+
private LinkedList<Integer> pool;
51+
private int[] dict; // 0 for available
52+
public PhoneDirectory(int maxNumbers) {
53+
pool = new LinkedList<>();
54+
for(int i = 0; i < maxNumbers; ++i) {
55+
pool.push(i);
56+
}
57+
dict = new int[maxNumbers];
58+
}
59+
60+
/** Provide a number which is not assigned to anyone.
61+
@return - Return an available number. Return -1 if none is available. */
62+
public int get() {
63+
int res;
64+
if(!pool.isEmpty()) {
65+
res = pool.pop();
66+
dict[res] = 1;
67+
}
68+
else { // no available
69+
res = -1;
70+
}
71+
72+
return res;
73+
}
74+
75+
/** Check if a number is available or not. */
76+
public boolean check(int number) {
77+
if(number < 0 || number >= dict.length) {
78+
return false;
79+
}
80+
return dict[number] == 0 ? true : false;
81+
}
82+
83+
/** Recycle or release a number. */
84+
public void release(int number) {// if used
85+
if(check(number)) { // available
86+
return;
87+
}
88+
89+
pool.push(number);
90+
dict[number] = 0;
91+
}
92+
}
93+
94+
/**
95+
* Your PhoneDirectory object will be instantiated and called as such:
96+
* PhoneDirectory obj = new PhoneDirectory(maxNumbers);
97+
* int param_1 = obj.get();
98+
* boolean param_2 = obj.check(number);
99+
* obj.release(number);
100+
*/

‎LeetCode/LinkedList/New Text Document.txt

Whitespace-only changes.

0 commit comments

Comments
 (0)