当前位置: 首页 > news >正文

【阶乘】个人练习-Leetcode-LCP 22. 黑白方格画

题目链接:https://leetcode.cn/problems/ccw6C7/description/

题目大意:给出一块白方格面积为n*n,给出一个数字k,每一次操作可以把方格的某一整行或者某一整列涂黑,求使得黑色格子数字为k的【最终图案】的个数。

思路:虽然是简单题,但还想了一会的。因为【最终图案数】并不是【操作方法数】。比如2*2的格子,【先涂一行再涂一列】和【先涂一列再涂一行】得到的图案是一样的。我们发现涂的行列具体是哪几行哪几列并不影响最终黑格子的数目,因此可以先得出【需要涂黑x行】和【需要涂黑y列】,然后求组合数 C n x C_n^x Cnx C n y C_n^y Cny的乘积即可。因为x, y对可能有多个,我们用一个vector<pair<int, int>>来保存。

然而要注意一下一些特殊情况:
k < n:那么就算只涂一行也会超过,不行
k == 0:什么都不用做,返回1

求阶乘的话可以用一个数组来保存结果,避免重复计算。

完整代码

class Solution {
public:vector<int> frac;int getFrac(int x) {if (x == 0)return frac[0] = 1;if (frac[x])return frac[x];elsereturn frac[x] = x*getFrac(x-1);}int paintingPlan(int n, int k) {if (k == 0)return 1;if (n > k)return 0;if (n*n == k)return 1;int ans = 0;vector<pair<int, int>> res;frac.resize(n+1, 0);for (int x = 0; x < n; x++) {for (int y = 0; y < n; y++) {if (x*n+y*(n-x) > k)break;else if (x*n+y*(n-x) == k) {res.emplace_back(make_pair(x, y));}else;}}for (auto p : res) {int x = p.first, y = p.second;ans += (getFrac(n)/getFrac(x)/getFrac(n-x)) * (getFrac(n)/getFrac(y)/getFrac(n-y));}return ans;}
};

相关文章:

【阶乘】个人练习-Leetcode-LCP 22. 黑白方格画

题目链接&#xff1a;https://leetcode.cn/problems/ccw6C7/description/ 题目大意&#xff1a;给出一块白方格面积为n*n&#xff0c;给出一个数字k&#xff0c;每一次操作可以把方格的某一整行或者某一整列涂黑&#xff0c;求使得黑色格子数字为k的【最终图案】的个数。 思路…...

十七、【文本编辑器(三)】图像坐标变换

目录 一、缩放功能 二、旋转功能 三、镜像功能 四、QMatrix简单介绍 一、缩放功能 &#xff08;1&#xff09;在头文件中添加 “protected slots:" 变量&#xff1a; void ShowZoomln( ); &#xff08;2&#xff09;在 createActionso函数的最后添力口事件关联&…...

生活中生智慧

【 圣人多过 小人无过 】 觉得自己做得不够才能做得更好&#xff0c;互相成全&#xff1b;反求诸己是致良知的第一步&#xff1b;有苦难才能超越自己&#xff0c;开胸怀和智慧&#xff1b;不浪费任何一次困苦&#xff0c;危机中寻找智慧&#xff0c;成长自己。 把困苦当作当下…...

2024第18届中国西部(成都)教育装备展12月14日举办

2025中国国际工业气体设备技术及应用展览会 2025 China International Industrial Gas Equipment Technology and Application Exhibition 时间&#xff1a;2025年3月18-20日 地点&#xff1a;北京全国农业展览馆&#xff08;新馆&#xff09; 展览前言 随着需求市场的持续…...

Webpack看这篇就够了

&#x1f49d;&#x1f49d;&#x1f49d;欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 非常期待和您一起在这个小…...

基于京东电商蓝牙耳机产品评论数据的情感分析与文本分析

摘要 随着电子商务的迅速发展&#xff0c;了解用户对产品的意见和情感倾向对企业至关重要。本研究旨在利用Python大数据技术对电商产品评论进行情感分析和主题建模&#xff0c;为企业提供有价值的市场洞察。 通过爬虫获取电商评论数据&#xff0c;使用pandas清洗和预处理数据&a…...

【Linux网络】poll{初识poll / poll接口 / poll vs select / poll开发多客户端echo服务器}

文章目录 1.初识pollpoll与select的主要联系与区别poll的原理poll的优点poll的缺点poll vs select 2.poll开发多客户端echo服务器封装套接字接口Makefile主函数日志服务聊天服务器 1.初识poll poll是Linux系统中的一个系统调用&#xff0c;它用于监控多个文件描述符&#xff08…...

数据库db文件损坏修复方法(sqlite3:database disk image is malformed)

参考博客&#xff1a; https://www.cnblogs.com/liuyangQAQ/p/18037546 sqlite3数据库提示database disk image is malformed 解决办法-CSDN博客 【SQL】sqlite数据库损坏报错&#xff1a;database disk image is malformed&#xff08;已解决&#xff09;-CSDN博客 一、第…...

Prometheus 云原生 - 微服务监控报警系统 (Promethus、Grafana、Node_Exporter)部署、简单使用

目录 开始 Prometheus 介绍 基本原理 组件介绍 下文部署组件的工作方式 Prometheus 生态安装&#xff08;Mac&#xff09; 安装 prometheus 安装 grafana 安装 node_exporter Prometheus 生态安装&#xff08;Docker&#xff09; 安装 prometheus 安装 Grafana 安装…...

Spring源码注解篇三:深入理解@Component注解

Component及其派生注解的源码 Spring框架作为Java开发中不可或缺的一部分&#xff0c;其依赖注入机制的核心是通过注解来实现的。本文将深入探讨Spring中Component及其派生注解的源码实现&#xff0c;分析Spring如何通过类路径扫描&#xff08;Classpath Scanning&#xff09;和…...

SpringBoot中常用的注解及其用法

1. 常用类注解 RestController和Controller是Spring中用于定义控制器的两个类注解. 1.1 RestController RestController是一个组合类注解,是Controller和ResponseBody两个注解的组合,在使 用 RestController 注解标记的类中&#xff0c;每个方法的返回值都会以 JSON 或 XML…...

【大语言模型】私有化搭建-企业知识库-知识问答系统

下面是我关于大语言模型学习的一点记录 目录 人工智能学习路线 MaxKB 系统(基于大语言模型的知识问答系统) 部署开源大语言模型LLM 1.CPU模式(没有好的GPU&#xff0c;算力和效果较差) 2.GPU模式&#xff08;需要有NVIDIA显卡支持&#xff09; Ollama网络配置 Ollama前…...

CSS常用的样式

字体和文本样式 font-family: 定义文本字体。 font-size: 设置字体大小。 color: 设置文本颜色。 text-align: 水平对齐文本&#xff08;左对齐、右对齐、居中、两端对齐&#xff09;。 line-height: 设置行间距。 text-decoration: 控制文本装饰线&#xff08;如下划线、…...

结合实体类型信息(2)——基于本体的知识图谱补全深度学习方法

1 引言 1.1 问题 目前KGC和KGE提案的两个主要缺点是:(1)它们没有利用本体信息;(二)对训练时未见的事实和新鲜事物不能预测的。 1.2 解决方案 一种新的知识图嵌入初始化方法。 1.3 结合的信息 知识库中的实体向量表示&#xff0b;编码后的本体信息——>增强 KGC 2基…...

如何在电脑上演示手机上APP,远程排查移动端app问题

0序&#xff1a; 对接客户&#xff0c;给领导演示移动端产品&#xff0c;或者远程帮用户排查移动端产品的问题。都需要让别人能够看到自己在操作手机。 会议室可以使用投屏&#xff0c;但需要切换电脑和手机。 排查问题经常都是截图、或者手机上录制视频&#xff0c;十分繁琐…...

SQL Server 创建用户并授权

创建用户前需要有一个数据库&#xff0c;创建数据库命令如下&#xff1a; CREATE DATABASE [数据库名称]; CREATE DATABASE database1; 一、创建登录用户 方式1&#xff1a;SQL命令 命令格式&#xff1a;CREATE LOGIN [用户名] WITH PASSWORD 密码; 例如&#xff0c;创建…...

网关设备BL122实现Modbus RTU/TCP转Profinet协议

Modbus与Profinet是两种广泛应用于工业自动化领域的通信协议&#xff1a;Modbus因其简单性和兼容性&#xff0c;在许多工业设备中得到广泛应用&#xff1b;而Profinet提供了高速、高精度的通信能力&#xff0c;适合于复杂控制系统和实时应用&#xff0c;但两者之间的差异导致了…...

采购管理软件:改善初创企业的采购流程

说到初创企业&#xff0c;人们往往会联想到一个宽松的工作环境&#xff0c;缺乏严格的流程规范&#xff0c;以及公司收入的迅猛增长。这种快速增长可能会被认为会导致工作流程的无序和缺乏结构&#xff0c;使得员工在决策上具有较大的自由度&#xff0c;例如在采购方面。 在这…...

Python 是一种用途广泛的编程语言,应用于各个领域

1. 网络和互联网开发: Python 拥有丰富的框架和库&#xff0c;使其成为 Web 开发的理想选择。 框架: Django 和 Pyramid 用于构建复杂的 Web 应用。Flask 和 Bottle 则适合轻量级应用和 API。 库: Python 标准库支持处理 HTML、XML、JSON 和电子邮件。此外&#xff0c;还有强大…...

【VUE】9、VUE项目中使用VUEX完成状态管理

Vuex 是一个专为 Vue.js 应用程序设计的状态管理模式&#xff0c;它帮助开发者更有效地管理组件间共享的状态。在 Vue 项目中使用 Vuex&#xff0c;可以解决复杂应用中状态管理的困扰&#xff0c;确保状态变更的可追踪性和一致性。 1、Vuex 核心概念 State&#xff08;状态&a…...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

浅谈 React Hooks

React Hooks 是 React 16.8 引入的一组 API&#xff0c;用于在函数组件中使用 state 和其他 React 特性&#xff08;例如生命周期方法、context 等&#xff09;。Hooks 通过简洁的函数接口&#xff0c;解决了状态与 UI 的高度解耦&#xff0c;通过函数式编程范式实现更灵活 Rea…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

AtCoder 第409​场初级竞赛 A~E题解

A Conflict 【题目链接】 原题链接&#xff1a;A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串&#xff0c;只有在同时为 o 时输出 Yes 并结束程序&#xff0c;否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

uni-app学习笔记三十五--扩展组件的安装和使用

由于内置组件不能满足日常开发需要&#xff0c;uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件&#xff0c;需要安装才能使用。 一、安装扩展插件 安装方法&#xff1a; 1.访问uniapp官方文档组件部分&#xff1a;组件使用的入门教程 | uni-app官网 点击左侧…...

DeepSeek越强,Kimi越慌?

被DeepSeek吊打的Kimi&#xff0c;还有多少人在用&#xff1f; 去年&#xff0c;月之暗面创始人杨植麟别提有多风光了。90后清华学霸&#xff0c;国产大模型六小虎之一&#xff0c;手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水&#xff0c;单月光是投流就花费2个亿。 疯…...