数据结构——数
直接解
【剑指offer】43. 1～n 整数中 1 出现的次数
题目描述
// 力扣
// 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。
// 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一
// 共出现了5次。
// 牛客
// 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
// 为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现
// 6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加
// 普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1
// 出现的次数）。 题解：
// 题目比较难，需要比较数学的处理。我们将个位，十位，百位等等这些位分开讨论。
// 比如n=126，1出现的次数 = (个位的1出现次数)+(十位的1出现次数)+(百位的1出现次数) // 力扣
// 这里是无注释的干净算法代码，注释版在下面
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35 MB, 在所有 Java 提交中击败了86.22%的用户
class Solution {
public int countDigitOne(int n) {
int count = 0;
int weight = 0;
int low = 0;
int high = n;
for (int base = 1; base <= n; base *= 10) {
weight = high % 10;
high = high / 10;
low = n % base;
if (weight > 1)
count += (high * base + base);
else if (weight == 1)
count += (high * base + low + 1);
else
count += (high * base);
}
return count;
}
}
// 力扣
// 下面是代码注释
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35 MB, 在所有 Java 提交中击败了86.22%的用户
class Solution {
public int countDigitOne(int n) {
int count = 0; // 保存答案，记录1出现的次数
int weight = 0; // 位指针，从个位开始到十位 百位，直至最高位遍历
int low = 0; // 位指针外的低位，初始化为0
int high = n; // 位指针外的高位，初始化为n
// for循环遍历n的位数，weight从最低位个位到n的最高位遍历，
// 遍历位的基数记为base。
// 比如n=126，则位指针weight从低到高将遍历6（个位）2（十位）1（百位）
// 则base分别为1（个位）,10（十位）,100（百位）。
for (int base = 1; base <= n; base *= 10) {
// 计算位指针weight，高位high÷10取余即可得到，
// 如n=126, 则weight=6（个位）
weight = high % 10;
// 高位high随着位指针weight的移动而左移，由于high初始化为n
// 之后算high直接high÷10取整即可。
// 假如n=126，位指针weight=6，则high = 126 / 10 = 12（取整）
// 正好是6左边的数，可见位指针weight和高位high的计算是除法的
// 两种取法。高位high每次÷10时，取整就可以左移得到下一次遍历的高位high，
// 取余就可以得到下一次遍历的位指针weight。我们利用这个特点
// 将高位high初始化为n，就可以得到第一个位指针weight。
high = high / 10;
// 低位的计算比较巧妙，在循环中，位指针weight从个位开始不断左移
// 的同时，我们记录了位指针weight所在位的基数base。
// 假如n=126，位指针weight指向了2，那么所在位的基数base为10（十位）
// 低位low通过n÷base取余可以得到。换句话说，由于得知位指针weight的
// 位置和基数，通过除法取余可以得到位指针weight右边的所有内容。
low = n % base;
// 计数方法：【"1"出现的次数=(个位的"1"出现次数)+(十位的"1"出现次数)+...】
// 根据这个原则，指针weight移动到哪位，我们就计算哪位的"1"的出现次数。
// 当指针遍历的位数字大于1时，该位出现"1"的次数，肯定包含高位数字本身
// 并且还包含当前位的基数。为什么呢？
// 假如n=126，指针weight指向6，因为是个位，首先基数base是1。
// weight>1，个位要到达6，就必须出现过一次"1"，所以要+base
// 如果指针weight指向2，因为是十位，首先base是10，
// weight>1，十位要达到2，就必须出现过十次"1"，所以还是要+base。
// weight为其他位时也同理。
// 那么加上高位high * base意思也是一样的，n=126，
// 指针weight指向6，则指针位肯定出现过base次的"1"，高位high为12，
// 能到达n = 12*base + 6*base这么大的数，weight遍历位已经出现过
// 12 * base轮的"1"了。所以还要加 high * base。
if (weight > 1)
count += (high * base + base);
// 若指针位weight==1，加high * base是不变的，但是由于weight不大于1
// ，到达当前指针weight这个数时出现的"1"可能不满base次，所以不能直接+base
// ，因为weight是1，每个和weight搭配的low都会使遍历位出现1次"1"，
// 所以出现了low次"1"，再加上low=0还会出现一次"1"，"1"总共出现了low+1次。
// 比如weight=1，low=4，那么遍历位的"1"肯定出现了4 + 1次，分别是
// 10,11,12,13,14。
else if (weight == 1)
count += (high * base + low + 1);
// 如果指针位weight为0，那么当前遍历位和低位都不会对当前遍历位
// 出现"1"有帮助。当前位出现"1"只可能来源于高位high，直接加 high * base
else
count += (high * base);
}
return count; // 循环结束，返回count
}
}
// 牛客
// 运行时间：11ms
// 占用内存：9652k
public class Solution {
public int NumberOf1Between1AndN_Solution(int n) {
int count = 0;
int weight = 0;
int high = n;
int low = 0;
for (int base = 1; base <= n; base *= 10) {
weight = high % 10;
high = high / 10;
low = n % base;
if (weight > 1)
count += (high * base) + base;
else if (weight == 1)
count += (high * base) + low + 1;
else
count += (high * base);
}
return count;
}
}
【剑指offer】44. 数字序列中某一位的数字
题目描述
// 44. 数字序列中某一位的数字
// 力扣
// 数字以0123456789101112131415…的格式序列化到一个字符序列中。
// 在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19
// 位是4，等等。
// 请写一个函数，求任意第n位对应的数字。 题解：
// 1.先求n所在的数字属于几位数，2.后求n所在的数字num，3.最后求n在数字num的第几位
// 如n=11，我们将
// 1：先求n所在的数字属于2位数
// 2：后求n所在的数字为10，
// 3：最后求得n在数字10的第二位，即目标为数字0。 // 力扣
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.3 MB, 在所有 Java 提交中击败了33.22%的用户
class Solution {
public int findNthDigit(int n) {
// 位数记录，如11为2位数，123为3位数。初始化digit为1
int digit = 1;
// 当前以位数digit所开始的数字，2位数开始的数字为10，1位数
// 开始的数字为1（0不算1位数）
long start = 1;
// 在当前位数digit下包含的数字数量。由于位数digit初始化为1，
// 所以位数为1的数字总共有1 2 3 4 5 6 7 8 9，共9个数字。
long count = 9;
// 先求n所在的数字num的位数digit
// 如果位数数字总数count少于n,执行循环
while (count < n) {
n -= count; // n减去当前位数数字总数count,若n=15,更新为n=15-9=6
digit++; // 位数更新
start *= 10; // 位数digit开始的数字start根据位数进行更新
count = 9 * start * digit; // count根据start和digit进行更新
}
// 若n=15更新为了n=6。位数digit同时可以理解为所在位数区间内
// 所有数字的长度，digit=2，说明所在位数区间内所有数字长度都为2，
// 而n-1表示从start（start=10）数字第一位开始，到达n=6位置的数位长度
// （所经历的位）即1->0->1->1->1->2，长度为5。
// 那么(n-1)/digit即可得到数字本身从start开始，在位数区间的数字长度（所经历的数）
// 即10->11->12，长度为2。此时再加上start即可得到n所在的数字num
long num = start + (n - 1) / digit;
// 求n所在数字的第几位
// n-1表示从start（start=10）数字第一位开始，到达n=6位置的数位长度
// 我们直接看这个长度能不能被digit整除即可
int i = (n - 1) % digit;
return Long.toString(num).charAt(i) - '0';
}
} 【剑指offer】49. 丑数
题目描述
// 力扣
// 我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求
// 按从小到大的顺序的第 n 个丑数。
// 牛客
// 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑
// 数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。
// 求按从小到大的顺序的第N个丑数。 题解：
///////////////////////////////////////////////////////////////////////
// 由题意可知，丑数n因子包括2 3 5，如果一个数能被2，3，5整除，那么连续将
// 其因子2，3，5除尽后（while (n%2 == 0): n = n/2...）得到的数为1。
// 这个数n就是丑数。我们大可以从1开始一个个判断每个整数是不是丑数
// 但是这样做效率太低了。
// 由于丑数因子相同，所以小丑数 × 2/3/5可以得到大丑数，这就可以用一个
// 数组存储丑数，利用动态规划使得我们从小丑数推断出大丑数。
// 注意要维持数组从小到大的性质。 // 力扣
// 执行用时： 2 ms, 在所有 Java 提交中击败了99.11% 的用户
// 内存消耗：37.3 MB, 在所有 Java 提交中击败了93.79%的用户
class Solution {
public int nthUglyNumber(int n) {
// for循环用于递归丑数数组的每一个位置，将该位置对应
// 的丑数从小到大推断出来。由于丑数只包含2 3 5这三个因子，
// 我们根据前面的小丑数，分别乘这三个因子就可以得到后面的大丑数，
// i2，i3，i5用于前面“小丑数”的索引，dp[i2]用于乘2，dp[i3]用于乘3，
// dp[i5]用于乘5，索引均初始化为0（数组第一位），
// 由于要分别乘3个因子，所以会得到3个丑数，又因为需要升序，
// 所以取乘出的三个丑数中最小的丑数作为当前遍历位置丑数即可。
// 此时参加推断的索引右移一位。
// 注意：再次强调，丑数的因子只有2,3,5，
// 我们设置i2，i3，i5这三个索引从0开始右移，
// 专门用于遍历索引乘2,3,5。也就是说所有的“小丑数”
// 都有机会被i2，i3，i5遍历并乘2 3 5中的任意一个，来推导下一个丑数
// 所以这个过程，就足以包含所有小丑数，推导出大丑数的所有情况（三种乘法）
int i2 = 0, i3 = 0, i5 = 0;
// 构建长度为n的数组，推断出的第n个元素(尾元素)就是我们要的元素
int[] dp = new int[n];
// 数组第一个丑数为1
dp[0] = 1;
for (int i = 1; i < n; i++) {
int b2 = dp[i2] * 2, b3 = dp[i3] * 3, b5 = dp[i5] * 5;
dp[i] = Math.min(b2, Math.min(b3, b5));
if (dp[i] == b2)
i2++;
if (dp[i] == b3)
i3++;
if (dp[i] == b5)
i5++;
}
return dp[n - 1];
}
}
// 牛客
// 运行时间：11ms，超过88.19%用Java提交的代码
// 占用内存：9584KB，超过71.92%用Java提交的代码
public class Solution {
public int GetUglyNumber_Solution(int index) {
if (index == 0)
return 0;
int[] dp = new int[index];
dp[0] = 1;
int i2 = 0, i3 = 0, i5 = 0;
for (int i = 1; i < index; i++) {
int b2 = dp[i2] * 2, b3 = dp[i3] * 3, b5 = dp[i5] * 5;
dp[i] = Math.min(b2, Math.min(b3, b5));
if (dp[i] == b2)
i2++;
if (dp[i] == b3)
i3++;
if (dp[i] == b5)
i5++;
}
return dp[index - 1];
}
} 【剑指offer】60. n个骰子的点数
题目描述：
// 60. n个骰子的点数
// 力扣
// 把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，
// 打印出s的所有可能的值出现的概率。
// 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n
// 个骰子所能掷出的点数集合中第 i 小的那个的概率。
// 这题其实可理解为求所有掷出点数的概率 题解：
// 力扣
// 如果n=1个骰子，可能出现的值的和为[1-6]一共6种，每个值概率相同，
// 如果n=2个骰子，可能出现的值的和为[2-12]共11种，
// 和为s=2的概率为1/6 * 1/6，
// 和为s=3的概率为1/6 * 1/6 (1和2) + 1/6 * 1/6 (2和1)。
// 如果n=3个骰子，可能出现的值的和为[3-18]共16种,
// 和为s=3的概率为1/6 * 1/6 * 1/6，
// 和为s=4的概率为1/6 * 1/6 * 1/6 (1 1 2) + 1/6 * 1/6 * 1/6 (2 1 1)
// + 1/6 * 1/6 * 1/6 (1 2 1)
//
// 可以看出，n个骰子的点数可以分解为n-1个骰子的点数遇到1个骰子的点数，
// 如此循环，其实是一个动态规划问题。
// 我们用数组下标作为骰子点数来理解，1个骰子的每一个点数出现的概率是1/6，
// 由于骰子从1开始，一路动态规划到n个骰子，所以我们将初始化n-1个骰子
// 概率为double[] pre = {1/6d, 1/6d, 1/6d, 1/6d, 1/6d, 1/6d}。
// 我们称pre为点数-概率计数数组，索引就是点数，元素就是点数(和)对应的概率
//
// for循环从2到n遍历会递增的骰子数量，记为i，假设n=2，则此时i=n=2，
// 根据骰子数n构建目标概率数组temp，n=2可以分解为"n-1个"和"1个骰子",
// 第二层for循环遍历"n-1骰子"的概率pre[j]，再第三层for循环遍历"1个骰子"，
// 的概率（就是1/6，所以实际就是for循环遍历6次，每次乘1/6），
// 下标就是骰子点数，所以temp[j + t] += pre[j] * 1/6。
// 那么此时"n-1(n-1=1)个骰子"的第一个点数(j=0)，遇到"1个骰子"的第一个
// 点数(t=0)（点数就是下标，两边都是第一个点数，所以点数之和是0+0
// 所以点数之和的概率是temp[0 + 0](j=t=0)）
// 的概率是temp[0 + 0] = pre[j]*1/6 = 1/6*1/6。以此类推，
// 第三层for循环第一次完成之后，"n-1个骰子"的第一个点数，
// 遇到"1个骰子"的6个点数之和的概率都会被算出来，存入相应temp中，
// temp的索引就是相应的点数之和，temp的元素就是点数之和对应的概率。
//
// "n-1个骰子"的所有点数概率（pre同样也是，索引记录点数，元素记录概率）
// 之后都会和"1个骰子"的6个点数计算相遇概率，并将计算好的概率存入temp中
// 最后第二层循环完成，temp赋给pre，第一层for循环开始下一个骰子的计算。
//
// 所有循环完成，返回点数-概率计数数组pre。
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：38.6 MB, 在所有 Java 提交中击败了74.58%的用户
class Solution {
public double[] dicesProbability(int n) {
double[] pre = {1/6d, 1/6d, 1/6d, 1/6d, 1/6d, 1/6d};
for (int i = 2; i <= n; i++) {
double temp[] = new double[i*6 - i + 1];
for (int j = 0; j < pre.length; j++) {
for (int t = 0; t < 6; t++)
temp[j + t] += pre[j] * 1/6;
}
pre = temp;
}
return pre;
}
}
// 可以试着将过程打印出来
class Solution {
public double[] dicesProbability(int n) {
double[] pre = {1/6d, 1/6d, 1/6d, 1/6d, 1/6d, 1/6d};
for (int i = 2; i <= n; i++) {
double temp[] = new double[i*6 - i + 1];
for (int j = 0; j < pre.length; j++) {
arrPrint(temp);
for (int t = 0; t < 6; t++)
temp[j + t] += pre[j] * 1/6;
}
pre = temp;
}
return pre;
}
// 辅助函数：将int[] 打印出来
private static void arrPrint(double[] arr) {
StringBuilder str = new StringBuilder();
str.append("[");
for (double v : arr) {
str.append(v + ", ");
}
str.delete(str.length() - 2, str.length());
str.append("]");
System.out.println(str.toString());
}
} 【剑指offer】62. 圆圈中最后剩下的数字
题目描述：
// 62. 圆圈中最后剩下的数字
// 力扣
// 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里
// 删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下
// 的最后一个数字。
// 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个
// 数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
// 牛客
// 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此
// 。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首
// 先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始
// 报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼
// 物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去..
// ..直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏
// 版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友
// 的编号是从0到n-1)
// 如果没有小朋友，请返回-1 题解：
// 力扣
// 数组的查找问题。n是数组长度，数组为[0, 1, .. , n-1]，元素等于索引，
// 步长为m。首先是升序数组，但是看题意无法用二分查找，而是约瑟夫环问题。
//
// 如果数组长度n=0，说明数组啥也没有，直接返回-1，
// 如果n=1，说明数组只有一个数0，剩下的数就是这个0，直接返回0。
//
// 返回主函数的递归调用，递归调用下一次去掉数字的情况，
// 去掉一个数字之后，数组长度为n - 1（去掉谁不重要，重要的是剩下谁
// ，所以我们不关心新数组其他元素的内容，不特意去修改，而是关心
// 去掉数字之后数组的长度为n-1），步长依然是m。
// 如果题目中每一次去掉的数字，都是从头往右数第m个位置，
// 那下一个去掉的元素就是lastRemaining(n - 1, m)。但是根据题意，
// 下一个要去掉的元素要在上一个去掉元素的位置开始，再往右数。
// 而上一个次去除元素时已经右移m个位置了，
// 所以下一个要去掉的元素为 lastRemaining(n - 1, m) + m，
// 总偏移量 = (从头往右的偏移量) + (上一个位置的偏移量）
// 注意，(总偏移量) 需要处理成 (总偏移量)%n，来模拟进位
// 的情况，如果 (lastRemaining(n - 1, m) + m) 的总偏移量超过数组遍历的长度，
// 则需要除n取余，来获得进位后的索引元素，
// 而如果 (lastRemaining(n - 1, m) + m)的总偏移量不超过数组长度，那么
// (总偏移量)%n 就是(总偏移量)自己，则不进位，“无事发生”。
// 比如：n=5, m=3
// [0, 1, 2, 3, 4]
// 第一次到2位置，删除2，下一个位置是2 + m = 2 + 3 = 5，5已经超过数组
// 遍历长度，进位:5 % 5 = 0，则进位到0这个位置元素，所以下一个删除元素
// 是0，如此递归循环下去。最后剩下一个元素时，依靠之前的条件判断
// 跳出递归返回即可。
// 执行用时：11 ms, 在所有 Java 提交中击败了46.60%的用户
// 内存消耗：40.3 MB, 在所有 Java 提交中击败了31.54%的用户
class Solution {
public int lastRemaining(int n, int m) {
if (n == 0)
return -1;
if (n == 1)
return 0;
return (lastRemaining(n - 1, m) + m) % n;
}
}
// 牛客
// 运行时间：11ms，超过92.79%用Java提交的代码
// 占用内存：9972KB，超过11.00%用Java提交的代码
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n == 0)
return -1;
if (n == 1)
return 0;
return (LastRemaining_Solution(n - 1, m) + m) % n;
}
} 【剑指offer】64. 求1+2+…+n
题目描述：
// 64. 求1+2+…+n
// 力扣
// 求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch
// 、case等关键字及条件判断语句（A?B:C）。
// 牛客
// 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、c
// ase等关键字及条件判断语句（A?B:C）。 题解：
// 力扣
// 数组的查找问题。n是数组长度，数组为[0, 1, .. , n-1]，元素等于索引，
// 步长为m。首先是升序数组，但是看题意无法用二分查找，而是约瑟夫环问题。
//
// 如果数组长度n=0，说明数组啥也没有，直接返回-1，
// 如果n=1，说明数组只有一个数0，剩下的数就是这个0，直接返回0。
//
// 返回主函数的递归调用，递归调用下一次去掉数字的情况，
// 去掉一个数字之后，数组长度为n - 1（去掉谁不重要，重要的是剩下谁
// ，所以我们不关心新数组其他元素的内容，不特意去修改，而是关心
// 去掉数字之后数组的长度为n-1），步长依然是m。
// 如果题目中每一次去掉的数字，都是从头往右数第m个位置，
// 那下一个去掉的元素就是lastRemaining(n - 1, m)。但是根据题意，
// 下一个要去掉的元素要在上一个去掉元素的位置开始，再往右数。
// 而上一个次去除元素时已经右移m个位置了，
// 所以下一个要去掉的元素为 lastRemaining(n - 1, m) + m，
// 总偏移量 = (从头往右的偏移量) + (上一个位置的偏移量）
// 注意，(总偏移量) 需要处理成 (总偏移量)%n，来模拟进位
// 的情况，如果 (lastRemaining(n - 1, m) + m) 的总偏移量超过数组遍历的长度，
// 则需要除n取余，来获得进位后的索引元素，
// 而如果 (lastRemaining(n - 1, m) + m)的总偏移量不超过数组长度，那么
// (总偏移量)%n 就是(总偏移量)自己，则不进位，“无事发生”。
// 比如：n=5, m=3
// [0, 1, 2, 3, 4]
// 第一次到2位置，删除2，下一个位置是2 + m = 2 + 3 = 5，5已经超过数组
// 遍历长度，进位:5 % 5 = 0，则进位到0这个位置元素，所以下一个删除元素
// 是0，如此递归循环下去。最后剩下一个元素时，依靠之前的条件判断
// 跳出递归返回即可。
// 执行用时：11 ms, 在所有 Java 提交中击败了46.60%的用户
// 内存消耗：40.3 MB, 在所有 Java 提交中击败了31.54%的用户
class Solution {
public int lastRemaining(int n, int m) {
if (n == 0)
return -1;
if (n == 1)
return 0;
return (lastRemaining(n - 1, m) + m) % n;
}
}
// 牛客
// 运行时间：11ms，超过92.79%用Java提交的代码
// 占用内存：9972KB，超过11.00%用Java提交的代码
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if (n == 0)
return -1;
if (n == 1)
return 0;
return (LastRemaining_Solution(n - 1, m) + m) % n;
}
} 特殊解——分治法 ：
【剑指offer】16. 数值的整数次方
题目描述：
// 力扣
// 实现函数double Power(double base, int exponent)，
// 求base的exponent次方。不得使用库函数，同时不需要考虑
// 大数问题。
// 牛客
// 给定一个double类型的浮点数x和int类型的整数exponent。
// 求x的exponent次方。
// 保证x和exponent不同时为0 题解：
// 直接法 //
// 牛客
// 运行时间：27ms
// 占用内存：10648k
public class Solution {
public double Power(double x, int n) {
if (x == 0)
return 0;
if (n == 0)
return 1;
if (n == 1)
return x;
if (n > 0) {
double res = x;
for (int i = 1; i < n; i++)
res *= x;
return res;
}
else {
double res = 1/x;
for (int i = 1; i < -n; i++)
res *= 1/x;
return res;
}
}
} // 直接法 //
// 牛客
// 运行时间：27ms
// 占用内存：10648k
public class Solution {
public double Power(double x, int n) {
if (x == 0)
return 0;
if (n == 0)
return 1;
if (n == 1)
return x;
if (n > 0) {
double res = x;
for (int i = 1; i < n; i++)
res *= x;
return res;
}
else {
double res = 1/x;
for (int i = 1; i < -n; i++)
res *= 1/x;
return res;
}
}
} 特殊解——位运算 ：
【剑指offer】15. 二进制中1的个数
题目描述：
// 力扣
// 请实现一个函数，输入一个整数（以二进制串形式），输出该数二进
// 制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是
// 1。因此，如果输入 9，则该函数输出 2。
// 牛客
// 输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。 题解：
/////////////////////////////// 逐次运算 ///////////////////////////////
// 牛客
// 无法通过测试，超出时间限制
public class Solution {
public int NumberOf1(int n) {
if (n == 0)
return 0;
int index = 1;
int count = 0;
while (index != 0)
if ((index & n) != 0) // 与运算找1，如果当前位是0，与运算结果就是0，count不会递增
count++;
index = index << 1; // index二进制整体左移一位
return count;
}
} ////////////////////////////// 末位相消 //////////////////////////////
// 最好还是用这种末位相消的方法来通过测试
// 假如一个二进制数010100，减1之后为010011，
// 可以看到，原来最右边的1变成了0
// 原来最右边的1再往右的所有0全变成了1。
// 如果让010100和010011做与运算，得到010000，
// 和原来010100比，010000最右边的1被与运算相消了
// 所以其实一个数n和n-1做与运算，可以消掉n最右边的1。
// 牛客
// 运行时间：10ms
// 占用内存：9556k
public class Solution {
public int NumberOf1(int n) {
if (n == 0)
return 0;
int count = 0;
while (n != 0) {
n = n&(n-1);
count++;
}
return count;
}
}
// 力扣
// 执行用时：1 ms, 在所有 Java 提交中击败了98.11%的用户
// 内存消耗：35.7 MB, 在所有 Java 提交中击败了43.89%的用户
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
if (n == 0)
return 0;
int count = 0;
while (n != 0) {
n = n&(n-1);
count++;
}
return count;
}
} 【剑指offer】65. 不用加减乘除做加法
题目描述：
// 65. 不用加减乘除做加法
// 力扣
// 写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”
// 、“/” 四则运算符号。
// 牛客
// 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运
// 算符号。 题解：
//////////////////////////// 位运算 //////////////////////////////
// 力扣
// 无进位情况下，位运算加法和异或逻辑运算相同，所以a ^ b表示没有进位的情况
// 下两数的和。有进位情况下，位运算加法和与逻辑运算相同（结果左移一位）
// 所以 (a & b) << 1 是进位情况下两数的和。
// 递归调用主函数add，将进位的加法结果和不进位的加法结果相加，
// 递归终止条件为当b==0，由于进位加法是与逻辑运算左移，
// 左移到最后会使得所有位为，即可停止。
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.3 MB, 在所有 Java 提交中击败了39.68%的用户
class Solution {
public int add(int a, int b) {
if (b == 0)
return a;
return add(a ^ b, (a & b) << 1);
}
}
// 牛客
// 运行时间：13ms，超过58.96%用Java提交的代码
// 占用内存：9600KB，超过72.42%用Java提交的代码
public class Solution {
public int Add(int num1,int num2) {
if (num2 == 0)
return num1;
return Add(num1 ^ num2, (num1 & num2) << 1);
}
}
特殊解——贪心算法 ：
【剑指offer】14.1. 剪绳子
题目描述：
// 力扣
// 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段
// （m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0]
// ,k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大
// 乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度
// 分别为2、3、3的三段，此时得到的最大乘积是18。
// 牛客
// 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数
// ，n>1并且m>1，m<=n），每段绳子的长度记为k[1],...,k[m]。请问k
// [1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我
// 们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 题解：
///////////////////////////// 动态规划 //////////////////////////
// 牛客
// 动态规划解不难，但是需要换个思路来理解。这时就可以把题目理解成，
// "找出整数n能够被其他小于n的正整数k[i](i>=0)加起来的所有组合(k[0],k[1],...,k[m])，
// 在这个过程中，再找出这些组合里乘积最大的，并返回这个乘积。"
// 把这个问题抽象出来，再动态规划求解：
// 对于整数n，n的组合数，
// 不仅是第一个组合数可以取任何值，第二个组合数也可以取任何值，
// 在动态规划题目《青蛙跳台阶》问题中，青蛙只能跳1阶或者2阶，
// 也就是说组合数只能要么是1，要么是2。
// 而在题目《变态跳台阶》问题中，这个青蛙可以跳1阶，也可以直接跳n阶
// 组合数可以取任意值。所以其实这道题的动态规划解，跟《变态跳台阶》问题很像。
// 但是中途要保存组合数最大的积，且组合数相加不超过n。
// 组合数可以取1，剩下n-1，有f(n-1)种可能
// 可以取2，剩下n-2，有f(n-2)种可能
// ...
// 且有f(n)=f(1)+f(2)+...+f(k1-1)+f(k1)，(1+2+..+k1=n, 1<k1<n)
// f(k1)=f(1)+f(2)+..+f(k2-2)+f(k2-1)，(1+2+..+k2=k1, 1<k2<k1)
// ...
// f(2)=1
// 力扣
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.3 MB, 在所有 Java 提交中击败了60.53%的用户
class Solution {
public int cuttingRope(int n) {
if (n < 2)
return 0;
if (n == 2)
return 1;
if (n == 3)
return 2;
int[] f = new int[n + 1];
f[1] = 1;
f[2] = 2;
f[3] = 3;
for (int i = 4; i <= n; i++) {
int max = 0;
for (int j = 1; j <= i/2; j++) {
if (max < f[j]*f[i-j])
max = f[j]*f[i-j];
}
f[i]=max;
}
return f[n];
}
}
// 执行用时：1 ms, 在所有 Java 提交中击败了42.32%的用户
// 内存消耗：35.3 MB, 在所有 Java 提交中击败了62.66%的用户
class Solution {
public int cuttingRope(int n) {
if (n < 2)
return 0;
int[] f = new int[n + 1];
f[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 1; j < i; j++) {
if (f[j] <= j && f[i] < j*(i-j))
f[i] = j*(i-j);
if (f[j] > j && f[i] < f[j]*(i-j))
f[i] = f[j]*(i-j);
}
}
return f[n];
}
}
// 牛客
// 运行时间：12ms
// 占用内存：9732k
public class Solution {
public int cutRope(int n) {
if (n < 2) // 题目已经说了会大于等于2，但还是习惯了写这个
return 0;
int[] f = new int[n + 1];
f[1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
if (f[j] <= j && f[i] < j*(i-j))
f[i] = j*(i-j);
if (f[j] > j && f[i] < f[j]*(i-j))
f[i] = f[j]*(i-j);
}
}
return f[n];
}
} //////////////////////////// 贪心算法 /////////////////////////////
// 需要记住的是：这类问题尽可能拆分出长度为3的绳子，
// 直到拆不出3，那就拆分成2，此时的总乘积就是最大的
// 力扣
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.5 MB, 在所有 Java 提交中击败了33.21%的用户
class Solution {
public int cuttingRope(int n) {
if (n < 2)
return 0;
if (n == 2)
return 1;
if (n == 3)
return 2;
int to3 = n / 3; // n/3，表示n中分理出to3这么多个3
// n如果能被3整除，那么to3=n/3, to3*3=n,所以n-to3*3==0
// 如果n不能被3整除，n-to3即为n/3的余数
// 如果n/3余数为1，则to3减1
// 如果n/3余数为2，则to3不变。（n/3，余数要么是1要么是2）
if (n - to3 * 3 == 1)
to3--;
// 如果n/3的余数(n - to3*3)为1,to3减1相当于放回一个3给(n - to3*3)
// 此时(n - to3*3)=4
// 如果n/3的余数(n - to3*3)为2，则to3不变，(n - to3*3)=2
int to2 = (n - to3 * 3) / 2;
// 分离好了2和3，直接返回3^to3 * 2^to2(to3个3相乘，乘to2个2相乘)
return (int) (Math.pow(3, to3)) * (int) (Math.pow(2, to2));
}
}
// 牛客
// 运行时间：12ms
// 占用内存：9716k
public class Solution {
public int cutRope(int n) {
if (n < 2)
return 0;
if (n == 2)
return 1;
if (n == 3)
return 2;
int to3 = n / 3;
if (n - to3 * 3 == 1)
to3--;
int to2 = (n - to3 * 3) / 2;
return (int) (Math.pow(3, to3)) * (int) (Math.pow(2, to2));
}
} 【剑指offer】14.2. 剪绳子 II
题目描述：
// 给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整
// 数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m - 1] 。请问
// k[0]*k[1]*...*k[m - 1] 可能的最大乘积是多少？例如，当绳子的长度
// 是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
// 答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，
// 请返回 1。 题解：
///// 贪心算法 //////
// 思路和剪绳子 I一样的，但是需要把过程分离，
// 每次乘3或乘2都要检查一下是否溢出
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.2 MB, 在所有 Java 提交中击败了81.56%的用户
class Solution {
public int cuttingRope(int n) {
if (n < 4) {
return n - 1;
}
else if (n == 4) {
return n;
}
long res = 1;;
while (n > 4) {
res *= 3;
res %= 1000000007;
n -= 3;
}
return (int) (res*n%1000000007);
}
} 特殊解——动态规划 ：
【剑指offer】46. 把数字翻译成字符串
题目描述:
// 46. 把数字翻译成字符串
// 力扣
// 给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，
// 1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可
// 能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同
// 的翻译方法。 题解：
/////////////////////////////////// 动态规划 ////////////////////////
// 力扣
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：35.2 MB, 在所有 Java 提交中击败了66.89%的用户
class Solution {
public int translateNum(int num) {
// num转为String类型用于遍历num中每个数字，记为s。
// 之后所有操作都基于s。
String s = Integer.toString(num);
if (s == null || s.length() == 0)
return 0;
int len = s.length(); // 取s长度
// dp数组，根据s[i-2]和s[i-1]（实际没有s[i-2]和s[i-1]）判断dp[i]
// 比如dp[2]表示s中前两个元素的组合数
int[] dp = new int[len + 1];
dp[0] = 1; // 初始化
dp[1] = 1;
for (int i = 2; i <= len; i++) {
// 结合s[i-2]和s[i-1]的情况（记为temp），
// 用dp[i-2] dp[i-1]来判断dp[i]
String temp = s.substring(i - 2, i);
// 如果temp中数字大于10，小于25，说明可以组合
// dp[i]为dp[i - 2]和dp[i - 1]之和。
if (temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
dp[i] = dp[i - 2] + dp[i - 1];
else
dp[i] = dp[i - 1]; // 否则不能组合，无法新增组合数
}
return dp[len]; // 最后返回dp结果，后一状态取决于前一状态，尾
// 元素即为最终状态
}
}
// 力扣
// 简略写法
// 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
// 内存消耗：34.9 MB, 在所有 Java 提交中击败了97.16%的用户
class Solution {
public int translateNum(int num) {
String s = Integer.toString(num);
if (s == null || s.length() == 0)
return 0;
int len = s.length();
int[] dp = new int[len + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= len; i++) {
String temp = s.substring(i - 2, i);
dp[i] = temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0 ? dp[i-2] + dp[i-1] : dp[i-1];
}
return dp[len];
}
}