题解

旋转数组的最小数字(剑指Offer-11) 题面 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组[3,4,5,1,2] 为[1,2,3,4,5] 的一个旋转，该数组的最小值为1。 ...

青蛙跳台阶问题(剑指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-09) 题面 用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 ) ...

重建二叉树(剑指Offer-07) 题面 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 示例 例如，给出 1前序遍历 preorder = [3,9,20,15,7] 2中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： ...

从尾到头打印链表(剑指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-04) 题面 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。 ...

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

Radix(PATA-1010) 题面 Given a pair of positive integers, for example, 6 and 110, can this equation 6 = 110 be true? The answer is yes, if 6 is a decimal number and 110 is a binary number. Now for any pair of positive integers N1 and N2, your task is to find the radix of one number while that of the other is given. 输入 Each input file contains one test case. Each case occupies a line which contains 4 positive integers: ...

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. ...

Maximum Subsequence Sum(PATA-1007) 题面 Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } 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. ...

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. ...

Counting Leaves(PATA-1004) 题面 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: 1ID K ID[1] ID[2] ... ID[K] where ID is a two-digit number representing a given non-leaf node, K is the number of its children, followed by a sequence of two-digit ID’s of its children. For the sake of simplicity, let us fix the root ID to be 01. ...

Emergency(PATA-1003) 题面 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. ...

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. ...

Theme Section(HDU-4763) 题面 It’s time for music! A lot of popular musicians are invited to join us in the music festival. Each of them will play one of their representative songs. To make the programs more interesting and challenging, the hosts are going to add some constraints to the rhythm of the songs, i.e., each song is required to have a ’theme section’. The theme section shall be played at the beginning, the middle, and the end of each song. More specifically, given a theme section E, the song will be in the format of ‘EAEBE’, where section A and section B could have arbitrary number of notes. Note that there are 26 types of notes, denoted by lower case letters ‘a’ - ‘z’. ...

Wow! Such Doge!(HDU-4847) 题面 Chen, Adrian (November 7, 2013). “Doge Is An Ac- tually Good Internet Meme. Wow.”. Gawker. Retrieved November 22, 2013. Doge is an Internet meme that became popular in 2013. The meme typically con- sists of a picture of a Shiba Inu dog ac- companied by multicolored text in Comic Sans MS font in the foreground. The text, representing a kind of internal monologue, is deliberately written in broken English, and usually contains the word “wow” and the phrases “such x”, “much x”, “many x”, “very x” and “so x”. Kabosu, the Shiba Inu featured in the original meme, was first pictured in a 2010 blog post by Atsuko Sato, a Japanese kindergarten teacher. Afterwards, varia- tions of the pictures using overlaid Comic Sans text were posted from a Tumblr blog, Shiba Confessions. However, the use of the intentionally misspelled “doge” dates back to June 2005, when it was mentioned in an episode of Homestar Runners puppet series. In August 2013, images of the meme were spammed on Reddit’s r/MURICA subreddit by 4chan’s random imageboard, /b/. A search of the term doge on Google Trends shows an explosion of popularity occurring in October 2013, and more so in the following month. By November 2013, the meme had become widespread on the Internet. Google later created a Doge Easter egg: when doge meme was entered into the YouTube search bar, all of the site’s text would be displayed in colorful Comic Sans, similar to the kind used by the meme. The meme was ranked #12 on MTV’s list of “50 Things Pop Culture Had Us Giving Thanks For” in 2013. Io9 compared the internal dialog of the Shiba Inu dogs to lolcat-speak. The image most commonly associated with the meme is of a female Shiba Inu named Kabosu, taken from a Japanese blog documenting the dog’s daily activities. The spelling of doge has several variants, leading to debate on its actual pronunciation. On December 13, Doge was named the “top meme” of 2013 by Know Your Meme. In December 2013, the Dogecoin was introduced as a new cryptocurrency, making it the first cryptocurrency to be based on an Internet meme; the viral phenomenon, along with usage of the Comic Sans MS typeface, gave it “the Internet density of a large star” according to Medium writer Quinn Norton. In late December 2013, members of the U.S. Congress produced material in the meme’s style. Huffington Post commented that Doge was “killed” because of the Congress members’ usage of the meme. By early 2014, Doge’s popularity was sustained by internet communities on social media, accompanied by the rapid growth and acceptance of Dogecoin. In April 2014, Doge experienced a second major media resurgence due to revelations of the Dogecoin community’s intent to sponsor Josh Wise in NASCAR and place a picture of the Shiba Inu on his vehicle. ...

最长回文(HDU-3068) 题面 给出一个只由小写英文字符a,b,c…y,z组成的字符串S,求S中最长回文串的长度. 回文就是正反读都是一样的字符串,如aba, abba等 ...

Girls’ research(HDU-3294) 题面 One day, sailormoon girls are so delighted that they intend to research about palindromic strings. Operation contains two steps: First step: girls will write a long string (only contains lower case) on the paper. For example, “abcde”, but ‘a’ inside is not the real ‘a’, that means if we define the ‘b’ is the real ‘a’, then we can infer that ‘c’ is the real ‘b’, ’d’ is the real ‘c’ ……, ‘a’ is the real ‘z’. According to this, string “abcde” changes to “bcdef”. Second step: girls will find out the longest palindromic string in the given string, the length of palindromic string must be equal or more than 2. ...

吉哥系列故事-完美队形II(HDU-4513) 题面 吉哥又想出了一个新的完美队形游戏！ 假设有n个人按顺序站在他的面前，他们的身高分别是h[1], h[2] … h[n]，吉哥希望从中挑出一些人，让这些人形成一个新的队形，新的队形若满足以下三点要求，则就是新的完美队形： ...

Finding Palindromes(POJ-3376) 题面 A word is called a palindrome if we read from right to left is as same as we read from left to right. For example, “dad”, “eye” and “racecar” are all palindromes, but “odd”, “see” and “orange” are not palindromes. Given n strings, you can generate n × n pairs of them and concatenate the pairs into single words. The task is to count how many of the so generated words are palindromes. ...

Palindrome(POJ-3974) 题面 Andy the smart computer science student was attending an algorithms class when the professor asked the students a simple question, “Can you propose an efficient algorithm to find the length of the largest palindrome in a string?” A string is said to be a palindrome if it reads the same both forwards and backwards, for example “madam” is a palindrome while “acm” is not. The students recognized that this is a classical problem but couldn’t come up with a solution better than iterating over all substrings and checking whether they are palindrome or not, obviously this algorithm is not efficient at all, after a while Andy raised his hand and said “Okay, I’ve a better algorithm” and before he starts to explain his idea he stopped for a moment and then said “Well, I’ve an even better algorithm!”. ...

Best Reward(HDU-3613) 题面 After an uphill battle, General Li won a great victory. Now the head of state decide to reward him with honor and treasures for his great exploit. One of these treasures is a necklace made up of 26 different kinds of gemstones, and the length of the necklace is n. (That is to say: n gemstones are stringed together to constitute this necklace, and each of these gemstones belongs to only one of the 26 kinds.) ...

Teacher YYF(POJ-3746) 题面 As we all know, grammar is very important when learning English. Now, YYF become a teacher of a primary school. The students are good at memory so they can tell the meaning and the function (noun, verb …) of the words in the textbook. But, they cannot use these words properly. In YYF’s mind, writing sentences is a good way to learn grammar. So he tells the student to write 20 sentences a day, using the word learned in the class. As YYF has a lot of student, he will receive many sentences from his student. What a horrible work to check all the sentences. You are one of YYF’s friends, so he asks you for help. You task is to write a program to check the sentences. ...

Period II(FZU-1901) 题面 For each prefix with length P of a given string S,if S[i]=S[i+P] for i in [0..SIZE(S)-p-1], then the prefix is a “period” of S. We want to all the periodic prefixs. 输入 Input contains multiple cases. The first line contains an integer T representing the number of cases. Then following T cases. Each test case contains a string S (1 <= SIZE(S) <= 1000000),represents the title.S consists of lowercase ,uppercase letter. ...

Game of CS(LightOJ-1355) 题面 Jolly and Emily are two bees studying in Computer Science. Unlike other bees they are fond of playing two-player games. They used to play Tic-tac-toe, Chess etc. But now since they are in CS they invented a new game that definitely requires some knowledge of computer science. Initially they draw a random rooted tree (a connected graph with no cycles) in a paper which consists of n nodes, where the nodes are numbered from 0 to n-1 and 0 is the root, and the edges are weighted. Initially all the edges are unmarked. And an edge weigh w, has w identical units. ...