LeetCode 37. 解数独

题目类型

1. 暴搜
2. dfs

题目链接

https://leetcode.cn/problems/sudoku-solver/submissions/

思路

1. 对每个没放数的格子，从1-9dfs枚举
2. 选择某个数i的时候 判断rows[x][i] cols[y][i] cells[x / 3][y / 3][i]的状态
3. 以上判断如果为false，回溯；为true，继续搜索下一个点(x, y + 1)

AC代码

class Solution {
public:
    // 行 列 小方格的枚举每个数的状态
    bool rows[9][9], cols[9][9], cells[3][3][9]; 
    void solveSudoku(vector<vector<char>>& board) {
        memset(rows, false, sizeof rows);
        memset(cols, false, sizeof cols);
        memset(cells, false, sizeof cells);

        // 初始化
        for (int i = 0; i < 9; i ++)
        {
            for (int j = 0; j < 9; j ++)
            {
                if (board[i][j] != '.')
                {
                    int t = board[i][j] - '1';
                    rows[i][t] = cols[j][t] = cells[i / 3][j / 3][t] = true;

                }
            }
        }
        // 从(0, 0)开始填
        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>> &board, int x, int y)
    {
        if (y == 9) y = 0, x ++;
        if (x == 9) return true;

        // 如果该位置已经有数了 则换下一个位置
        if (board[x][y] != '.') return dfs(board, x, y + 1);
        // 否则这个位置可以插入，枚举一下
        for (int i = 0; i < 9; i ++)
        {
            if (!rows[x][i] && !cols[y][i] && !cells[x / 3][y / 3][i])
            {
                rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = true;
                board[x][y] = '1' + i;
                if (dfs(board, x, y + 1)) return true;
                // 回溯
                board[x][y] = '.';
                rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = false;
            }
        }
        return false;
    }
};

LeetCode 37. 解数独

题目类型

1. 暴搜
2. dfs

题目链接

https://leetcode.cn/problems/sudoku-solver/submissions/

思路

1. 对每个没放数的格子，从1-9dfs枚举
2. 选择某个数i的时候 判断rows[x][i] cols[y][i] cells[x / 3][y / 3][i]的状态
3. 以上判断如果为false，回溯；为true，继续搜索下一个点(x, y + 1)

AC代码

class Solution {
public:
    // 行 列 小方格的枚举每个数的状态
    bool rows[9][9], cols[9][9], cells[3][3][9]; 
    void solveSudoku(vector<vector<char>>& board) {
        memset(rows, false, sizeof rows);
        memset(cols, false, sizeof cols);
        memset(cells, false, sizeof cells);

        // 初始化
        for (int i = 0; i < 9; i ++)
        {
            for (int j = 0; j < 9; j ++)
            {
                if (board[i][j] != '.')
                {
                    int t = board[i][j] - '1';
                    rows[i][t] = cols[j][t] = cells[i / 3][j / 3][t] = true;

                }
            }
        }
        // 从(0, 0)开始填
        dfs(board, 0, 0);
    }

    bool dfs(vector<vector<char>> &board, int x, int y)
    {
        if (y == 9) y = 0, x ++;
        if (x == 9) return true;

        // 如果该位置已经有数了 则换下一个位置
        if (board[x][y] != '.') return dfs(board, x, y + 1);
        // 否则这个位置可以插入，枚举一下
        for (int i = 0; i < 9; i ++)
        {
            if (!rows[x][i] && !cols[y][i] && !cells[x / 3][y / 3][i])
            {
                rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = true;
                board[x][y] = '1' + i;
                if (dfs(board, x, y + 1)) return true;
                // 回溯
                board[x][y] = '.';
                rows[x][i] = cols[y][i] = cells[x / 3][y / 3][i] = false;
            }
        }
        return false;
    }
};

LeetCode 35. 搜索插入位置

题目类型

二分

题目链接

https://leetcode.cn/problems/search-insert-position

思路

使用二分搜素比较简单 直接AC，这里只讲搜索左边界的思路（对应是AC代码1），右边界的思路（对应AC代码2）

1. 使用二分搜索≤target数的位置l
2. 如果target > nums[l]，则插入位置为l+1，否则为l

AC代码1

// 二分写法一：
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (target > nums[l]) return l + 1;
        else return l;
    }
};

AC代码2

// 二分写法二
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        if (target <= nums[r]) return r;
        else return r + 1;
    }
};

LeetCode 35. 搜索插入位置

题目类型

二分

题目链接

https://leetcode.cn/problems/search-insert-position

思路

使用二分搜素比较简单 直接AC，这里只讲搜索左边界的思路（对应是AC代码1），右边界的思路（对应AC代码2）

1. 使用二分搜索≤target数的位置l
2. 如果target > nums[l]，则插入位置为l+1，否则为l

AC代码1

// 二分写法一：
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (target > nums[l]) return l + 1;
        else return l;
    }
};

AC代码2

// 二分写法二
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int n = nums.size();
        int l = 0, r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        if (target <= nums[r]) return r;
        else return r + 1;
    }
};

#include <iostream>

using namespace std;
const int N = 40010;
int p[N];
int n, m;

int get(int x, int y)
{
    return x * n + y;
}

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

int main()
{
    cin >> n >> m;
    // 初始化并查集
    for (int i = 0; i < n * n; i ++ ) p[i] = i;

    int res = 0;
    for (int i = 1; i <= m; i ++)
    {
        int x, y;
        char d;
        cin >> x >> y >> d;

        x --, y --;
        int a = get(x, y);
        int b;
        if (d == 'D') b = get(x + 1, y);
        else b = get(x, y + 1);

        int pa = find(a), pb = find(b);
        if (pa == pb)
        {
            res = i;
            break;
        }
        else 
        {
            p[pa] = pb;
        }
    }

    if (res) cout << res << endl;
    else cout << "draw" << endl;
    return 0;
}

LeetCode 31. 下一个排列

题目类型

1. 数组
2. 找规律题

题目链接

https://leetcode.cn/problems/next-permutation/

思路

建议画图用例子模拟

[2 3 5 4 1] => [2 4 1 3 5]

1. 先用指针k从后往前找，找到第一个不满足nums[k - 1]>nums[k]的位置，即k即往后的都为降序
2. 如果k在nums起始位置，则将整个数组反转，否则执行3
3. 用指针t从指针k所在位置往右寻找，找到第一个大于nums[k-1]的数,此时整个数为nums[t - 1]
4. 并且将nums[k-1]和nums[t - 1]互换
5. 将k后面的序列反转

AC代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        // 2 3 5 4 1
        // 此时处于5这个位置
        while (k > 0 && nums[k - 1] >= nums[k]) k --;
        // 整个序列都是降序
        if (k <= 0) 
        {
            reverse(nums.begin(), nums.end());
        }
        else
        {
            int t = k;
            while (t <= nums.size() - 1 && nums[t] > nums[k - 1]) t ++;
            swap(nums[k - 1], nums[t - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};

LeetCode 31. 下一个排列

题目类型

1. 数组
2. 找规律题

题目链接

https://leetcode.cn/problems/next-permutation/

思路

建议画图用例子模拟

[2 3 5 4 1] => [2 4 1 3 5]

1. 先用指针k从后往前找，找到第一个不满足nums[k - 1]>nums[k]的位置，即k即往后的都为降序
2. 如果k在nums起始位置，则将整个数组反转，否则执行3
3. 用指针t从指针k所在位置往右寻找，找到第一个大于nums[k-1]的数,此时整个数为nums[t - 1]
4. 并且将nums[k-1]和nums[t - 1]互换
5. 将k后面的序列反转

AC代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        // 2 3 5 4 1
        // 此时处于5这个位置
        while (k > 0 && nums[k - 1] >= nums[k]) k --;
        // 整个序列都是降序
        if (k <= 0) 
        {
            reverse(nums.begin(), nums.end());
        }
        else
        {
            int t = k;
            while (t <= nums.size() - 1 && nums[t] > nums[k - 1]) t ++;
            swap(nums[k - 1], nums[t - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0; // k作为存储下标
        for (int i = 1; i < nums.size(); i ++)
        {
            if (nums[i] != nums[k])
            {
                k ++;
                nums[k] = nums[i];
            }
        }
        return k + 1;
    }
};

LeetCode 25. K 个一组翻转链表（***）

题目类型

1. 链表
2. k组翻转

题目链接

https://leetcode.cn/problems/reverse-nodes-in-k-group/

思路

此时看起来不难，实际实现的时候很容易出错，建议多刷几次

1. 每次检验是否下一组足够k个元素，不够则break 够的话继续往下执行
2. 对于 p->a->b->c->d 从a开始进行k-1次循环反转指针,而且注意在反转指针之前要把b->next存起来

   auto c = b->next, b->next = a

3. k-1次之后（也就是该组已经反转成功后） 此时将p->next->next = b，落到了下一组以b为开始的反转的前一个结点（可以看做是虚拟结点）
4. 继续以上操作

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        for (auto p = dummy;;)
        {
            // 判断是否满足k个元素
            auto q = p;
            for (int i = 0; i < k && q; i ++) q = q->next;
            if (!q) break; // 不满足直接跳出


            // 满足有k个元素
            auto a = p->next, b = a->next;
            for (int i = 0; i < k - 1; i ++) // 内部交换k - 1次
            {
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            }
            auto t = p->next;
            p->next = a;
            t->next = b;
            p = t;
        }
        return dummy->next;
    }
};

LeetCode 25. K 个一组翻转链表（***）

题目类型

1. 链表
2. k组翻转

题目链接

https://leetcode.cn/problems/reverse-nodes-in-k-group/

思路

此时看起来不难，实际实现的时候很容易出错，建议多刷几次

1. 每次检验是否下一组足够k个元素，不够则break 够的话继续往下执行
2. 对于 p->a->b->c->d 从a开始进行k-1次循环反转指针,而且注意在反转指针之前要把b->next存起来

   auto c = b->next, b->next = a

3. k-1次之后（也就是该组已经反转成功后） 此时将p->next->next = b，落到了下一组以b为开始的反转的前一个结点（可以看做是虚拟结点）
4. 继续以上操作

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;

        for (auto p = dummy;;)
        {
            // 判断是否满足k个元素
            auto q = p;
            for (int i = 0; i < k && q; i ++) q = q->next;
            if (!q) break; // 不满足直接跳出


            // 满足有k个元素
            auto a = p->next, b = a->next;
            for (int i = 0; i < k - 1; i ++) // 内部交换k - 1次
            {
                auto c = b->next;
                b->next = a;
                a = b, b = c;
            }
            auto t = p->next;
            p->next = a;
            t->next = b;
            p = t;
        }
        return dummy->next;
    }
};