1、递归和循环
斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
示例1
输入：4
返回值：3
使用递归非常消耗时间和空间，还可能引起栈溢出，故使用循环更优。
public class Solution {
public int Fibonacci(int n) {
if(n<0||n>39)
return -1;
if(n==0||n==1)
return n;
int a=0,b=1;
int sum=0;
for(int i=2;i<=n;i++)
{
sum=a+b;
a=b;
b=sum;
}
return sum;
}
}测试用例
- 功能测试（输入3，5，10等）；
- 临界值测试（输入0，1，2）；
- 性能测试（输入较大的数字，如40，50，100等）。
2、查找和排序
旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
示例1
输入：[3,4,5,1,2]
返回值：1
public class Solution {
public int minNumberInRotateArray(int [] array) {
int l=0,h=array.length-1;
int m=0;
while(l<=h)
{
if(h-l==1)
return array[h];
m=(l+h)/2;
//数组中首位中数字相等时，无法确定中间元素是属于前面还是后面的递增子数组
//只能使用顺序查找
if(array[h]==array[m]&&array[l]==array[m])
{
lhmEqual(l,h,array);
}
if(array[h]>=array[m])
h=m;
else if(array[l]<=array[m])
l=m;
}
return 0;
}
public int lhmEqual(int l,int h,int[] array)
{
int r=array[l];
for(int i=l+1;i<=h;i++)
{
if(array[i]<r)
r=array[i];
}
return r;
}
}测试用例
- 功能测试（输入的数组为非递减的旋转数组，有重复的数字或者没有重复的数字）；
- 边界测试（输入的数组为非递减数组，只包含一个数字的数组）；
- 特殊用例测试（输入为空）。
3、回溯法
矩阵中的路径
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
[a s a]
[b f d]
[c c e]
[e s e]
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
public class Solution {
public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
boolean[] visited=new boolean[rows*cols];
int pathCount=0;
for(int i=0;i<rows;++i)
{
for(int j=0;j<cols;++j)
{
if(hasPath(matrix,rows,i,cols,j,str,pathCount,visited))
return true;
}
}
return false;
}
public boolean hasPath(char[] matrix,int rows,int i,int cols,int j,char[] str,int pathCount,boolean[] visited)
{
int index=i*cols+j;
if (i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[pathCount] || visited[index])
return false;
if(pathCount==str.length-1)
return true;
boolean f=false;
if(i>=0&&j>=0&&i<rows&&j<cols&&matrix[index]==str[pathCount]&&!visited[index])
{
pathCount++;
visited[index]=true;
f=hasPath(matrix,rows,i+1,cols,j,str,pathCount,visited)
||hasPath(matrix,rows,i-1,cols,j,str,pathCount,visited)
||hasPath(matrix,rows,i,cols,j+1,str,pathCount,visited)
||hasPath(matrix,rows,i,cols,j-1,str,pathCount,visited);
if(!f)
{
pathCount--;
visited[index]=false;
}
}
return f;
}
}测试用例
- 功能测试（在多行多列的矩阵中存在或者不存在路径）；
- 边界值测试（矩阵只有一行或者一列；矩阵和路径中所有字符都是相同的）；
- 特殊输入测试（输入为空）。
机器人的运动范围
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
public class Solution {
public int movingCount(int threshold, int rows, int cols)
{
int count=0;
boolean[] visited=new boolean[rows*cols];
for(int i=0;i<cols*rows;i++)
visited[i]=false;
count=numCount(threshold,rows,cols,0,0,visited);
return count;
}
//统计数量
public int numCount(int threshold,int rows,int cols,int i,int j,boolean[] visited)
{
int count=0;
int index=i*cols+j;
if(i>=0&&j>=0&&i<rows&&j<cols&&!visited[index]&&check(i,j)<=threshold)
{
visited[index]=true;
count=1+numCount(threshold,rows,cols,i+1,j,visited)
+numCount(threshold,rows,cols,i-1,j,visited)
+numCount(threshold,rows,cols,i,j+1,visited)
+numCount(threshold,rows,cols,i,j-1,visited);
}
return count;
}
//判断是否有资格进入方格
public int check(int i,int j)
{
int sum=0;
while(i>0)
{
sum+=i%10;
i/=10;
}
while(j>0)
{
sum+=j%10;
j/=10;
}
return sum;
}
}测试用例
- 功能测试（方格为多行多列；k为正数）；
- 边界值测试（方格只有一行或者一列；k为0）；
- 特殊输入测试（k为负数）。
4、动态规划与贪婪算法
剪绳子
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
输入描述:输入一个数n，意义见题面。（2 <= n <= 60）
返回值描述:输出答案。
示例1
输入：8
返回值：18
//动态规划
public class Solution {
public int cutRope(int target) {
int[] r=new int[target+1];
r[2]=2;
r[3]=3;//疑惑，不是说m>1吗
for(int i=4;i<=target;i++)
{
int max=0;
for(int j=2;j<=i/2;j++)
{
r[i]=r[j]*r[i-j];
if(r[i]>max)
max=r[i];
}
r[i]=max;
}
return r[target];
}
}
//贪婪算法
import java.lang.*;
public class Solution {
public int cutRope(int target) {
int numOf3=0;
int reOf3=0;
numOf3=target/3;
reOf3=target%3;
int s=1;
if(reOf3==0)
s=(int)Math.pow(3,numOf3);
else if(reOf3==1)
s=(int)Math.pow(3,numOf3-1)*4;
else
s=(int)Math.pow(3,numOf3)*2;
return s;
}
}测试用例
- 功能测试（绳子长度>=5）；
- 边界值测试（绳子长度为0，1，2，3，4）。
5、位运算
二进制中哦个1的个数
输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
示例1
输入：10
返回值：2
分析：在计算机系统中，数值一律用补码来表示和存储。正数的原码、反码、补码都是其本身。也就是说，根本就不需要考虑数的符号问题。
//解法1
public class Solution {
public int NumberOf1(int n) {
int sum=0;
while(n!=0){
sum+=n&1;//逐个判断低位是否为1；
n=n>>>1;//无符号右移，例如从11101变成1110
}
return sum;
}
}
//解法2
//把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0。
//那么一个整数的二进制中有多少个1，就可以进行多少次这样的操作。
public class Solution {
public int NumberOf1(int n) {
int sum=0;
while(n!=0){
sum++;
n=n&(n-1);
}
return sum;
}
}测试用例
- 正数（包括边界值1、0x7FFFFFFF）；
- 负数（包括边界值0x80000000、0xFFFFFFFF）；
- 0。
京公网安备 11010502036488号