Posts tagged as “array”

花花酱 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:

花花酱 LeetCode 451. Sort Characters By Frequency

By zxi on September 13, 2017

Problem:

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Input:
“tree”

Output:
“eert”

Explanation:
‘e’ appears twice while ‘r’ and ‘t’ both appear once.
So ‘e’ must appear before both ‘r’ and ‘t’. Therefore “eetr” is also a valid answer.
Example 2:

Input:
“cccaaa”

Output:
“cccaaa”

Explanation:
Both ‘c’ and ‘a’ appear three times, so “aaaccc” is also a valid answer.
Note that “cacaca” is incorrect, as the same characters must be together.
Example 3:

Input:
“Aabb”

Output:
“bbAa”

Explanation:
“bbaA” is also a valid answer, but “Aabb” is incorrect.
Note that ‘A’ and ‘a’ are treated as two different characters.

Idea:

Counting sort

Solution 1:

Sort the string based on element frequency

// Author: Huahua

// Running time: 289 ms

class Solution {

public:

string frequencySort(string& s) {

array<int, 128> f{0};

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

// Author: Huahua

// Running time: 139 ms

class Solution {

public:

string frequencySort(string& s) {

map<char, int> f;

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

// Author: Huahua

// Running time: 29 ms

class Solution {

public:

string frequencySort(string& s) {

array<int, 128> f{0};

for(char c:s) ++f[c];

sort(s.begin(), s.end(), [&f] (char a, char b) {

return f[a] > f[b] || (f[a] == f[b] && a > b);

});

return s;

}

};

Solution 2:

Counting sort

// Author: Huahua

// Running time: 12 ms

class Solution {

public:

string frequencySort(const string& s) {

vector<int> f(128, 0);

for(char c:s) ++f[c];

vector<pair<int,char>> v;

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

if (f[i] > 0) v.emplace_back(f[i], i);

}

sort(v.rbegin(), v.rend());

string ans;

for(const auto& kv : v) {

ans.append(kv.first, kv.second);

}

return ans;

}

};

花花酱 LeetCode 268. Missing Number

By zxi on September 9, 2017

Problem:

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Idea:

sum / xor

Solution:

// Author: Huahua

class Solution {

public:

// Solution 1: Sum

int missingNumber(vector<int>& nums) {

int n = nums.size();

int x = (0+n)*(n+1)/2 - accumulate(nums.begin(), nums.end(), 0);

return x;

}

// Solution 2: XOR

int missingNumber(vector<int>& nums) {

int n = nums.size();

int x = 0;

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

x = x ^ i ^ nums[i-1];

return x;

}

};

花花酱 LeetCode 154. Find Minimum in Rotated Sorted Array II

By zxi on September 7, 2017

Problem:

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

Find the minimum element.

The array may contain duplicates.

Idea:

Divide and conquer

Time complexity:

Average: O(logn)

Worst: O(n)

Solution:

// Author: Huahua

class Solution {

public:

int findMin(vector<int> &num) {

return findMin(num, 0, num.size()-1);

}

int findMin(const vector<int>& num, int l, int r)

{

// One or two elements, solve it directly

if (l+1 >= r) return

min(num[l], num[r]);

// Sorted

if (num[l] < num[r])

return num[l];

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

// Recursively find the solution

return min(findMin(num, l, m - 1),

findMin(num, m, r));

}

};

Related Problems: