Algorithm 分类

题目内容

给你一个长度为 n 的整数数组 nums，其中 nums 是范围 [0..n - 1] 内所有数字的一个排列。

MorseWayne2025/8/10...大约 3 分钟

概要

初识DP(dynamic programming)问题，我觉得这是一个非常抽象的算法思想，我反反复复想了很久，一直在思考这类问题为什么可以这么做。

DP问题解法的一个核心概念就是要理解状态转移以及找到状态转移公式，我们求解的答案是程序在某个特定状态下的表现，而这个状态是一个或者多个历史的状态变化(多个历史状态压缩成一个状态，这个就叫状态压缩)而来。对于程序每一个可能出现的状态，都能通过一个通用的方式从历史状态变化而来，这一类问题我们就将其叫做DP问题，寻找状态转移公式也就是我们常说的寻找最优子问题。

MorseWayne2025/8/8...大约 4 分钟

链表环

判断链表是否有环以及找到环的位置的通用做法就是快慢指针，在探讨具体的算法前，我们先了解下面的基础知识，当然你也可以去阅读维基百科 Floyd判圈算法。

知识点1

存在一个环，环的大小为n，有两个指针p1, p2, p1每次在环内可以移动一步，p2在环内每次可以移动两步, p1和p2必然在链表的某一个位置相遇，证明如下：

MorseWayne2025/8/8...大约 4 分钟

打家劫舍

题目内容

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

MorseWayne2025/8/8...大约 4 分钟

互不侵犯

题目描述

在 N×N 的棋盘里面放 K 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 8 个格子。

个人答案

展开代码

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

using namespace std;

long long getCnt(int N, int K)
{
    int maxCnt = 1 << N;
    vector<vector<vector<long long>>> dp(N, vector<vector<long long>>(K + 1, vector<long long>(maxCnt, 0)));
    for (int val = 0; val < maxCnt; ++val) {
        if (val & ((val << 1) | (val >> 1))) {
            continue;
        }
        int currCnt = __builtin_popcount(val);
        if (currCnt > K) {
            continue;
        }
        dp[0][currCnt][val] = 1;
    }
    dp[0][0][0] = 1;

    for (int row = 1; row < N; ++row) {
        for (int totalCnt = 0; totalCnt <= K; ++totalCnt) {
            for (int currVal = 0; currVal < maxCnt; ++currVal) {
                int currCnt = __builtin_popcount(currVal);
                if (currCnt > totalCnt) {
                    continue;
                }
                if (currVal & ((currVal << 1) | (currVal >> 1))) {
                    continue;
                }
                for (int lastVal = 0; lastVal < maxCnt; ++lastVal) {
                    if (currVal & (lastVal | lastVal << 1 | lastVal >> 1)) {
                        continue;
                    }
                    dp[row][totalCnt][currVal] += dp[row - 1][totalCnt - currCnt][lastVal];
                }
            }
        }
    }
    return std::accumulate(dp[N - 1][K].begin(), dp[N - 1][K].end(), 0ll);
}

#include <iostream>

int main()
{
    int N = 0;
    int K = 0;
    cin >> N >> K;
    cout << getCnt(N, K) << endl;
}

MorseWayne2025/8/8...小于 1 分钟