【模板】前缀和 难度：2星 前缀和模板题。我们定义 sum[i]sum[i]sum[i] 为前 iii 个数之和，可以通过预处理 O(n)O(n)O(n) 求出所有的 sum[i]sum[i]sum[i]，那么查询区间 [l,r][l,r][l,r] 中所有数之和只需要输出 sum[r]−sum[l−1]sum[r]-sum[l-1]sum[r]−sum[l−1] 即可，每次查询的复杂度为 O(1)O(1)O(1) 。 #include<bits/stdc++.h> using namespace std; int a[101010]; long long sum[101010];...

nico和niconiconi 难度：3星 计 dp[i]dp[i]dp[i] 代表前 iii 个字符的计数最大值。 那么可得转移方程： 若取当前子串"nico"： if(substring(i−3,i)==nico)thenif(substring(i-3,i)==nico)thenif(substring(i−3,i)==nico)then dp[i]=max(dp[i],dp[i−4]+a)dp[i]=max(dp[i],dp[i-4]+a)dp[i]=max(dp[i],dp[i−4]+a) 若取当前子串"niconi"： if(substring(i−5,i)==niconi)the...

不相邻取数 难度：2星 设 dp[i][0]dp[i][0]dp[i][0] 为不取第 iii 个数的情况下，前 iii 个数不相邻取数的最大值；dp[i][1]dp[i][1]dp[i][1] 为取第 iii 个数的情况下，前 iii 个数不相邻取数的最大值。那么有转移方程： 不取当前数，那么前一个数取不取都行： dp[i][0]=max(dp[i−1][1],dp[i−1][0])dp[i][0]=max(dp[i-1][1],dp[i-1][0])dp[i][0]=max(dp[i−1][1],dp[i−1][0]) 若取当前数，那么前一个数一定不能取： dp[i][1]=dp[i−1]...

子数组最大连续和 难度：2星 解法1 动态规划 定义 dp[i]dp[i]dp[i] 为前 iii 个数中，以第 iii 个数结尾的子数组最大连续和。 于是有转移方程： dp[i]=max(dp[i−1]+a[i],a[i])dp[i]=max(dp[i-1]+a[i],a[i])dp[i]=max(dp[i−1]+a[i],a[i]) 其中，前面部分代表选择前面的区间的最大值，后面部分代表直接选择a[i]。 最终答案是所有的 dp[i]dp[i]dp[i] 的最大值。  #include<bits/stdc++.h> using namespace std; long long ...

可以先树形dp预处理出每个节点子树的节点个数。那么当且仅当每个节点满足以下条件有解：     若当前节点x与父节点颜色相同，那么它的子节点子树大小必须为偶数，子节点颜色和x不同。     若当前节点x与父节点颜色不同，那么它的子节点子树大小一定有且仅有一个奇数、其他的均为偶数。x的“奇数大小子树”的那个子节点颜色和x相同，其他都和x不同。    #include<bits/stdc++.h> using namespace std; vector<int>g[200020]; int dp[2 00020]; int su(int x,int pr){ int i,su...

预备知识     十进制转十六进制规则 十六进制每一位上可以是从小到大为 0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F 一共16个数，即逢 16 进1，其中用 A，B，C，D，E，F（字母使用大写）这六个字母来分别表示10，11，12，13，14，15。 十进制转化为十六进制计算方式，简单说就是整数除以 16 取余，直到商为 0 为止，然后从最后一个余数读到第一个。由于每次除后得到的余数可能会大于 9，而十六进制采用 A、B、C、D、E、F 表示10，11，12，13，14，15，所以要建立这之间的关系，可以采用查表法。   C++ string 类添加字符的函数 pushb...

预备知识    字符串相关函数       int atoi(const char * nptr); 将整数字符串转换成 int 类型的整数       char  strtok(char  str, const char * delim); 将字符串按照 delim 中的字符进行分割。当 strtok() 在参数 str 的字符串中发现参数 delim 分割字符时，则会将该字符改为 \0 字符，当连续出现多个时只替换第一个为 \0。在第一次调用时，strtok() 必须给与参数 str 字符串，往后调用则将参数 str 设置为 空指针，每次调用成功则返回指向被分割出片段的指针。       ...

预备知识    set 容器   使用 set 容器存储的各个键值对，要求键 key 和值 value 必须相等。基于 set 容器的这种特性，当使用 set 容器存储键值对时，只需要为其提供各键值对中的 value 值（也就是 key 的值）即可。map、multimap 容器都会自行根据键的大小对存储的键值对进行排序，set 容器也会如此，只不过 set 容器中各键值对的键 key 和值 value 是相等的，根据 key 排序，也就等价为根据 value 排序。 本题中可能需要使用的 set 方法：      成员方法     功能       begin()     返回指向容器中第一...

预备知识    map 容器   map 容器存储的都是 pair 对象，也就是用 pair 类模板创建的键值对。其中，各个键值对的键和值可以是任意数据类型，包括 C++ 基本数据类型（int、double 等）、使用结构体或类自定义的类型。在使用 map 容器存储多个键值对时，该容器会自动根据各键值对的键的大小，按照既定的规则进行排序。默认情况下，map 容器选用 std::less<T> 排序规则（其中 T 表示键的数据类型），其会根据键的大小对所有键值对做升序排序。 使用 map 容器存储的各个键值对，键的值既不能重复也不能被修改。换句话说，map 容器中存储的各个键值对不仅...

预备知识    运算符重载的语法 ：        定义重载的运算符就像定义函数，只是该函数的名字是 operator@，这里的@代表了被重载的运算符。       重载的运算符像任何其他函数一样也是一个函数，当编译器遇到适当的模式时，就会调用这个函数。   小时和分钟转换：    1 小时 = 60 分钟       给定一个分钟数 mins，如果超过 60 分钟，则需要转换成小时和分钟。具体计算方式如下：      mins / 60 得到小时数   mins % 60 得到分钟数    思路、步骤    设计时间类（Timer）...

点和圆的关系 [2190767]   预备知识    两个坐标点 p1(x1，y1)、p2(x2，y2) 直接的距离为：           判断点和圆的关系，只需要计算该点和圆心的距离 d，和圆的半径 r 进行比较：    如果 d = r，则点在圆上       如果 d < r，则点在圆内       如果 d > r，则点在圆外     思路、步骤    设计点类（Pointer）    成员变量：x轴坐标（int x），y轴坐标（int y）       成员方法：公共的访问方法 void setX(int x)、int getX()、void setY(int y)、i...

class Solution { public: ListNode* ReverseList(ListNode* pHead) { if (!pHead) return nullptr; vector<ListNode*> v; while (pHead) { v.push_back(pHead); pHead = pHead->next; } reverse(v.begin(), v.end()); // 反转vector，也可以逆向遍历 ListNode *head = v[0]; ListNode *cur = head; for (int i=1; i<v.si...

通过instanceof运算符判断obj是否属于右边类所创建对象，instanceof是Java的保留关键字。它的作用是测试它左边的对象是否是它右边的类的实例，返回值为boolean类型。若返回结果为true，若是则调用调用Object的getClass()方法获得Class对象，之后用getSimpleName()方法来获取这个类的名称（此环境下使用getName()方法也可以获得正确结果，但在常规情况下，使用getName()会返回包括包名在内的实体名称，这里需要注意），本题的代码参考写法如下： if (obj instanceof Sub1) { Sub1 sub1 = (Sub1) o...

按照题中要求，应该补充该类的getInstance()方法，由于Singleton类是单例的，每次调用该类的getInstance()方法都将得到相同的Singleton类型实例，所以getInstance()方法的返回类型应为Singleton。预设代码中，getInstance()方法为类直接调用，所以该方法应为静态方法，那么此处得知getInstance()方法的应为： public static Singleton getInstance() { }  在该方法中进行判断，若instance == null即不存在实例时则新建Singleton，否则直接返回已有的instance。将此...