题目汇总
11.旋转数组的最小数字（简单），本题考查查找和排序
12.矩阵中的路径—回溯问题（中等），本题考查回溯法
13.机器人的运动范围（中等），本题考查回溯法
14.剪绳子（中等），本题考查动态规划和贪婪算法
15.二进制中1的个数（简单），本题考查位运算
16.数值的整数次方（中等），本题考查代码的完整性
17.打印从1到最大的n位数（困难）****
18.删除链表的节点（简单）
19.正则表达式匹配（困难），本题考查字符串和正则表达式
20.表示数值的字符串（中等），本题考查字符串
11.旋转数组的最小数字（简单），本题考查查找和排序
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
思路一：暴力法查找
从头到尾遍历数组一次，找出最小的元素，时间复杂度：O(n)
import java.util.ArrayList;
import java.util.*;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int len = array.length;
if(len==0)
return 0;
for(int i=0;i<len-1;i++){
if(array[i]>array[i+1])
return array[i+1];
}
return array[0];
}
}
思路二：排序
利用Arrays工具类里的排序函数，排序后的第一个元素一定是最小元素，时间复杂度：O(nlogn)但是没有利用输入的旋转数组的特性
import java.util.ArrayList;
import java.util.*;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int len = array.length;
if(len==0)
return 0;
Arrays.sort(array);
return array[0];
}
}
思路三：二分查找法
用两个指针分别指向数组的第一个元素和最后一个元素，找到数组中间的元素
参考题解：https://blog.nowcoder.net/n/dcb0f2e6ffd44e1895b7a5297e362778?f=comment
二分查找变种，没有具体的值用来比较。那么用中间值和高低位进行比较，看处于递增还是递减序列，进行操作缩小范围。
处于递增：low上移
处于递减：high下移（如果是high-1，则可能会错过最小值，因为找的就是最小值）
其余情况：low++缩小范围
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int start=0;
int end=array.length-1;
int mid=start;
while(start < end){
// 子数组是非递减的数组，10111
if (array[start] < array[end])
return array[start];
mid = start + (end - start) / 2;
if(array[mid] > array[start])
start = mid + 1;
else if(array[mid] < array[end])
end = mid;
else start++;
}
return array[start];
}
}
12.矩阵中的路径—回溯问题（中等），本题考查回溯法
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
思路：回溯法
回溯法从解决问题每一步的所有可能选项里系统地选择出一个可行的解决方案。回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了其中一个选项时，就进入下一步，然后又面临新的选项，就这样重复选择，直至达到最终的状态。通常回溯法适合用递归实现算法。当我们到达某一个节点时，尝试所有可能的选项并在满足条件的前提下递归地抵达下一个节点。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
if(matrix == null || rows < 1 || cols < 1 || str == null)
return false;
//和字符矩阵大小一样的布尔值矩阵标识路径是否已经进入每个格子
boolean[] visited = new boolean[matrix.length];
int pathLength = 0;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(hasPathCore(matrix, rows, cols, i, j, str, pathLength, visited)){
return true;
}
}
}
return false;
}
public boolean hasPathCore(char[] matrix, int rows, int cols,int i, int j, char[] str, int pathLength, boolean[] visited){
if(str.length==pathLength)
return true;
int index = i*cols+j;
boolean hasPath = false;
if(i >= 0 && i<rows && j>=0 && j<cols && matrix[index]==str[pathLength]&&!visited[index]){
pathLength++;
visited[index]=true;
//访问上下左右，回溯
hasPath = hasPathCore(matrix, rows, cols, i, j-1, str, pathLength, visited)
||hasPathCore(matrix, rows, cols, i-1, j, str, pathLength, visited)
||hasPathCore(matrix, rows, cols, i+1, j, str, pathLength, visited)
||hasPathCore(matrix, rows, cols, i, j+1, str, pathLength, visited);
if(!hasPath){
pathLength--;
visited[index] = false;
}
}
return hasPath;
}
}
13.机器人的运动范围（中等），本题考查回溯法
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
思路：回溯法
这个方格可以看作是一个m×n的矩阵，在这个矩阵中，除边界上的格子之外，其他格子都有四个相邻的格子。
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
if(threshold<0 || rows<=0 || cols<=0)
return 0;
//标记数组，判断节点是否被访问,初始值都为false
boolean[][] visited = new boolean[rows][cols];
return movingCountCore(threshold, rows, cols,0,0,visited);
}
public int movingCountCore(int threshold, int rows, int cols,int i,int j,boolean visited[][]){
int count = 0;
if(i>=0 &&i<rows && j>=0 && j<cols && getDigitSum(i)+getDigitSum(j)<=threshold && !visited[i][j])
{
visited[i][j]=true;//设置当前节点被访问
count = 1 + movingCountCore(threshold, rows, cols,i-1,j,visited)
+ movingCountCore(threshold, rows, cols,i,j-1,visited)
+ movingCountCore(threshold, rows, cols,i+1,j,visited)
+ movingCountCore(threshold, rows, cols,i,j+1,visited);
}
return count;
}
//得到一个数字的数位之和
public int getDigitSum(int number){
int sum = 0;
while(number > 0){
sum += number % 10;
number /= 10;
}
return sum;
}
}
14.剪绳子（中等），本题考查动态规划和贪婪算法
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少?
应用动态规划求解问题的特点
1.求一个问题的最优解
2.整体问题的最优解是依赖各个子问题的最优解
3.大问题分解为若干小问题，小问题之间还有相互重叠的更小的子问题
4.从上往下分析问题，从下往上求解问题。子问题在分解大问题的过程中重复出现，为了避免重复求解子问题，利用从下往上的顺序先计算小问题的最优解并存储下来，再以此为基础求取大问题的最优解。？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
思路一：动态规划
public class Solution {
public int cutRope(int target) {
if(target < 2)
return 0;
if(target == 2)
return 1;
if(target == 3)
return 2;
int[] products = new int[target+1];
products[0] = 0;
products[1] = 1;
products[2] = 2;
products[3] = 3;
int max = 0;
for(int i=4;i<=target;i++){
max = 0;
for(int j=1;j<=i/2;j++){
int product = products[j]*products[i-j];
if(max<product)
max = product;
products[i] = max;
}
}
max = products[target];
return max;
}
}
上述代码中，子问题的最优解存储在数组products中数组中，第i个元素表示把长度为i的绳子剪成若干段之后各段长度乘积的最大值，即f(i)。代码中第一个for循环变量i是顺序递增的，这意味着计算顺序是自下而上的。因此在求f(i)之前，对于每一个j(0<i<j)而言，f(j)都已经求解出来了，并且结果存储在products[j]里。为了求解f(i)，我们需要求出所有可能的f(j)×f(i-j)并比较得出它们的最大值。这就是代码中第二个for循环的功能。
思路二：贪婪算法
当target>=5时，尽可能多地剪长度为3的绳子；当剩下的绳子长度为4时，把绳子剪成两端长度为2的绳子。
import java.lang.Math;
public class Solution {
public int cutRope(int target) {
if(target < 2)
return 0;
if(target == 2)
return 1;
if(target == 3)
return 2;
//尽可能多剪长度为3的绳子
int timesOf3 = target/3;
//绳子最后剩下的长度为4的时候，不能再剪去长度为3的绳子
//把绳子剪成长度为2的两段，因为2×2>3×1
if(target - timesOf3*3==1)
timesOf3-=1;
int timesOf2 = (target - timesOf3*3)/2;
return (int)(Math.pow(3,timesOf3))*(int)(Math.pow(2,timesOf2));
}
}
15.二进制中1的个数（简单），本题考查位运算
位运算是把数字用二进制表示之后，对每一位上0或者1的运算。位运算总共有5种运算：与、或、异或、左移和右移。
与、或、异或的运算规律.png
左移运算符m<<n表示把m左移n位。在左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0
例如：
00001010<<2=00101000
10001010<<3=01010000
右移运算符m>>n表示把m右移n位。在右移n位的时候，左右边的n位将被丢弃，但右移时处理最左边位的情形稍微复杂。
如果一个数字原先是正数，则右移之后在最左边补n个0；
如果一个数字原先是负数，则右移之后在最左边补n个1；
例如：
00001010>>2=00000010
10001010>>3=11110001
题目描述
输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。例如9的二进制是1001，输入9，函数输出2。
思路：
把一个整数减去1，都是把最右边的1变成0。如果它的右边还有0，则所有的0都变成1，而它左边的所有位都保持不变。把一个整数和它减去1的结果做位与运算，相当于把它最右边的1变成0。例如1100减去1结果是1011，1100和1011做位与运算得到的结果是1000。把1100最右边的1变成了0，结果刚好是1000。
总结起来就是：把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0。那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。（自己真是想不到啊哭了对自己充满嫌弃）
参考网址：https://blog.nowcoder.net/n/09d025ecf6b5486cb3ba3360dea03ada?f=comment
public class Solution {
public int NumberOf1(int n) {
int count=0;
while(n!=0){
count++;
n=n&(n-1);
}
return count;
}
}
16.数值的整数次方（中等），本题考查代码的完整性
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0
思路一：简单的数学理解
很自然的写出了下面的代码
public class Solution {
public double Power(double base, int exponent) {
double result = 1.0;
for(int i=1;i<=exponent;i++){
result*=base;
}
return result;
}
}
但是提交的程序没有通过所有的测试用例，case通过率为40.00%，只考虑了指数是正数的情况，没有考虑到指数为负数和0的情况。
接下来考虑指数为负数和0的情况：
1.当指数为负数时，可以对指数取绝对值，算出次方的结果后再取倒数。如果此时底数是0，就会对0求取倒数，导致程序出错。
2.当指数为0时，如果底数不是0，结果为1。
public class Solution {
public double Power(double base, int exponent) {
if(base==0.0)
return 0.0;
double result=1.0;
if(exponent>0){
for(int i=1;i<=exponent;i++){
result*=base;
}
}
if(exponent<0){
int e = -exponent;
for(int i=1;i<=e;i++){
result*=base;
}
result=1.0/result;
}
if(exponent==0){
result = 1.0;
}
return result;
}
简洁的写法：
public class Solution {
public double Power(double base, int exponent) {
if(base==0.0)
return 0.0;
double result=1.0d;
int e = exponent > 0 ? exponent : -exponent;
for(int i=0;i<e;i++){
result*=base;
}
return exponent>0? result : 1/result;
}
}
思路二：递归
书上既全面又高效的解法
搬运网址https://blog.nowcoder.net/n/b026f9aab5934904960bfaa65b0bfb83?f=comment
// 递归写法
public class Solution {
public static double Power(double base, int exp) {
boolean flag = exp < 0;
if (flag) {
exp = -exp;
}
double result = getPower(base, exp);
return flag ? 1 / result : result;
}
public static double getPower(double base, int exp) {
if (exp == 0) {
return 1;
}
if (exp == 1) {
return base;
}
double ans = getPower(base, exp >> 1);
ans *= ans;
if ((exp & 1) == 1) {
ans *= base;
}
return ans;
}
}
注意：
用右移运算符代替了除以2，用位与运算符代替了求余运算符%来判断一个数是奇数还是偶数。位运算的效率比乘除法及求余运算的效率要高很多。
17.打印从1到最大的n位数（困难）****
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
思路：
当输入的n很大的时候，用整形和长整型都会溢出，需要考虑大数问题。
用字符串表示数字，字符串里每个字符都是‘0’到‘9’之间的某一个字符，用来表示数字中的一位。因为最大的是n位的，因此我们需要一个长度为n+1的字符串（字符串中最后一个是结束符号‘\0’。当实际数字不够n位的时候，在字符串的前半部分补0）。
首先我们把字符串中的每一个数字都初始化为‘0’，然后每一次为字符串表示的数字加1，再打印出来。
在字符串表达数字上模拟加法，我们首先设置是否溢出标识，是否进位标识，以及取得字符数组长度，遍历这个字符数组，在末尾进行+1操作，如果末尾字符在+1后变为不小于10的数字，我们将末尾减去10加上‘0’字符赋值为末位，进位标识设置为1，在循环次位时+1，然后再判断是否为不小于10，是的话重复上面的步骤。直到判断高位是不是不小于10，是的话字符数组溢出；如果末尾字符在+1后是小于10的数字，直接加上‘0’赋值给末尾，跳出当前循环，返回没有溢出。
class Solution {
public void printNumbers(int n) {
if(n <= 0){
System.out.println("输入的n没有意义");
return;
}
//声明字符数组,用来存放一个大数
char number[] = new char[n+1];
for (int i = 0; i < number.length; ++i) { //放字符0进行初始化
number[i] = '0';
}
while(!incrementNumber(number)){ //没到最大值时,就不断循环打印
printNumber(number); //打印大数
}
}
//在表示数字的字符串number上加1
private boolean incrementNumber(char[] number) {
boolean isOverflow = false; //判断是否溢出
int nTakeOver = 0; //判断是否进位
int nLength = number.length;
for (int i = nLength - 1; i >= 0 ; --i) {
// nSum表示当前位是几
// 除个位外的位, 其值等于原来的值(number[i] - '0')加上进位的标识
// 个位的值等于原来的值加1
int nSum = number[i] - '0' + nTakeOver;
if(i == nLength - 1){ //末尾自加1
++nSum;
}
// 接着判断当前位改变后是否能进位
// 大于等于10则进位;否则不变
// 有进位的时候要注意是谁有进位! 最高位有进位的话表示改变前已经达到最大值;
if(nSum >= 10){
if(i == 0){
isOverflow = true;
}else{
nSum -= 10;
nTakeOver = 1;
number[i] = (char) ('0' + nSum);
}
}else{
number[i] = (char) (nSum + '0');
break;
}
}
return isOverflow;
}
private void printNumber(char[] number) {
boolean isBeginning0 = true;
int nLength = number.length;
for (int i = 0; i < nLength; ++i) {
if(isBeginning0 && number[i]!='0'){
isBeginning0 = false;
}
if(!isBeginning0){
System.out.print(number[i]);
}
}
System.out.println();
}
}
18.题目一描述：删除链表的节点（简单），本题考查链表
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 :
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
思路：
找到值为 val 的节点，删除该节点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head == null)
return head;
if(head.val == val)
return head.next;
ListNode pre = head;
ListNode cur = head.next;
while(cur!=null && cur.val!=val){
pre = cur;
cur = cur.next;
}
pre.next = cur.next;
return head;
}
}
18.题目二描述：删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
输入: 1->1->2->3->3
输出: 1->2->3
思路：
cur.val 和 cur.next.val 相等时删除重复元素
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode cur = head;
while(cur != null && cur.next != null) {
if(cur.val == cur.next.val) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}
return head;
}
}
19.正则表达式匹配（困难），本题考查字符串和正则表达式
思路：
1.当模式中的第二个字符不是'^'时，如果字符串中的第一个字符和模式中的第一个字符相匹配，那么在字符串和模式上都要向后移动一个字符，然后匹配剩余的字符串和模式。如果字符串中的第一个字符和模式中的第一个字符不相匹配，则直接返回false
2.当模式中的第二个字符是''时
(1)当‘^’匹配0个字符时，字符串当前字符不变，模式上向后移动两个字符，跳过这个‘*’符号；
(2)当‘^’匹配1个或多个时，如果字符串中的第一个字符和模式中的第一个字符相匹配，则在字符串上向后移动一个字符，模式上有两个选择：可以保持不变，可以向后移动两个字符。
public class Solution {
public boolean match(char[] str, char[] pattern)
{
if(str==null||pattern==null){
return false;
}
int i = 0;
int j = 0;
return matchOfstrAndpattern(str,i,pattern,j);
}
public boolean matchOfstrAndpattern(char[] str, int i,char[] pattern, int j){
if(i==str.length&&j==pattern.length){
return true;
}
//j先到尾部则匹配失败
if(j==pattern.length&&i<str.length){
return false;
}
//pattern的第二个字符为'*'
//当‘*’匹配1个或多个时，如果str中的第一个字符和pattern中的第一个字符相匹配
//则在str上向后移动一个字符，pattern上有两个选择：可以保持不变，可以向后移动两个字符。
if(j+1<pattern.length&&pattern[j+1]=='*'){
if((i!=str.length&&str[i]==pattern[j])||(i!=str.length&&pattern[j]=='.')){
return matchOfstrAndpattern(str,i,pattern,j+2)
||matchOfstrAndpattern(str,i+1,pattern,j+2)
||matchOfstrAndpattern(str,i+1,pattern,j);
}else{
//当‘*’匹配0个字符时，str当前字符不变，pattern模式上向后移动两个字符，跳过这个‘*’符号；
return matchOfstrAndpattern(str,i,pattern,j+2);
}
}
//pattern的第二个字符不为'*'
//str中的第一个字符和pattern中的第一个字符相匹配，都向后移动一个字符，然后匹配剩余的字符串和模式。
if((i!=str.length&&str[i]==pattern[j])||(i!=str.length&&pattern[j]=='.')){
return matchOfstrAndpattern(str,i+1,pattern,j+1);
}else{
//第一个字符不匹配
return false;
}
}
}
20.表示数值的字符串（中等），本题考查字符串
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
思路一：正则表达式
表示数值的字符串遵循A[.[B]][e|EC]或者.B[e|EC]，其中A为数值的整数部分，B紧跟着小数点为数值的小数部分，C紧跟着'e'或者'E'为数值的指数部分。A和C都是可能以'+'或者'-'开头的0-9的数位串，B也是0-9的数位串，前面不能有正负号
正则表达式形式为"^[-+]?[0-9](\.[0-9])?([eE][-+]?[0-9]+)?$"
public class Solution {
public boolean isNumeric(char[] str) {
String string = String.valueOf(str);
return string.matches("^[-+]?[0-9]*(\\.[0-9]*)?([eE][-+]?[0-9]+)?$");
}
}
思路二：依次扫描各部分
表示数值的字符串遵循A[.[B]][e|EC]或者.B[e|EC]，其中A为数值的整数部分，B紧跟着小数点为数值的小数部分，C紧跟着'e'或者'E'为数值的指数部分。A和C都是可能以'+'或者'-'开头的0-9的数位串，B也是0-9的数位串，前面不能有正负号
public class Solution {
int index;
public boolean isNumeric(char[] str) {
if(str == null)
return false;
index=0;
boolean flag = scanInteger(str);
//出现'.'，判断小数部分
if(index<str.length && str[index]=='.'){
index++;
//小数可以没有整数部分，如.12等于0.12
//小数点后面可以没有数字，如12.等于12.0
//小数点前面和后面可以都有数字，如12.12
flag = scanUnsignedInteger(str) || flag;
}
//如果出现'e'或者'E'，判断指数部分
if(index<str.length && (str[index]=='e'||str[index]=='E')) {
index++;
//当e或者E前面没有数字时，整个字符串不能表示数字，如e1、.e1
//当e或者E后面没有整数时，整个字符串不能表示数字，如12e、12e+5.4
flag = scanInteger(str)&&flag;
}
return index>=str.length && flag;
}
//扫描带正负符号的整数部分，匹配A和C部分
public boolean scanInteger(char[] str) {
if(index<str.length && (str[index]=='+'||str[index]=='-'))
index++;
return scanUnsignedInteger(str);
}
//扫描无符号整数部分，匹配B部分
public boolean scanUnsignedInteger(char[] str) {
int temp=index;
while(index<str.length && str[index]>='0' && str[index]<='9')
index++;
return index>temp;//是的话返回1，否的话返回0
}
}
