public class Solution {
private int[][] dirs = new int[4][]{
new int[]{0,1},
new int[]{1,0},
new int[]{-1,0},
new int[]{0,-1}
};
private Queue<int[]> queue = new Queue<int[]>();
public int ClosedIsland(int[][] grid) {
int result = 0;
for (int i = 0; i < grid.Length; i++){
for (int j = 0; j < grid[0].Length; j++){
if (grid[i][j] == 0){
queue.Enqueue(new int[]{i, j});
if (BFS(grid)) result++;
}
}
}
return result;
}
private bool BFS(int[][] grid){
bool island = true;
while (queue.Count > 0){
int[] land = queue.Dequeue();
foreach (int[] dir in dirs){
int r = land[0] + dir[0];
int c = land[1] + dir[1];
if (r < 0 || r >= grid.Length || c < 0 || c >= grid[0].Length){
island = false;
continue;
}
if (grid[r][c] == 0){
grid[r][c] = 1;
queue.Enqueue(new int[]{r,c});
}
}
}
return island;
}
}
活动打卡代码
LeetCode 1254. 统计封闭岛屿的数目
C# BFS代码
public class FindElements {
private Queue<TreeNode> queue = new Queue<TreeNode>();
private HashSet<int> set = new HashSet<int>();
public FindElements(TreeNode root) {
root.val = 0;
queue.Enqueue(root);
while (queue.Count > 0){
TreeNode current = queue.Dequeue();
set.Add(current.val);
if (current.left != null){
current.left.val = (current.val << 1) + 1;
queue.Enqueue(current.left);
}
if (current.right != null){
current.right.val = (current.val << 1) + 2;
queue.Enqueue(current.right);
}
}
}
public bool Find(int target) {
return set.Contains(target);
}
}
C# DFS代码
public class FindElements {
private HashSet<int> set = new HashSet<int>();
public FindElements(TreeNode root) {
root.val = 0;
DFS(root, 0);
}
private void DFS(TreeNode node, int value){
set.Add(value);
if (node.left != null){
DFS(node.left, 1 + (value << 1));
}
if (node.right != null){
DFS(node.right, 2 + (value << 1));
}
}
public bool Find(int target) {
return set.Contains(target);
}
}
活动打卡代码
LeetCode 1261. 在受污染的二叉树中查找元素
public class FindElements {
private Queue<TreeNode> queue = new Queue<TreeNode>();
private HashSet<int> set = new HashSet<int>();
public FindElements(TreeNode root) {
root.val = 0;
queue.Enqueue(root);
while (queue.Count > 0){
TreeNode current = queue.Dequeue();
set.Add(current.val);
if (current.left != null){
current.left.val = (current.val << 1) + 1;
queue.Enqueue(current.left);
}
if (current.right != null){
current.right.val = (current.val << 1) + 2;
queue.Enqueue(current.right);
}
}
}
public bool Find(int target) {
return set.Contains(target);
}
}
C# 代码
public class Solution {
public ListNode DetectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next;
slow = slow.next;
if (fast != null){
fast = fast.next;
}
if (fast == slow){
slow = head;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}
活动打卡代码
LeetCode 142. 环形链表 II
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode DetectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next;
slow = slow.next;
if (fast != null){
fast = fast.next;
}
if (fast == slow){
slow = head;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}
}
C# 代码
public class Solution {
public ListNode MiddleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
活动打卡代码
LeetCode 876. 链表的中间结点
public class Solution {
public ListNode MiddleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
C# 代码
public class Solution {
public int FindLUSlength(string[] strs) {
int result = -1;
for (int i = 0; i < strs.Length; i++){
bool isSub = false;
for (int j = 0; j < strs.Length; j++){
if (i != j && Check(strs[i], strs[j])){
isSub = true;
break;
}
}
if (!isSub) result = Math.Max(result, strs[i].Length);
}
return result;
}
private bool Check(string a, string b){
if (a.Length > b.Length) return false;
int i = 0;
foreach (char ch in b){
if (i < a.Length && ch == a[i]){
i++;
}
}
return i == a.Length;
}
}
活动打卡代码
LeetCode 522. 最长特殊序列 II
public class Solution {
public int FindLUSlength(string[] strs) {
int result = -1;
for (int i = 0; i < strs.Length; i++){
bool isSub = false;
for (int j = 0; j < strs.Length; j++){
if (i != j && Check(strs[i], strs[j])){
isSub = true;
break;
}
}
if (!isSub) result = Math.Max(result, strs[i].Length);
}
return result;
}
private bool Check(string a, string b){
if (a.Length > b.Length) return false;
int i = 0;
foreach (char ch in b){
if (i < a.Length && ch == a[i]){
i++;
}
}
return i == a.Length;
}
}
活动打卡代码
AcWing 885. 求组合数 I
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2010, mod = 1e9 + 7;
int c[N][N];
void init(){
for (int i = 0; i < N; i++){
for (int j = 0; j <= i; j++){
if (!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
}
}
}
int main()
{
int n;
cin >> n;
init();
while (n--){
int a, b;
cin >> a >> b;
cout << c[a][b] << endl;
}
return 0;
}
