Posts published in “Easy”

花花酱 LeetCode 733. Flood Fill

By zxi on November 28, 2017

Problem:

An image is represented by a 2-D array of integers, each integer representing the pixel value of the image (from 0 to 65535).

Given a coordinate (sr, sc) representing the starting pixel (row and column) of the flood fill, and a pixel value newColor, “flood fill” the image.

To perform a “flood fill”, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color as the starting pixel), and so on. Replace the color of all of the aforementioned pixels with the newColor.

At the end, return the modified image.

Example 1:

Input:

image = [[1,1,1],[1,1,0],[1,0,1]]

sr = 1, sc = 1, newColor = 2

Output: [[2,2,2],[2,2,0],[2,0,1]]

Explanation:

From the center of the image (with position (sr, sc) = (1, 1)), all pixels connected

by a path of the same color as the starting pixel are colored with the new color.

Note the bottom corner is not colored 2, because it is not 4-directionally connected

to the starting pixel.

Note:

The length of image and image[0] will be in the range [1, 50].
The given starting pixel will satisfy 0 <= sr < image.length and 0 <= sc < image[0].length.
The value of each color in image[i][j] and newColor will be an integer in [0, 65535].

Idea

DFS

Solution:

C++ / DFS

Time complexity: O(mn)

Space complexity: O(1)

// Author: Huahua

// Runtime: 33 ms

class Solution {

public:

vector<vector<int>> floodFill(vector<vector<int>>& image,

int sr, int sc, int newColor) {

if (image[sr][sc] == newColor) return image;

int m = image.size();

int n = image[0].size();

floodFill(image, sc, sr, n, m, image[sr][sc], newColor);

return image;

}

private:

void floodFill(vector<vector<int>>& image,

int x, int y, int n, int m, int orgColor, int newColor) {

if (x < 0 || x >= n || y < 0 || y >= m) return;

if (image[y][x] != orgColor) return;

image[y][x] = newColor;

floodFill(image, x + 1, y, n, m, orgColor, newColor);

floodFill(image, x - 1, y, n, m, orgColor, newColor);

floodFill(image, x, y + 1, n, m, orgColor, newColor);

floodFill(image, x, y - 1, n, m, orgColor, newColor);

}

};

Related Problems:

花花酱 LeetCode 53. Maximum Subarray

By zxi on November 27, 2017

Problem:

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Idea:

Solution:

C++

// Author: Huahua

// Runtime: 6 ms (better than 98.66%)

class Solution {

public:

int maxSubArray(vector<int>& nums) {

vector<int> f(nums.size());

f[0] = nums[0];

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

f[i] = max(f[i - 1] + nums[i], nums[i]);

return *std::max_element(f.begin(), f.end());

}

};

花花酱 LeetCode 657. Judge Route Circle

By zxi on November 27, 2017

Problem:

Initially, there is a Robot at position (0, 0). Given a sequence of its moves, judge if this robot makes a circle, which means it moves back to the original place.

The move sequence is represented by a string. And each move is represent by a character. The valid robot moves are R (Right), L (Left), U (Up) and D (down). The output should be true or false representing whether the robot makes a circle.

Example 1:

1 2	Input: "UD" Output: true

Example 2:

1 2	Input: "LL" Output: false

Idea:

Simulation

Solution:

C++

// Author: Huahua

// Runtime: 19 ms

class Solution {

public:

bool judgeCircle(string moves) {

int cx{0};

int cy{0};

for (const char move : moves) {

switch(move) {

case 'U':

cy--;

break;

case 'D':

cy++;

break;

case 'R':

cx++;

break;

case 'L':

cx--;

break;

}

return cx==0 && cy==0;

}

};

花花酱 LeetCode 1. Two Sum

By zxi on November 23, 2017

Problem:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Idea:

Brute force / Hashtable

Solution1:

Brute force / C++

Time complexity: O(n^2)

Space complexity: O(1)

// Author: Huahua

// Runtime: 166 ms

class Solution {

public:

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

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

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

int sum = nums[i] + nums[j];

if (sum == target) {

return {i, j};

}

return {};

}

};

Solution 2:

Hashtable / C++

Time complexity: O(n)

Space complexity: O(n)

// Author: Huahua

// Runtime: 6 ms

class Solution {

public:

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

unordered_map<int, int> indies;

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

indies[nums[i]] = i;

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

int left = target - nums[i];

if (indies.count(left) && indies[left] != i) {

return {i, indies[left]};

}

return {};

}

};

花花酱 LeetCode 731. My Calendar II – 花花酱

By zxi on November 19, 2017

Problem:

Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example 1:

MyCalendar();

MyCalendar.book(10, 20); // returns true

MyCalendar.book(50, 60); // returns true

MyCalendar.book(10, 40); // returns true

MyCalendar.book(5, 15); // returns false

MyCalendar.book(5, 10); // returns true

MyCalendar.book(25, 55); // returns true

Explanation<b>:</b>

The first two events can be booked. The third event can be double booked.

The fourth event (5, 15) can't be booked, because it would result in a triple booking.

The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.

The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;

the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.
In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

Idea:

Brute Force

Solution1:

Brute Force

Time Complexity: O(n^2)

Space Complexity: O(n)

// Author: Huahua

// Runtime: 82 ms

class MyCalendarTwo {

public:

MyCalendarTwo() {}

bool book(int start, int end) {

for (const auto& kv : overlaps_)

if (max(start, kv.first) < min(end, kv.second)) return false;

for (const auto& kv : booked_) {

const int ss = max(start, kv.first);

const int ee = min(end, kv.second);

if (ss < ee) overlaps_.emplace_back(ss, ee);

}

booked_.emplace_back(start, end);

return true;

}

private:

vector<pair<int, int>> booked_;

vector<pair<int, int>> overlaps_;

};

Java

// Author: Huahua

// Runtime: 156 ms

class MyCalendarTwo {

private List<int[]> booked_;

private List<int[]> overlaps_;

public MyCalendarTwo() {

booked_ = new ArrayList<>();

overlaps_ = new ArrayList<>();

}

public boolean book(int start, int end) {

for (int[] range : overlaps_)

if (Math.max(range[0], start) < Math.min(range[1], end))

return false;

for (int[] range : booked_) {

int ss = Math.max(range[0], start);

int ee = Math.min(range[1], end);

if (ss < ee) overlaps_.add(new int[]{ss, ee});

}

booked_.add(new int[]{start, end});

return true;

}

Python

"""

Author: Huahua

Runtime: 638 ms

"""

class MyCalendarTwo:

def __init__(self):

self.booked_ = []

self.overlaps_ = []

def book(self, start, end):

for s, e in self.overlaps_:

if start < e and end > s: return False

for s, e in self.booked_:

if start < e and end > s:

self.overlaps_.append([max(start, s), min(end, e)])

self.booked_.append([start, end])

return True

Solution 2:

Counting

Time Complexity: O(n^2logn)

Space Complexity: O(n)

// Author: Huahua

// Runtime: 212 ms

class MyCalendarTwo {

public:

MyCalendarTwo() {}

bool book(int start, int end) {

++delta_[start];

--delta_[end];

int count = 0;

for (const auto& kv : delta_) {

count += kv.second;

if (count == 3) {

--delta_[start];

++delta_[end];

return false;

}

if (kv.first > end) break;

}

return true;

}

private:

map<int, int> delta_;

};

Related Problems: