Posts tagged as “cycle”

花花酱 LeetCode 202. Happy Number

By zxi on December 5, 2021

Write an algorithm to determine if a number n is happy.

A happy number is a number defined by the following process:

Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.

Return true if n is a happy number, and false if not.

Example 1:

Input: n = 19
Output: true
Explanation:
1² + 9² = 82
8² + 2² = 68
6² + 8² = 100
1² + 0² + 0² = 1

Example 2:

Input: n = 2
Output: false

Constraints:

1 <= n <= 2³¹ - 1

Solution: Simulation

We can use a hasthable to store all the number we generated so far.

Time complexity: O(L)
Space complexity: O(L)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

unordered_set<int> s;

while (n != 1) {

if (!s.insert(n).second) return false;

n = getNext(n);

}

return true;

}

};

Optimization: Space reduction

Since the number sequence always has a cycle, we can use slow / fast pointers to detect the cycle without using a hastable.

Time complexity: O(L)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool isHappy(int n) {

auto getNext = [](int x) -> int {

int ans = 0;

while (x) {

ans += (x % 10) * (x % 10);

x /= 10;

}

return ans;

};

int slow = n;

int fast = getNext(n);

do {

slow = getNext(slow);

fast = getNext(getNext(fast));

} while (slow != fast);

return slow == 1;

}

};

花花酱 LeetCode 1559. Detect Cycles in 2D Grid

By zxi on August 23, 2020

Given a 2D array of characters grid of size m x n, you need to find if there exists any cycle consisting of the same value in grid.

A cycle is a path of length 4 or more in the grid that starts and ends at the same cell. From a given cell, you can move to one of the cells adjacent to it – in one of the four directions (up, down, left, or right), if it has the same value of the current cell.

Also, you cannot move to the cell that you visited in your last move. For example, the cycle (1, 1) -> (1, 2) -> (1, 1) is invalid because from (1, 2) we visited (1, 1) which was the last visited cell.

Return true if any cycle of the same value exists in grid, otherwise, return false.

Example 1:

Input: grid = [["a","a","a","a"],["a","b","b","a"],["a","b","b","a"],["a","a","a","a"]]
Output: true
Explanation: There are two valid cycles shown in different colors in the image below:

Example 2:

Input: grid = [["c","c","c","a"],["c","d","c","c"],["c","c","e","c"],["f","c","c","c"]]
Output: true
Explanation: There is only one valid cycle highlighted in the image below:

Example 3:

Input: grid = [["a","b","b"],["b","z","b"],["b","b","a"]]
Output: false

Constraints:

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid consists only of lowercase English letters.

Solution: DFS

Finding a cycle in an undirected graph => visiting a node that has already been visited and it’s not the parent node of the current node.
b b
b b
null -> (0, 0) -> (0, 1) -> (1, 1) -> (1, 0) -> (0, 0)
The second time we visit (0, 0) which has already been visited before and it’s not the parent of the current node (1, 0) ( (1, 0)’s parent is (1, 1) ) which means we found a cycle.

Time complexity: O(m*n)
Space complexity: O(m*n)

C++

class Solution {

public:

bool containsCycle(vector<vector<char>>& grid) {

const int m = grid.size();

const int n = grid[0].size();

vector<vector<int>> seen(m, vector<int>(n));

vector<int> dirs{0, 1, 0, -1, 0};

function<bool(int, int, int, int)> dfs = [&](int i, int j, int pi, int pj) {

++seen[i][j];

for (int d = 0; d < 4; ++d) {

int ni = i + dirs[d];

int nj = j + dirs[d + 1];

if (ni < 0 || nj < 0 || ni >= m || nj >= n) continue;

if (grid[ni][nj] != grid[i][j]) continue;

if (!seen[ni][nj]) {

if (dfs(ni, nj, i, j)) return true;

} else if (ni != pi || nj != pj) {

return true;

}

return false;

};

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

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

if (!seen[i][j]++ && dfs(i, j, -1, -1))

return true;

return false;

}

};

花花酱 LeetCode 802. Find Eventual Safe States

By zxi on March 17, 2018

Problem

https://leetcode.com/problems/find-eventual-safe-states/description/

题目大意：给一个有向图，找出所有不可能进入环的节点。

In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop.

Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.

Which nodes are eventually safe? Return them as an array in sorted order.

The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph.

Example:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Here is a diagram of the above graph.

Note:

graph will have length at most 10000.
The number of edges in the graph will not exceed 32000.
Each graph[i] will be a sorted list of different integers, chosen within the range [0, graph.length - 1].

Idea: Finding Cycles

Solution 1: DFS

A node is safe if and only if: itself and all of its neighbors do not have any cycles.

Time complexity: O(V + E)

Space complexity: O(V + E)

// Author: Huahua

// Running time: 155 ms

class Solution {

public:

vector<int> eventualSafeNodes(vector<vector<int>>& graph) {

vector<State> states(graph.size(), UNKNOWN);

vector<int> ans;

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

if (dfs(graph, i, states) == SAFE)

ans.push_back(i);

return ans;

}

private:

enum State {UNKNOWN, VISITING, SAFE, UNSAFE};

State dfs(const vector<vector<int>>& g, int cur, vector<State>& states) {

if (states[cur] == VISITING)

return states[cur] = UNSAFE;

if (states[cur] != UNKNOWN)

return states[cur];

states[cur] = VISITING;

for (int next : g[cur])

if (dfs(g, next, states) == UNSAFE)

return states[cur] = UNSAFE;

return states[cur] = SAFE;

}

};

Posts tagged as “cycle”

花花酱 LeetCode 202. Happy Number

Solution: Simulation

C++

Optimization: Space reduction

C++

花花酱 LeetCode 142. Linked List Cycle II

Solution 1: Hashtset

C++

Solution: Fast slow pointers

C++

花花酱 LeetCode 1559. Detect Cycles in 2D Grid

Solution: DFS

C++

花花酱 LeetCode 141. Linked List Cycle

Problem

Solution1: HashTable

Solution2: Fast + Slow pointers

花花酱 LeetCode 802. Find Eventual Safe States

Problem

Idea: Finding Cycles

Solution 1: DFS

Related Problems