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
