Posts published in November 2017

花花酱 LeetCode 724. Find Pivot Index

By zxi on November 13, 2017

Problem:

Given an array of integers nums, write a method that returns the “pivot” index of this array.

We define the pivot index as the index where the sum of the numbers to the left of the index is equal to the sum of the numbers to the right of the index.

If no such index exists, we should return -1. If there are multiple pivot indexes, you should return the left-most pivot index.

Example 1:

Input:

nums = [1, 7, 3, 6, 5, 6]

Output: 3

Explanation:

The sum of the numbers to the left of index 3 (nums[3] = 6) is equal to the sum of numbers to the right of index 3.

Also, 3 is the first index where this occurs.

Example 2:

Input:

nums = [1, 2, 3]

Output: -1

Explanation:

There is no index that satisfies the conditions in the problem statement.

Note:

The length of nums will be in the range [0, 10000].
Each element nums[i] will be an integer in the range [-1000, 1000].

Idea:

Solution:

C++

// Author: Huahua

// Runtime: 43 ms

class Solution {

public:

int pivotIndex(vector<int>& nums) {

const int sum = accumulate(nums.begin(), nums.end(), 0);

int l = 0;

int r = sum;

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

r -= nums[i];

if (l == r) return i;

l += nums[i];

}

return -1;

}

};

Java

// Author: Huahua

// Runtime: 133 ms

class Solution {

public int pivotIndex(int[] nums) {

int sum = IntStream.of(nums).sum();

int l = 0;

int r = sum;

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

r -= nums[i];

if (l == r) return i;

l += nums[i];

}

return -1;

}

Python

"""

Author: Huahua

Runtime: 112 ms

"""

class Solution:

def pivotIndex(self, nums):

l, r = 0, sum(nums)

for i in range(len(nums)):

r -= nums[i]

if l == r: return i

l += nums[i]

return -1

花花酱 LeetCode 98. Validate Binary Search Tree

By zxi on November 11, 2017

Problem:

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node’s key.
The right subtree of a node contains only nodes with keys greater than the node’s key.
Both the left and right subtrees must also be binary search trees.

Example 1:

/ \

1 3

Binary tree [2,1,3], return true.

Example 2:

/ \

2 3

Binary tree [1,2,3], return false.

Solution 1

Traverse the tree and limit the range of each subtree and check whether root’s value is in the range.

Time complexity: O(n)

Space complexity: O(n)

Note: in order to cover the range of -2^31 ~ 2^31-1, we need to use long or nullable integer.

C++/long

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, LLONG_MIN, LLONG_MAX);

}

private:

bool isValidBST(TreeNode* root, long min_val, long max_val) {

if (!root) return true;

if (root->val <= min_val || root->val >= max_val)

return false;

return isValidBST(root->left, min_val, root->val)

&& isValidBST(root->right, root->val, max_val);

}

};

C++/nullable

class Solution {

public:

bool isValidBST(TreeNode* root) {

return isValidBST(root, nullptr, nullptr);

}

private:

bool isValidBST(TreeNode* root, int* min_val, int* max_val) {

if (!root) return true;

if ((min_val && root->val <= *min_val)

||(max_val && root->val >= *max_val))

return false;

return isValidBST(root->left, min_val, &root->val)

&& isValidBST(root->right, &root->val, max_val);

}

};

Java/nullable

// Author: Huahua

// Running time: 1 ms

class Solution {

public boolean isValidBST(TreeNode root) {

return isValidBST(root, null, null);

}

private boolean isValidBST(TreeNode root, Integer min, Integer max) {

if (root == null) return true;

if ((min != null && root.val <= min)

||(max != null && root.val >= max))

return false;

return isValidBST(root.left, min, root.val)

&& isValidBST(root.right, root.val, max);

}

Solution 2

Do an in-order traversal, the numbers should be sorted, thus we only need to compare with the previous number.

Time complexity: O(n)

Space complexity: O(n)

C++

class Solution {

public:

bool isValidBST(TreeNode* root) {

prev_ = nullptr;

return inOrder(root);

}

private:

TreeNode* prev_;

bool inOrder(TreeNode* root) {

if (!root) return true;

if (!inOrder(root->left)) return false;

if (prev_ && root->val <= prev_->val) return false;

prev_ = root;

return inOrder(root->right);

}

};

Java

// Author: Huahua

// Running time: 1 ms

class Solution {

private TreeNode prev;

public boolean isValidBST(TreeNode root) {

prev = null;

return inOrder(root);

}

private boolean inOrder(TreeNode root) {

if (root == null) return true;

if (!inOrder(root.left)) return false;

if (prev != null && root.val <= prev.val) return false;

prev = root;

return inOrder(root.right);

}

Solution: Binary Search

C++

// Author: Huahua

// Runtime: 52 ms

class Solution {

public:

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {

const int n1 = nums1.size();

const int n2 = nums2.size();

// Make sure n1 <= n2

if (n1 > n2) return findMedianSortedArrays(nums2, nums1);

const int k = (n1 + n2 + 1) / 2;

int l = 0;

int r = n1;

while (l < r) {

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

const int m2 = k - m1;

if (nums1[m1] < nums2[m2 - 1])

l = m1 + 1;

else

r = m1;

}

const int m1 = l;

const int m2 = k - l;

const int c1 = max(m1 <= 0 ? INT_MIN : nums1[m1 - 1],

m2 <= 0 ? INT_MIN : nums2[m2 - 1]);

if ((n1 + n2) % 2 == 1)

return c1;

const int c2 = min(m1 >= n1 ? INT_MAX : nums1[m1],

m2 >= n2 ? INT_MAX : nums2[m2]);

return (c1 + c2) * 0.5;

}

};

Java

// Author: Huahua

// Runtime: 66 ms

class Solution {

public double findMedianSortedArrays(int[] nums1, int[] nums2) {

int n1 = nums1.length;

int n2 = nums2.length;

if (n1 > n2)

return findMedianSortedArrays(nums2, nums1);

int k = (n1 + n2 + 1) / 2;

int l = 0;

int r = n1;

while (l < r) {

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

int m2 = k - m1;

if (nums1[m1] < nums2[m2 - 1])

l = m1 + 1;

else

r = m1;

}

int m1 = l;

int m2 = k - l;

int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1 - 1],

m2 <= 0 ? Integer.MIN_VALUE : nums2[m2 - 1]);

if ((n1 + n2) % 2 == 1)

return c1;

int c2 = Math.min(m1 >= n1 ? Integer.MAX_VALUE : nums1[m1],

m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);

return (c1 + c2) * 0.5;

}

Posts published in November 2017

花花酱 LeetCode 724. Find Pivot Index

花花酱 LeetCode 98. Validate Binary Search Tree

Solution 1

C++/long

C++/nullable

Java/nullable

Solution 2

C++

Java

Related Problem

花花酱 LeetCode 91. Decode Ways

花花酱 LeetCode 4. Median of Two Sorted Arrays

Solution: Binary Search

C++

Java

Related Problem:

花花酱 LeetCode 169. Majority Element