- 整数中1出现的次数
求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
编程之美上给出的规律：
1、 如果第i位（自右至左，从1开始标号）上的数字为0（小于x），则第i位可能出现1的次数由更高位决定（若没有高位，视高位为0），等于更高位数字 * 当前位数的权重10^(i-1)。
2、如果第i位上的数字为1(等于x)，则第i位上可能出现1的次数不仅受更高位影响，还受低位影响（若没有低位，视低位为0），等于更高位数字 * 当前位数的权重10^(i-1)+（低位数字+1）。
3、如果第i位上的数字大于1(大于x)，则第i位上可能出现1的次数仅由更高位决定（若没有高位，视高位为0），等于（更高位数字+1） * 当前位数的权重10^(i-1)。
这个思路中，如果不是求1出现的次数，而是求其他1-9任意一个次数，就是比较大于、等于、小于这个数就行了，分别对应上边的三条规则。0的出现次数需要余外计算。
X的数目
这里的 X∈[1,9] ，因为 X=0 不符合下列规律，需要单独计算。
首先要知道以下的规律：
从 1 至 10，在它们的个位数中，任意的 X 都出现了 1 次。
从 1 至 100，在它们的十位数中，任意的 X 都出现了 10 次。
从 1 至 1000，在它们的百位数中，任意的 X 都出现了 100 次。
依此类推，从 1 至 10^ i ，在它们的左数第二位（右数第 i 位）中，任意的 X 都出现了 10^(i-1) 次。
这个规律很容易验证，这里不再多做说明。
接下来以 n=2593,X=5 为例来解释如何得到数学公式。从 1 至 2593 中，数字 5 总计出现了 813 次，其中有 259 次出现在个位，260 次出现在十位，294 次出现在百位，0 次出现在千位。
public int NumberOf1Between1AndN_Solution(int n) {
int low,cur,temp,i=1;
int high = n;//记录高位数
int total = 0; //总的1的数量
if(n < 1)
return 0;
while(high!=0) {
//记忆2593 此时i=2，依次拆分25 9 3
high = n/powerBaseof10(i);//// 获取第i位的高位
temp = n%powerBaseof10(i);
cur = temp/powerBaseof10(i-1);// 获取第i位
low = temp%powerBaseof10(i-1);// 获取第i位的低位
if(cur ==1) {
total += high * powerBaseof10(i-1) + low +1;
}
else if (cur > 1) {
total += (high + 1) * powerBaseof10(i -1);
}
else {
total += high * powerBaseof10(i-1);
}
i++;
}
return total;
}
//就是求10^base次方
public int powerBaseof10(int base) {
return (int)Math.pow(10, base);
}v
- 扑克牌顺子
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
public boolean isContinuous(int [] numbers) {
if(numbers == null || numbers.length ==0)
return false;
int zero = 0;//记录0的个数
int diff = 0;//记录空缺的数
Arrays.sort(numbers);
for (int i = 0; i < numbers.length -1; i++) {
if(numbers[i] == 0) {
zero++; //找不到非0的就继续下一次循环
continue;
}
if (numbers[i] != numbers[i+1]) {
diff += numbers[i+1] - numbers[i] -1 ;//4 和 8，中间空缺3
}
else
return false;//说明有对子，肯定不是顺子
}
if(diff<= zero)
return true;//如果diff小于zero，那么zero放在最后就行，因为任意值
return false;
}
- 孩子们的游戏（圆圈中剩下的数）
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
public int LastRemaining_Solution(int n, int m) {
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < n; i++) {
list.add(i);
}
int bt = 0;
while(list.size() >1) {
//// 删除报数为m-1的人（从0开始）
//解析看前面
bt = (bt + m -1)%list.size();
list.remove(bt);
}
return list.size()==1?list.get(0):-1;
}
递归方法：（注意推到公式）
public int LastRemaining_Solution(int n, int m) {
if (m < 1 || n < 1)
return -1;
int last = 0;
// i代表有目前有个人
for (int i = 2; i <= n; i++)
last = (last + m) % i;
return last;
}
- 替换空格
请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
String s = str.toString();
if(s.equals("")) {
return s;
}
StringBuffer sb = new StringBuffer();
for(int i=0;i<s.length();i++) {
if(s.charAt(i) == ' ') {
sb.append("%20");
}else {
sb.append(s.charAt(i));
}
}
return sb.toString();
- 斐波那契数列
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39
public int Fibonacci(int n) {
if(n<=1) {
return n;
}
int a = 1;
int b = 1;
int tmp = 0;
for(int i=2;i<n;i++) {
tmp = a + b;
a = b;
b = tmp;
}
return b;
}
递归会用时更多
- 跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
int count = 0;
public int JumpFloor(int target) {
tiao(1,target);
tiao(2,target);
return count;
}
private void tiao(int sum, int target) {
// TODO 自动生成的方法存根
if(sum > target) {
return;
}
if(sum == target) {
count++;
return;
}
tiao(sum+1,target);
tiao(sum+2,target);
}
- 变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
int count = 0;
public int JumpFloorII(int target) {
for(int i=1;i<target+1;i++) {
tiao(i,target);
}
return count;
}
private void tiao(int sum, int target) {
// TODO 自动生成的方法存根
if(sum > target) {
return;
}
if(sum == target) {
count++;
return;
}
for(int i=1;i<target+1;i++) {
tiao(sum+i,target);
}
}
循环加递归去跳
答案：
public class Solution {
public int JumpFloorII(int target) {
int res = 1;
for(int i =1;i <=target-1;i++){
res = res * 2;
}
return res;
}
}
- 矩形覆盖
我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
int res = 0;
if(target == 0)
return 0;
else if(target == 2)
return 2;
else if(target ==1)
return 1;
else
res = RectCover(target - 1) + RectCover(target-2);
return res;
- 数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
保证base和exponent不同时为0
//本题注意的是exponent小于0 或者 等于 0 的情况 还有base为0的情况
double result = 1;
if(exponent < 0){
base = 1/base;
exponent = (-1) * exponent;
for (int i = 1; i <= exponent; i++) {
result = result *base;
}
}
else{
for (int i = 1; i <= exponent; i++) {
result = result *base;
}
}
return result;
- 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
public ArrayList<Integer> printMatrix(int [][] matrix){
ArrayList<Integer> list = new ArrayList<Integer>();
int topRow = 0;
int topCol = 0;
int downRow = matrix.length - 1;
int downCol = matrix[0].length - 1;
while (topRow <= downRow && topCol <= downCol) { //当满足左上角的小于等于右下角就可以循环
printCircle(list, matrix, topRow++, topCol++, downRow--, downCol--);
}
return list;
}
public void printCircle(ArrayList<Integer> list, int [][] matrix, int topRow, int topCol, int downRow, int downCol) {
if (topRow == downRow) { //子矩阵只有一行的时候
for (int i = topCol; i <= downCol; i++) {//注意循环开始的条件，是从这一列开始，不是从零
list.add(matrix[topRow][i]);
}
}
else if (topCol == downCol) {//子矩阵只有一列的时候
for (int i = topRow; i <= downRow; i++) {//
list.add(matrix[i][topCol]);
}
}
else { //其他的情况下
int currentRow = topRow;
int currentCol = topCol;
while (currentCol != downCol) {//左到右 本行最后一个不访问，在下个循环里面。如图
list.add(matrix[topRow][currentCol]);
currentCol++;
}
while (currentRow != downRow) {//上到下0
list.add(matrix[currentRow][downCol]);
currentRow++;
}
while (currentCol != topCol) {//右到左
list.add(matrix[downRow][currentCol]);
currentCol--;
}
while (currentRow != topRow) {//下到上
list.add(matrix[currentRow][topCol]);
currentRow--;
}
}
}
自己弄循环条件没搞好。。。
- 最小的k个数
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<Integer>();
if(k > input.length) {
return list;
}
Arrays.sort(input);
for(int i=0;i<k;i++) {
list.add(input[i]);
}
return list;
}
答案用大顶堆。。。
- 丑数
把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
public int GetUglyNumber_Solution(int index) {
if(index <= 0)
return 0;
int [] res = new int[index];
res[0] = 1;//先把1放入
int m2 = 0;//控制乘以2的位置，假设得到一个丑数是乘以2得到的，
//那么下一次就是数组中的下一个丑数可能达到。
int m3 = 0;
int m5 = 0;
for (int i = 1; i < index; i++) {
int min = Math.min(res[m2]*2, Math.min(res[m3]*3, res[m5]*5));
res[i] = min;//最小的那个作为当前的丑数
//判断是由谁乘以得到的
if(res[m2] *2 == min)//假设res[1]是乘以2得到的丑数，那么下一次就要判断
//是否是res[2]乘以2可能得到丑数，所以就要++
m2++;
if(res[m3]*3 == min)
m3++;
if(res[m5]*5 == min)
m5++;
}
return res[index - 1];
}
网友评论