Posts tagged as “easy”

花花酱 LeetCode 441. Arranging Coins

By zxi on July 7, 2018

Problem

You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly kcoins.

Given n, find the total number of full staircase rows that can be formed.

n is a non-negative integer and fits within the range of a 32-bit signed integer.

Example 1:

n = 5

The coins can form the following rows:
¤
¤ ¤
¤ ¤

Because the 3rd row is incomplete, we return 2.

Example 2:

n = 8

The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

Because the 4th row is incomplete, we return 3.

Solution: Math

Time complexity: O(sqrt(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int arrangeCoins(int n) {

for (long i = sqrt(n) * 2 + 1; i >= 0; --i)

if (i * (i + 1) / 2 <= n) return i;

return -1;

}

};

Time complexity: O(1)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

int arrangeCoins(int n) {

// x * (1 + x) / 2 <= n

// x^2 + x - 2n <= 0

// x <= (-1 + sqrt(1 + 8n)) / 2

return (-1 + sqrt(1 + static_cast<long>(n) * 8)) / 2;

}

};

花话酱 LeetCode 859. Buddy Strings

By zxi on June 26, 2018

Problem

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.

Example 1:

Input: A = "ab", B = "ba"
Output: true

Example 2:

Input: A = "ab", B = "ab"
Output: false

Example 3:

Input: A = "aa", B = "aa"
Output: true

Example 4:

Input: A = "aaaaaaabc", B = "aaaaaaacb"
Output: true

Example 5:

Input: A = "", B = "aa"
Output: false

Note:

0 <= A.length <= 20000
0 <= B.length <= 20000
A and B consist only of lowercase letters.

Solution: HashTable

Time complexity: O(n)

Space complexity: O(26)

// Author: Huahua

// Running time: 7 ms

class Solution {

public:

bool buddyStrings(string A, string B) {

if (A.length() != B.length()) return false;

vector<int> ca(26);

vector<int> cb(26);

int diff = 0;

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

if (A[i] != B[i] && diff++ > 2) return false;

++ca[A[i]-'a'];

++cb[B[i]-'a'];

}

for (int i = 0; i < 26; ++i) {

if (diff == 0 && ca[i] > 1) return true;

if (ca[i] != cb[i]) return false;

}

return diff == 2;

}

};

花花酱 LeetCode 852. Peak Index in a Mountain Array

By zxi on June 17, 2018

Problem

Let’s call an array A a mountain if the following properties hold:

A.length >= 3
There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]

Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].

Example 1:

Input: [0,1,0]
Output: 1

Example 2:

Input: [0,2,1,0]
Output: 1

Note:

3 <= A.length <= 10000
0 <= A[i] <= 10^6
A is a mountain, as defined above.

Solution1: Liner Scan

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

for (int i = 1; i < A.size(); ++i)

if (A[i] < A[i - 1]) return i - 1;

}

};

C++/STL

// Author: Huahua

// Running time: 16 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

return max_element(begin(A), end(A)) - begin(A);

}

};

Solution 2: Binary Search

Find the smallest l such that A[l] > A[l + 1].

Time complexity: O(logn)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 18 ms

class Solution {

public:

int peakIndexInMountainArray(vector<int>& A) {

int l = 0;

int r = A.size();

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > A[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

};

Java

// Author: Huahua, 3 ms

class Solution {

public int peakIndexInMountainArray(int[] A) {

int l = 0;

int r = A.length;

while (l < r) {

int m = l + (r - l) / 2;

if (A[m] > A[m + 1])

r = m;

else

l = m + 1;

}

return l;

}

Python3

# Author: Huahua, 40 ms

class Solution:

def peakIndexInMountainArray(self, A):

l, r = 0, len(A)

while l < r:

m = l + (r - l) // 2

if A[m] > A[m + 1]:

r = m

else:

l = m + 1

return l

花花酱 LeetCode 849. Maximize Distance to Closest Person

By zxi on June 11, 2018

Problem

In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty.

There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.

Return that maximum distance to closest person.

Example 1:

Input: [1,0,0,0,1,0,1]
Output: 2
Explanation: 
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.

Example 2:

Input: [1,0,0,0]
Output: 3
Explanation: 
If Alex sits in the last seat, the closest person is 3 seats away.
This is the maximum distance possible, so the answer is 3.

Note:

1 <= seats.length <= 20000
seats contains only 0s or 1s, at least one 0, and at least one 1.

Solution

Time complexity: O(n)

Space complexity: O(1)

// Author: Huahua

// Running time: 15 ms

class Solution {

public:

int maxDistToClosest(vector<int>& seats) {

int n = seats.size();

int prev = -1;

int ans = 0;

for (int i = 0; i <= n; ++i) {

if (i == n) ans = max(ans, n - prev - 1);

else if (seats[i]) {

if (prev == -1) ans = i;

else ans = max(ans, (i - prev) / 2);

prev = i;

}

return ans;

}

};

花花酱 LeetCode 844. Backspace String Compare

By zxi on June 3, 2018

Problem

题目大意：给你2个字符串表示打字顺序，判断它们的结果是否相同，’#’表示退格键。

https://leetcode.com/problems/backspace-string-compare/description/

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1 <= S.length <= 200
1 <= T.length <= 200
S and T only contain lowercase letters and '#' characters.

Solution: Simulation

Time complexity: O(|S| + |T|)

Space complexity: O(|S| + |T|)

C++

// Author: Huahua

// Running time: 5 ms

class Solution {

public:

bool backspaceCompare(string S, string T) {

return type(S) == type(T);

}

private:

string type(string S) {

string o;

for (char c : S)

if (c == '#') {

if (!o.empty())

o.pop_back();

} else {

o.push_back(c);

}

return o;

}

};

Java

// Author: Huahua, 7 ms

class Solution {

public boolean backspaceCompare(String S, String T) {

return type(S).equals(type(T));

}

private String type(String s) {

StringBuilder sb = new StringBuilder();

for (char c : s.toCharArray()) {

if (c == '#') {

if (sb.length() > 0)

sb.setLength(sb.length() - 1);

} else {

sb.append(c);

}

return sb.toString();

}

Python3

# Author: Huahua, 40 ms

class Solution:

def backspaceCompare(self, S, T):

def sim(S):

ans = ''

for c in S:

if c == '#':

if len(ans) > 0: ans = ans[:-1]

else:

ans += c

return ans

return sim(S) == sim(T)