剑指offer4

91

剑指 Offer II 091. 粉刷房子

一排房子n个，可以涂成红色、蓝色、绿色这三种颜色中的一种，需要让各个颜色并不相同

给定一个花费数组，其中的每个元素就是该房子涂成红、蓝、绿三种颜色所需要的花费

计算粉刷完所有房子最少的花费成本

#include <algorithm>
#include <iostream>
#include <vector>

int minCost(std::vector<std::vector<int>> &costs) {
  std::vector<int> dp = costs[0];
  for (size_t i = 1; i < costs.size(); ++i) {
    std::vector<int> dpNew(3);
    for (int j = 0; j < 3; ++j) {
      dpNew[j] = std::min(dp[(j + 1) % 3], dp[(j + 2) % 3]) + costs[i][j];
    }
    dp = dpNew;
  }
  return std::min({dp[0], dp[1], dp[2]});
}

int main() {
  std::vector<std::vector<int>> costs = {{17, 2, 17}, {16, 16, 5}, {14, 3, 19}};
  std::cout << "Minimum cost: " << minCost(costs) << std::endl;
  return 0;
}

package main

func minCost(costs [][]int) int {
	dp := costs[0]
	for _, cost := range costs[1:] {
		dpNew := make([]int, 3)
		for j, c := range cost {
			dpNew[j] = min(dp[(j+1)%3], dp[(j+2)%3]) + c
		}
		dp = dpNew
	}
	return min(min(dp[0], dp[1]), dp[2])
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}

92

剑指 Offer II 092. 翻转字符

一个0 1组成的字符串，求使得s单调递增(前面全是0 后面全是1)的最小翻转次数

#include <algorithm>
#include <iostream>
#include <string>

int min(int a, int b) { return (a < b) ? a : b; }

int minFlipsMonoIncr(const std::string &s) {
  int dp0 = 0, dp1 = 0;
  for (char c : s) {
    int dp0New = dp0, dp1New = std::min(dp0, dp1);
    if (c == '1') {
      dp0New++;
    } else {
      dp1New++;
    }
    dp0 = dp0New;
    dp1 = dp1New;
  }
  return std::min(dp0, dp1);
}

int main() {
  std::string s = "00110";
  std::cout << "Minimum flips: " << minFlipsMonoIncr(s) << std::endl;
  return 0;
}

package main

func minFlipsMonoIncr(s string) int {
	dp0, dp1 := 0, 0
	for _, c := range s {
		dp0New, dp1New := dp0, min(dp0, dp1)
		if c == '1' {
			dp0New++
		} else {
			dp1New++
		}
		dp0, dp1 = dp0New, dp1New
	}
	return min(dp0, dp1)
}

93

剑指 Offer II 093. 最长斐波那契数列

给定一个递增的正整数数组，找到其中最长的一个满足斐波那契数列的元素

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

int max(int a, int b) { return (a > b) ? a : b; }

int lenLongestFibSubseq(const std::vector<int> &arr) {
  int n = arr.size();
  std::unordered_map<int, int> indices;
  for (int i = 0; i < n; ++i) {
    indices[arr[i]] = i;
  }
  std::vector<std::vector<int>> dp(n, std::vector<int>(n, 0));
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = n - 1; j >= 0 && arr[j] * 2 > arr[i]; --j) {
      auto it = indices.find(arr[i] - arr[j]);
      if (it != indices.end()) {
        int k = it->second;
        dp[j][i] = max(dp[k][j] + 1, 3);
        ans = max(ans, dp[j][i]);
      }
    }
  }
  return ans;
}

int main() {
  std::vector<int> arr = {1, 3, 7, 11, 12, 14, 18};
  std::cout << "Length of longest Fibonacci-like subsequence: "
            << lenLongestFibSubseq(arr) << std::endl;
  return 0;
}

package main

func lenLongestFibSubseq(arr []int) (ans int) {
	n := len(arr)
	indices := make(map[int]int, n)
	for i, x := range arr {
		indices[x] = i
	}
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	for i, x := range arr {
		for j := n - 1; j >= 0 && arr[j]*2 > x; j-- {
			if k, ok := indices[x-arr[j]]; ok {
				dp[j][i] = max(dp[k][j]+1, 3)
				ans = max(ans, dp[j][i])
			}
		}
	}
	return
}

func max(a, b int) int {
	if b > a {
		return b
	}
	return a
}

94

剑指 Offer II 094. 最少回文分割

给定一个字符串s，找到分割的最小次数，将s分割成字串，且每个字串都是回文串，

#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <vector>

int minCut(const std::string &s) {
  int n = s.size();
  std::vector<std::vector<bool>> g(n, std::vector<bool>(n, true));
  for (int i = n - 1; i >= 0; --i) {
    for (int j = i + 1; j < n; ++j) {
      g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
    }
  }

  std::vector<int> f(n, INT_MAX);
  for (int i = 0; i < n; ++i) {
    if (g[0][i]) {
      f[i] = 0;
    } else {
      for (int j = 0; j < i; ++j) {
        if (g[j + 1][i]) {
          f[i] = std::min(f[i], f[j] + 1);
        }
      }
    }
  }
  return f[n - 1];
}

int main() {
  std::string s = "aab";
  std::cout << "Minimum cuts needed for a palindrome partitioning: "
            << minCut(s) << std::endl;
  return 0;
}

package main

import "math"

func minCut(s string) int {
	n := len(s)
	g := make([][]bool, n)
	for i := range g {
		g[i] = make([]bool, n)
		for j := range g[i] {
			g[i][j] = true
		}
	}
	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			g[i][j] = s[i] == s[j] && g[i+1][j-1]
		}
	}

	f := make([]int, n)
	for i := range f {
		if g[0][i] {
			continue
		}
		f[i] = math.MaxInt64
		for j := 0; j < i; j++ {
			if g[j+1][i] && f[j]+1 < f[i] {
				f[i] = f[j] + 1
			}
		}
	}
	return f[n-1]
}

95

剑指 Offer II 095. 最长公共子序列

找到两个字符串的最长的公共子序列(即满足不改变字符的相对顺序的情况下删除某些字符)

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int max(int a, int b) { return (a > b) ? a : b; }

int longestCommonSubsequence(const std::string &text1,
                             const std::string &text2) {
  int m = text1.size(), n = text2.size();
  std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));

  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if (text1[i] == text2[j]) {
        dp[i + 1][j + 1] = dp[i][j] + 1;
      } else {
        dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j]);
      }
    }
  }
  return dp[m][n];
}

int main() {
  std::string text1 = "abcde";
  std::string text2 = "ace";
  std::cout << "Length of longest common subsequence: "
            << longestCommonSubsequence(text1, text2) << std::endl;
  return 0;
}

package main

func longestCommonSubsequence(text1, text2 string) int {
	m, n := len(text1), len(text2)
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
	}
	for i, c1 := range text1 {
		for j, c2 := range text2 {
			if c1 == c2 {
				dp[i+1][j+1] = dp[i][j] + 1
			} else {
				dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
			}
		}
	}
	return dp[m][n]
}

96

剑指 Offer II 096. 字符串交织

判断两个字符串s1 s2交织(轮流选择元素)后是否与s3相等

#include <iostream>
#include <string>
#include <vector>

bool isInterleave(const std::string &s1, const std::string &s2,
                  const std::string &s3) {
  int n = s1.size(), m = s2.size(), t = s3.size();
  if (n + m != t) {
    return false;
  }
  std::vector<bool> f(m + 1, false);
  f[0] = true;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= m; ++j) {
      int p = i + j - 1;
      if (i > 0) {
        f[j] = f[j] && s1[i - 1] == s3[p];
      }
      if (j > 0) {
        f[j] = f[j] || (f[j - 1] && s2[j - 1] == s3[p]);
      }
    }
  }
  return f[m];
}

int main() {
  std::string s1 = "aabcc";
  std::string s2 = "dbbca";
  std::string s3 = "aadbbcbcac";
  std::cout << "Is interleaving: "
            << (isInterleave(s1, s2, s3) ? "true" : "false") << std::endl;
  return 0;
}

package main

func isInterleave(s1 string, s2 string, s3 string) bool {
	n, m, t := len(s1), len(s2), len(s3)
	if (n + m) != t {
		return false
	}
	f := make([]bool, m+1)
	f[0] = true
	for i := 0; i <= n; i++ {
		for j := 0; j <= m; j++ {
			p := i + j - 1
			if i > 0 {
				f[j] = f[j] && s1[i-1] == s3[p]
			}
			if j > 0 {
				f[j] = f[j] || f[j-1] && s2[j-1] == s3[p]
			}
		}
	}
	return f[m]
}

97

剑指 Offer II 097. 子序列的数目

判断字符串s中有多少个子序列是在t中出现了

#include <iostream>
#include <string>
#include <vector>

int numDistinct(const std::string &s, const std::string &t) {
  int m = s.size(), n = t.size();
  if (m < n) {
    return 0;
  }
  std::vector<std::vector<int>> dp(m + 1, std::vector<int>(n + 1, 0));
  for (int i = 0; i <= m; ++i) {
    dp[i][n] = 1;
  }
  for (int i = m - 1; i >= 0; --i) {
    for (int j = n - 1; j >= 0; --j) {
      if (s[i] == t[j]) {
        dp[i][j] = dp[i + 1][j + 1] + dp[i + 1][j];
      } else {
        dp[i][j] = dp[i + 1][j];
      }
    }
  }
  return dp[0][0];
}

int main() {
  std::string s = "rabbbit";
  std::string t = "rabbit";
  std::cout << "Number of distinct subsequences: " << numDistinct(s, t)
            << std::endl;
  return 0;
}

package main

func numDistinct(s, t string) int {
	m, n := len(s), len(t)
	if m < n {
		return 0
	}
	dp := make([][]int, m+1)
	for i := range dp {
		dp[i] = make([]int, n+1)
		dp[i][n] = 1
	}
	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if s[i] == t[j] {
				dp[i][j] = dp[i+1][j+1] + dp[i+1][j]
			} else {
				dp[i][j] = dp[i+1][j]
			}
		}
	}
	return dp[0][0]
}

98

剑指 Offer II 098. 路径的数目

一个m*n的网格，从左上到右下，只能向下或者向右移动一步，问总共有多少条不同的路径。

#include <iostream>
#include <vector>

int uniquePaths(int m, int n) {
  std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
  for (int i = 0; i < m; ++i) {
    dp[i][0] = 1;
  }
  for (int j = 0; j < n; ++j) {
    dp[0][j] = 1;
  }
  for (int i = 1; i < m; ++i) {
    for (int j = 1; j < n; ++j) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

int main() {
  int m = 3, n = 7;
  std::cout << "Number of unique paths: " << uniquePaths(m, n) << std::endl;
  return 0;
}

package main

func uniquePaths(m, n int) int {
	dp := make([][]int, m)
	for i := range dp {
		dp[i] = make([]int, n)
		dp[i][0] = 1
	}
	for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

99

剑指 Offer II 099. 最小路径之和

一个m*n的网格，从左上角到右下角的路径，使得路径上的数字总和为最小。

每次向下或者向右移动一步

#include <algorithm>
#include <iostream>
#include <vector>

int min(int x, int y) { return (x < y) ? x : y; }

int minPathSum(const std::vector<std::vector<int>> &grid) {
  if (grid.empty() || grid[0].empty()) {
    return 0;
  }
  int rows = grid.size(), columns = grid[0].size();
  std::vector<std::vector<int>> dp(rows, std::vector<int>(columns, 0));
  dp[0][0] = grid[0][0];
  for (int i = 1; i < rows; ++i) {
    dp[i][0] = dp[i - 1][0] + grid[i][0];
  }
  for (int j = 1; j < columns; ++j) {
    dp[0][j] = dp[0][j - 1] + grid[0][j];
  }
  for (int i = 1; i < rows; ++i) {
    for (int j = 1; j < columns; ++j) {
      dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
    }
  }
  return dp[rows - 1][columns - 1];
}

int main() {
  std::vector<std::vector<int>> grid = {{1, 3, 1}, {1, 5, 1}, {4, 2, 1}};
  std::cout << "Minimum path sum: " << minPathSum(grid) << std::endl;
  return 0;
}

package main

func minPathSum(grid [][]int) int {
	if len(grid) == 0 || len(grid[0]) == 0 {
		return 0
	}
	rows, columns := len(grid), len(grid[0])
	dp := make([][]int, rows)
	for i := 0; i < len(dp); i++ {
		dp[i] = make([]int, columns)
	}
	dp[0][0] = grid[0][0]
	for i := 1; i < rows; i++ {
		dp[i][0] = dp[i-1][0] + grid[i][0]
	}
	for j := 1; j < columns; j++ {
		dp[0][j] = dp[0][j-1] + grid[0][j]
	}
	for i := 1; i < rows; i++ {
		for j := 1; j < columns; j++ {
			dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
		}
	}
	return dp[rows-1][columns-1]
}

100

剑指 Offer II 100. 三角形中最小路径之和

一个三角形的矩阵，从上往下找到最小路径之和

下标移动的时候只能移动到i以及i+1

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int min(int x, int y) { return (x < y) ? x : y; }

int minimumTotal(const std::vector<std::vector<int>> &triangle) {
  int n = triangle.size();
  std::vector<std::vector<int>> f(n, std::vector<int>(n, 0));
  f[0][0] = triangle[0][0];
  for (int i = 1; i < n; ++i) {
    f[i][0] = f[i - 1][0] + triangle[i][0];
    for (int j = 1; j < i; ++j) {
      f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
    }
    f[i][i] = f[i - 1][i - 1] + triangle[i][i];
  }
  int ans = INT_MAX;
  for (int i = 0; i < n; ++i) {
    ans = min(ans, f[n - 1][i]);
  }
  return ans;
}

int main() {
  std::vector<std::vector<int>> triangle = {
      {2}, {3, 4}, {6, 5, 7}, {4, 1, 8, 3}};
  std::cout << "Minimum total path sum: " << minimumTotal(triangle)
            << std::endl;
  return 0;
}

package main

import "math"

func minimumTotal(triangle [][]int) int {
	n := len(triangle)
	f := make([][]int, n)
	for i := 0; i < n; i++ {
		f[i] = make([]int, n)
	}
	f[0][0] = triangle[0][0]
	for i := 1; i < n; i++ {
		f[i][0] = f[i-1][0] + triangle[i][0]
		for j := 1; j < i; j++ {
			f[i][j] = min(f[i-1][j-1], f[i-1][j]) + triangle[i][j]
		}
		f[i][i] = f[i-1][i-1] + triangle[i][i]
	}
	ans := math.MaxInt32
	for i := 0; i < n; i++ {
		ans = min(ans, f[n-1][i])
	}
	return ans
}

101

剑指 Offer II 101. 分割等和子集

给定一个非空的正整数数组 nums ，请判断能否将这些数字分成元素和相等的两部分。

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

bool canPartition(std::vector<int> &nums) {
  int n = nums.size();
  if (n < 2) {
    return false;
  }

  int sum = std::accumulate(nums.begin(), nums.end(), 0);
  int maxNum = *std::max_element(nums.begin(), nums.end());
  if (sum % 2 != 0) {
    return false;
  }

  int target = sum / 2;
  if (maxNum > target) {
    return false;
  }

  std::vector<std::vector<bool>> dp(n, std::vector<bool>(target + 1, false));
  for (int i = 0; i < n; ++i) {
    dp[i][0] = true;
  }
  dp[0][nums[0]] = true;
  for (int i = 1; i < n; ++i) {
    int v = nums[i];
    for (int j = 1; j <= target; ++j) {
      if (j >= v) {
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - v];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }
  return dp[n - 1][target];
}

int main() {
  std::vector<int> nums = {1, 5, 11, 5};
  std::cout << "Can partition: " << (canPartition(nums) ? "true" : "false")
            << std::endl;
  return 0;
}

package main

func canPartition(nums []int) bool {
	n := len(nums)
	if n < 2 {
		return false
	}

	sum, max := 0, 0
	for _, v := range nums {
		sum += v
		if v > max {
			max = v
		}
	}
	if sum%2 != 0 {
		return false
	}

	target := sum / 2
	if max > target {
		return false
	}

	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, target+1)
	}
	for i := 0; i < n; i++ {
		dp[i][0] = true
	}
	dp[0][nums[0]] = true
	for i := 1; i < n; i++ {
		v := nums[i]
		for j := 1; j <= target; j++ {
			if j >= v {
				dp[i][j] = dp[i-1][j] || dp[i-1][j-v]
			} else {
				dp[i][j] = dp[i-1][j]
			}
		}
	}
	return dp[n-1][target]
}

102

剑指 Offer II 102. 加减的目标值

给定一个数组以及target值，提供正负符号使得数组中的和等于目标值

#include <iostream>
#include <vector>

void backtrack(const std::vector<int> &nums, int target, int index, int sum,
               int &count) {
  if (index == nums.size()) {
    if (sum == target) {
      count++;
    }
    return;
  }
  backtrack(nums, target, index + 1, sum + nums[index], count);
  backtrack(nums, target, index + 1, sum - nums[index], count);
}

int findTargetSumWays(const std::vector<int> &nums, int target) {
  int count = 0;
  backtrack(nums, target, 0, 0, count);
  return count;
}

int main() {
  std::vector<int> nums = {1, 1, 1, 1, 1};
  int target = 3;
  std::cout << "Number of ways to reach target sum: "
            << findTargetSumWays(nums, target) << std::endl;
  return 0;
}

package main

func findTargetSumWays(nums []int, target int) (count int) {
	var backtrack func(int, int)
	backtrack = func(index, sum int) {
		if index == len(nums) {
			if sum == target {
				count++
			}
			return
		}
		backtrack(index+1, sum+nums[index])
		backtrack(index+1, sum-nums[index])
	}
	backtrack(0, 0)
	return
}

103

剑指 Offer II 103. 最少的硬币数目

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

每种硬币的数量是无限的。

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int min(int a, int b) { return (a < b) ? a : b; }

int coinChange(const std::vector<int> &nums, int target) {
  std::vector<int> dp(target + 1, INT_MAX);
  dp[0] = 0;
  for (int num : nums) {
    for (int i = 0; i <= target - num; ++i) {
      if (dp[i] == INT_MAX) {
        continue;
      }
      dp[i + num] = min(dp[i + num], dp[i] + 1);
    }
  }
  return dp[target] == INT_MAX ? -1 : dp[target];
}

int main() {
  std::vector<int> nums = {1, 2, 5};
  int target = 11;
  std::cout << "Minimum coins needed: " << coinChange(nums, target)
            << std::endl;
  return 0;
}

package main

import "math"

func coinChange(nums []int, target int) int {
	dp := make([]int, target+1)
	for i := 1; i <= target; i++ {
		dp[i] = math.MaxInt32
	}
	for _, num := range nums {
		for i := 0; i <= target-num; i++ {
			if dp[i] == math.MaxInt32 {
				continue
			}
			dp[i+num] = min(dp[i+num], dp[i]+1)
		}
	}
	if dp[target] == math.MaxInt32 {
		return -1
	}
	return dp[target]
}

104

剑指 Offer II 104. 排列的数目

给定一个由不同正整数组成的数组 nums ，和一个目标整数 target 。请从 nums 中找出并返回总和为 target 的元素组合的个数。数组中的数字可以在一次排列中出现任意次，但是顺序不同的序列被视作不同的组合。

#include <iostream>
#include <vector>

int combinationSum4(const std::vector<int> &nums, int target) {
  std::vector<int> dp(target + 1, 0);
  dp[0] = 1;
  for (int i = 1; i <= target; ++i) {
    for (int num : nums) {
      if (num <= i) {
        dp[i] += dp[i - num];
      }
    }
  }
  return dp[target];
}

int main() {
  std::vector<int> nums = {1, 2, 3};
  int target = 4;
  std::cout << "Number of combinations: " << combinationSum4(nums, target)
            << std::endl;
  return 0;
}

package main

func combinationSum4(nums []int, target int) int {
	dp := make([]int, target+1)
	dp[0] = 1
	for i := 1; i <= target; i++ {
		for _, num := range nums {
			if num <= i {
				dp[i] += dp[i-num]
			}
		}
	}
	return dp[target]
}

105

剑指 Offer II 105. 岛屿的最大面积

01二维矩阵，全1代表陆地，找到岛屿的最大面积

#include <iostream>
#include <vector>

int getArea(std::vector<std::vector<int>> &grid,
            std::vector<std::vector<bool>> &visited, int i, int j) {
  int m = grid.size(), n = grid[0].size();
  if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == 0 || visited[i][j]) {
    return 0;
  }
  visited[i][j] = true;
  return getArea(grid, visited, i - 1, j) + getArea(grid, visited, i + 1, j) +
         getArea(grid, visited, i, j - 1) + getArea(grid, visited, i, j + 1) +
         1;
}

int maxAreaOfIsland(std::vector<std::vector<int>> &grid) {
  int m = grid.size(), n = grid[0].size();
  std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
  int ans = 0;
  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      int area = getArea(grid, visited, i, j);
      if (area > ans) {
        ans = area;
      }
    }
  }
  return ans;
}

int main() {
  std::vector<std::vector<int>> grid = {
      {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
      {0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0},
      {0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0},
      {0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0},
      {0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0}};
  std::cout << "Maximum area of island: " << maxAreaOfIsland(grid) << std::endl;
  return 0;
}

package main

func maxAreaOfIsland(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	visited := make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	var getArea func(int, int) int
	getArea = func(i, j int) int {
		if i < 0 || i == m || j < 0 || j == n {
			return 0
		}
		if grid[i][j] == 0 || visited[i][j] {
			return 0
		}
		visited[i][j] = true
		return getArea(i-1, j) + getArea(i+1, j) + getArea(i, j-1) + getArea(i, j+1) + 1
	}
	ans := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			area := getArea(i, j)
			if area > ans {
				ans = area
			}
		}
	}
	return ans
}

106

剑指 Offer II 106. 二分图

二分图定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为二分图。

如果图是二分图，返回 true ；否则，返回 false 。

#include <functional>
#include <iostream>
#include <vector>

const int UNCOLOR = 0, RED = 1, GREEN = 2;

bool isBipartite(const std::vector<std::vector<int>> &graph) {
  int n = graph.size();
  std::vector<int> state(n, UNCOLOR);
  bool valid = true;

  std::function<void(int, int)> dfs = [&](int idx, int color) -> void {
    int necolor = (color == RED) ? GREEN : RED;
    state[idx] = color;

    for (int ne : graph[idx]) {
      if (state[ne] == UNCOLOR) {
        dfs(ne, necolor);
      } else {
        valid = (necolor == state[ne]);
      }

      if (!valid) {
        return;
      }
    }
  };

  for (int i = 0; i < n && valid; ++i) {
    if (state[i] == UNCOLOR) {
      dfs(i, RED);
    }
  }
  return valid;
}

int main() {
  std::vector<std::vector<int>> graph = {{1, 3}, {0, 2}, {1, 3}, {0, 2}};
  std::cout << "Is bipartite: " << (isBipartite(graph) ? "true" : "false")
            << std::endl;
  return 0;
}

package main

var (
	UNCOLOR, RED, GREEN = 0, 1, 2
)

func isBipartite(graph [][]int) bool {
	n := len(graph)

	state := make([]int, n)
	valid := true

	var dfs func(idx, color int)
	dfs = func(idx, color int) {
		necolor := RED
		if color == RED {
			necolor = GREEN
		}
		state[idx] = color

		for _, ne := range graph[idx] {
			if state[ne] == UNCOLOR {
				dfs(ne, necolor)
			} else {
				valid = necolor == state[ne]
			}

			if !valid {
				return
			}
		}
	}

	for i := 0; i < n && valid; i++ {
		if state[i] == UNCOLOR {
			dfs(i, RED)
		}
	}
	return valid
}

107

剑指 Offer II 107. 矩阵中的距离

一个01矩阵，找到每个元素距离其最近0的距离长度，结果用二维矩阵表达

#include <iostream>
#include <queue>
#include <vector>

std::vector<std::vector<int>> updateMatrix(std::vector<std::vector<int>> &mat) {
  int m = mat.size();
  int n = mat[0].size();
  std::vector<std::vector<int>> res(m, std::vector<int>(n, 0));
  std::vector<int> dx = {1, 0, -1, 0};
  std::vector<int> dy = {0, -1, 0, 1};
  std::queue<std::pair<int, int>> queue;

  for (int i = 0; i < m; ++i) {
    for (int j = 0; j < n; ++j) {
      if (mat[i][j] == 0) {
        queue.push({i, j});
      }
    }
  }

  while (!queue.empty()) {
    int x = queue.front().first;
    int y = queue.front().second;
    queue.pop();
    for (int k = 0; k < 4; ++k) {
      int nx = x + dx[k];
      int ny = y + dy[k];
      if (nx >= 0 && ny >= 0 && nx < m && ny < n && mat[nx][ny] == 1) {
        if (res[nx][ny] == 0 || res[x][y] + 1 < res[nx][ny]) {
          res[nx][ny] = res[x][y] + 1;
          queue.push({nx, ny});
        }
      }
    }
  }

  return res;
}

int main() {
  std::vector<std::vector<int>> mat = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
  std::vector<std::vector<int>> result = updateMatrix(mat);
  for (const auto &row : result) {
    for (int val : row) {
      std::cout << val << " ";
    }
    std::cout << std::endl;
  }
  return 0;
}

package main

func updateMatrix(mat [][]int) [][]int {
	m := len(mat)
	n := len(mat[0])
	res := make([][]int, m)
	for i := range res {
		res[i] = make([]int, n)
	}
	dx := []int{1, 0, -1, 0}
	dy := []int{0, -1, 0, 1}
	var queue [][]int
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if mat[i][j] == 0 {
				queue = append(queue, []int{i, j})
			}
		}
	}
	for len(queue) > 0 {
		x := queue[0][0]
		y := queue[0][1]
		queue = queue[1:]
		for k := 0; k < 4; k++ {
			nx := x + dx[k]
			ny := y + dy[k]
			if nx >= 0 && ny >= 0 && nx < m && ny < n && mat[nx][ny] == 1 {
				if res[nx][ny] == 0 || res[x][y]+1 < res[nx][ny] {
					res[nx][ny] = res[x][y] + 1
					queue = append(queue, []int{nx, ny})
				}
			}
		}
	}
	return res
}

108

剑指 Offer II 108. 单词演变

将单词从begin转换成end需要的最小步骤，并且每次的转换中间节点要在wordList中出现

#include <climits>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

int ladderLength(const std::string &beginWord, const std::string &endWord,
                 std::vector<std::string> &wordList) {
  std::unordered_map<std::string, int> wordId;
  std::vector<std::vector<int>> graph;
  int idCounter = 0;

  auto addWord = [&](std::string word) -> int {
    if (wordId.find(word) == wordId.end()) {
      wordId[word] = idCounter++;
      graph.push_back({});
    }
    return wordId[word];
  };

  auto addEdge = [&](std::string word) -> int {
    int id1 = addWord(word);
    std::string s = word;
    for (size_t i = 0; i < s.size(); ++i) {
      char originalChar = s[i];
      s[i] = '*';
      int id2 = addWord(s);
      graph[id1].push_back(id2);
      graph[id2].push_back(id1);
      s[i] = originalChar;
    }
    return id1;
  };

  for (const auto &word : wordList) {
    addEdge(word);
  }
  int beginId = addEdge(beginWord);
  if (wordId.find(endWord) == wordId.end()) {
    return 0;
  }
  int endId = wordId[endWord];

  const int inf = INT_MAX;
  std::vector<int> dist(wordId.size(), inf);
  dist[beginId] = 0;
  std::queue<int> queue;
  queue.push(beginId);

  while (!queue.empty()) {
    int v = queue.front();
    queue.pop();
    if (v == endId) {
      return dist[endId] / 2 + 1;
    }
    for (int w : graph[v]) {
      if (dist[w] == inf) {
        dist[w] = dist[v] + 1;
        queue.push(w);
      }
    }
  }
  return 0;
}

int main() {
  std::vector<std::string> wordList = {"hot", "dot", "dog",
                                       "lot", "log", "cog"};
  std::string beginWord = "hit";
  std::string endWord = "cog";
  std::cout << "Ladder length: " << ladderLength(beginWord, endWord, wordList)
            << std::endl;
  return 0;
}

package main

import "math"

func ladderLength(beginWord string, endWord string, wordList []string) int {
	wordId := map[string]int{}
	graph := [][]int{}
	addWord := func(word string) int {
		id, has := wordId[word]
		if !has {
			id = len(wordId)
			wordId[word] = id
			graph = append(graph, []int{})
		}
		return id
	}
	addEdge := func(word string) int {
		id1 := addWord(word)
		s := []byte(word)
		for i, b := range s {
			s[i] = '*'
			id2 := addWord(string(s))
			graph[id1] = append(graph[id1], id2)
			graph[id2] = append(graph[id2], id1)
			s[i] = b
		}
		return id1
	}

	for _, word := range wordList {
		addEdge(word)
	}
	beginId := addEdge(beginWord)
	endId, has := wordId[endWord]
	if !has {
		return 0
	}

	const inf int = math.MaxInt64
	dist := make([]int, len(wordId))
	for i := range dist {
		dist[i] = inf
	}
	dist[beginId] = 0
	queue := []int{beginId}
	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]
		if v == endId {
			return dist[endId]/2 + 1
		}
		for _, w := range graph[v] {
			if dist[w] == inf {
				dist[w] = dist[v] + 1
				queue = append(queue, w)
			}
		}
	}
	return 0
}

109

剑指 Offer II 109. 开密码锁

四个环形波轮组成的锁，找到转到目标值target的最小转动次数，另外不能转动到deadends列表中的数据

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

int openLock(std::vector<std::string> &deadends, std::string target) {
  if (target == "0000") {
    return 0;
  }

  std::unordered_set<std::string> deadendsSet(deadends.begin(), deadends.end());
  if (deadendsSet.count(target) || deadendsSet.count("0000")) {
    return -1;
  }

  std::unordered_set<std::string> visit;

  auto getnei = [](std::string state) -> std::vector<std::string> {
    std::vector<std::string> res;
    std::string s = state;
    for (int i = 0; i < 4; ++i) {
      char ch = s[i];
      s[i] = ch + 1;
      if (s[i] > '9') {
        s[i] = '0';
      }
      res.push_back(s);

      s[i] = ch - 1;
      if (s[i] < '0') {
        s[i] = '9';
      }
      res.push_back(s);

      s[i] = ch;
    }
    return res;
  };

  std::queue<std::string> queue;
  queue.push("0000");
  int step = 0;
  while (!queue.empty()) {
    int size = queue.size();
    for (int i = 0; i < size; ++i) {
      std::string state = queue.front();
      queue.pop();
      for (const auto &ne : getnei(state)) {
        if (!visit.count(ne) && !deadendsSet.count(ne)) {
          if (ne == target) {
            return step + 1;
          }
          visit.insert(ne);
          queue.push(ne);
        }
      }
    }
    ++step;
  }
  return -1;
}

int main() {
  std::vector<std::string> deadends = {"0201", "0101", "0102", "1212", "2002"};
  std::string target = "0202";
  std::cout << "Minimum turns to open lock: " << openLock(deadends, target)
            << std::endl;
  return 0;
}

package main

func openLock(deadends []string, target string) int {
	if target == "0000" {
		return 0
	}

	deadendsSet := map[string]bool{}
	for _, item := range deadends {
		deadendsSet[item] = true
	}
	if deadendsSet[target] || deadendsSet["0000"] {
		return -1
	}

	visit := map[string]bool{}

	getnei := func(state string) []string {
		res := []string{}
		s := []byte(state)
		for i, ch := range s {
			s[i] = ch + 1
			if s[i] > '9' {
				s[i] = '0'
			}
			res = append(res, string(s))

			s[i] = ch - 1
			if s[i] < '0' {
				s[i] = '9'
			}
			res = append(res, string(s))

			s[i] = ch
		}
		return res
	}

	queue := []string{"0000"}
	step := 0
	for len(queue) > 0 {
		newqueue := []string{}
		for _, state := range queue {
			for _, ne := range getnei(state) {
				if !visit[ne] && !deadendsSet[ne] {
					if ne == target {
						return step + 1
					}
					visit[ne] = true
					newqueue = append(newqueue, ne)
				}
			}
		}
		queue = newqueue
		step++
	}
	return -1
}

110

剑指 Offer II 110. 所有路径

给定一个邻接矩阵结构，用于表示一个有向有环图，找到其中的所有的从0到n-1节点的路径

#include <iostream>
#include <vector>

void dfs(const std::vector<std::vector<int>> &graph, std::vector<int> &stk,
         std::vector<std::vector<int>> &ans, int x) {
  if (x == graph.size() - 1) {
    ans.push_back(stk);
    return;
  }
  for (int y : graph[x]) {
    stk.push_back(y);
    dfs(graph, stk, ans, y);
    stk.pop_back();
  }
}

std::vector<std::vector<int>>
allPathsSourceTarget(const std::vector<std::vector<int>> &graph) {
  std::vector<std::vector<int>> ans;
  std::vector<int> stk = {0};
  dfs(graph, stk, ans, 0);
  return ans;
}

int main() {
  std::vector<std::vector<int>> graph = {{1, 2}, {3}, {3}, {}};
  std::vector<std::vector<int>> result = allPathsSourceTarget(graph);
  for (const auto &path : result) {
    for (int node : path) {
      std::cout << node << " ";
    }
    std::cout << std::endl;
  }
  return 0;
}

package main

func allPathsSourceTarget(graph [][]int) (ans [][]int) {
	stk := []int{0}
	var dfs func(int)
	dfs = func(x int) {
		if x == len(graph)-1 {
			ans = append(ans, append([]int{}, stk...))
			return
		}
		for _, y := range graph[x] {
			stk = append(stk, y)
			dfs(y)
			stk = stk[:len(stk)-1]
		}
	}
	dfs(0)
	return
}

111

剑指 Offer II 111. 计算除法

给定一些已知变量除法获取到的值，提供数据查询结果

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

struct Edge {
  int to;
  double weight;
};

std::vector<double>
calcEquation(const std::vector<std::vector<std::string>> &equations,
             const std::vector<double> &values,
             const std::vector<std::vector<std::string>> &queries) {
  std::unordered_map<std::string, int> id;
  int idCounter = 0;

  for (const auto &eq : equations) {
    const std::string &a = eq[0];
    const std::string &b = eq[1];
    if (id.find(a) == id.end()) {
      id[a] = idCounter++;
    }
    if (id.find(b) == id.end()) {
      id[b] = idCounter++;
    }
  }

  std::vector<std::vector<Edge>> graph(idCounter);
  for (size_t i = 0; i < equations.size(); ++i) {
    int v = id[equations[i][0]];
    int w = id[equations[i][1]];
    graph[v].push_back({w, values[i]});
    graph[w].push_back({v, 1.0 / values[i]});
  }

  auto bfs = [&](int start, int end) -> double {
    std::vector<double> ratios(idCounter, 0.0);
    ratios[start] = 1.0;
    std::queue<int> queue;
    queue.push(start);

    while (!queue.empty()) {
      int v = queue.front();
      queue.pop();
      if (v == end) {
        return ratios[v];
      }
      for (const auto &e : graph[v]) {
        if (ratios[e.to] == 0.0) {
          ratios[e.to] = ratios[v] * e.weight;
          queue.push(e.to);
        }
      }
    }
    return -1.0;
  };

  std::vector<double> ans(queries.size());
  for (size_t i = 0; i < queries.size(); ++i) {
    const std::string &startStr = queries[i][0];
    const std::string &endStr = queries[i][1];
    if (id.find(startStr) == id.end() || id.find(endStr) == id.end()) {
      ans[i] = -1.0;
    } else {
      ans[i] = bfs(id[startStr], id[endStr]);
    }
  }
  return ans;
}

int main() {
  std::vector<std::vector<std::string>> equations = {{"a", "b"}, {"b", "c"}};
  std::vector<double> values = {2.0, 3.0};
  std::vector<std::vector<std::string>> queries = {
      {"a", "c"}, {"b", "a"}, {"a", "e"}, {"a", "a"}, {"x", "x"}};
  std::vector<double> result = calcEquation(equations, values, queries);
  for (double val : result) {
    std::cout << val << " ";
  }
  std::cout << std::endl;
  return 0;
}

package main

func calcEquation(equations [][]string, values []float64, queries [][]string) []float64 {
	// 给方程组中的每个变量编号
	id := map[string]int{}
	for _, eq := range equations {
		a, b := eq[0], eq[1]
		if _, has := id[a]; !has {
			id[a] = len(id)
		}
		if _, has := id[b]; !has {
			id[b] = len(id)
		}
	}

	// 建图
	type edge struct {
		to     int
		weight float64
	}
	graph := make([][]edge, len(id))
	for i, eq := range equations {
		v, w := id[eq[0]], id[eq[1]]
		graph[v] = append(graph[v], edge{w, values[i]})
		graph[w] = append(graph[w], edge{v, 1 / values[i]})
	}

	bfs := func(start, end int) float64 {
		ratios := make([]float64, len(graph))
		ratios[start] = 1
		queue := []int{start}
		for len(queue) > 0 {
			v := queue[0]
			queue = queue[1:]
			if v == end {
				return ratios[v]
			}
			for _, e := range graph[v] {
				if w := e.to; ratios[w] == 0 {
					ratios[w] = ratios[v] * e.weight
					queue = append(queue, w)
				}
			}
		}
		return -1
	}

	ans := make([]float64, len(queries))
	for i, q := range queries {
		start, hasS := id[q[0]]
		end, hasE := id[q[1]]
		if !hasS || !hasE {
			ans[i] = -1
		} else {
			ans[i] = bfs(start, end)
		}
	}
	return ans
}

112

剑指 Offer II 112. 最长递增路径

给定一个 m x n 整数矩阵 matrix ，找出其中最长递增路径的长度。

#include <iostream>
#include <queue>
#include <vector>

std::vector<std::pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int rows, columns;

int longestIncreasingPath(std::vector<std::vector<int>> &matrix) {
  if (matrix.empty() || matrix[0].empty()) {
    return 0;
  }
  rows = matrix.size();
  columns = matrix[0].size();
  std::vector<std::vector<int>> outdegrees(rows, std::vector<int>(columns, 0));

  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < columns; ++j) {
      for (const auto &dir : dirs) {
        int newRow = i + dir.first;
        int newColumn = j + dir.second;
        if (newRow >= 0 && newRow < rows && newColumn >= 0 &&
            newColumn < columns && matrix[newRow][newColumn] > matrix[i][j]) {
          outdegrees[i][j]++;
        }
      }
    }
  }

  std::queue<std::pair<int, int>> queue;
  for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < columns; ++j) {
      if (outdegrees[i][j] == 0) {
        queue.push({i, j});
      }
    }
  }

  int ans = 0;
  while (!queue.empty()) {
    ans++;
    int size = queue.size();
    for (int i = 0; i < size; ++i) {
      auto cell = queue.front();
      queue.pop();
      int row = cell.first;
      int column = cell.second;
      for (const auto &dir : dirs) {
        int newRow = row + dir.first;
        int newColumn = column + dir.second;
        if (newRow >= 0 && newRow < rows && newColumn >= 0 &&
            newColumn < columns &&
            matrix[newRow][newColumn] < matrix[row][column]) {
          outdegrees[newRow][newColumn]--;
          if (outdegrees[newRow][newColumn] == 0) {
            queue.push({newRow, newColumn});
          }
        }
      }
    }
  }
  return ans;
}

int main() {
  std::vector<std::vector<int>> matrix = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
  std::cout << "Longest increasing path: " << longestIncreasingPath(matrix)
            << std::endl;
  return 0;
}

package main

var (
	dirs = [][2]int{
		{-1, 0},
		{1, 0},
		{0, -1},
		{0, 1},
	}
	rows, columns int
)

func longestIncreasingPath(matrix [][]int) int {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return 0
	}
	rows, columns = len(matrix), len(matrix[0])
	outdegrees := make([][]int, rows)
	for i := 0; i < rows; i++ {
		outdegrees[i] = make([]int, columns)
	}
	for i := 0; i < rows; i++ {
		for j := 0; j < columns; j++ {
			for _, dir := range dirs {
				newRow, newColumn := i+dir[0], j+dir[1]
				if newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] > matrix[i][j] {
					outdegrees[i][j]++
				}
			}
		}
	}

	queue := [][]int{}
	for i := 0; i < rows; i++ {
		for j := 0; j < columns; j++ {
			if outdegrees[i][j] == 0 {
				queue = append(queue, []int{i, j})
			}
		}
	}
	ans := 0
	for len(queue) != 0 {
		ans++
		size := len(queue)
		for i := 0; i < size; i++ {
			cell := queue[0]
			queue = queue[1:]
			row, column := cell[0], cell[1]
			for _, dir := range dirs {
				newRow, newColumn := row+dir[0], column+dir[1]
				if newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns && matrix[newRow][newColumn] < matrix[row][column] {
					outdegrees[newRow][newColumn]--
					if outdegrees[newRow][newColumn] == 0 {
						queue = append(queue, []int{newRow, newColumn})
					}
				}
			}
		}
	}
	return ans
}

113

剑指 Offer II 113. 课程顺序

总共n门课，并且有一些先后依赖顺序，返回要完成所有课程所需要的一个正确的课程顺序

#include <iostream>
#include <queue>
#include <vector>

std::vector<int> findOrder(int numCourses,
                           std::vector<std::vector<int>> &prerequisites) {
  std::vector<std::vector<int>> edges(numCourses);
  std::vector<int> indeg(numCourses, 0);
  std::vector<int> result;

  for (const auto &info : prerequisites) {
    edges[info[1]].push_back(info[0]);
    indeg[info[0]]++;
  }

  std::queue<int> q;
  for (int i = 0; i < numCourses; ++i) {
    if (indeg[i] == 0) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    int u = q.front();
    q.pop();
    result.push_back(u);
    for (int v : edges[u]) {
      indeg[v]--;
      if (indeg[v] == 0) {
        q.push(v);
      }
    }
  }

  if (result.size() != numCourses) {
    return {};
  }
  return result;
}

int main() {
  int numCourses = 4;
  std::vector<std::vector<int>> prerequisites = {
      {1, 0}, {2, 0}, {3, 1}, {3, 2}};
  std::vector<int> order = findOrder(numCourses, prerequisites);
  for (int course : order) {
    std::cout << course << " ";
  }
  std::cout << std::endl;
  return 0;
}

package main

func findOrder(numCourses int, prerequisites [][]int) []int {
	var (
		edges  = make([][]int, numCourses)
		indeg  = make([]int, numCourses)
		result []int
	)

	for _, info := range prerequisites {
		edges[info[1]] = append(edges[info[1]], info[0])
		indeg[info[0]]++
	}

	q := []int{}
	for i := 0; i < numCourses; i++ {
		if indeg[i] == 0 {
			q = append(q, i)
		}
	}

	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		result = append(result, u)
		for _, v := range edges[u] {
			indeg[v]--
			if indeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	if len(result) != numCourses {
		return []int{}
	}
	return result
}

114

剑指 Offer II 114. 外星文字典

通过已知的满足特定顺序的字符串数组，来推导出这个而特定的顺序

#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

std::string alienOrder(const std::vector<std::string> &words) {
  std::unordered_map<char, std::vector<char>> g;
  std::unordered_map<char, int> inDeg;
  for (char c : words[0]) {
    inDeg[c] = 0;
  }

  for (size_t i = 1; i < words.size(); ++i) {
    const std::string &s = words[i - 1];
    const std::string &t = words[i];
    for (char c : t) {
      inDeg[c] += 0;
    }
    for (size_t j = 0; j < s.size() && j < t.size(); ++j) {
      if (s[j] != t[j]) {
        g[s[j]].push_back(t[j]);
        inDeg[t[j]]++;
        break;
      }
    }
    if (s.size() > t.size() && s.substr(0, t.size()) == t) {
      return "";
    }
  }

  std::string order;
  std::queue<char> q;
  for (const auto &[u, d] : inDeg) {
    if (d == 0) {
      q.push(u);
    }
  }

  while (!q.empty()) {
    char u = q.front();
    q.pop();
    order.push_back(u);
    for (char v : g[u]) {
      if (--inDeg[v] == 0) {
        q.push(v);
      }
    }
  }

  if (order.size() != inDeg.size()) {
    return "";
  }
  return order;
}

int main() {
  std::vector<std::string> words = {"wrt", "wrf", "er", "ett", "rftt"};
  std::string result = alienOrder(words);
  std::cout << "Alien dictionary order: " << result << std::endl;
  return 0;
}

package main

func alienOrder(words []string) string {
	g := map[byte][]byte{}
	inDeg := map[byte]int{}
	for _, c := range words[0] {
		inDeg[byte(c)] = 0
	}
next:
	for i := 1; i < len(words); i++ {
		s, t := words[i-1], words[i]
		for _, c := range t {
			inDeg[byte(c)] += 0
		}
		for j := 0; j < len(s) && j < len(t); j++ {
			if s[j] != t[j] {
				g[s[j]] = append(g[s[j]], t[j])
				inDeg[t[j]]++
				continue next
			}
		}
		if len(s) > len(t) {
			return ""
		}
	}

	order := make([]byte, len(inDeg))
	q := order[:0]
	for u, d := range inDeg {
		if d == 0 {
			q = append(q, u)
		}
	}
	for len(q) > 0 {
		u := q[0]
		q = q[1:]
		for _, v := range g[u] {
			if inDeg[v]--; inDeg[v] == 0 {
				q = append(q, v)
			}
		}
	}
	if cap(q) == 0 {
		return string(order)
	}
	return ""
}

115

剑指 Offer II 115. 重建序列

https://leetcode.cn/problems/ur2n8P/?favorite=e8X3pBZi

#include <iostream>
#include <queue>
#include <vector>

bool sequenceReconstruction(const std::vector<int> &nums,
                            const std::vector<std::vector<int>> &sequences) {
  int n = nums.size();
  std::vector<std::vector<int>> g(n + 1);
  std::vector<int> inDeg(n + 1, 0);

  for (const auto &sequence : sequences) {
    for (size_t i = 1; i < sequence.size(); ++i) {
      int x = sequence[i - 1];
      int y = sequence[i];
      g[x].push_back(y);
      inDeg[y]++;
    }
  }

  std::queue<int> q;
  for (int i = 1; i <= n; ++i) {
    if (inDeg[i] == 0) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    if (q.size() > 1) {
      return false;
    }
    int x = q.front();
    q.pop();
    for (int y : g[x]) {
      if (--inDeg[y] == 0) {
        q.push(y);
      }
    }
  }

  return true;
}

int main() {
  std::vector<int> nums = {1, 2, 3};
  std::vector<std::vector<int>> sequences = {{1, 2}, {1, 3}};
  std::cout << "Can reconstruct sequence: "
            << (sequenceReconstruction(nums, sequences) ? "true" : "false")
            << std::endl;
  return 0;
}

package main

func sequenceReconstruction(nums []int, sequences [][]int) bool {
	n := len(nums)
	g := make([][]int, n+1)
	inDeg := make([]int, n+1)
	for _, sequence := range sequences {
		for i := 1; i < len(sequence); i++ {
			x, y := sequence[i-1], sequence[i]
			g[x] = append(g[x], y)
			inDeg[y]++
		}
	}

	q := []int{}
	for i := 1; i <= n; i++ {
		if inDeg[i] == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		if len(q) > 1 {
			return false
		}
		x := q[0]
		q = q[1:]
		for _, y := range g[x] {
			if inDeg[y]--; inDeg[y] == 0 {
				q = append(q, y)
			}
		}
	}
	return true
}

116

剑指 Offer II 116. 省份数量

省份是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中省份的数量。

#include <iostream>
#include <vector>

int find(std::vector<int> &parent, int x) {
  if (parent[x] != x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
}

void unionSets(std::vector<int> &parent, int from, int to) {
  parent[find(parent, from)] = find(parent, to);
}

int findCircleNum(const std::vector<std::vector<int>> &isConnected) {
  int n = isConnected.size();
  std::vector<int> parent(n);
  for (int i = 0; i < n; ++i) {
    parent[i] = i;
  }

  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (isConnected[i][j] == 1) {
        unionSets(parent, i, j);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (parent[i] == i) {
      ++ans;
    }
  }
  return ans;
}

int main() {
  std::vector<std::vector<int>> isConnected = {{1, 1, 0}, {1, 1, 0}, {0, 0, 1}};
  std::cout << "Number of provinces: " << findCircleNum(isConnected)
            << std::endl;
  return 0;
}

package main

func findCircleNum(isConnected [][]int) (ans int) {
	n := len(isConnected)
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	union := func(from, to int) {
		parent[find(from)] = find(to)
	}

	for i, row := range isConnected {
		for j := i + 1; j < n; j++ {
			if row[j] == 1 {
				union(i, j)
			}
		}
	}
	for i, p := range parent {
		if i == p {
			ans++
		}
	}
	return
}

117

剑指 Offer II 117. 相似的字符串

寻找一个字符串数组中，有多少个分组，这些分组里面都是同一种字母异位词。

#include <iostream>
#include <string>
#include <vector>

class UnionFind {
public:
  UnionFind(int n) : parent(n), size(n, 1), setCount(n) {
    for (int i = 0; i < n; ++i) {
      parent[i] = i;
    }
  }

  int find(int x) {
    if (parent[x] != x) {
      parent[x] = find(parent[x]);
    }
    return parent[x];
  }

  void unionSets(int x, int y) {
    int fx = find(x), fy = find(y);
    if (fx == fy)
      return;
    if (size[fx] < size[fy])
      std::swap(fx, fy);
    size[fx] += size[fy];
    parent[fy] = fx;
    --setCount;
  }

  bool inSameSet(int x, int y) { return find(x) == find(y); }

  int getSetCount() const { return setCount; }

private:
  std::vector<int> parent;
  std::vector<int> size;
  int setCount;
};

bool isSimilar(const std::string &s, const std::string &t) {
  int diff = 0;
  for (size_t i = 0; i < s.size(); ++i) {
    if (s[i] != t[i]) {
      ++diff;
      if (diff > 2) {
        return false;
      }
    }
  }
  return true;
}

int numSimilarGroups(const std::vector<std::string> &strs) {
  int n = strs.size();
  UnionFind uf(n);
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      if (!uf.inSameSet(i, j) && isSimilar(strs[i], strs[j])) {
        uf.unionSets(i, j);
      }
    }
  }
  return uf.getSetCount();
}

int main() {
  std::vector<std::string> strs = {"tars", "rats", "arts", "star"};
  std::cout << "Number of similar groups: " << numSimilarGroups(strs)
            << std::endl;
  return 0;
}

package main

type unionFind struct {
	parent, size []int
	setCount     int // 当前连通分量数目
}

func newUnionFind(n int) *unionFind {
	parent := make([]int, n)
	size := make([]int, n)
	for i := range parent {
		parent[i] = i
		size[i] = 1
	}
	return &unionFind{parent, size, n}
}

func (uf *unionFind) find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.find(uf.parent[x])
	}
	return uf.parent[x]
}

func (uf *unionFind) union(x, y int) {
	fx, fy := uf.find(x), uf.find(y)
	if fx == fy {
		return
	}
	if uf.size[fx] < uf.size[fy] {
		fx, fy = fy, fx
	}
	uf.size[fx] += uf.size[fy]
	uf.parent[fy] = fx
	uf.setCount--
}

func (uf *unionFind) inSameSet(x, y int) bool {
	return uf.find(x) == uf.find(y)
}

func isSimilar(s, t string) bool {
	diff := 0
	for i := range s {
		if s[i] != t[i] {
			diff++
			if diff > 2 {
				return false
			}
		}
	}
	return true
}

func numSimilarGroups(strs []string) int {
	n := len(strs)
	uf := newUnionFind(n)
	for i, s := range strs {
		for j := i + 1; j < n; j++ {
			if !uf.inSameSet(i, j) && isSimilar(s, strs[j]) {
				uf.union(i, j)
			}
		}
	}
	return uf.setCount
}

118

剑指 Offer II 118. 多余的边

给定一个无向图，找到找出一条可以删除的边，使其变为树

#include <iostream>
#include <vector>

int find(std::vector<int> &parent, int x) {
  if (parent[x] != x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
}

bool unionSets(std::vector<int> &parent, int from, int to) {
  int x = find(parent, from);
  int y = find(parent, to);
  if (x == y) {
    return false;
  }
  parent[x] = y;
  return true;
}

std::vector<int>
findRedundantConnection(const std::vector<std::vector<int>> &edges) {
  std::vector<int> parent(edges.size() + 1);
  for (size_t i = 0; i < parent.size(); ++i) {
    parent[i] = i;
  }

  for (const auto &edge : edges) {
    if (!unionSets(parent, edge[0], edge[1])) {
      return edge;
    }
  }
  return {};
}

int main() {
  std::vector<std::vector<int>> edges = {{1, 2}, {1, 3}, {2, 3}};
  std::vector<int> result = findRedundantConnection(edges);
  std::cout << "Redundant connection: [" << result[0] << ", " << result[1]
            << "]" << std::endl;
  return 0;
}

package main

func findRedundantConnection(edges [][]int) []int {
	parent := make([]int, len(edges)+1)
	for i := range parent {
		parent[i] = i
	}
	var find func(int) int
	find = func(x int) int {
		if parent[x] != x {
			parent[x] = find(parent[x])
		}
		return parent[x]
	}
	union := func(from, to int) bool {
		x, y := find(from), find(to)
		if x == y {
			return false
		}
		parent[x] = y
		return true
	}
	for _, e := range edges {
		if !union(e[0], e[1]) {
			return e
		}
	}
	return nil
}

119

剑指 Offer II 119. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

要求时间复杂度为O(n)

#include <iostream>
#include <unordered_set>
#include <vector>

int longestConsecutive(const std::vector<int> &nums) {
  std::unordered_set<int> numSet(nums.begin(), nums.end());
  int longestStreak = 0;

  for (int num : numSet) {
    if (numSet.find(num - 1) == numSet.end()) {
      int currentNum = num;
      int currentStreak = 1;

      while (numSet.find(currentNum + 1) != numSet.end()) {
        currentNum++;
        currentStreak++;
      }

      longestStreak = std::max(longestStreak, currentStreak);
    }
  }

  return longestStreak;
}

int main() {
  std::vector<int> nums = {100, 4, 200, 1, 3, 2};
  std::cout << "Longest consecutive sequence length: "
            << longestConsecutive(nums) << std::endl;
  return 0;
}

package main

func longestConsecutive(nums []int) int {
	numSet := map[int]bool{}
	for _, num := range nums {
		numSet[num] = true
	}
	longestStreak := 0
	for num := range numSet {
		if !numSet[num-1] {
			currentNum := num
			currentStreak := 1
			for numSet[currentNum+1] {
				currentNum++
				currentStreak++
			}
			if longestStreak < currentStreak {
				longestStreak = currentStreak
			}
		}
	}
	return longestStreak
}