剪绳子
题目1
给你一根长度为n的绳子，请把绳子剪成m段(m,n都是整数，n>1并且m>1)，每段绳子的长度记为k[0],k[1],…,k[m],请问k[0]k[1]…*k[m]可能的最大乘积是多少？
方法
定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值，即f(n) = max(f(i)*f(n-i))，其中0<i<n。
import java.util.Scanner;
/**
* f(n) = max(f(i)*f(n-i))
* @author Think
*
*/
public class CutRope {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
//i=1,2,3的情况
if(m == 0 || m == 1){
System.out.println(0);
}else if(m == 2){
System.out.println(1);
}else if(m == 3){
System.out.println(2);
}
//path[i]代表长度为i的绳子剪成若干段之后各段长度乘积的最大值，i >= 4
int[] path = new int[m+1];
path[0] = 0;
path[1] = 1;
path[2] = 2;
path[3] = 3;
int max = 0;
for(int i = 4; i <= m; i++){
for(int j = 1; j <= i / 2; j++){
path[i] = path[j] * path[i-j];
if(path[i] > max){
max = path[i];
}
}
path[i] = max;
}
System.out.println(path[m]);
}
}
##打印从1到最大的n位数
题目2
输入数字n，按顺序打印出从1到最大的n位十进制数。比如输入3，则打印出1,2,3一直到最大的3位数999
方法
由于这道题没有说n的大小，因此这道题要考虑大数情况，所以得使用字符串。对于此题直接进行全排列，递归求解即可。
import java.util.Scanner;
/**
* 考虑大数情况，得用字符串
* @author Think
*
*/
public class Print1_TO_Nweishu {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String str = "";
judge(str,n,0);
}
public static void judge(String str, int n, int num){
if(n == num){
System.out.println(str);
return;
}
for(int i = 0; i < 10; i++){
judge(str+(i), n, num+1);
}
}
}
数字序列中某一位的数字 （WAP面试时遇到的）
题目
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位(从0开始计数)是5，第13位是1，第19位是4，等等，求任意第n位对应的数字
方法
设第1001位的数字
1. 找到1001-10 = 991位的数字
2. 找到991-2*90 = 811位的数字
3. 811-3*900 < 0,由于811 = 270*3+1,意味着第811位是从100开始的第270个数字即370的中间一位，也就是7
public class SeqNum {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
if(m <= 10){
System.out.println(m % 10);
}else{
m = m - 10;
int i = 2;
int n = 90;
int base = 10;
while((m - i*n) > 0 ){
m = m - i * n;
i++;
n = n * base;
}
int t = m % i;
m = m / i;
int res = (int)Math.pow(10, i) + m;
int temp = 0;
while(res != 0 && temp <= i-t){
t = res % 10;
res = res / 10;
temp++;
}
System.out.println(t);
}
}
}
把数字翻译成字符串
题目
给定一个数字，按照如下规则把它翻译成字符串：0->a,1->b,…,25->z。一个数字可能有多个翻译，例如，12258有5种不同的翻译，分别为bccfi,bwfi,bczi,mcfi,mzi。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。
方法
使用递归来解决。因为此题没有最优子结构所以不能使用动态规划。
定义函数f(i)表示从第i位数字开始的不同翻译的数目，那么f(i) = f(i+1)+g(i,i+1)*f(i+2),当第i位和第i+1位两位数字拼接起来的数字在10-25的范围内时，函数g(i,i+1)的值为1，否则为0.
尽管使用递归的思路来分析这个问题，但是由于存在重复的子问题，递归不是解决这个问题的最佳方法，如12258 == 12+258 || 1+2258 2258=22+58|| 2+258,258重复出现。
一般递归从最大的问题开始从上而下解决问题，我们也可以从最小的子问题开始自下而上解决问题，这样就可以消除重复的子问题
import java.util.Scanner;
/**
* 数字转字符串，使用递归，不是动态规划，因为没有满足最优子结构的条件,同时递归从末尾到开头
* @author Think
*
*/
public class IntToString {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
String s = String.valueOf(m);
int[] count = new int[s.length()];
for(int i = s.length()-1; i >= 0; i--){
if(i < s.length()-1){
count[i] = count[i+1];
}else{
count[i] = 1;
}
if(i < s.length()-1){
int digitA = s.charAt(i)-'0';
int digitB = s.charAt(i+1)-'0';
int digit = digitA * 10 + digitB;
if(digit >= 10 && digit <= 25){
//224=22+4
if(i < s.length() - 2)
count[i] = count[i] + count[i+2];
//23=23
else
count[i] = count[i] + 1;
}
}
}
System.out.println(count[0]);
}
}
最长不含重复字符的子字符串
题目
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。假设字符串中只包含’a’-‘z’的字符。例如，在字符串”arabcacfr”中，最长的不含重复字符的子字符串是”acfr”，长度为4.
方法
使用动态规划。定义函数f(i)表示以第i个字符为结尾的不包含重复字符的子字符串的最长长度。从左往右逐一扫描字符串中的每个字符，计算以第i个字符为结尾的不包含重复字符的子字符串的最长长度f(i)时，我们已经知道f(i-1)
如果第i个字符之前没有出现过，那么f(i) = f(i-1)+1
如果第i个字符之前已经出现过，那么计算第i个字符和它上次出现在字符串中的位置的距离，并记为d，接着分两种情形分析：
1）d<=f(i-1)，此时第i个字符出现在f(i-1)对应的最长子字符串之中，因此f(i) = d，意味着在第i个字符出现两次所夹的子字符串中再也没有其他重复的字符
2）d>f(i-1)，此时第i个字符上次出现在f(i-1)对应的最长子字符串之前，仍有f(i) = f(i-1) + 1
本题创建了一个长度为26的数组position用来存储每一个字符上一次出现在在字符串的下标，初始化为-1
import java.util.Scanner;
public class LongestNoRepeatedString {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int[] pos = new int[26];
for(int i = 0; i < 26; i++){
pos[i] = -1;
}
int[] res = new int[s.length()];
res[0] = 1;
pos[(int)(s.charAt(0)-'a')] = 0;
int max = Integer.MIN_VALUE;
for(int i = 1; i < s.length(); i++){
if(pos[(int)(s.charAt(i)-'a')] < 0){
res[i] = res[i-1] + 1;
if(max < res[i]){
max = res[i];
}
}else{
int d = i-pos[(int)(s.charAt(i)-'a')];
if(d <= res[i-1]){
res[i] = d;
}else{
res[i] = res[i-1] + 1;
if(max < res[i]){
max = res[i];
}
}
}
pos[(int)(s.charAt(i)-'a')] = i;
}
System.out.println(max);
}
}
判断是否为平衡二叉树
题目
判断是否为平衡二叉树？
方法
后序遍历
public class IsBalancedTree {
class BinaryTreeNode{
BinaryTreeNode left;
BinaryTreeNode right;
}
public boolean isBalanced(BinaryTreeNode pRoot){
int[] depth = new int[1];
return balanced(pRoot,depth);
}
public boolean balanced(BinaryTreeNode pRoot, int[] depth){
if(pRoot == null){
depth[0] = 0;
return true;
}
int[] left = new int[1];
int[] right = new int[1];
if(balanced(pRoot.left,left)&&balanced(pRoot.right,right)){
if(left[0]-right[0]< 1 ||left[0]-right[0]>-1){
depth[0] = 1+(right[0] > left[0]?right[0]:left[0]);
return true;
}
}
return false;
}
}
数组中唯一只出现一次的数字
题目
在一个数组除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
方法
若题目为数组中的数字除一个只出现一次之外，其他数字都出现了两次，则可以用XOR,可是这个思路在这里不能解决问题。
沿用位运算的思路。如果一个数字出现三次，那么它的二进制表示的每一位也出现三次，如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被3整除。
我们把数组中所有数字的二进制表示的每一位都加起来，如果某一位的和能被3整除，那么只出现一次的数字的二进制表示中对应的那一位是0，否则就是1。
public class OneNumThreeNums {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public int find(int[] numbers, int length){
int[] num = new int[32];
for(int i = 0; i < length; i++){
int mask = 1;
for(int j = 31; j >= 0; j--){
int bit = numbers[i] & mask;
num[j] = num[j] + bit;
mask = mask << 1;
}
}
int res = 0;
for(int i = 0; i < 32; i++){
res = res << 1;
res = res+(num[i]%3);
}
return res;
}
}
n个骰子的点数
题目
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值得出现的概率
方法1
基于递归求骰子点数，可是时间效率不够高。
可以先把n个骰子分为两堆：第一堆只有一个，另一堆有n-1个。单独的那一个可能出现1-6的点数。我们需要计算机1-6每一种点数和剩下的n-1个骰子来计算点数和。接下来把剩下的n-1个骰子仍然分成两堆：第一堆只有一个；第二堆有n-2个。我们把上一轮那个单独骰子的点数和这一轮单独骰子的点数相加，再和剩下的n-2个骰子来计算点数和。
定义一个长度为6n-n+1的数组，将和为s的点数出现的次数保存在第s-n个元素里
public static void probability(int number){
int[] pro = new int[number*6-number+1];
prob(pro,number);
}
public static void prob(int[] pro,int number){
for(int i = 1; i <= 6; i++){
p(pro,number,number,1);
}
}
public static void p(int[] pro, int start, int current, int sum){
if(current == 1){
pro[sum-start]++;
return;
}
for(int i = 1; i <= 6; i++){
p(pro,start,current-1,sum+i);
}
}
方法2
基于循环求骰子点数，时间性能好
定义两个数组pro[0]和pro[1]来存储骰子的点数之和。在一轮循环中，一个数组的第n项等于另一个数组的第n-1,n-2,n-3,n-4,n-5,n-6项的和。在下一轮循环中，我们交换这两个数组在重复这一计算过程。
public static void printProbability(int number){
int[][] pro = new int[2][number*6+1];
int flag = 0;
for(int i = 1; i <= 6; i++){
pro[flag][i] = 1;
}
for(int k = 2; k <= number; k++){
for(int i = 0; i < k; i++){
pro[1-flag][i] = 0;
}
for(int j = k; j <= k*6; j++){
pro[1-flag][j] = 0;
for(int p = 1; p <= 6; p++){
if(j-p >= 0)
pro[1-flag][j] += pro[flag][j-p];
}
}
flag = 1-flag;
}
}
股票的最大利润
题目
假设把某股票的价格按照时间先后顺序存储在数组中国，请问买卖该股票一次可能获得的最大利润是多少？例如，一只股票在某些时间节点的价格为{9,11,8,5,7,12,16,14}。如果我们能在价格5的时候买入并在价格16时卖出，则能收获最大的利润11。
方法
如果在扫描到数组中的第i个数字时，只要能够记住之前的i-1个数字中的最小值，就能计算出当前价位卖出时可能得到的最大利润。
public class MaxStore {
public static int max(int[] numbers, int length){
if(numbers.length < 2){
return 0;
}
int min = numbers[0];
int maxdiff = numbers[1]-numbers[0];
for(int i = 2; i < length; i++){
if(numbers[i-1] < min){
min = numbers[i-1];
}
if(numbers[i] - min >= maxdiff){
maxdiff = numbers[i] - min;
}
}
return maxdiff;
}
}