清风的技术小屋

不为所动, 做更专业的自己

0%

Posted on Edited on

问题描述

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

Follow-up:

Can you solve it without using extra space?

Related Topics: Linked List, Two Pointers

原问题: 142. Linked List Cycle II

中文翻译版: 142. 环形链表 II

解决方案

解决方案1

用一个 Set 保存已访问的节点，此时可以遍历整个链表并返回第一个出现重复的节点。时间复杂度为 O(n)，空间复杂度为 O(n)

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> node_set;
        ListNode *node;

        node = head;
        while (node != NULL) {
            if (node_set.find(node) == node_set.end())
                node_set.insert(node);
            else
                return node;
            node = node->next;
        }

        return node;
    }
};

解决方案2

方案2是 LeetCode 141 解题思路的进一步改进，算法分为两个阶段：

  • 阶段1 : 首先使用快指针 fast 和慢指针 slow 遍历链表，如果链表有环，两指针最终会相遇到某个节点
  • 阶段2 : 初始化额外的两个指针，ptr1 指向链表的头节点，ptr2 指向相遇节点。然后，我们每次将它们往前移动一步，直到它们相遇，它们相遇的点就是环的入口，返回这个节点

关于阶段2的实现原理，这里提供一个不错的解答说明：LeetCode: 环形链表 II 官方解答

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (NULL == head || NULL == head->next)
            return NULL;

        ListNode *slow, *fast;

        slow = fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                break;
        }
        // no cycle
        if (slow != fast)
            return NULL;

        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }

        return fast;
    }
};

Posted on Edited on

问题描述

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

  • push(x) -- Push element x onto stack.
  • pop() -- Removes the element on top of the stack.
  • top() -- Get the top element.
  • getMin() -- Retrieve the minimum element in the stack.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top();    // return 0
minStack.getMin(); // return -2

Constraints:

  • Methods pop, top and getMin operations will always be called on non-empty stacks.

Related Topics: Stack, Design

原问题: 155. Min Stack

中文翻译版: 155. 最小栈

解决方案

可以使用两个栈解决该题，一个栈stack存储push进来的数据，另一个栈min_stack存储现有数据的最小值，两个栈存储同等数量的元素。关键的操作 push 实现如下：

  • push : push的数据为x，如果x小于min_stack栈顶的值，说明x比现用元素值都要小，则将x压入min_stack，否则将min_stack栈顶的值压入min_stack
参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class MinStack {
private:
    stack<int> m_stack;
    stack<int> m_min_stack;

public:
    /** initialize your data structure here. */
    MinStack() {

    }

    void push(int x) {
        if (m_stack.empty()) {
            m_stack.push(x);
            m_min_stack.push(x);
        } else {
            int top = m_min_stack.top();

            if (top > x)
                m_min_stack.push(x);
            else
                m_min_stack.push(top);

            m_stack.push(x);
        }
    }

    void pop() {
        m_stack.pop();
        m_min_stack.pop();
    }

    int top() {
        return m_stack.top();
    }

    int getMin() {
        return m_min_stack.top();
    }
};

Posted on Edited on

1. 问题描述

Reverse a singly linked list.

Example:

1
2
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Related Topics: Linked List

原问题: 206. Reverse Linked List

中文翻译版: 206. 反转链表

2. 解决方案

2.1 非递归

非递归的解决方案是按原始顺序迭代节点，并将它们逐个移动到链表的头部。以下举个例子进行说明

黑色节点23是原始头节点。

  1. 首先，我们将黑色节点的下一个节点（即节点6）移动到链表的头部：

  2. 然后，我们将黑色节点的下一个节点（即节点15）移动到链表的头部：

  3. 黑色结点的下一个结点现在是空。因此，我们停止这一过程并返回新的头结点15

从以上流程可以知道该算法的时间复杂度为 O(N)，空间复杂度为 O(1)

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur, *next;

        cur = head;
        while (cur != NULL && cur->next != NULL) {
            next = cur->next;
            cur->next = next->next;
            next->next = head;
            head = next;
        }

        return head;
    }
};

2.2 递归

用递归解此题时，此时递归的函数返回的是反转链表后的新的头节点 new_head，进行整合时，只需要将头节点 head 添加到反转链表的尾部即可。拿前面例子来说，头节点23后部分都已经反转完毕，此时链表构造为

1
23 -> 6 <- 15

此时 new_head 指向节点15，head 指向节点23，要将节点23添加到反转链表尾部，执行以下操作即可：

1
2
head->next->next = head
head->next = NULL

经过以上操作以后，链表构造变为

1
NULL <- 23 <- 6 <- 15

最后返回新的头节点 new_head 即可

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode *new_head;

        new_head = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;

        return new_head;
    }
};

Posted on Edited on

问题描述

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example 1:

1
2
Input: 1->2->3->4->5->NULL
Output: 1->3->5->2->4->NULL

Example 2:

1
2
Input: 2->1->3->5->6->4->7->NULL
Output: 2->3->6->7->1->5->4->NULL

Note:

  • The relative order inside both the even and odd groups should remain as it was in the input.
  • The first node is considered odd, the second node even and so on ...

Related Topics: Linked List

原问题: 328. Odd Even Linked List

中文翻译版: 328. 奇偶链表

解决方案

解此题主要需要两个指针 odd 以及 even，odd 指向奇节点，even 指向偶节点。odd 从第一个节点开始遍历，even 从第二节点开始遍历，两个指针每次移动都是移动两个节点，每次移动前，先将 next 字段指向下下个节点，即

1
2
odd = odd->next->next;
even = even->next->next;

这样当两个指针遍历完链表时，链表刚好被分为两部分，odd 指向奇节点链表最后一个节点，此时将这两个链表拼在一起即可。偶节点链表头部是头节点的下一个节点，由于在指针遍历时，会破坏链表结构，因此在遍历前先保存该节点 node，链表拼接时只需

1
odd->next = node
参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if (head == NULL || head->next == NULL)
            return head;

        ListNode *even, *odd, *node;

        odd = head;
        even = head->next;
        node = head->next;
        while (odd != NULL && odd->next != NULL
               && even != NULL && even->next != NULL) {
            odd->next = odd->next->next;
            odd = odd->next;
            even->next = even->next->next;
            even = even->next;
        }
        odd->next = node;

        return head;
    }
};

Posted on Edited on

问题描述

Remove all elements from a linked list of integers that have value val.

Example:

1
2
Input:  1->2->6->3->4->5->6, val = 6
Output: 1->2->3->4->5

Related Topics: Linked List

原问题: 203. Remove Linked List Elements

中文翻译版: 203. 移除链表元素

解决方案

链表删除基本操作的实现，使用三个指针 prev、curr 以及 next，prev 指向 curr 前一个节点，curr 指向要删除的节点，next 指向 curr 下一个节点。curr 从头节点开始遍历，按照链表删除元素操作依次删除值为 val 的节点即可

1
2
3
4
next = curr->next;
prev->next = next;
delete curr;
curr = next;

这里要注意的是头节点，如果头节点的值刚好 val，这个删除操作和上面的代码片段有少许区别

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode *prev, *curr, *next;

        prev = NULL;
        curr = head;
        while (curr != NULL) {
            if (curr->val == val) {
                next = curr->next;
                if (prev == NULL)
                    head = next;
                else
                    prev->next = next;
                delete curr;
                curr = next;
            } else {
                prev = curr;
                curr = curr->next;
            }
        }

        return head;
    }
};

Posted on Edited on

问题描述

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Note: Do not use any built-in library function such as sqrt.

Example 1:

1
2
Input: 16
Output: true

Example 2:

1
2
Input: 14
Output: false

Related Topics: Math, Binary Search

原问题: 367. Valid Perfect Square

中文翻译版: 367. 有效的完全平方数

解决方案

本题换种说法就是：求正整数 num 的平方根 x，且 x 的平方等于 num，如何求正整数的平方根，可以用二分查找进行求解，这个可以参考LeetCode原题 69. Sqrt(x)（解题报告：LeetCode 69 - Sqrt(x)），二分查找后得到的平方根 x，只需判断 x 的平方是否等于 num 即可判断 num 是否为完全平方数

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
using namespace std;


class Solution {
public:
    bool isPerfectSquare(int num) {
        long long low, mid, high;

        low = 0;
        high = (long)num + 1;
        while (low < high) {
            mid = low + (high - low) / 2;
            if (mid * mid < num)
                low = mid + 1;
            else
                high = mid;
        }

        // if it doesn't find square of number
        if (low * low != num)
            return false;

        return true;
    }
};


int main()
{
    int num;
    Solution solu;

    // max of int
    // num = 2147483647;
    num = 14;
    cout << num << " is perfect square: "
         << solu.isPerfectSquare(num) << endl;
    return 0;
}

Posted on Edited on

问题描述

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

1
2
3
Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Follow up:

Could you do this in one pass?

Related Topics: Linked List, Two Pointers

原问题: 19. Remove Nth Node From End of List

中文翻译版: 19. 删除链表的倒数第N个节点

解决方案

这道题可以使用双指针方法解决，设定两个指针 p1 和 p2，先让指针 p1 遍历 n 个节点，然后指针 p2 开始和指针 p1 同步遍历链表，当指针 p1 遍历完链表后，指针 p2 刚好指向倒数第 n 个节点，此时删除该节点即可。

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == NULL)
            return NULL;

        ListNode *pos1, *pos2, *prev;
        int step;

        prev = NULL;
        pos1 = pos2 = head;
        step = 0;
        while (pos2 != NULL) {
            pos2 = pos2->next;
            step += 1;
            if (step > n) {
                prev = pos1;
                pos1 = pos1->next;
            }
        }
        if (prev == NULL)
            head = head->next;
        else
            prev->next = pos1->next;

        return head;
    }
};

Posted on Edited on

问题描述

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Example 1:

1
2
3
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.

Example 2:

1
2
3
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

1
2
3
4
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

Related Topics: Linked List

原问题: 160. Intersection of Two Linked Lists

中文翻译版: 160. 相交链表

解决方案

这里假设两条链表有相交节点，如下图所示：

图中 AD 线段代表链表1，线段 CB 加 线段 BD 代表链表2，链表1要长于链表2，两条链表相交于节点 B，链表1长度为 |AD| = |AB| + |BD| = p + n，链表2长度为 |CB| + |BD| = m + n（注明：这里长度定义为从线段开始节点遍历到结束节点所要移动的节点数）

现在开始同时遍历链表1和链表2，由于链表2比链表1要短，所以链表2最先遍历完，此时链表1遍历到节点 E，因此 |AE| = m + n，继续遍历链表2直到遍历结束，从节点 E 到节点 D 的长度为 ED = q

根据图中表示，我们可以得到一个等式，那就是

1
2
3
    |AB| + |BD| = |AE| + |ED|
==>  p + n = m + n + q
==>  p - m = q

从上面等式可以得到 |AB| - |CB| = q，等式说明了链表1头节点 A 到相交节点 B 的长度比链表2头节点 C 到相交节点 B 长度要长 q，这个 q 是已知量，说明链表1第 q 个节点到节点 B 的距离要等于链表2节点 C 到节点 B 的距离。这里就可以得出该题的一个解题思路：

1
2
设定两个指针p1和p2，分别用于遍历链表1和链表2，指针p1先移动到链表1的第q个节点，
然后指针p2开始遍历链表2，直到 p1 == p2，此时 p1 为两个链表相交节点
参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (NULL == headA || NULL == headB)
            return NULL;
        if (headA == headB)
            return headA;

        ListNode *prevA, *prevB;
        ListNode *currA, *currB;
        ListNode *posA, *posB;

        prevA = prevB = NULL;
        posA = currA = headA;
        posB = currB = headB;
        while ((currA != NULL) || (currB != NULL)) {
            if (currA != NULL) {
                prevA = currA;
                currA = currA->next;
            } else {
                posB = posB->next;
            }
            if (currB != NULL) {
                prevB = currB;
                currB = currB->next;
            } else {
                posA = posA->next;
            }
        }
        // have intersection
        if (prevA == prevB) {
            while (posA != posB) {
                posA = posA->next;
                posB = posB->next;
            }
            return posA;
        }

        return NULL;
    }
};

Posted on Edited on

问题描述

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Related Topics: Linked List, Two Pointers

原问题: 141. Linked List Cycle

中文翻译版: 141. 环形链表

解决方案

该题可以使用双指针方法进行解决，设定快指针 fast 和慢指针 slow，两指针同时从头节点 head 出发，慢指针每前进一个节点，快指针就前进两个节点，如果链表有环，由于两指针前进速度不同，最终两指针会汇聚在同一个节点，即 fast == slow，否则，快指针会最先到达链表节点，两指针不会汇聚在一起。

参考解题代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include "List.h"
using namespace std;

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head == NULL)
            return false;

        ListNode *fast, *slow;
        fast = slow = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
                return true;
        }

        return false;
    }
};

int main()
{
    ListNode *node1 = create_list_node(1);
    ListNode *node2 = create_list_node(2);
    ListNode *node3 = create_list_node(3);
    ListNode *node4 = create_list_node(4);
    connect_list_nodes(node1, node2);
    connect_list_nodes(node2, node3);
    connect_list_nodes(node3, node4);
    connect_list_nodes(node4, node2);

    Solution solu;
    cout << solu.hasCycle(node1) << endl;

    return 0;
}

Posted on Edited on

问题描述

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

  1. Each row must contain the digits 1-9 without repetition.
  2. Each column must contain the digits 1-9 without repetition.
  3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: true

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input:
[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being 
    modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

Note:

  • A Sudoku board (partially filled) could be valid but is not necessarily solvable.
  • Only the filled cells need to be validated according to the mentioned rules.
  • The given board contain only digits 1-9 and the character '.'.
  • The given board size is always 9x9.

Related Topics: Hash Table

原问题: 36. Valid Sudoku

中文翻译版: 36. 有效的数独

解决方案

方案1

根据题目说明，一个有效的数独，满足三个条件：

  1. 每行数字有重复数字
  2. 每列不能有重复数字
  3. 每个 3x3 块中不能有重复数字

怎么判断一行、一列或者一个小块中是否有重复数字，此时我们可以给用哈希表进行快速查找判断。首先我们分别给每一行、每一列以及每一小块建立一个哈希表，然后我们遍历所有数字，当遍历到某个数字时，我们根据该数字所处的行、列以及小块找到对应的哈希表，查找该数字是否在哈希表中出现，如果出现，说明该数独是无效的，否则我们将该数字存入哈希表，继续遍历。

参考解题代码1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <vector>
#include <unordered_set>
#include <iostream>
using namespace std;


class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        vector<unordered_set<char>> row_sets(9);
        vector<unordered_set<char>> column_sets(9);
        vector<unordered_set<char>> block_sets(9);

        char ch;
        int block_id;
        for (auto i=0; i<9; i++) {
            for (auto j=0; j<9; j++) {
                ch = board[i][j];

                if (ch == '.')
                    continue;

                if (row_sets[i].find(ch) == row_sets[i].end())
                    row_sets[i].insert(ch);
                else
                    return false;

                if (column_sets[j].find(ch) == column_sets[j].end())
                    column_sets[j].insert(ch);
                else
                    return false;

                block_id = int(i / 3.0) * 3 + int(j / 3.0);
                if (block_sets[block_id].find(ch) == block_sets[block_id].end())
                    block_sets[block_id].insert(ch);
                else
                    return false;
            }
        }

        return true;
    }
};

int main()
{
    vector<vector<char>> board = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'}, 
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'}, 
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'}, 
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'}, 
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'}, 
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'}, 
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'}, 
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };

    for (auto i=0; i<board.size(); i++) {
        for (auto j=0; j<board[i].size(); j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }

    Solution solu;
    cout << "Is valid: " << solu.isValidSudoku(board) << endl;

    return 0;
}

方案2

同方案1的思想，只不过此时一行、一列以及一小块对应的哈希表分别用一个整数进行替代，通过该整数的某一位是否为1来进行重复数字判断，主要使用的是位与运算 & 和位或运算 |。当遍历到某个数字 x 时，该数字所在行对应的整数为 y，此时判断该数字是否重复可以进行如下操作：

1
y & (1 << x)

如果该表达式值非0，说明 y 的第 x 位是1，这说明该数字之前出现过，否则该表达式值为0。如果该数字未重复出现，则 y 设为：

1
y = y | (1 << x)
参考解题代码2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;


class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int row_status[board.size()];
        int col_status[board.size()];
        int cell_status[board.size()];
        int digit, cell, block_size, num_blocks;

        for (int i=0; i<board.size(); i++) {
            row_status[i] = 0;
            col_status[i] = 0;
            cell_status[i] = 0;
        }

        block_size = int(sqrt(board.size()));
        num_blocks = board.size() / block_size;
        for (int i=0; i<board.size(); i++) {
            for (int j=0; j<board[i].size(); j++) {
                if (board[i][j] == '.')
                    continue;

                digit = 1 << (board[i][j] - '0');
                cell = (i / block_size) * num_blocks + (j / block_size);
                if ((row_status[i] & digit) != 0)
                    return false;
                if ((col_status[j] & digit) != 0)
                    return false;
                if ((cell_status[cell] & digit) != 0)
                    return false;
                row_status[i] |= digit;
                col_status[j] |= digit;
                cell_status[cell] |= digit;
            }
        }

        return true;
    }
};

int main()
{
    vector<vector<char>> board = {
            {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
            {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
            {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
            {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
            {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
            {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
            {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
            {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
            {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };

    for (auto i=0; i<board.size(); i++) {
        for (auto j=0; j<board[i].size(); j++) {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }

    Solution solu;
    cout << "Is valid: " << solu.isValidSudoku(board) << endl;

    return 0;
}