花花酱 LeetCode 977. Squares of a Sorted Array

By zxi on January 20, 2019

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order.

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

Solution: Two pointers + Merge two sorted arrays

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

c++

// Author: Huahua, running time: 120 ms

class Solution {

public:

vector<int> sortedSquares(vector<int>& A) {

vector<int> ans(A.size());

auto e = prev(end(A));

auto s = begin(A);

auto it = end(ans);

while (--it >= begin(ans)) {

if (e > s && abs(*e) > abs(*s))

*it = pow(*e--, 2);

else

*it = pow(*s++, 2);

}

return ans;

}

};

花花酱 LeetCode 220. Contains Duplicate III

By zxi on December 20, 2018

Given an array of integers, find out whether there are two distinct indices i and j in the array such that the absolute difference between nums[i] and nums[j] is at most t and the absolute difference between i and j is at most k.

Example 1:

Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

Example 2:

Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

Example 3:

Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

Solution: Sliding Window + Multiset (OrderedSet)

Maintaining a sliding window of sorted numbers of k + 1. After the i-th number was inserted into the sliding window, check whether its left and right neighbors satisfy abs(nums[i] – neighbor) <= t

Time complexity: O(nlogk)
Space complexity: O(k)

C++

// Author: Huahua, running time: 12 ms

class Solution {

public:

bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {

multiset<long> s;

for (int i = 0; i < nums.size(); ++i) {

if (i > k)

s.erase(s.find(nums[i - k - 1]));

auto it = s.insert(nums[i]);

if (it != begin(s) && *it - *prev(it) <= t)

return true;

if (next(it) != end(s) && *next(it) - *it <= t)

return true;

}

return false;

}

};

花花酱 LeetCode 744. Find Smallest Letter Greater Than Target

By zxi on December 11, 2017

Problem:

Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.

Letters also wrap around. For example, if the target is target = 'z' and letters = ['a', 'b'], the answer is 'a'.

Examples:

Input:

letters = ["c", "f", "j"]

target = "a"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "c"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "d"

Output: "f"

Input:

letters = ["c", "f", "j"]

target = "g"

Output: "j"

Input:

letters = ["c", "f", "j"]

target = "j"

Output: "c"

Input:

letters = ["c", "f", "j"]

target = "k"

Output: "c"

Note:

letters has a length in range [2, 10000].
letters consists of lowercase letters, and contains at least 2 unique letters.
target is a lowercase letter.

Link: https://leetcode.com/problems/find-smallest-letter-greater-than-target/description/

Idea:

Scan the array Time complexity: O(n)
Binary search Time complexity: O(logn)

Solution 1:

C++ / Scan

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

for (const char c : letters)

if (c > target) return c;

return letters.front();

}

};

C++ / Set

// Author: Huahua

// Runtime: 16 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

vector<int> seen(26, 0);

for (const char c : letters)

seen[c - 'a'] = 1;

while (true) {

if (++target > 'z') target = 'a';

if (seen[target - 'a']) return target;

}

return ' ';

}

};

C++ / Binary Search

// Author: Huahua

// Runtime: 15 ms

class Solution {

public:

char nextGreatestLetter(vector<char>& letters, char target) {

int l = 0;

int r = letters.size();

while (l < r) {

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

if (letters[m] <= target)

l = m + 1;

else

r = m;

}

return letters[l % letters.size()];

}

};

花花酱 LeetCode 21: Merge Two Sorted Lists

By zxi on September 3, 2017

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Solution 1: Iterative O(n)

// Author: Huahua

class Solution {

public:

Solution 1: Iterative

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

ListNode dummy(0);

ListNode* tail=&dummy;

while(l1 && l2) {

if(l1->val < l2->val) {

tail->next=l1;

l1=l1->next;

}else{

tail->next=l2;

l2=l2->next;

}

tail=tail->next;

}

if(l1) tail->next = l1;

if(l2) tail->next = l2;

return dummy.next;

}

};

Solution 2: Recursive O(n)

// Author: Huahua

class Solution {

public:

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

// If one of the list is emptry, return the other one.

if(!l1 || !l2) return l1 ? l1 : l2;

// The smaller one becomes the head.

if(l1->val < l2->val) {

l1->next = mergeTwoLists(l1->next, l2);

return l1;

} else {

l2->next = mergeTwoLists(l1, l2->next);

return l2;

}

};

Posts tagged as “sorted”

花花酱 LeetCode 977. Squares of a Sorted Array

Solution: Two pointers + Merge two sorted arrays

c++

花花酱 LeetCode 220. Contains Duplicate III

Solution: Sliding Window + Multiset (OrderedSet)

C++

花花酱 LeetCode 744. Find Smallest Letter Greater Than Target

花花酱 LeetCode 21: Merge Two Sorted Lists