Posts tagged as “array”

花花酱 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 678. Valid Parenthesis String

By zxi on September 30, 2017

Problem:

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

Any left parenthesis '(' must have a corresponding right parenthesis ')'.
Any right parenthesis ')' must have a corresponding left parenthesis '('.
Left parenthesis '(' must go before the corresponding right parenthesis ')'.
'*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
An empty string is also valid.

Example 1:

1 2	Input: "()" Output: True

Example 2:

1 2	Input: "(*)" Output: True

Example 3:

1 2	Input: "(*))" Output: True

Note:

The string size will be in the range [1, 100].

Idea:

Dynamic Programming / Counting

Solution 1:

C++ / DP / Top-down O(n^3)

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

bool checkValidString(const string& s) {

int l = s.length();

m_ = vector<vector<int>>(l, vector<int>(l, -1));

return isValid(s, 0, l - 1);

}

private:

vector<vector<int>> m_;

bool isValid(const string& s, int i, int j) {

if (i > j) return true;

if (m_[i][j] >= 0) return m_[i][j];

if (i == j) return m_[i][j] = (s[i] == '*');

if ((s[i] == '(' || s[i] == '*')

&&(s[j] == ')' || s[j] == '*')

&& isValid(s, i + 1, j - 1))

return m_[i][j] = 1;

for (int p = i; p < j; ++p)

if (isValid(s, i, p) && isValid(s, p + 1, j))

return m_[i][j] = 1;

return m_[i][j] = 0;

}

};

C++ / DP/ Bottom-up O(n^3)

// Author: Huahua

// Runtime: 12 ms

class Solution {

public:

bool checkValidString(const string& s) {

int l = s.length();

if (l == 0) return true;

vector<vector<int>> dp(l, vector<int>(l, 0));

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

if (s[i] == '*') dp[i][i] = 1;

for (int len = 2; len <= l; ++len)

for (int i = 0; i <= l - len; ++i) {

int j = i + len - 1;

// (...), *...), (...*, *...*

if ((s[i] == '(' || s[i] == '*')

&&(s[j] == ')' || s[j] == '*'))

if (len == 2 || dp[i + 1][j - 1]) {

dp[i][j] = 1;

continue;

}

for (int k = i; k < j; ++k)

if (dp[i][k] && dp[k + 1][j]) {

dp[i][j] = 1;

break;

}

return dp[0][l - 1];

}

};

C++ / Counting O(n)

// Author: Huahua

// Runtime: 3 ms

class Solution {

public:

bool checkValidString(string s) {

int min_op = 0;

int max_op = 0;

for (char c : s) {

if (c == '(') ++min_op; else --min_op;

if (c != ')') ++max_op; else --max_op;

if (max_op < 0) return false;

min_op = max(0, min_op);

}

return min_op == 0;

}

};

Java / DP / Bottom-up O(n^3)

class Solution {

public boolean checkValidString(String s) {

int l = s.length();

if (l == 0) return true;

boolean[][] dp = new boolean[l][l];

char[] ss = s.toCharArray();

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

if (ss[i] == '*') dp[i][i] = true;

for (int len = 2; len <= l; ++len)

for (int i = 0; i + len <= l; ++i) {

int j = i + len - 1;

if ((ss[i] == '*' || ss[i] == '(')

&&(ss[j] == '*' || ss[j] == ')')) {

if (len == 2 || dp[i + 1][j - 1]) {

dp[i][j] = true;

continue;

}

for (int k = i; k < j; ++k)

if (dp[i][k] && dp[k + 1][j]) {

dp[i][j] = true;

break;

}

return dp[0][l - 1];

}

花花酱 LeetCode 683. K Empty Slots

By zxi on September 29, 2017

题目大意：有n个花盆，第i天，第flowers[i]个花盆的花会开。问是否存在一天，两朵花之间有k个空花盆。

Problem:

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:

Input: 
flowers: [1,3,2]
k: 1
Output: 2
Explanation: In the second day, the first and the third flower have become blooming.

Example 2:

Input: 
flowers: [1,2,3]
k: 1
Output: -1

Note:

The given array will be in the range [1, 20000].

Idea:

BST/Buckets

Solution 2: BST

C++

// Author: Huahua

// Runtime: 228 ms

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

set<int> xs;

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

int x = flowers[i];

auto r = xs.insert(x).first;

auto l = r;

if (++r != xs.end() && *r == x + k + 1) return i + 1;

if (l != xs.begin() && *(--l) == x - k - 1) return i + 1;

}

return -1;

}

};

Solution 3: Buckets

C++

// Author: Huahua

// Runtime: 196 ms (better than 94%)

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

++k;

int bs = (n + k - 1) / k;

vector<int> lows(bs, INT_MAX);

vector<int> highs(bs, INT_MIN);

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

int x = flowers[i];

int p = x / k;

if (x < lows[p]) {

lows[p] = x;

if (p > 0 && highs[p - 1] == x - k) return i + 1;

}

if (x > highs[p]) {

highs[p] = x;

if (p < bs - 1 && lows[p + 1] == x + k) return i + 1;

}

return -1;

}

};

Solution 1: TLE with latest test cases

C++

// Author: Huahua

// Runtime: 192 ms (better than 97.85%)

class Solution {

public:

int kEmptySlots(vector<int>& flowers, int k) {

int n = flowers.size();

if (n == 0 || k >= n) return -1;

std::unique_ptr<char[]> f(new char[n+1]);

memset(f.get(), 0, (n + 1)*sizeof(char));

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

if (IsValid(flowers[i], k, n, f.get()))

return i + 1;

return -1;

}

private:

bool IsValid(int x, int k, int n, char* f) {

f[x] = 1;

if (x + k + 1 <= n && f[x + k + 1]) {

bool valid = true;

for (int i = 1; i <= k; ++i)

if (f[x + i]) {

valid = false;

break;

}

if (valid) return true;

}

if (x - k - 1 > 0 && f[x - k - 1]) {

for (int i = 1; i <= k; ++i)

if (f[x - i]) return false;

return true;

}

return false;

}

};

Java

// Author: Huahua

// Runtime: 17 ms

class Solution {

public int kEmptySlots(int[] flowers, int k) {

int n = flowers.length;

if (n == 0 || k >= n) return -1;

int[] f = new int[n + 1];

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

if (IsValid(flowers[i], k, n, f))

return i + 1;

return -1;

}

private boolean IsValid(int x, int k, int n, int[] f) {

f[x] = 1;

if (x + k + 1 <= n && f[x + k + 1] == 1) {

boolean valid = true;

for (int i = 1; i <= k; ++i)

if (f[x + i] == 1) {

valid = false;

break;

}

if (valid) return true;

}

if (x - k - 1 > 0 && f[x - k - 1] == 1) {

for (int i = 1; i <= k; ++i)

if (f[x - i] == 1) return false;

return true;

}

return false;

}

Python

"""

Author: Huahua

Runtime: 398 ms

"""

class Solution:

def kEmptySlots(self, flowers, k):

n = len(flowers)

f = [0] * (n + 1)

i = 0

def isValid(x, k, n, f):

f[x] = 1

if x + k + 1 <= n and f[x + k + 1] == 1:

valid = True

for i in range(k):

if f[x + i + 1] == 1:

valid = False

break

if valid: return True

if x - k - 1 > 0 and f[x - k - 1] == 1:

for i in range(k):

if f[x - i - 1] == 1:

return False

return True

return False

for x in flowers:

i += 1

if isValid(x, k, n, f): return i

return -1

花花酱 LeetCode 682. Baseball Game

By zxi on September 23, 2017

Problem:

You’re now a baseball game point recorder.

Given a list of strings, each string can be one of the 4 following types:

Integer (one round’s score): Directly represents the number of points you get in this round.
"+" (one round’s score): Represents that the points you get in this round are the sum of the last two validround’s points.
"D" (one round’s score): Represents that the points you get in this round are the doubled data of the last valid round’s points.
"C" (an operation, which isn’t a round’s score): Represents the last valid round’s points you get were invalid and should be removed.

Each round’s operation is permanent and could have an impact on the round before and the round after.

You need to return the sum of the points you could get in all the rounds.

Example 1:

Input: ["5","2","C","D","+"]

Output: 15

Explanation:

Round 1: You could get 5 points. The sum is: 5.

Round 2: You could get 2 points. The sum is: 7.

Operation 1: The round 2's data was invalid. The sum is: 5.

Round 3: You could get 10 points (the round 2's data has been removed). The sum is: 15.

Round 4: You could get 5 + 10 = 15 points. The sum is: 30.

Example 2:

Input: ["5","-2","4","C","D","9","+","+"]

Output: 27

Explanation:

Round 1: You could get 5 points. The sum is: 5.

Round 2: You could get -2 points. The sum is: 3.

Round 3: You could get 4 points. The sum is: 7.

Operation 1: The round 3's data is invalid. The sum is: 3.

Round 4: You could get -4 points (the round 3's data has been removed). The sum is: -1.

Round 5: You could get 9 points. The sum is: 8.

Round 6: You could get -4 + 9 = 5 points. The sum is 13.

Round 7: You could get 9 + 5 = 14 points. The sum is 27.

Note:

The size of the input list will be between 1 and 1000.
Every integer represented in the list will be between -30000 and 30000.

Idea:

Simulation

Solution:

C++:

class Solution {

public:

int calPoints(vector<string>& ops) {

vector<int> s;

int sum = 0;

for (const string& op : ops) {

if (op == "+")

s.push_back(s.end()[-1] + s.end()[-2]);

else if (op == "C")

s.pop_back();

else if (op == "D")

s.push_back(s.back() * 2);

else

s.push_back(stoi(op));

}

return accumulate(s.begin(), s.end(), 0);

}

};

Java:

class Solution {

public int calPoints(String[] ops) {

List<Integer> s = new ArrayList<Integer>();

for (String op : ops) {

int n = s.size();

if (op.equals("+"))

s.add(s.get(n - 1) + s.get(n - 2));

else if (op.equals("C"))

s.remove(n - 1);

else if (op.equals("D"))

s.add(s.get(n - 1) * 2);

else

s.add(Integer.parseInt(op));

}

return s.stream().reduce(0, Integer::sum);

}

Python

class Solution:

def calPoints(self, ops):

"""

:type ops: List[str]

:rtype: int

"""

s = []

for op in ops:

if op == "+": s += [s[-1] + s[-2]]

elif op == "C": s = s[:-1]

elif op == "D": s += [s[-1]*2]

else: s += [int(op)]

return sum(s)

花花酱 LeetCode 380. Insert Delete GetRandom O(1)

By zxi on September 16, 2017

Problem:

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the set if not already present.
remove(val): Removes an item val from the set if present.
getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.

Idea:

Hashtable + array

Time complexity:

O(1)

Solution:

// Author: Huahua

// Running time: 49 ms

class RandomizedSet {

public:

/** Initialize your data structure here. */

RandomizedSet() {}

/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */

bool insert(int val) {

if(m_.count(val)) return false;

m_[val] = vals_.size();

vals_.push_back(val);

return true;

}

/** Removes a value from the set. Returns true if the set contained the specified element. */

bool remove(int val) {

if(!m_.count(val)) return false;

int index = m_[val];

m_[vals_.back()] = index;

m_.erase(val);

std::swap(vals_[index], vals_.back());

vals_.pop_back();

return true;

}

/** Get a random element from the set. */

int getRandom() {

int index = rand() % vals_.size();

return vals_[index];

}

private:

// val -> index in the array

unordered_map<int, int> m_;

vector<int> vals_;

};

Related Problems: