2024-12-3

130. 被围绕的区域 低级错误*2，浪费时间1h以上

type UF struct {
	count  int
	parent []int
}

func NewUF(n int) *UF {
	parent := make([]int, n)
	for i := range parent {
		parent[i] = i
	}
	return &UF{
		count:  n,
		parent: parent,
	}
}

func (u *UF) Find(x int) int {
	if u.parent[x] != x {
		u.parent[x] = u.Find(u.parent[x])
	}
	return u.parent[x] //第一个错，这里写成了 return x
}

func (u *UF) Connnected(p int, q int) bool {
	return u.Find(p) == u.Find(q)
}

func (u *UF) Union(p int, q int) {
	rootP := u.Find(p)
	rootQ := u.Find(q)
	if rootP == rootQ {
		return
	}
	u.parent[rootQ] = rootP
	u.count--
}

func (u *UF) Count() int {
	return u.count
}

func solve(board [][]byte) {
	m, n := len(board), len(board[0])
	uf := NewUF(m*n + 1)

	dummy := m * n

	for j, ele := range board[0] {
		if ele == 'O' {
			uf.Union(dummy, j)
		}
	}

	for j, ele := range board[m-1] {
		if ele == 'O' {
			uf.Union(dummy, (m-1)*n+j)
		}
	}

	for i, ele := range board {
		if ele[0] == 'O' {
			uf.Union(dummy, i*n)
		}
		if ele[n-1] == 'O' {
			uf.Union(dummy, i*n+n-1)
		}
	}

	for i := 1; i < m-1; i++ {
		for j := 1; j < n-1; j++ {
			if board[i][j] != 'O' {
				continue
			}
			if board[i-1][j] == 'O' {
				uf.Union(i*n+j, (i-1)*n+j)
			}
			if board[i+1][j] == 'O' {
				uf.Union(i*n+j, (i+1)*n+j) // 第二个错，这里写成了uf.Union(i*n+1, (i+1)*n+j)
			}
			if board[i][j-1] == 'O' {
				uf.Union(i*n+j, i*n+j-1)
			}
			if board[i][j+1] == 'O' {
				uf.Union(i*n+j, i*n+j+1)
			}
		}
	}

	for i := 1; i < m-1; i++ {
		for j := 1; j < n-1; j++ {
			if board[i][j] == 'O' && !uf.Connnected(dummy, i*n+j) {
				board[i][j] = 'X'
			}
		}
	}
}

2024-12-2

721. 账户合并 低级错误，调试浪费半个小时

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, vector<int>> emailToIndexes;
        for (int i = 0; i < accounts.size(); i++) {
            const vector<string> &account = accounts[i];
            for (int j = 1; j < account.size(); j++) {
                emailToIndexes[account[j]].push_back(i);
            }
        }

        vector<vector<string>> ans;
        unordered_set<string> visitedEmails;

        for (auto it = emailToIndexes.begin(); it != emailToIndexes.end(); it++) {
            string email = it->first;
            vector<int> indexes = it->second;
            if (visitedEmails.count(email)) { /* 如果当前email已访问过，则跳过 */
                continue;
            }
            queue<string> q;
            q.push(email);
            visitedEmails.insert(email);
            vector<string> mergedEmails;
            int tmpIndex = emailToIndexes[email][0]; /* 当前email对应的任意一个acounts的index */
            string accountName = accounts[tmpIndex][0];
            mergedEmails.push_back(accountName);
            mergedEmails.push_back(email);
            while (!q.empty()) {
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    string curEmail = q.front();
                    q.pop();
                    cout << curEmail << " ";
                    for (auto index : emailToIndexes[curEmail]) { // 这里错误把curEmail写成了email
                        const vector<string>& account = accounts[index];
                        for (int j = 1; j < account.size(); j++) {
                            string tmpEmail = account[j];
                            if (!visitedEmails.count(tmpEmail)) {
                                q.push(tmpEmail);
                                cout << tmpEmail << " ";
                                visitedEmails.insert(tmpEmail);
                                mergedEmails.push_back(tmpEmail);
                            }
                        }
                    }
                    cout << endl;
                }
            }
            sort(mergedEmails.begin() + 1, mergedEmails.end());
            ans.push_back(mergedEmails);
        }
        return ans;
    }
};