1. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

出处：

https://edu.csdn.net/practice/23386787

代码：

public class climbStairs {public static class Solution {public int climbStairs(int n) {int[] num = new int[n + 1];num[0] = 1;num[1] = 1;for (int i = 2; i <= n; i++) {num[i] = num[i - 1] + num[i - 2];}return num[n];}}public static void main(String[] args) {Solution s = new Solution();System.out.println(s.climbStairs(2));System.out.println(s.climbStairs(3));System.out.println(s.climbStairs(5));}
}

输出：

2
3
8

注：本题本质就是斐波那契数列，当然也可以用递归法：

public class climbStairs {
public static class Solution {
public int climbStairs(int n) {
if (n < 2) return 1;
return climbStairs(n-1) + climbStairs(n-2);
}
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.climbStairs(2));
System.out.println(s.climbStairs(3));
System.out.println(s.climbStairs(5));
}
}

2. 数字 1 的个数

给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

示例 1：

输入：n = 13
输出：6

示例 2：

输入：n = 0
输出：0

提示：

0 <= n <= 10^9

代码：

public class CountDigitOne {public static class Solution {public int countDigitOne(int n) {if (n < 1)return 0;int len = getLenOfNum(n);if (len == 1)return 1;int tmp = (int) Math.pow(10, len - 1);int first = n / tmp;int firstOneNum = first == 1 ? n % tmp + 1 : tmp;int otherOneNUm = first * (len - 1) * (tmp / 10);return firstOneNum + otherOneNUm + countDigitOne(n % tmp);}private int getLenOfNum(int n) {int len = 0;while (n != 0) {len++;n /= 10;}return len;}}public static void main(String[] args) {Solution s = new Solution();System.out.println(s.countDigitOne(13));System.out.println(s.countDigitOne(0));System.out.println(s.countDigitOne(23));}
}

输出：

6
0
13

3. 区间和的个数

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例 1：

输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

示例 2：

输入：nums = [0], lower = 0, upper = 0
输出：1

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
-10^5 <= lower <= upper <= 10^5
题目数据保证答案是一个 32 位 的整数

出处：

https://edu.csdn.net/practice/23386788

代码：

public class CountRangeSum {public static class Solution {public int countRangeSum(int[] nums, long lower, long upper) {long sums[] = new long[nums.length];for (int i = 0; i < nums.length; i++) {sums[i] = ((i - 1 >= 0) ? sums[i - 1] : 0) + nums[i];}int result = divideAndConquer(sums, 0, sums.length - 1, upper, lower);return result;}private int divideAndConquer(long sums[], int start, int end, long upper, long lower) {if (start > end)return 0;if (start == end)return (sums[start] <= upper && sums[start] >= lower) ? 1 : 0;int mid = (start + end) / 2;int counts = 0;counts += divideAndConquer(sums, start, mid, upper, lower);counts += divideAndConquer(sums, mid + 1, end, upper, lower);int ls = start, le = mid;while (le >= start && sums[mid + 1] - sums[le] <= upper)le--;for (int r = mid + 1; r <= end; r++) {while (ls <= mid && sums[r] - sums[ls] >= lower)ls++;while (le + 1 <= mid && sums[r] - sums[le + 1] > upper)le++;if (ls - le - 1 < 0)continue;counts += (ls - le - 1);}ls = start;int i = 0, r = mid + 1;long merged[] = new long[end - start + 1];while (ls <= mid || r <= end) {if (ls > mid || (r <= end && sums[r] < sums[ls])) {merged[i++] = sums[r++];} else {merged[i++] = sums[ls++];}}for (i = 0; i < merged.length; i++) {sums[start + i] = merged[i];}return counts;}}public static void main(String[] args) {Solution s = new Solution();int[] nums = {-2,5,-1};System.out.println(s.countRangeSum(nums, -2, 2));int[] zero = {0};System.out.println(s.countRangeSum(zero, 0, 0));}
}

输出：

3
1