520. 检测大写字母 我们定义，在以下情况时，单词的大写用法是正确的： 全部字母都是大写，比如 "USA" 。 单词中所有字母都不是大写，比如 "leetcode" 。 如果单词不只含有一个字母，只有首字母大写， 比如 "Google" 。 给你一个字符串 word 。如果大写用法正确，返回 true ；否则，返回 false 。 示例 1： 输入： word = "USA" 输出： true 示例 2： 输入： word = "FlaG" 输出： false 思路 ac表示当前状态，state表示输入状态 由第一个字母大小写决定ac初状态 word[0]大写：ac初状态0 word[0]小写：ac初状态2 当ac初状态0时（即首字母大写）：下一个字母可以大写，也可以小写 当ac初状态2时（即首字母小写）：下一个字母只能小写 当ac状态为1时（即前n个字母均大写）：下一个字母只能大写 当ac状态为2时（即当前字母小写）：下一个字母只能小写 以上状态转移失败均跳转到ac=4，具体流程如图所示。 python实现： class Solution: def detectCapita....

原地标记/交换 一、原地标记 题干：题目限制空间复杂度 思路： step1：想出空间o(n)map方法 step2：以原数组下标做o(n)map方法的key，想办法在数据上做手脚 step3：再遍历时，检查数据是否被做了手脚 448. 找到所有数组中消失的数字 class Solution { public: vector<int> findDisappearedNumbers(vector<int>& nums) { vector<int> res; int size=nums.size(); for(auto num:nums){ int temp = (num - 1) % size; nums[temp] += size; } for(int i=0;i<size;i++){ if(nums[i]<=size){ res.push_back(i+1); } } return res; } }; 442. 数组中重复的数据 class Solution {....

189. 轮转数组 给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。 示例 1: 输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4] 示例 2: 输入： nums = [-1,-100,3,99], k = 2 输出： [3,99,-1,-100] 解释: 向右轮转 1 步: [99,-1,-100,3] 向右轮转 2 步: [3,99,-1,-100] 以矩阵的观点 \begin{matrix} C=[A,B] \\ C^T=[B^T,A^T]\\ 目标：[B,A]=[(B^T)^T,(A^T)^T] \end{matrix} 此题用R表示翻转 \begin{matrix} C=[A,B] \ \ \ C^R=[B^R,A^R]\\ 目标：[B,A]=[(B^R)^R,(A^R)^R] \end{matrix} 操作 结果 ....

前缀和 特征 求「连续段」区域和 分类 一维前缀和 303 二维前缀和 304 通用公式 ans = sum[j] - sum[i - 1]。 例子 303. 区域和检索 - 数组不可变 给定一个整数数组 nums，处理以下类型的多个查询: 计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right 实现 NumArray 类： NumArray(int[] nums) 使用数组 nums 初始化对象 int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的 总和 ，包含 left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] ) 示例 1： 输入： ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] 输出：....

数组的遍历 485、495、414、628 414. 第三大的数 给你一个非空数组，返回此数组中 第三大的数 。如果不存在，则返回数组中最大的数。 示例 1： 输入：[3, 2, 1] 输出： 1 解释： 第三大的数是 1 。 示例 2： 输入：[1, 2] 输出： 2 解释： 第三大的数不存在, 所以返回最大的数 2 。 示例 3： 输入：[2, 2, 3, 1] 输出： 1 解释： 注意，要求返回第三大的数，是指在所有不同数字中排第三大的数。 此例中存在两个值为 2 的数，它们都排第二。在所有不同数字中排第三大的数为 1 。 提示： 1 <= nums.length <= 104 -231 <= nums[i] <= 231 - 1 进阶： 你能设计一个时间复杂度 O(n) 的解决方案吗？ 思路 方法一：堆排序 略 方法二：set容器排序+去重 class Solution { public: int thirdMax(vector<int>& nums) { set<int> s;//排序队列 for(in....

1009 Product of Polynomials This time, you are supposed to find A×B where A and B are two polynomials. 这次，你需要找到两个多项式 A 和 B 的乘积。 Input Specification: Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K\quad N_1\quad a_{N1}\quad N_2\quad a_{N2}\quad...\quad N_K\quad a_{NK} where K is the number of nonzero terms in the polynomial, N_i and a_{Ni} (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that $....

1008 Elevator The highest building in our city has only one elevator. A request list is made up with N positive numbers. The numbers denote at which floors the elevator will stop, in specified order. It costs 6 seconds to move the elevator up one floor, and 4 seconds to move down one floor. The elevator will stay for 5 seconds at each stop. 我们城市最高的建筑只有一台电梯。有一个请求列表由 N 个正整数组成，这些数字指定电梯停在哪些楼层，按指定的顺序。电梯每上升一层需要 6 秒钟，每下降一层需要 4 秒钟。电梯每停留一个楼层需要 5 秒钟。 For a given request list, you are to compute the total ....

1007 Maximum Subsequence Sum Given a sequence of K integers { N1, N2, ..., N**K }. A continuous subsequence is defined to be { N**i, N**i+1, ..., N**j } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20. Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum ....

1006 Sign In and Sign Out At the beginning of every day, the first person who signs in the computer room will unlock the door, and the last one who signs out will lock the door. Given the records of signing in's and out's, you are supposed to find the ones who have unlocked and locked the door on that day. 每天开始时，第一个在电脑房签到的人将解锁门，最后一个签退的人将锁门。给定签到和签退的记录，你需要找出当天解锁和锁门的人。 Input Specification: Each input file contains one test case. Each case contains the records for one day. The case starts with a pos....

1005 Spell It Right Given a non-negative integer N, your task is to compute the sum of all the digits of N, and output every digit of the sum in English. 给定一个非负整数N，你的任务是计算N的所有数字的和，并输出总和的每个数字的英文表示。 Input Specification: Each input file contains one test case. Each case occupies one line which contains an N (≤10^{100}). 每个输入文件包含一个测试用例。每个测试用例占据一行，其中包含一个N(≤10^{100})。 Output Specification: For each test case, output in one line the digits of the sum in English words. There must be one space between tw....

1004 Counting Leaves A family hierarchy is usually presented by a pedigree tree. Your job is to count those family members who have no child. 一个家庭的层级结构通常用家谱树来表示。你的任务是统计那些没有孩子的家庭成员。 输入格式： Each input file contains one test case. Each case starts with a line containing 0<N<100, the number of nodes in a tree, and M (<N), the number of non-leaf nodes. Then M lines follow, each in the format: ID K ID[1] ID[2] ... ID[K] where ID is a two-digit number representing a given non-leaf node, K is t....

C++快速回顾重点 本文是《算法笔记》胡凡、曾磊著 的精炼总结。用于博主本人的快速复习，具有极强主观性，请酌情学习。 一、C/C++语言基础 变量 int占4字节，**范围大概$10^9$**内。 long long占8字节，$10^9$外用long long。 float占4字节，1位符号位、8位指数位、23位尾数位，有效精度6~7位。 double占8字节，1位符号位、11位指数位、52位尾数位，有效精度15~16位。尽量用double。 char小写字母比大写字母ascll码大32。 char单个字符常量必须用单引号。 char[]字符串常量用双引号。 bool在整型转布尔时，非零为true，零为false 常量 宏定义末尾不加分号 #define 标识符 常量 推荐使用const定义常量 const 数据类型 变量名 = 常量 宏定义陷阱 #include<iostream> using namespace std; #define CAL(x) (x * 2 + 1) int main(){ int a = 1; printf("%d\n"....

迪杰斯特拉算法 万物基于传销——硬核的半佛仙人 题目是PAT的题目，Advanced Level 1003 Emergency 代码是github的代码，原仓库地址https://github.com/liuchuo/PAT 1003 Emergency 紧急事件 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the....

1003 Emergency 紧急事件 As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible. 作为一名城市的紧急救援队队长，你....

1002 A+B for Polynomials This time, you are supposed to find A+B where A and B are two polynomials. 这次，你需要找到两个多项式A和B的和。 Input Specification: Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N_1 a_{N1} N_2 a_{N2} ... N_{K} a_{NK} where K is the number of nonzero terms in the polynomial, N_{i} and a_{Ki} (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10 ， 0≤N_{K}<⋯<N_{2}<N_{1}....

1001 A+B Format Calculate a+b and output the sum in standard format -- that is, the digits must be separated into groups of three by commas (unless there are less than four digits). 计算a+b并以标准格式输出——也就是说，除非数字少于四位，否则数字必须用逗号分隔成三组。 Input Specification: Each input file contains one test case. Each case contains a pair of integers a and b where −106≤a,b≤106. The numbers are separated by a space. 每个输入文件包含一个测试用例。每个用例包含一对整数a和b，其中−106≤a，b≤106。数字由空格分隔。 Output Specification: For each test case, you should ou....