王清楚

题解

ACM(1) PAT(3) uva(1) 未归档(9)

/ 注册

全部文章 / 题解（共94篇）

【牛客题霸题解】进制转换来自专栏

我们先了解一下N进制的本质：假设N进制每个位置上的数是a_i则一个4位的N进制数可以表示为则这个数字的数值 = 例：10进制数178可以表示为16进制数1AB可以表示为然后我们再继续思考一下：如何获得一个十进制的每一位？比如：对于十进制数178，我们想要获得1、7、8，先用178对10取模，可以获得...

2020-12-03

16 1349

【牛客题霸题解】跳台阶来自专栏

我们先来观察一下跳到台阶1的方案：① 0⇒1跳到台阶2的方案：① 0⇒1⇒2② 0⇒2跳到台阶3的方案：① 0⇒1⇒2⇒3② 0⇒2⇒3③ 0⇒1⇒3跳到台阶4的方案：① 0⇒1⇒2⇒3⇒4② 0⇒2⇒3⇒4③ 0⇒1⇒3⇒4④ 0⇒1⇒2⇒4⑤ 0⇒2⇒4可以发现：跳到台阶4的方案是从台阶3跳1级...

2020-12-03

6 823

【牛客题霸题解】反转字符串来自专栏

解法一:开辟一个和str长度大小相同的一个字符串ans，把传入的str倒序赋值到ans字符串上，时间复杂度,额外空间复杂度c++ class Solution { public: string solve(string str) { string ans = str; ...

2020-12-02

28 1444

【牛客题霸题解】括号序列来自专栏

题目中给出的字符串仅包含字符'(',')','{','}','['和']',对字符串中的每一个字符进行遍历，如果是右括号的话，需要看一下栈顶元素是不是和它匹配的左括号。如果是的话，那这两个括号是一对，让栈顶元素出栈不满足配对条件的话，就让该元素进栈如果字符串是一个合法的括号序列，那么整个字符串遍历完...

2020-11-19

22 1815

【题解】dia和尊严

根据题目给出的条件，一个人可以有多个下属，但一个人最多只能有一个上级。可以得出其实是一棵树。我们要求的其实就是从根节点到每一个节点的代价，这个代价是根节点到这个节点的边权加上这个节点的点权。所以只需要进行一次dfs，dfs的过程中记录边权，然后计算每个点的代价的时候加上这个点的点权就可以了。...

2020-11-12

5 0

【牛客题霸题解】二分查找来自专栏

题目要求：在有序数组中查找第一个大于等于给定值的位置，如果不存在，输出数组的长度加一。先考虑这样一个问题：对于一个有序数组来说，什么情况下是不存第一个大于等于的位置呢？即：数组中的所有数都比小，可以写成 if(a[n-1]<v) return n+1;判完这个条件...

2020-11-11

32 1451

【题解】子数组的最大异或和

记表示数组前个数的异或和，就是区间的异或和那如果想知道以位置结尾的子数组的最大异或和，只需要知道和中的数异或的最大值就可以了。（即这些区间异或和的最大值）那怎么样快速地知道和中的数异或和的最大值呢?我们利用前缀树的结构，对每一个，从最高位到最低位判断。这里需要注意一下，因为我们想...

2020-10-15

3 1309

【题解】换钱的最少货币数

表示组成价值需要的最少的货币数如果目前情况下价值目前最少能由个货币组成，那么加了一个价值的商品，就可以由个货币组成对于每一个物品，从循环一遍，更新dp的值。所有的物品都加入完毕以后，就是结果。 #include<iostream> using namespace std; co...

2020-10-10

6 870

【题解】比大小

利用栈来操作，如果当前入栈的元素比栈顶元素大，那这个元素就是栈顶元素右边第一个比栈顶元素大的元素。如果当前元素比栈顶元素小。或者栈为空，那当前元素入栈。 #include<iostream> #include<stack> #include<vector> usi...

2020-09-23

4 793

【题解】遍历二叉树

这道题一开始看到的时候想先把二叉树剪出来，然后再找出叶子节点做一个动态规划，然后仔细一想发现，对于满二叉树来说，中序遍历的第1，3，5，7.。。项就是叶子节点。那我们就可以直接获得叶子节点了，然后用表示前个节点可以获得的最大粮食数，可以从(偷当前节点的粮食)和(不偷当前节点的粮食)转移而来...

2020-09-22

8 735