Huahua’s Tech Road

花花酱 LeetCode 166. Fraction to Recurring Decimal

By zxi on November 28, 2021

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10⁴ for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: "0.5"

Example 2:

Input: numerator = 2, denominator = 1
Output: "2"

Example 3:

Input: numerator = 2, denominator = 3
Output: "0.(6)"

Example 4:

Input: numerator = 4, denominator = 333
Output: "0.(012)"

Example 5:

Input: numerator = 1, denominator = 5
Output: "0.2"

Constraints:

-2³¹ <= numerator, denominator <= 2³¹ - 1
denominator != 0

Solution: Hashtable

Time complexity: O(?)

C++

// Author: Huahua

class Solution {

public:

string fractionToDecimal(int numerator, int denominator) {

stringstream ss,ss2;

long long n = numerator;

long long d = denominator;

if ( n > 0 && d < 0 || n < 0 && d > 0) {

ss << "-";

n = abs(n);

d = abs(d);

}

ss << (n / d);

long long r = n % d;

bool loop = false;

int count = 0;

int loop_start;

if (r) {

n = r;

ss << ".";

unordered_map<int, int> rs;

rs[r] = 0;

while (r) {

n = n*10;

r = n % d;

ss2 << (n / d);

n = r;

if (r && rs.count(r)) {

loop = true;

loop_start = rs[r];

break;

}

rs[r] = ++count;

}

if (loop) {

auto s2 = ss2.str();

ss << s2.substr(0, loop_start) << "(" << s2.substr(loop_start) << ")";

} else {

ss << ss2.str();

}

return ss.str();

}

};

花花酱 LeetCode 160. Intersection of Two Linked Lists

By zxi on November 28, 2021

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

intersectVal – The value of the node where the intersection occurs. This is 0 if there is no intersected node.
listA – The first linked list.
listB – The second linked list.
skipA – The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
skipB – The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Constraints:

The number of nodes of listA is in the m.
The number of nodes of listB is in the n.
0 <= m, n <= 3 * 10⁴
1 <= Node.val <= 10⁵
0 <= skipA <= m
0 <= skipB <= n
intersectVal is 0 if listA and listB do not intersect.
intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Follow up: Could you write a solution that runs in O(n) time and use only O(1) memory?

Solution 1: Two Passes by swapping heads

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

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

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

ListNode* a = headA;

ListNode* b = headB;

while (a != b) {

a = a ? a->next : headB;

b = b ? b->next : headA;

}

return a;

}

};

花花酱 LeetCode 155. Min Stack

By zxi on November 28, 2021

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output

[null,null,null,null,-3,null,0,-2]

Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2

Constraints:

-2³¹ <= val <= 2³¹ - 1
Methods pop, top and getMin operations will always be called on non-empty stacks.
At most 3 * 10⁴ calls will be made to push, pop, top, and getMin.

Solution 1: Two Stacks

One normal stack, one monotonic stack to store the min values.

Time complexity: O(1) per op
Space complexity: O(n)

C++

// Author: Huahua

class MinStack {

public:

void push(int x) {

m_data.push(x);

if (m_s.empty() || x <= m_s.top())

m_s.push(x);

}

void pop() {

if (!m_s.empty() && m_data.top() == m_s.top())

m_s.pop();

m_data.pop();

}

int top() {

return m_data.top();

}

int getMin() {

return m_s.empty() ? m_data.top() : m_s.top();

}

private:

stack<int> m_data;

stack<int> m_s;

};

花花酱 LeetCode 151. Reverse Words in a String

By zxi on November 28, 2021

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Example 4:

Input: s = "  Bob    Loves  Alice   "
Output: "Alice Loves Bob"

Example 5:

Input: s = "Alice does not even like bob"
Output: "bob like even not does Alice"

Constraints:

1 <= s.length <= 10⁴
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Solution: Stack

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

string reverseWords(string s) {

stringstream ss(s);

stack<string> st;

string w;

while (ss >> w)

st.push(w);

string ans;

while (!st.empty()) {

ans += st.top();

st.pop();

if (!st.empty()) ans += ' ';

}

return ans;

}

};

Solution: In-Place

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

string reverseWords(string& s) {

reverse(begin(s), end(s));

int l = 0;

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

if (s[i] == ' ') continue;

if (l) ++l;

j = i;

while (j < s.length() && s[j] != ' ') ++j;

reverse(begin(s) + l, begin(s) + j);

l += (j - i);

i = j;

}

s.resize(l);

return s;

}

};

花花酱 LeetCode 142. Linked List Cycle II

By zxi on November 28, 2021

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Constraints:

The number of the nodes in the list is in the range [0, 10⁴].
-10⁵ <= Node.val <= 10⁵
pos is -1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Solution 1: Hashtset

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

ListNode *detectCycle(ListNode *head) {

unordered_set<ListNode*> s;

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

if (!s.insert(cur).second) return cur;

return nullptr;

}

};

Solution: Fast slow pointers

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode *detectCycle(ListNode *head) {

unordered_set<ListNode*> s;

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

if (!s.insert(cur).second) return cur;

return nullptr;

}

};

Huahua's Tech Road

花花酱 LeetCode 166. Fraction to Recurring Decimal

Solution: Hashtable

C++

花花酱 LeetCode 160. Intersection of Two Linked Lists

Solution 1: Two Passes by swapping heads

C++

花花酱 LeetCode 155. Min Stack

Solution 1: Two Stacks

C++

花花酱 LeetCode 151. Reverse Words in a String

Solution: Stack

C++

Solution: In-Place

C++

花花酱 LeetCode 142. Linked List Cycle II

Solution 1: Hashtset

C++

Solution: Fast slow pointers

C++