花花酱 LeetCode 703. Kth Largest Element in a Stream

By zxi on July 12, 2018

Problem

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Your KthLargest class will have a constructor which accepts an integer k and an integer array nums, which contains initial elements from the stream. For each call to the method KthLargest.add, return the element representing the kth largest element in the stream.

Example:

int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3);   // returns 4
kthLargest.add(5);   // returns 5
kthLargest.add(10);  // returns 5
kthLargest.add(9);   // returns 8
kthLargest.add(4);   // returns 8

Note:
You may assume that nums‘ length ≥ k-1 and k ≥ 1.

Solution: BST / Min Heap

Time complexity: O(nlogk)

Space complexity: O(k)

C++ / BST

// Author: Huahua

// Running time: 32 ms

class KthLargest {

public:

KthLargest(int k, vector<int> nums): k_(k) {

for (int num : nums)

add(num);

}

int add(int val) {

s_.insert(val);

if (s_.size() > k_)

s_.erase(s_.begin());

return *s_.begin();

}

private:

const int k_;

multiset<int> s_;

};

C++ / Min Heap

// Author: Huahua

// Running time: 28 ms

class KthLargest {

public:

KthLargest(int k, vector<int> nums): k_(k) {

for (int num : nums)

add(num);

}

int add(int val) {

s_.push(val);

if (s_.size() > k_)

s_.pop();

return s_.top();

}

private:

const int k_;

priority_queue<int, vector<int>, greater<int>> s_; // min heap

};

花花酱 LeetCode 700. Search in a Binary Search Tree

By zxi on July 12, 2018

Problem

Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node’s value equals the given value. Return the subtree rooted with that node. If such node doesn’t exist, you should return NULL.

For example,

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

You should return this subtree:

      2     
     / \   
    1   3

In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.

Solution: Recursion

Time complexity: O(logn ~ n)

Space complexity: O(logn ~ n)

// Author: Huahua

// Running time: 24 ms

class Solution {

public:

TreeNode* searchBST(TreeNode* root, int val) {

if (root == nullptr) return nullptr;

if (val == root->val)

return root;

else if (val > root->val)

return searchBST(root->right, val);

return searchBST(root->left, val);

}

};

花花酱 LeetCode 704. Binary Search

By zxi on July 12, 2018

Problem

Given a sorted (in ascending order) integer array nums of n elements and a target value, write a function to search target in nums. If target exists, then return its index, otherwise return -1.

Example 1:

Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4

Example 2:

Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1

Note:

You may assume that all elements in nums are unique.
n will be in the range [1, 10000].
The value of each element in nums will be in the range [-9999, 9999].

Solution: Binary Search

Time complexity: O(logn)

Space complexity: O(1)

// Author: Huahua

// Running time: 32 ms

class Solution {

public:

int search(vector<int>& nums, int target) {

int l = 0;

int r = nums.size();

while (l < r) {

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

if (nums[m] == target)

return m;

else if (nums[m] > target)

r = m;

else

l = m + 1;

}

return -1;

}

};

STL

// Author: Huahua

// Running time: 36 ms

class Solution {

public:

int search(vector<int>& nums, int target) {

auto it = lower_bound(nums.begin(), nums.end(), target);

if (it == nums.end() || *it != target) return -1;

return it - nums.begin();

}

};

花花酱 LeetCode 709. To Lower Case

By zxi on July 12, 2018

Problem

Implement function ToLowerCase() that has a string parameter str, and returns the same string in lowercase.

Solution

Time complexity: O(n)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

string toLowerCase(string str) {

for (char &c : str)

if (c >= 'A' && c <= 'Z') c = c - 'A' + 'a';

return str;

}

};

Java

// Author: Huahua, 1 ms

class Solution {

public String toLowerCase(String str) {

char[] s = str.toCharArray();

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

if (s[i] >= 'A' && s[i] <= 'Z') s[i] = (char)(s[i] - 'A' + 'a');

return new String(s);

}

Python3

# Author: Huahua, 40 ms

class Solution:

def toLowerCase(self, str):

ans = ''

for c in str:

if c >= 'A' and c <= 'Z':

ans += chr(ord(c) + 32)

else:

ans += c

return ans

Python3 1-linear

# Author: Huahua, 68 ms

class Solution:

def toLowerCase(self, str):

return ''.join(chr(ord(c) + 32) if c >= 'A' and c <= 'Z' else c for c in str)

花花酱 LeetCode 775. Global and Local Inversions

By zxi on July 9, 2018

Problem

We have some permutation A of [0, 1, ..., N - 1], where N is the length of A.

The number of (global) inversions is the number of i < j with 0 <= i < j < N and A[i] > A[j].

The number of local inversions is the number of i with 0 <= i < N and A[i] > A[i+1].

Return true if and only if the number of global inversions is equal to the number of local inversions.

Example 1:

Input: A = [1,0,2]
Output: true
Explanation: There is 1 global inversion, and 1 local inversion.

Example 2:

Input: A = [1,2,0]
Output: false
Explanation: There are 2 global inversions, and 1 local inversion.

Note:

A will be a permutation of [0, 1, ..., A.length - 1].
A will have length in range [1, 5000].
The time limit for this problem has been reduced.

Solution1: Brute Force (TLE)

Time complexity: O(n^2)

Space complexity: O(1)

C++

// Author: Huahua

// Running time: TLE (208/208 test cases passed)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

const int n = A.size();

int local = 0;

for (int i = 0; i < n - 1; ++i)

if (A[i] > A[i + 1]) ++local;

int global = 0;

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

for (int j = i + 1; j < n; ++j)

if (A[i] > A[j] && ++global > local) return false;

return global == local;

}

};

Solution2: MergeSort

Time complexity: O(nlogn)

Space complexity: O(n)

// Author: Huahua

// Running time: 52 ms (<96.42%)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

const int n = A.size();

int local = 0;

for (int i = 0; i < n - 1; ++i)

if (A[i] > A[i + 1]) ++local;

tmp = vector<int>(n);

int global = mergeSort(A, 0, n - 1);

return global == local;

}

private:

vector<int> tmp;

int mergeSort(vector<int>& A, int l, int r) {

if (l >= r) return 0;

const int len = r - l + 1;

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

int inv = mergeSort(A, l, m) + mergeSort(A, m + 1, r);

int i = l;

int j = m + 1;

int k = 0;

while (i <= m && j <= r) {

if (A[i] <= A[j]) {

tmp[k++] = A[i++];

} else {

tmp[k++] = A[j++];

inv += m - i + 1;

}

while (i <= m) tmp[k++] = A[i++];

while (j <= r) tmp[k++] = A[j++];

std::copy(tmp.begin(), tmp.begin() + len, A.begin() + l);

return inv;

}

};

// Author: Huahua

// Running time: 208 ms

public class Solution {

public bool IsIdealPermutation(int[] A) {

var n = A.Length;

var localInv = 0;

for (var i = 1; i < n; ++i)

if (A[i] < A[i - 1]) ++localInv;

tmp = new int[n];

var globalInv = MergeSort(A, 0, n - 1);

return localInv == globalInv;

}

private int[] tmp;

private int MergeSort(int[] A, int l, int r) {

if (l >= r) return 0;

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

int inv = MergeSort(A, l, m) + MergeSort(A, m + 1, r);

int i = l;

int j = m + 1;

int k = 0;

while (i <= m && j <= r) {

if (A[i] <= A[j]) {

tmp[k++] = A[i++];

} else {

inv += m - i + 1;

tmp[k++] = A[j++];

}

while (i <= m) tmp[k++] = A[i++];

while (j <= r) tmp[k++] = A[j++];

Array.Copy(tmp, 0, A, l, k);

return inv;

}

Solution3: Input Property

Input is a permutation of [0, 1, …, N – 1]

Time Complexity: O(n)

Space Complexity: O(1)

// Author: Huahua

// Running time: 40 ms (<99.26%)

class Solution {

public:

bool isIdealPermutation(vector<int>& A) {

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

if (abs(A[i] - i) > 1) return false;

return true;

}

};

Huahua's Tech Road

花花酱 LeetCode 703. Kth Largest Element in a Stream

Problem

Solution: BST / Min Heap

花花酱 LeetCode 700. Search in a Binary Search Tree

Problem

Solution: Recursion

花花酱 LeetCode 704. Binary Search

Problem

Solution: Binary Search

花花酱 LeetCode 709. To Lower Case

Problem

Solution

C++

Java

Python3

Python3 1-linear

花花酱 LeetCode 775. Global and Local Inversions

Problem

Solution1: Brute Force (TLE)

Solution2: MergeSort

Solution3: Input Property