Posts tagged as “easy”

花花酱 LeetCode 24. Swap Nodes in Pairs

By zxi on October 2, 2018

Problem

Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:

Your algorithm should use only constant extra space.
You may not modify the values in the list’s nodes, only nodes itself may be changed.

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

ListNode *swapPairs(ListNode *head) {

if (!head || !head->next) return head;

ListNode d(0);

d.next = head;

head = &d;

while (head && head->next && head->next->next) {

auto n1 = head->next;

auto n2 = n1->next;

n1->next = n2->next;

n2->next = n1;

head->next = n2;

head = n1;

}

return d.next;

}

};

Python3

class Solution:

def swapPairs(self, head):

if not head or not head.next: return head

dummy = ListNode(0)

dummy.next = head

head = dummy

while head.next and head.next.next:

n1, n2 = head.next, head.next.next

n1.next = n2.next

n2.next = n1

head.next = n2

head = n1

return dummy.next

Problem

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

Note that an empty string is also considered valid.

Example 1:

Input: "()"
Output: true

Example 2:

Input: "()[]{}"
Output: true

Example 3:

Input: "(]"
Output: false

Example 4:

Input: "([)]"
Output: false

Example 5:

Input: "{[]}"
Output: true

Solution: Stack

Using a stack to track the existing open parentheses, if the current one is a close parenthesis but does not match the top of the stack, return false, otherwise pop the stack. Check whether the stack is empty in the end.

Time complexity: O(n)

Space complexity: O(n)

C++

// Author: Huahua, 0 ms

class Solution {

public:

bool isValid(string s) {

map<char, char> p{{')', '('}, {']', '['}, {'}', '{'}};

stack<char> st;

for (char c : s) {

if (!p.count(c)) {

st.push(c);

} else {

if (st.empty() || p[c] != st.top()) return false;

st.pop();

}

return st.empty();

}

};

Python3

# Author: Huahua

class Solution:

def isValid(self, s):

p = {')' : '(', ']': '[', '}' : '{'}

stack = []

for c in s:

if c not in p:

stack.append(c)

else:

if not stack or stack[-1] != p[c]: return False

stack.pop()

return not stack

Problem

n a deck of cards, each card has an integer written on it.

Return true if and only if you can choose X >= 2 such that it is possible to split the entire deck into 1 or more groups of cards, where:

Each group has exactly X cards.
All the cards in each group have the same integer.

Example 1:

Input: [1,2,3,4,4,3,2,1]
Output: true
Explanation: Possible partition [1,1],[2,2],[3,3],[4,4]

Example 2:

Input: [1,1,1,2,2,2,3,3]
Output: false
Explanation: No possible partition.

Example 3:

Input: [1]
Output: false
Explanation: No possible partition.

Example 4:

Input: [1,1]
Output: true
Explanation: Possible partition [1,1]

Example 5:

Input: [1,1,2,2,2,2]
Output: true
Explanation: Possible partition [1,1],[2,2],[2,2]

Note:

1 <= deck.length <= 10000
0 <= deck[i] < 10000

Solution 1: HashTable + Brute Force

Try all possible Xs. 2 ~ deck.size()

Time complexity: ~O(n)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms

class Solution {

public:

bool hasGroupsSizeX(vector<int>& deck) {

unordered_map<int, int> counts;

for (int card : deck) ++counts[card];

for (int i = 2; i <= deck.size(); ++i) {

if (deck.size() % i) continue;

bool ok = true;

for (const auto& pair : counts)

if (pair.second % i) {

ok = false;

break;

}

if (ok) return true;

}

return false;

}

};

Solution 2: HashTable + GCD

Time complexity: O(nlogn)

Space complexity: O(1)

C++

// Author: Huahua, 16 ms

class Solution {

public:

bool hasGroupsSizeX(vector<int>& deck) {

unordered_map<int, int> counts;

for (int card : deck) ++counts[card];

int X = deck.size();

for (const auto& p : counts)

X = __gcd(X, p.second);

return X >= 2;

}

};

Java

// Author: Somebody

class Solution {

public boolean hasGroupsSizeX(int[] deck) {

HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

for (int i=0; i<deck.length; i++) {

int curr = deck[i];

if (map.containsKey(curr)) {

map.put(curr, map.get(curr) + 1);

} else {

map.put(curr, 1);

}

// O(nLogn)

int gcd = 0;

for(Integer key: map.keySet()) {

gcd = findGCDOfTwoNumbers(map.get(key), gcd);

}

return gcd >= 2;

}

// O(Log n)

public static int findGCDOfTwoNumbers (int a, int b) {

if (b == 0) {

return a;

}

return findGCDOfTwoNumbers(b, a%b);

}

花花酱 LeetCode 88. Merge Sorted Array

By zxi on September 27, 2018

Problem

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

Solution:

Fill nums1 from back to front

Time complexity: O(m + n)

Space complexity: O(1) in-place

C++

// Author: Huahua

class Solution {

public:

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

int i = m - 1;

int j = n - 1;

int tail = m + n - 1;

while (j >= 0)

nums1[tail--] = (i >= 0 && nums1[i] > nums2[j]) ? nums1[i--] : nums2[j--];

}

};

花花酱 LeetCode 13. Roman to Integer

By zxi on September 19, 2018

Problem

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: C = 100, L = 50, XXX = 30 and III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

Solution

accumulate the value of each letter.

If the value of current letter is greater than the previous one, deduct twice of the previous value.

e.g. IX, 1 + 10 – 2 * 1 = 9 instead of 1 + 10 = 11

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int romanToInt(string s) {

map<char, int> m{{'I', 1}, {'V', 5},

{'X', 10}, {'L', 50},

{'C', 100}, {'D', 500},

{'M', 1000}};

int ans = 0;

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

ans += m[s[i]];

if (i > 0 && m[s[i]] > m[s[i - 1]])

ans -= 2 * m[s[i - 1]];

}

return ans;

}

};

Java

// Author: Huahua

class Solution {

private int v(char R) {

switch (R) {

case 'I' : return 1;

case 'V' : return 5;

case 'X' : return 10;

case 'L' : return 50;

case 'C' : return 100;

case 'D' : return 500;

case 'M' : return 1000;

default: break;

}

return 0;

}

public int romanToInt(String s) {

int ans = 0;

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

ans += v(s.charAt(i));

if ( i > 0 && v(s.charAt(i)) > v(s.charAt(i - 1)))

ans -= 2 * v(s.charAt(i - 1));

}

return ans;

}

Python3

class Solution:

def romanToInt(self, s):

m = {'I' : 1, 'V': 5, 'X': 10, 'L' : 50,

'C' : 100, 'D': 500, 'M': 1000}

ans = m[s[0]]

for c, p in zip(s[1:], s[0:-1]):

ans += m[c]

if m[c] > m[p]: ans -= 2 * m[p]

return ans

Posts tagged as “easy”

花花酱 LeetCode 20. Valid Parentheses

Problem

Solution: Stack

C++

Python3

Related Problems

花花酱 LeetCode 914. X of a Kind in a Deck of Cards

Problem

Solution 1: HashTable + Brute Force

C++

Solution 2: HashTable + GCD

C++

Java

花花酱 LeetCode 88. Merge Sorted Array

Problem

Solution:

C++

花花酱 LeetCode 13. Roman to Integer

Problem

Solution

C++

Java

Python3