Press "Enter" to skip to content

Posts tagged as “array”

花花酱 LeetCode 724. Find Pivot Index

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:

Example 2:

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:

DP

Solution:

C++

 

Java

 

Python

 

 

花花酱 LeetCode 678. Valid Parenthesis String

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:

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

Example 1:

Example 2:

Example 3:

Note:

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



Idea:

Dynamic Programming / Counting

Solution 1:

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

 

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

 

C++ / Counting O(n)

 

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

 

花花酱 LeetCode 683. K Empty Slots

题目大意:有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:

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

Idea:

BST/Buckets



 

Solution 2: BST

C++

Solution 3: Buckets

C++

Solution 1: TLE with latest test cases

C++

Java

Python

花花酱 LeetCode 682. Baseball Game

Problem:

You’re now a baseball game point recorder.

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

  1. Integer (one round’s score): Directly represents the number of points you get in this round.
  2. "+" (one round’s score): Represents that the points you get in this round are the sum of the last two validround’s points.
  3. "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.
  4. "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:

Example 2:

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++:

 

Java:

 

Python

 

 

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

Problem:

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

  1. insert(val): Inserts an item val to the set if not already present.
  2. remove(val): Removes an item val from the set if present.
  3. 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:

 

Related Problems: