基础

简介 快速排序算法是对冒泡排序算法的一种改进。平均时间复杂度$O(nlogn)$，最坏时间复杂度$O(n^2)$。 快速排序的基本思想：每趟排序选择一个基准值pivot，使得小于pivot的元素和大于pivot的元素分隔于pivot两侧，即每一趟确定了一个元素的位置。然后对基准值两侧的区间进行递归，以达到整个序列有序。 ...

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

字符串的排列(剑指Offer-38) 题面 输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。 示例 1输入：s = "abc" 2输出：["abc","acb","bac","bca","cab","cba"] 限制 11 <= s 的长度 <= 8 思路 dfs遍历回溯。 ...

栈的压入、弹出序列(剑指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-28) 题面 请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。 例如，二叉树 [1,2,2,3,4,4,3] 是对称的。 1 1 2 / \ 3 2 2 4 / \ / \ 5 3 4 4 3 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: ...

二叉树的镜像(剑指Offer-27) 题面 请完成一个函数，输入一个二叉树，该函数输出它的镜像。 例如输入： 1 4 2 / \ 3 2 7 4 / \ / \ 51 3 6 9 镜像输出： 1 4 2 / \ 3 7 2 4 / \ / \ 59 6 3 1 示例 1输入：root = [4,2,7,1,3,6,9] 2输出：[4,7,2,9,6,3,1] 限制 10 <= 节点个数 <= 1000 思路 递归。 ...

树的子结构(剑指Offer-26) 题面 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A: ...

调整数组顺序使奇数位于偶数前面(剑指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 . ...

正则表达式匹配(剑指Offer-19) 题面 请实现一个函数用来匹配包含'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。 ...

打印从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： ...

二进制中1的个数(剑指Offer-15) 题面 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。 ...

机器人的运动范围(剑指Offer-13) 题面 地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？ ...

矩阵中的路径(剑指Offer-12) 题面 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格，那么该路径不能再次进入该格子。例如，在下面的3×4的矩阵中包含一条字符串“bfce”的路径（路径中的字母用加粗标出）。 ...

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

数组中重复的数字(剑指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. ...

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

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