斐波那契数列
题目：输入一个整数n，输出斐波那契数列的第n项（从0开始，第0项为0）。
思路：
- fabonacci(0) ---> 0
- fabonacci(2) ---> 1
- fabonacci(3) ---> 1
- fabonacci(4) ---> 2
- fabonacci(5) ---> 3
- ……
- fabonacci(n) ---> fabonacci(n-1)+fabonacci(n-2)
public class Fibonacci {
/**
* 解法1：递归。
* 时间复杂度：O(2^n)。
* 重复计算比较多。
* @param n
* @return
*/
public static int fibonacci1(int n) {
if (n < 0) {
throw new RuntimeException("n不能小于0！");
} else if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
return fibonacci1(n-1) + fibonacci1(n-2);
}
}
/**
* 解法2：非递归。
* 时间复杂度：O(n)。
* @param n
* @return
*/
public static int fibonacci2(int n) {
if (n < 0) {
throw new RuntimeException("n不能小于0！");
} else if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else {
int a = 0;
int b = 1;
int res = 0;
for (int i = 1; i < n; i++) {
res = a + b;
a = b;
b = res;
}
return res;
}
}
} 跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
思路：
- 假设青蛙从第n级台阶往下跳，它第一次可以跳到第n-1级台阶或第n-2级台阶。由此递推，即jumpfloor(n)=jumpfloor(n-1)+jumpfloor(n-2)。
- jumpfloor(1) ---> 1
- jumpfloor(2) ---> 2
- jumpfloor(3) ---> 3
- jumpfloor(4) ---> 5
- ……
- jumpfloor(n) ---> jumpfloor(n-1)+jumpfloor(n-2)
public class JumpFloor {
/**
* 解法1：递归。
* @param n
* @return
*/
public static int jumpfloor1(int n) {
if (n < 0) {
throw new RuntimeException("n不能小于0！");
} else if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
return jumpfloor1(n - 1) + jumpfloor1(n - 2);
}
}
/**
* 解法2：非递归。
* @param n
* @return
*/
public static int jumpfloor2(int n) {
if (n < 0) {
throw new RuntimeException("n不能小于0！");
} else if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
} else if (n == 2) {
return 2;
} else {
int a = 1;
int b = 2;
int res = 0;
for (int i = 2; i < n; i++) {
res = a + b;
a = b;
b = res;
}
return res;
}
}
}
变态跳台阶
题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
思路1：
- jumpFloorII(1) ---> 1
- jumpFloorII(2) ---> 2
- jumpFloorII(3) ---> 4
- jumpFloorII(4) ---> 8
- ……
- jumpFloorII(n) ---> 2^(n-1)
思路2：
- jumpFloorII(n)=jumpFloorII(n-1)+ jumpFloorII(n-2)+……+jumpFloorII(1)
- jumpFloorII(n-1)=jumpFloorII(n-2)+ jumpFloorII(n-3)+……+jumpFloorII(1)
- jumpFloorII(n)=2*jumpFloorII(n-1)
public class JumpFloorII {
public static int jumpFloorII(int n) {
if (n < 0) {
throw new RuntimeException("n不能小于0！");
} else if (n == 0) {
return 0;
} else {
int res = 1;
for (int i = 1; i < n; i++) {
res *= 2;
}
return res;
}
}
}
二维数组中的查找
题目：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
思路：
[
[1,2,3,4,5],
[2,3,4,5,6],
[3,4,5,6,7],
[4,5,6,7,8]
];
从第一行最后一位开始比较，如果target更大，向下移动一位，继续比较；如果target更小，向左移动一位，继续比较；直到找到target返回true，或者遍历完整个数组都没找到，返回false。
public class Solution {
public boolean Find(int target, int [][] array) {
int i = 0;
int j = array[0].length - 1;
while (i < array.length && j >= 0) {
if (target == array[i][j]) {
return true;
} else if (target > array[i][j]) {
i++;
} else {
j--;
}
}
return false;
}
}
用两个栈实现队列
题目：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
import java.util.Stack;
public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if(stack1.empty() && stack2.empty()){
throw new RuntimeException("Queue is empty!");
}
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
} 替换空格
题目：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer stringBuffer = new StringBuffer();
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i) == ' ') {
stringBuffer.append("%20");
} else {
stringBuffer.append(str.charAt(i));
}
}
return stringBuffer.toString();
}
} 旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
public class Solution {
public int minNumberInRotateArray(int [] array) {
int length = array.length;
if(length == 0) {
return 0;
}
int left = 0;
int right = length-1;
int mid = 0;
while(left < right) {
if(array[left] < array[right]) {
return array[left];
}
mid = (left+right)/2;
if(array[mid] < array[right]) {
right = mid;
} else if(array[mid] > array[right]) {
left = mid+1;
} else {
left++;
}
}
return array[left];
}
}
调整数组顺序使奇数位于偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
解法一：使用辅助数组。
public class Solution {
public void reOrderArray(int [] array) {
int oddNum = 0; // array中奇数的个数
int evenNum = 0; // array中偶数的个数
int arrLen = array.length; // array的长度
int modVal = 0; // (arr[i] % 2)
for(int i = 0; i < arrLen; i++) {
modVal = array[i] % 2;
if(modVal != 0) { // 如果为奇数，oddNum加1
oddNum++;
} else { // 如果为偶数，evenNum加1
evenNum++;
}
}
int[] oddArr = new int[oddNum]; // 存放奇数的数组
int[] evenArr = new int[evenNum]; // 存放偶数的数组
int oddIndex = 0;
int evenIndex = 0;
for(int i = 0; i < arrLen; i++) {
modVal = array[i] % 2;
if(modVal != 0) { // 如果为奇数
oddArr[oddIndex] = array[i];
oddIndex++;
} else { // 如果为偶数
evenArr[evenIndex] = array[i];
evenIndex++;
}
}
for(int i = 0; i < arrLen; i++) {
if(i < oddNum) {
array[i] = oddArr[i];
} else {
array[i] = evenArr[i - oddNum];
}
}
}
} 解法二：冒泡排序。 public class Solution {
public void reOrderArray(int [] array) {
int length = array.length;
int temp;
for (int i = 1; i < length; i++) {
for (int j = 0; j < length - i; j++) {
if (array[j] % 2 == 0 && array[j+1] % 2 == 1) {
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
} 包含min函数的栈
题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
import java.util.Stack;
public class Solution {
private Stack<Integer> dataStack = new Stack<>();
private Stack<Integer> minStack = new Stack<>();
public void push(int node) {
if (dataStack.isEmpty()) {
dataStack.push(node);
minStack.push(node);
} else {
dataStack.push(node);
if(minStack.peek() > node) {
minStack.push(node);
} else {
minStack.push(minStack.peek());
}
}
}
public int pop() {
if(dataStack.isEmpty()) {
throw new RuntimeException("栈空！");
}
minStack.pop();
return dataStack.pop();
}
public int top() {
return dataStack.peek();
}
public int min() {
return minStack.peek();
}
} 栈的压入、弹出序列
题目：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
int pushLen = pushA.length;
int popLen = popA.length;
if(pushLen == 0 || pushLen != popLen) {
return false;
}
Stack<Integer> stack = new Stack<>();
int index = 0;
for(int i = 0; i < pushLen; i++) {
stack.push(pushA[i]);
while(!stack.isEmpty() && stack.peek() == popA[index]) {
stack.pop();
index++;
}
}
return stack.isEmpty();
}
} 从尾到头打印链表
题目：输入一个链表，按链表从尾到头的顺序返回一个ArrayList。
解法一：借助Stack。
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
ListNode cur = listNode;
while(cur != null) {
stack.push(cur.val);
cur = cur.next;
}
while(!stack.isEmpty()) {
list.add(stack.pop());
}
return list;
}
} 解法二：借助数组。 /**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<>();
int length = 0;
ListNode cur = listNode;
while(cur != null) {
length++;
cur = cur.next;
}
int[] vals = new int[length];
cur = listNode;
int index = length-1;
while(cur != null) {
vals[index--] = cur.val;
cur = cur.next;
}
for(int i = 0; i < length; i++) {
list.add(vals[i]);
}
return list;
}
} 链表中倒数第k个结点
题目：输入一个链表，输出该链表中倒数第k个结点。
思路：定义两个指针：first、second，让first先走k步，随后first、second一起走，直到first走到终点，此时second指向倒数第k个结点。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode first, second;
first = second = head;
int i = 0;
for (; first != null; i++) {
if (i >= k)
second = second.next;
first = first.next;
}
return i < k ? null : second;
}
} 反转链表
题目：输入一个链表，反转链表后，输出新链表的表头。
解法一：实时调整链表指向。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode newHead = null;
ListNode temp;
ListNode cur = head;
while(cur != null) {
temp = cur;
cur = cur.next;
temp.next = newHead;
newHead = temp;
}
return newHead;
}
} 解法二：使用Stack。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {
// 第一种情况：如果head为空，返回null
if(head == null) {
return null;
}
// 第二种情况：如果head不为空
Stack<ListNode> stack = new Stack<>();
ListNode cur = head;
while(cur != null) {
stack.push(cur);
cur = cur.next;
}
ListNode newHead = new ListNode(stack.pop().val);
ListNode node = null;
cur = newHead;
while(!stack.isEmpty()) {
node = new ListNode(stack.pop().val);
cur.next = node;
cur = cur.next;
}
return newHead;
}
} 合并两个排序的链表
题目：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
if(list1 == null){
return list2;
}else if(list2==null){
return list1;
}
ListNode newHead = null;
ListNode cur1 = list1;
ListNode cur2 = list2;
if(cur1.val < cur2.val) {
newHead = cur1;
cur1 = cur1.next;
} else {
newHead = cur2;
cur2 = cur2.next;
}
ListNode curHead = newHead;
while(cur1 != null || cur2 != null) {
if(cur1 == null) {
curHead.next = cur2;
break;
} else if(cur2 == null) {
curHead.next = cur1;
break;
} else {
if(cur1.val < cur2.val) {
curHead.next = cur1;
cur1 = cur1.next;
curHead = curHead.next;
} else {
curHead.next = cur2;
cur2 = cur2.next;
curHead = curHead.next;
}
}
}
return newHead;
}
} 复杂链表的复制
题目：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead) {
if(pHead == null) {
return null;
}
RandomListNode currentNode = pHead;
//1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
RandomListNode cloneNode;
RandomListNode nextNode;
while(currentNode != null){
cloneNode = new RandomListNode(currentNode.label);
nextNode = currentNode.next;
currentNode.next = cloneNode;
cloneNode.next = nextNode;
currentNode = nextNode;
}
currentNode = pHead;
//2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
while(currentNode != null) {
currentNode.next.random = currentNode.random == null ? null : currentNode.random.next;
currentNode = currentNode.next.next;
}
//3、拆分链表，将链表拆分为原链表和复制后的链表
currentNode = pHead;
RandomListNode pCloneHead = currentNode.next;
while(currentNode != null) {
cloneNode = currentNode.next;
currentNode.next = cloneNode.next;
cloneNode.next = cloneNode.next == null ? null : cloneNode.next.next;
currentNode = currentNode.next;
}
return pCloneHead;
}
} 两个链表的第一个公共结点
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
if (pHead1 == pHead2) {
return pHead1;
}
ListNode p1 = pHead1;
ListNode p2 = pHead2;
int k = 0;
while (p1 != null && p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
if (p1 != null) {
while (p1 != null) {
k++;
p1 = p1.next;
}
p1 = pHead1;
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
p2 = pHead2;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
if (p2 != null) {
while (p2 != null) {
k++;
p2 = p2.next;
}
p2 = pHead2;
for (int i = 0; i < k; i++) {
p2 = p2.next;
}
p1 = pHead1;
while (p1 != p2) {
p1 = p1.next;
p2 = p2.next;
}
return p1;
}
return null;
}
} 封装后： /*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
if (pHead1 == pHead2) {
return pHead1;
}
ListNode p1 = pHead1;
ListNode p2 = pHead2;
int k = 0;
while (p1 != null && p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
if (p1 != null) {
return find(p2, p1, pHead2, pHead1, k);
}
if (p2 != null) {
return find(p1, p2, pHead1, pHead2, k);
}
return null;
}
private ListNode find(ListNode sP, ListNode lP, ListNode sPHead, ListNode lPHead, int k) {
while (lP != null) {
k++;
lP = lP.next;
}
lP = lPHead;
for (int i = 0; i < k; i++) {
lP = lP.next;
}
sP = sPHead;
while (sP != lP) {
sP = sP.next;
lP = lP.next;
}
return sP;
}
} 孩子们的游戏（圆圈中最后剩下的数）
题目：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1。
解法一：环形链表
class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n <= 0 || m <= 0) {
return -1;
}
ListNode head = new ListNode(0);
ListNode node = head;
for (int i = 1; i < n; i++) {
node.next = new ListNode(i);
node = node.next;
}
node.next = head;
int k = 0;
while (node.next != node) {
if (++k == m) {
node.next = node.next.next;
k = 0;
} else {
node = node.next;
}
}
return node.val;
}
} 解法二：找规律 => f(n, m) = (f(n-1, m) + m) % n ①递归
public class Solution {
public int fun(int n, int m) {
if (n <= 0 || m <= 0) return -1;
return n == 1 ? 0 : (fun(n - 1, m) + m) % n;
}
} ②循环 public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n <= 0 || m <= 0) {
return -1;
}
int ans = 0;
for (int i = 2; i <= n; i++) {
ans = (ans + m) % n;
}
return ans;
}
} 链表中环的入口结点
题目：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ListNode EntryNodeOfLoop(ListNode pHead) {
if (pHead == null) {
return null;
}
ListNode fastPointer = pHead;
ListNode slowPointer = pHead;
while (fastPointer != null && fastPointer.next != null) {
fastPointer = fastPointer.next.next;
slowPointer = slowPointer.next;
if (fastPointer == slowPointer) {
break;
}
}
if (fastPointer == null || fastPointer.next == null) {
return null;
}
fastPointer = pHead;
while (fastPointer != slowPointer) {
fastPointer = fastPointer.next;
slowPointer = slowPointer.next;
}
return fastPointer;
}
} 二进制中1的个数
题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
思路：
- 如果一个整数不为0，那么这个整数至少有一位是1。
- 如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。 其余所有位将不会受到影响。
- 举个例子：
- 一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011。
- 我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。
- 例如：1100 & 1011 = 1000。
- 也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0。那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。
public class Solution {
public int NumberOf1(int n) {
int count = 0;
while(n != 0){
n = n & (n - 1);
count++;
}
return count;
}
} 不用加减乘除做加法
题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
思路：两个二进制的相加结果是用一个异或门实现的；两个二进制的进位结果是用一个与门来实现的。
public class Solution {
public int Add(int num1,int num2) {
int result, ans;
do {
result = num1 ^ num2; // 每一位相加
ans = (num1 & num2) << 1; // 进位
num1 = result;
num2 = ans;
} while (ans != 0);
return result;
}
} 数组中出现次数超过一半的数字
题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：遍历数组，每两个不同的数相互消除，最后剩下的数就可能是大于一半的数字。
public class Solution {
public int MoreThanHalfNum_Solution(int [] array) {
if(array == null || array.length == 0)return 0;
int preValue = array[0];//用来记录上一次的记录
int count = 1;//preValue出现的次数（相减之后）
for(int i = 1; i < array.length; i++){
if(array[i] == preValue)
count++;
else{
count--;
if(count == 0){
preValue = array[i];
count = 1;
}
}
}
int num = 0;//需要判断是否真的是大于1半数
for(int i = 0; i < array.length; i++)
if(array[i] == preValue)
num++;
return (num > array.length/2) ? preValue : 0;
}
} 整数中1出现的次数（从1到n整数中1出现的次数）
题目：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
思路一（遍历测试）：
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int counts,num;
counts = 0;
if(n < 1){
return 0;
}
for(int i = 1;i <= n;i++){
num = i;
while(num > 0){
if(num%10 == 1){
counts++;
}
num /= 10;
}
}
return counts;
}
} 思路二：- 个位数上的1的个数：(n/10)1 + if(n%10)<1?0:((n%10-1)+1)
- *十位数上的1的个数：(n/100)10 + if(n%100)<10?0:((n%100-10)+1)
- *百位数上1的个数：(n/1000)100 + if(n%1000)<100?0:((n%1000-100)+1)
- *总计i：*(n/(10i))i + if(n%(10i))< i ?0:((n%(10*i)-i)+1)，i是小于n的最高位数目：i=pow(10, log10(n))
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
if(n <= 0)return 0;
int count = 0;
for(int i=1; i <= n; i*=10){
//计算在第i位上总共有多少个1
count = count + (n/(10*i))*i;
//不足i的部分有可能存在1
int mod = n%(10*i);
//如果超出2*i -1，则多出的1的个数是固定的
if(mod > 2*i -1) {
count+=i;
} else{
//只有大于i的时候才能会存在1
if(mod >= i) {
count += (mod -i)+1;
}
}
}
return count;
}
} 
京公网安备 11010502036488号