水题

数组中出现次数超过一半的数字(剑指Offer-39) 题面 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 2输出: 2 限制 11 <= 数组长度 <= 50000 思路 摩尔投票法基于这样一个事实，当一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数。 ...

栈的压入、弹出序列(剑指Offer-31) 题面 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。 ...

包含min函数的栈(剑指Offer-30) 题面 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。 示例 1MinStack minStack = new MinStack(); 2minStack.push(-2); 3minStack.push(0); 4minStack.push(-3); 5minStack.min(); --> 返回 -3. 6minStack.pop(); 7minStack.top(); --> 返回 0. 8minStack.min(); --> 返回 -2. 限制 1各函数的调用总次数不超过 20000 次 思路 除了常规的栈，再维护一个单调栈，从栈顶到栈底递增 ...

顺时针打印矩阵(剑指Offer-29) 题面 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 示例 示例 1： 1输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 2输出：[1,2,3,6,9,8,7,4,5] 示例 2： ...

调整数组顺序使奇数位于偶数前面(剑指Offer-21) 题面 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。 示例 1输入：nums = [1,2,3,4] 2输出：[1,3,2,4] 3注：[3,1,2,4] 也是正确的答案之一。 限制 0 <= nums.length <= 50000 1 <= nums[i] <= 10000 思路 定义头指针 left，尾指针 right。left 一直往右移，直到它指向的值为偶数，right 一直往左移，直到它指向的值为奇数。交换 nums[left] 和 nums[right]。重复上述操作，直到 left==right . ...

打印从1到最大的n位数(剑指Offer-17) 题面 输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。 示例 示例 1： 1输入: n = 1 2输出: [1,2,3,4,5,6,7,8,9] 限制 用返回一个整数列表来代替打印 n 为正整数 思路 简简单单for循环。 ...

二进制中1的个数(剑指Offer-16) 题面 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。 示例 示例 1： 1输入：x = 2.00000, n = 10 2输出：1024.00000 示例 2： ...

青蛙跳台阶问题(剑指Offer-10.2) 题面 一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。 ...

斐波那契数列(剑指Offer-10.1) 题面 写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下： 1F(0) = 0, F(1) = 1 2F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。 ...

从尾到头打印链表(剑指Offer-06) 题面 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 1输入：head = [1,3,2] 2输出：[2,3,1] 限制 10 <= 链表长度 <= 10000 思路 简单遍历链表，然后reverse一下就好。 ...

替换空格(剑指Offer-05) 题面 请实现一个函数，把字符串 s 中的每个空格替换成"%20"。 示例 1输入：s = "We are happy." 2输出："We%20are%20happy." 限制 10 <= s 的长度 <= 10000 思路 resize一下，然后双指针逆序遍历。 ...

数组中重复的数字(剑指Offer-03) 题面 找出数组中重复的数字。 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 ...

Elevator(PATA-1008) 题面 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. For a given request list, you are to compute the total time spent to fulfill the requests on the list. The elevator is on the 0th floor at the beginning and does not have to return to the ground floor when the requests are fulfilled. ...

Product of Polynomials(PATA-1009) 题面 This time, you are supposed to find A×B where A and B are two polynomials. 输入 Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤NK<⋯<N2<N1≤1000. ...

Sign In and Sign Out(PATA-1006) 题面 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. 输入 Each input file contains one test case. Each case contains the records for one day. The case starts with a positive integer M, which is the total number of records, followed by M lines, each in the format: ...

Spell It Right(PATA-1005) 题面 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. 输入 Each input file contains one test case. Each case occupies one line which contains an N (≤10^100). 输出 For each test case, output in one line the digits of the sum in English words. There must be one space between two consecutive words, but no extra space at the end of a line. ...

A+B for Polynomials(PATA-1002) 题面 This time, you are supposed to find A+B where A and B are two polynomials. 输入 Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 … NK aNK where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤NK<⋯<N2<N1≤1000. ...

A+B Format(PATA-1001) 题面 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). 输入 Each input file contains one test case. Each case contains a pair of integers a and b where −10^6≤a,b≤10^6. The numbers are separated by a space. ...

解码PAT准考证 (PATB-1095) 题面 PAT 准考证号由 4 部分组成： 第 1 位是级别，即 T 代表顶级；A 代表甲级；B 代表乙级； 第 2~4 位是考场编号，范围从 101 到 999； 第 5~10 位是考试日期，格式为年、月、日顺次各占 2 位； 最后 11~13 位是考生编号，范围从 000 到 999。 现给定一系列考生的准考证号和他们的成绩，请你按照要求输出各种统计信息。 ...

谷歌的招聘 (PATB-1094) 题面 2004 年 7 月，谷歌在硅谷的 101 号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以 .com 结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10 位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。 ...

字符串A+B (PATB-1093) 题面 给定两个字符串 A 和 B，本题要求你输出 A+B，即两个字符串的并集。要求先输出 A，再输出 B，但重复的字符必须被剔除。 输入 输入在两行中分别给出 A 和 B，均为长度不超过 10^6的、由可见 ASCII 字符 (即码值为32~126)和空格组成的、由回车标识结束的非空字符串。 ...

最好吃的月饼 (PATB-1092) 题面 月饼是久负盛名的中国传统糕点之一，自唐朝以来，已经发展出几百品种。 若想评比出一种“最好吃”的月饼，那势必在吃货界引发一场腥风血雨…… 在这里我们用数字说话，给出全国各地各种月饼的销量，要求你从中找出销量冠军，认定为最好吃的月饼。 ...

N-自守数 (PATB-1091) 题面 如果某个数 K 的平方乘以 N 以后，结果的末尾几位数等于 K，那么就称这个数为“N-自守数”。例如 3×922=25392，而 25392 的末尾两位正好是 92，所以 92 是一个 3-自守数。 ...

危险品装箱 (PATB-1090) 题面 集装箱运输货物时，我们必须特别小心，不能把不相容的货物装在一只箱子里。比如氧化剂绝对不能跟易燃液体同箱，否则很容易造成爆炸。 本题给定一张不相容物品的清单，需要你检查每一张集装箱货品清单，判断它们是否能装在同一只箱子里。 ...

狼人杀-简单版 (PATB-1089) 题面 以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1 号玩家说：“2 号是狼人”，2 号玩家说：“3 号是好人”，3 号玩家说：“4 号是狼人”，4 号玩家说：“5 号是好人”，5 号玩家说：“4 号是好人”。已知这 5 名玩家中有 2 人扮演狼人角色，有 2 人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？ ...

三人行 (PATB-1088) 题面 子曰：“三人行，必有我师焉。择其善者而从之，其不善者而改之。” 本题给定甲、乙、丙三个人的能力值关系为：甲的能力值确定是 2 位正整数；把甲的能力值的 2 个数字调换位置就是乙的能力值；甲乙两人能力差是丙的能力值的 X 倍；乙的能力值是丙的 Y 倍。请你指出谁比你强应“从之”，谁比你弱应“改之”。 ...

有多少不同的值 (PATB-1087) 题面 当自然数 n 依次取 1、2、3、……、N 时，算式 ⌊n/2⌋+⌊n/3⌋+⌊n/5⌋ 有多少个不同的值？（注：⌊x⌋ 为取整函数，表示不超过 x 的最大自然数，即 x 的整数部分。） ...

就不告诉你 (PATB-1086) 题面 做作业的时候，邻座的小盆友问你：“五乘以七等于多少？”你应该不失礼貌地围笑着告诉他：“五十三。”本题就要求你，对任何一对给定的正整数，倒着输出它们的乘积。 ...

PAT单位排行 (PATB-1085) 题面 每次 PAT 考试结束后，考试中心都会发布一个考生单位排行榜。本题就请你实现这个功能。 输入 输入第一行给出一个正整数 N（≤105），即考生人数。随后 N 行，每行按下列格式给出一个考生的信息： ...

外观数列 (PATB-1084) 题面 外观数列是指具有以下特点的整数序列： 1d, d1, d111, d113, d11231, d112213111, ... 它从不等于 1 的数字 d 开始，序列的第 n+1 项是对第 n 项的描述。比如第 2 项表示第 1 项有 1 个 d，所以就是 d1；第 2 项是 1 个 d（对应 d1）和 1 个 1（对应 11），所以第 3 项就是 d111。又比如第 4 项是 d113，其描述就是 1 个 d，2 个 1，1 个 3，所以下一项就是 d11231。当然这个定义对 d = 1 也成立。本题要求你推算任意给定数字 d 的外观数列的第 N 项。 ...