easy – Page 51 – Huahua’s Tech Road

花花酱 LeetCode 125. Valid Palindrome

By zxi on April 10, 2019

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Solution: Two pointers

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

C++

class Solution {

public:

bool isPalindrome(string s) {

int i = 0;

int j = s.length() - 1;

while (i < j) {

while (i < j && !isalnum(s[i])) ++i;

while (i < j && !isalnum(s[j])) --j;

if (tolower(s[i++]) != tolower(s[j--]))

return false;

}

return true;

}

};

花花酱 LeetCode 66. Plus One

By zxi on April 10, 2019

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution: Big Integer

Process from right to left (lest significant to most signification). Use carry to indicate whether need +1 for next digit or not.

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

c++

class Solution {

public:

vector<int> plusOne(vector<int>& digits) {

int carry = 1;

for (int i = digits.size() - 1; i >= 0; --i) {

digits[i] += carry;

carry = digits[i] / 10;

digits[i] %= 10;

}

if (carry) digits.insert(begin(digits), carry);

return digits;

}

};

花花酱 LeetCode 1013. Pairs of Songs With Total Durations Divisible by 60

By zxi on March 16, 2019

In a list of songs, the i-th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

Input: [30,20,150,100,40]
Output: 3
Explanation: Three pairs have a total duration divisible by 60:
(time[0] = 30, time[2] = 150): total duration 180
(time[1] = 20, time[3] = 100): total duration 120
(time[1] = 20, time[4] = 40): total duration 60

Example 2:

Input: [60,60,60]
Output: 3
Explanation: All three pairs have a total duration of 120, which is divisible by 60.

Note:

1 <= time.length <= 60000
1 <= time[i] <= 500

Solution: Two Sum of 60

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

C++

// Author: Huahua, running time: 36 ms, 11.6 MB

class Solution {

public:

int numPairsDivisibleBy60(vector<int>& time) {

vector<int> c(60);

int ans = 0;

for (int t : time) {

t %= 60;

ans += c[(60 - t) % 60];

++c[t];

}

return ans;

}

};

花花酱 LeetCode 1012. Complement of Base 10 Integer

By zxi on March 16, 2019

Every non-negative integer N has a binary representation. For example, 5 can be represented as "101" in binary, 11 as "1011" in binary, and so on. Note that except for N = 0, there are no leading zeroes in any binary representation.

The complement of a binary representation is the number in binary you get when changing every 1 to a 0 and 0 to a 1. For example, the complement of "101" in binary is "010" in binary.

For a given number N in base-10, return the complement of it’s binary representation as a base-10 integer.

Example 1:

Input: 5
Output: 2
Explanation: 5 is "101" in binary, with complement "010" in binary, which is 2 in base-10.

Example 2:

Input: 7
Output: 0
Explanation: 7 is "111" in binary, with complement "000" in binary, which is 0 in base-10.

Example 3:

Input: 10
Output: 5
Explanation: 10 is "1010" in binary, with complement "0101" in binary, which is 5 in base-10.

Note:

0 <= N < 10^9

Solution: Bit

Find the smallest binary number c that is all 1s, (e.g. “111”, “11111”) that is greater or equal to N.
ans = C ^ N or C – N

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

C++

// Author: Huahua, running time: 4 ms, 8 MB

class Solution {

public:

int bitwiseComplement(int N) {

int c = 1;

while (c < N)

c = (c << 1) | 1;

return N ^ c;

}

};

花花酱 LeetCode 1005. Maximize Sum Of Array After K Negations

By zxi on March 9, 2019

Given an array A of integers, we must modify the array in the following way: we choose an i and replace A[i] with -A[i], and we repeat this process K times in total. (We may choose the same index i multiple times.)

Return the largest possible sum of the array after modifying it in this way.

Example 1:

Input: A = [4,2,3], K = 1
Output: 5
Explanation: Choose indices (1,) and A becomes [4,-2,3].

Example 2:

Input: A = [3,-1,0,2], K = 3
Output: 6
Explanation: Choose indices (1, 2, 2) and A becomes [3,1,0,2].

Example 3:

Input: A = [2,-3,-1,5,-4], K = 2
Output: 13
Explanation: Choose indices (1, 4) and A becomes [2,3,-1,5,4].

Note:

1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100

Solution: Sorting

Flip as many as negative numbers as possible, if K > # of negative numbers and K is odd, flip the smallest element in the array.

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

C++

// Author: Huahua 8 ms 8.6MB

class Solution {

public:

int largestSumAfterKNegations(vector<int>& A, int K) {

std::sort(begin(A), end(A));

for (int& a : A) {

if (!K) break;

if (a < 0) {

a = -a;

--K;

}

return accumulate(begin(A), end(A), 0) - (K % 2 ? *min_element(begin(A), end(A)) * 2 : 0);

}

};

Posts tagged as “easy”

花花酱 LeetCode 125. Valid Palindrome

C++

花花酱 LeetCode 66. Plus One

c++

花花酱 LeetCode 1013. Pairs of Songs With Total Durations Divisible by 60

Solution: Two Sum of 60

C++

花花酱 LeetCode 1012. Complement of Base 10 Integer

Solution: Bit

C++

花花酱 LeetCode 1005. Maximize Sum Of Array After K Negations

Solution: Sorting

C++