花花酱 LeetCode 889. Spiral Matrix III

By zxi on August 13, 2018

Problem

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid.

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.)

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

Example 2:

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

Note:

1 <= R <= 100
1 <= C <= 100
0 <= r0 < R
0 <= c0 < C

Solution: Simulation

We can find out the moving sequence is ESWWNNEEESSSWWWWNNNN.

The pattern is 1,1,2,2,3,3,4,4,… steps in one direction, and turn right for 90 degrees.

directions are E,S,W,N,E,S,W,N…

Time complexity: O(max(R,C)^2)

Space complexity: O(1) or O(RC) if ans included.

// Author: Huahua

// Running time: 52 ms

class Solution {

public:

vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {

vector<vector<int>> ans;

int k = 0;

int dirs[][2]{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // ESWN

int d = 0; // E

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

while (++k) {

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

for (int j = 0; j < k; ++j) {

c0 += dirs[d][0];

r0 += dirs[d][1];

if (c0 < 0 || c0 >= C || r0 < 0 || r0 >= R) continue;

ans.push_back({r0, c0});

if (ans.size() == R * C) return ans;

}

d = (d + 1) % 4;

}

return {};

}

};

花花酱 SP5 Binary Search

By zxi on August 12, 2018

Template:

Time complexity: O(log(r-l)) * O(f(m) + g(m))

Space complexity: O(1)

"""

Returns the smallest number m such that g(m) is true.

"""

def binary_search(l, r):

while l < r:

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

if f(m): return m # if m is the answer

if g(m):

r = m # new range [l, m)

else

l = m + 1 # new range [m+1, r)

return l # or not found

Slides:

Lower Bound / Upper Bound

#include <iostream>

#include <vector>

using namespace std;

int upper_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

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

if (A[m] > val)

r = m;

else

l = m + 1;

}

return l;

}

int lower_bound(const vector<int>& A, int val, int l, int r) {

while (l < r) {

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

if (A[m] >= val)

r = m;

else

l = m + 1;

}

return l;

}

int main() {

vector<int> A{1, 2, 2, 2, 4, 4, 5};

cout << lower_bound(A, 0, 0, A.size()) << endl; // 0

cout << lower_bound(A, 2, 0, A.size()) << endl; // 1

cout << lower_bound(A, 3, 0, A.size()) << endl; // 4

cout << upper_bound(A, 2, 0, A.size()) << endl; // 4

cout << upper_bound(A, 4, 0, A.size()) << endl; // 6

cout << upper_bound(A, 5, 0, A.size()) << endl; // 7

}

Mentioned Problems

花花酱 LeetCode 886. Possible Bipartition

By zxi on August 12, 2018

Problem

Given a set of N people (numbered 1, 2, ..., N), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if dislikes[i] = [a, b], it means it is not allowed to put the people numbered a and b into the same group.

Return true if and only if it is possible to split everyone into two groups in this way.

Example 1:

Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]

Example 2:

Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false

Example 3:

Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false

Note:

1 <= N <= 2000
0 <= dislikes.length <= 10000
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
There does not exist i != j for which dislikes[i] == dislikes[j].

Solution: Graph Coloring

Color a node with one color, and color all it’s disliked nodes with another color, if can not finish return false.

Time complexity: O(V+E)

Space complexity: O(V+E)

C++ / DFS

// Author: Huahua

// Running time: 96 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

g_ = vector<vector<int>>(N);

for (const auto& d : dislikes) {

g_[d[0] - 1].push_back(d[1] - 1);

g_[d[1] - 1].push_back(d[0] - 1);

}

colors_ = vector<int>(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors_[i] == 0 && !dfs(i, 1)) return false;

return true;

}

private:

vector<vector<int>> g_;

vector<int> colors_;

bool dfs(int cur, int color) {

colors_[cur] = color;

for (int nxt : g_[cur]) {

if (colors_[nxt] == color) return false;

if (colors_[nxt] == 0 && !dfs(nxt, -color)) return false;

}

return true;

}

};

C++ / BFS

// Author: Huahua

// Running time: 100 ms

class Solution {

public:

bool possibleBipartition(int N, vector<vector<int>>& dislikes) {

vector<vector<int>> g(N);

for (const auto& d : dislikes) {

g[d[0] - 1].push_back(d[1] - 1);

g[d[1] - 1].push_back(d[0] - 1);

}

queue<int> q;

vector<int> colors(N, 0); // 0: unknown, 1: red, -1: blue

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

if (colors[i] != 0) continue;

q.push(i);

colors[i] = 1;

while (!q.empty()) {

int cur = q.front(); q.pop();

for (int nxt : g[cur]) {

if (colors[nxt] == colors[cur]) return false;

if (colors[nxt] != 0) continue;

colors[nxt] = -colors[cur];

q.push(nxt);

}

return true;

}

};

Problem

We are given two sentences A and B. (A sentence is a string of space separated words. Each word consists only of lowercase letters.)

A word is uncommon if it appears exactly once in one of the sentences, and does not appear in the other sentence.

Return a list of all uncommon words.

You may return the list in any order.

Example 1:

Input: A = "this apple is sweet", B = "this apple is sour"
Output: ["sweet","sour"]

Example 2:

Input: A = "apple apple", B = "banana"
Output: ["banana"]

Note:

0 <= A.length <= 200
0 <= B.length <= 200
A and B both contain only spaces and lowercase letters.

Solution: HashTable

Time complexity: O(m+n)

Space complexity: O(m+n)

C++

class Solution {

public:

vector<string> uncommonFromSentences(string A, string B) {

istringstream ss(A + " " + B);

unordered_map<string, int> counts;

string s;

while (ss >> s) ++counts[s];

vector<string> ans;

for (const auto& p : counts)

if (p.second == 1)

ans.push_back(p.first);

return ans;

}

};

花花酱 LeetCode 707. Design Linked List

By zxi on August 9, 2018

Problem

Design your implementation of the linked list. You can choose to use the singly linked list or the doubly linked list. A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node. If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement these functions in your linked list class:

get(index) : Get the value of the index-th node in the linked list. If the index is invalid, return -1.
addAtHead(val) : Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.
addAtTail(val) : Append a node of value val to the last element of the linked list.
addAtIndex(index, val) : Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted.
deleteAtIndex(index) : Delete the index-th node in the linked list, if the index is valid.

Example:

MyLinkedList linkedList = new MyLinkedList();

linkedList.addAtHead(1);

linkedList.addAtTail(3);

linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3

linkedList.get(1); // returns 2

linkedList.deleteAtIndex(1); // now the linked list is 1->3

linkedList.get(1); // returns 3

Note:

All values will be in the range of [1, 1000].
The number of operations will be in the range of [1, 1000].
Please do not use the built-in LinkedList library.

Solution: Single linked list

Keep tracking head and tail of the list.

Time Complexity:

addAtHead, addAtTail O(1)

addAtIndex O(index)

deleteAtIndex O(index)

Space complexity: O(1)

C++

Tracking head/tail and size of the list.

// Author: Huahua

// Running time: 24 ms

class MyLinkedList {

public:

MyLinkedList(): head_(nullptr), tail_(nullptr), size_(0) {}

~MyLinkedList() {

Node* node = head_;

while (node) {

Node* cur = node;

node = node->next;

delete cur;

}

head_ = nullptr;

tail_ = nullptr;

}

int get(int index) {

if (index < 0 || index >= size_) return -1;

auto node = head_;

while (index--)

node = node->next;

return node->val;

}

void addAtHead(int val) {

head_ = new Node(val, head_);

if (size_++ == 0)

tail_ = head_;

}

void addAtTail(int val) {

auto node = new Node(val);

if (size_++ == 0) {

head_ = tail_ = node;

} else {

tail_->next = node;

tail_ = tail_->next;

}

void addAtIndex(int index, int val) {

if (index < 0 || index > size_) return;

if (index == 0) return addAtHead(val);

if (index == size_) return addAtTail(val);

Node dummy(0, head_);

Node* prev = &dummy;

while (index--) prev = prev->next;

prev->next = new Node(val, prev->next);

++size_;

}

void deleteAtIndex(int index) {

if (index < 0 || index >= size_) return;

Node dummy(0, head_);

Node* prev = &dummy;

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

prev = prev->next;

Node* node_to_delete = prev->next;

prev->next = prev->next->next;

if (index == 0) head_ = prev->next;

if (index == size_ - 1) tail_ = prev;

delete node_to_delete;

--size_;

}

private:

struct Node {

int val;

Node* next;

Node(int _val): Node(_val, nullptr) {}

Node(int _val, Node* _next): val(_val), next(_next) {}

};

Node* head_;

Node* tail_;

int size_;

};

// Author: Huahua

// Running time: 28 ms

class MyLinkedList {

public:

MyLinkedList(): head_(nullptr), tail_(nullptr), dummy_(0), size_(0) {}

~MyLinkedList() {

Node* node = head_;

while (node) {

Node* cur = node;

node = node->next;

delete cur;

}

head_ = nullptr;

tail_ = nullptr;

}

int get(int index) {

if (index < 0 || index >= size_) return -1;

return getNode(index)->val;

}

void addAtHead(int val) {

head_ = new Node(val, head_);

if (size_++ == 0)

tail_ = head_;

}

void addAtTail(int val) {

auto node = new Node(val);

if (size_++ == 0) {

head_ = tail_ = node;

} else {

tail_->next = node;

tail_ = tail_->next;

}

void addAtIndex(int index, int val) {

if (index < 0 || index > size_) return;

if (index == 0) return addAtHead(val);

if (index == size_) return addAtTail(val);

Node* prev = getNode(index - 1);

prev->next = new Node(val, prev->next);

++size_;

}

void deleteAtIndex(int index) {

if (index < 0 || index >= size_) return;

Node* prev = getNode(index - 1);

Node* node_to_delete = prev->next;

prev->next = node_to_delete->next;

if (index == 0) head_ = prev->next;

if (index == size_ - 1) tail_ = prev;

delete node_to_delete;

--size_;

}

private:

struct Node {

int val;

Node* next;

Node(int _val): Node(_val, nullptr) {}

Node(int _val, Node* _next): val(_val), next(_next) {}

};

Node* head_; // Does not own

Node* tail_; // Does not own

Node dummy_;

int size_;

Node* getNode(int index) {

dummy_.next = head_;

Node* n = &dummy_;

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

n = n->next;

return n;

}

};

Python3

"""

Author: Huahua

Running time: 132 ms

"""

class Node:

def __init__(self, val, _next=None):

self.val = val

self.next = _next

class MyLinkedList:

def __init__(self):

self.head = self.tail = None

self.size = 0

def getNode(self, index):

n = Node(0, self.head)

for i in range(index + 1):

n = n.next

return n

def get(self, index):

if index < 0 or index >= self.size: return -1

return self.getNode(index).val

def addAtHead(self, val):

n = Node(val, self.head)

self.head = n

if self.size == 0:

self.tail = n

self.size += 1

def addAtTail(self, val):

n = Node(val)

if self.size == 0:

self.head = self.tail = n

else:

self.tail.next = n

self.tail = n

self.size += 1

def addAtIndex(self, index, val):

if index < 0 or index > self.size: return

if index == 0: return self.addAtHead(val)

if index == self.size: return self.addAtTail(val)

prev = self.getNode(index - 1)

n = Node(val, prev.next)

prev.next = n

self.size += 1

def deleteAtIndex(self, index):

if index < 0 or index >= self.size: return

prev = self.getNode(index - 1)

prev.next = prev.next.next

if index == 0: self.head = prev.next

if index == self.size - 1: self.tail = prev

self.size -= 1

Java

// Author: Huahua

// Running time: 74 ms

class MyLinkedList {

class Node {

public int val;

public Node next;

public Node(int val) { this.val = val; this.next = null; }

public Node(int val, Node next) { this.val = val; this.next = next; }

}

private Node head;

private Node tail;

private int size;

public MyLinkedList() {

this.head = this.tail = null;

this.size = 0;

}

private Node getNode(int index) {

Node n = new Node(0, this.head);

while (index-- >= 0) {

n = n.next;

}

return n;

}

public int get(int index) {

if (index < 0 || index >= size) return -1;

return getNode(index).val;

}

public void addAtHead(int val) {

this.head = new Node(val, this.head);

if (this.size++ == 0)

this.tail = this.head;

}

public void addAtTail(int val) {

Node n = new Node(val);

if (this.size++ == 0)

this.head = this.tail = n;

else

this.tail = this.tail.next = n;

}

public void addAtIndex(int index, int val) {

if (index < 0 || index > this.size) return;

if (index == 0) { this.addAtHead(val); return; }

if (index == size) { this.addAtTail(val); return; }

Node prev = this.getNode(index - 1);

prev.next = new Node(val, prev.next);

++this.size;

}

public void deleteAtIndex(int index) {

if (index < 0 || index >= this.size) return;

Node prev = this.getNode(index - 1);

prev.next = prev.next.next;

if (index == 0) this.head = prev.next;

if (index == this.size - 1) this.tail = prev;

--this.size;

}

花花酱 LeetCode 889. Spiral Matrix III

Problem

Solution: Simulation

花花酱 SP5 Binary Search

Mentioned Problems

花花酱 LeetCode 886. Possible Bipartition

Problem

Solution: Graph Coloring

C++ / DFS

C++ / BFS

Related Problem

花花酱 LeetCode 888. Uncommon Words from Two Sentences

Problem

Solution: HashTable

Huahua's Tech Road

花花酱 LeetCode 889. Spiral Matrix III

Problem

Solution: Simulation

花花酱 SP5 Binary Search

Mentioned Problems

花花酱 LeetCode 886. Possible Bipartition

Problem

Solution: Graph Coloring

C++ / DFS

C++ / BFS

Related Problem

花花酱 LeetCode 888. Uncommon Words from Two Sentences

Problem

Solution: HashTable

花花酱 LeetCode 707. Design Linked List

Problem

Solution: Single linked list