Huahua’s Tech Road

花花酱 LeetCode 171. Excel Sheet Column Number

By zxi on November 28, 2021

Given a string columnTitle that represents the column title as appear in an Excel sheet, return its corresponding column number.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnTitle = "A"
Output: 1

Example 2:

Input: columnTitle = "AB"
Output: 28

Example 3:

Input: columnTitle = "ZY"
Output: 701

Example 4:

Input: columnTitle = "FXSHRXW"
Output: 2147483647

Constraints:

1 <= columnTitle.length <= 7
columnTitle consists only of uppercase English letters.
columnTitle is in the range ["A", "FXSHRXW"].

Solution: Base conversion

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

C++

// Author: Huahua

class Solution {

public:

int titleToNumber(string s) {

int ans = 0;

for (int i = s.length() - 1, cur = 0; i >= 0; --i) {

cur = cur ? cur * 26 : 1;

ans += (s[i] - 'A' + 1) * cur;

}

return ans;

}

};

花花酱 LeetCode 168. Excel Sheet Column Title

By zxi on November 28, 2021

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnNumber = 1
Output: "A"

Example 2:

Input: columnNumber = 28
Output: "AB"

Example 3:

Input: columnNumber = 701
Output: "ZY"

Example 4:

Input: columnNumber = 2147483647
Output: "FXSHRXW"

Constraints:

1 <= columnNumber <= 2³¹ - 1

Solution: Base conversion

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

string convertToTitle(int n) {

string ans;

do {

n--;

ans += 'A' + (char)(n % 26);

n /= 26;

} while (n);

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 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 171. Excel Sheet Column Number

Solution: Base conversion

C++

Related Problems

花花酱 LeetCode 168. Excel Sheet Column Title

Solution: Base conversion

C++

Related Problems

花花酱 LeetCode 166. Fraction to Recurring Decimal

Solution: Hashtable

C++

花花酱 LeetCode 155. Min Stack

Solution 1: Two Stacks

C++

Huahua's Tech Road

花花酱 LeetCode 171. Excel Sheet Column Number

Solution: Base conversion

C++

Related Problems

花花酱 LeetCode 168. Excel Sheet Column Title

Solution: Base conversion

C++

Related Problems

花花酱 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++