Moon

题目描述题目链接 硬币。给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007) 示例1： 12345 输入: n = 5 输出：2 解释: 有两种方式可以凑成总金额:5=55=1+1+1+1+1 示例2： 1234567 输入: n = 10 输出：4 解释: 有四种方式可以凑成总金额:10=1010=5+510=5+1+1+1+1+110=1+1+1+1+1+1+1+1+1+1 算法1(动态规划) $O(n^2)$分析题意，不难看出这是一道经典的完全背包模型题 完全背包模型为： 共有 i种物品，从中选出若干个装满体积为j的背包，所能达到的最大价值，每种物品的体积为vi, 价值为 wi 每种物品可以选0~无限个 完全背包的思考方式如下： 首先，要认识到每种方案的选择都是一类状态的结果，因此很容易想到需要使用动态规划 其次，按照动态规划的思考路线，首先思考动态规划的递推数组含义： 由于数组是包含了物品种类i，物品体积j两个因素，因此很容易想到需要使用二维数组来进行表示 f[i][j]表示，从 ...

题目描述题目链接 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 示例 :给定二叉树 12345 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。   注意：两结点之间的路径长度是以它们之间边的数目表示。 算法1(递归) $O(n)$根据题目描述，需要求出树的最大直径。不难分析出，树的最大直径为： 某个节点左子树和右子树最大深度的和，即找到某一个节点，分别向左子树深入和右子树深入，找到两边深入的最大值，并求其和的最大值 那么我们遍历整个树，即可找到这样一个最大的节点，即最大直径 那么递归基是什么呢？我们可以发现，当一个节点还有孩子节点时，那么它的深度是可以继续 +1 的，而当节点是叶子节点，就是其不存在左右子树时，他的深度不会增加 因此我们可以根据节点本身是否为空、节点是否有左右孩子，来判断节点的深度是否需要更新。 1234567891011121314151617181920212223242526 ...

树状数组与线段树都是非常强大的数据结构，在很多算法题中得到应用，因此需要进行掌握。 题目特征 单点更新 区间查询一般来讲，需要求上述问题的解时，常常会用到线段树或树状数组 需要注意的是，区间求和问题还可以用前缀和来进行求解，但是前缀和的局限之处在于其前缀和数组在初始化之后就固定了，每当更新其中某一个点的信息时，需要重复更新整个前缀和数组，有过多的冗余计算，因此遇到动态更新区间内的点时，无法使用前缀和来进行求解。 树状数组树状数组使用一维数组来表示，结构与操作十分简单，但是其原理证明十分复杂 树状数组在结构上将数据分为若干层： 数组下标从 1 开始，其二进制表示中有多少个 0 ，就视其为第几层 这种结构划分使得树状数组从原本普通的一维线性数组变成了一种具有树状层次的数据结构 而在此划分的基础上，所有第 0 层位置存储的是其原来的数据，所有大于 0 层的位置存放的数据是在此位置之前且尚未被统计过的数据之和 线段树操作： push up: 利用子结点的信息来更新当前节点的信息 build: 在一段区间上初始化线段树 modify: 单点修改操作 query: 区间查询操作

本周周赛未能按时参加，因此本篇仅作题目的思考记录以及分析，不涉及成绩总结。 第一题:处理字符串题目描述: 给定一个由大小写字母构成的字符串，请你对该字符串进行如下处理： - 将所有大写字母替换为相应的小写字母。 - 删除其中的所有元音字母。 - 在每个辅音字母前面插入一个 .。 字母 a，o，y，e，u，i 为元音字母，其余字母均为辅音字母。 注意，y 其实是半元音字母，在本题中规定其为元音字母。 本题是惯例的签到题，无难度，直接按照题目给定的要求来做即可，代码如下： 1234567891011121314151617181920212223242526272829#include <iostream>using namespace std;int main(){ string s; cin >> s; //输入 for(int i = 0; i < s.size(); i ++) // 转换为小写 s[i] = tolower(s[i]); string res = "& ...

计算机系统漫游全书第一章以一种高层次的角度展示了计算机系统的复杂与精巧。简单介绍了计算机的组成、信息的本质、程序的执行过程、计算机软件与硬件如何联系、处理器的工作内容等一些主要涉及计算机内部系统的内容。 计算机中的信息在计算机中，所有的信息都按照二进制(0 和 1)来存储, 称为位(bit), 所有的数字、字符、操作，都按照一定的位序列来排列，计算机能够根据位序列的不同识别不同的符号。所以，所有保存在计算机中的信息对于计算机来说都仅仅是一连串位序列而已，是上下文的顺序赋予了其独特的、人类赋予其的含义。 程序编译的过程 hello.c 是我们编写的代码，称为源程序或源代码 预处理阶段 预处理器(cpp)根据 hello.c 源代码，向原本的代码中加入头文件引入的地方，将文件存储为 hello.i 编译阶段 编译器(ccl) 将 hello.i 翻译为 hello.s，包含一个汇编程序 汇编阶段 汇编器(as) 将 hello.s 翻译为机器语言指令， 存储为 hello.o 链接阶段 在程序中使用的 C 标准库中的函数可以被连接器(ld) 合并至 hello.o 文件中，最终得到可执 ...

题目描述题目链接 请你设计一个数据结构，支持 添加新单词 和 查找字符串是否与任何先前添加的字符串匹配 。 实现词典类 WordDictionary ： WordDictionary() 初始化词典对象void addWord(word) 将 word 添加到数据结构中，之后可以对它进行匹配bool search(word) 如果数据结构中存在字符串与 word 匹配，则返回 true ；否则，返回  false 。word 中可能包含一些 ‘.’ ，每个 . 都可以表示任何一个字母。   示例： 123456789101112131415输入：["WordDictionary","addWord","addWord","addWord","search","search","search","search"][[],["bad"],["dad"],["mad"],[& ...

题目描述 题目链接 给定一个大小为 $n \le 10^6$ 的数组。 有一个大小为 $k$ 的滑动窗口，它从数组的最左边移动到最右边。 你只能在窗口中看到 $k$ 个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子： 该数组为 [1 3 -1 -3 5 3 6 7]，$k$ 为 $3$。 窗口位置 最小值 最大值 [1 3 -1] -3 5 3 6 7 -1 3 1 [3 -1 -3] 5 3 6 7 -3 3 1 3 [-1 -3 5] 3 6 7 -3 5 1 3 -1 [-3 5 3] 6 7 -3 5 1 3 -1 -3 [5 3 6] 7 3 6 1 3 -1 -3 5 [3 6 7] 3 7 你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。 输入格式 输入包含两行。 第一行包含两个整数 $n$ 和 $k$，分别代表数组长度和滑动窗口的长度。 第二行有 $n$ 个整数，代表数组的具体数值。 同行数据之间用空格隔开。 输出格式 输出包含两个 ...

题目描述题目链接 维护一个字符串集合，支持两种操作： I x 向集合中插入一个字符串 x；Q x 询问一个字符串在集合中出现了多少次。共有 N 个操作，输入的字符串总长度不超过 105，字符串仅包含小写英文字母。 输入格式第一行包含整数 N，表示操作数。 接下来 N 行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。 输出格式对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。 每个结果占一行。 数据范围$1 ≤ N ≤ 2 ∗ 104$ 输入样例： 1234565I abcQ abcQ abI abQ ab 输出样例： 123101 算法1(数组模拟Trie树) $O(n)$可以构造 Trie 前缀树来统计字符串集合中的字符 Trie树构造思路： 每个单词从头开始， 依次将单词的每个字符插入到 Trie 树中，在插入过程中，将每个单词的 a - z 映射到 0 - 25 可以使用 idx 来统计单词个数，第 0 个单词表示Trie 树的根，也表示单词的结尾 在每个单词的结尾，使用 cnt 数组来统计在此处结尾的单词个数 空间复杂度： ...

题目描述 题目链接 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 1234示例 1：输入：head = [1,2,3,4,5]输出：[5,4,3,2,1] 1234示例 2：输入：head = [1,2]输出：[2,1] 1234示例 3：输入：head = []输出：[] 算法1 (迭代) O(n)O(n)O(n) 从头结点开始，两个一组翻转，将后一个节点的next指针指向其前一个几点，随后迭代进行 当后节点为空时，说明整个链表已经反转结束 调整头结点的next指针为空即可 1234567891011121314151617181920212223242526272829/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nul ...

题目描述 题目链接 给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。 例如： 12345678A -> 1B -> 2C -> 3...Z -> 26AA -> 27AB -> 28 ... 样例 1234示例 1：输入：columnNumber = 1输出："A" 1234示例 2：输入：columnNumber = 28输出："AB" 1234示例 3：输入：columnNumber = 701输出："ZY" 1234示例 4：输入：columnNumber = 2147483647输出："FXSHRXW" 算法1 进制转换 O(logn)O(logn)O(logn) 思路： 数字若是 1-26，说明最后的字符有一位 数字若是 27( > 26) - 26 * 26, 说明数字有两位 … 因此，首先根据数字的大小算出总共有多少位 最后按照进制转换枚举每一位数字是多少即可 12345678910111213141516171 ...