题目汇总https://leetcode-cn.com/tag/math/
423. 从英文中重建数字中等[✔]
441. 排列硬币简单[✔]
453. 最小移动次数使数组元素相等简单[✔]
458. 可怜的小猪困难（不做了吧）
462. 最少移动次数使数组元素相等 II中等[✔]
478. 在圆内随机生成点中等（不做了吧，题解只有20）
483. 最小好进制困难（不做了吧，题解只有20）
507. 完美数简单[✔]
517. 超级洗衣机困难（不做了吧，题解只有16）
423. 从英文中重建数字中等
给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字
0-9。按升序输出原始的数字。
注意:
- 输入只包含小写英文字母。
- 输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
- 输入字符串的长度小于 50,000。
示例 1:
输入: "owoztneoer"
输出: "012" (zeroonetwo)
示例 2:
输入: "fviefuro"
输出: "45" (fourfive)
思路：
class Solution {//执行用时：4 ms, 在所有 Java 提交中击败了99.20%的用户，2020/07/26
public String originalDigits(String s) {
char[] count = new char[26 + (int)'a'];
for(char letter: s.toCharArray()){
count[letter]++;
}
int[] out = new int[10];
out[0] = count['z']; //'z'只出现在数字 0 中
out[2] = count['w']; //'w'只出现在数字 2 中
out[4] = count['u']; //'u'只出现在数字 4 中
out[6] = count['x']; //'x'只出现在数字 6 中
out[8] = count['g']; //'g'只出现在数字 8 中
out[3] = count['h'] - out[8]; //'h'只出现在数字 8 和 3 中
out[5] = count['f'] - out[4]; //'f'只出现在数字 4 和 5 中
out[7] = count['s'] - out[6]; //'s'只出现在数字 6 和 7 中
out[9] = count['i'] - out[5] - out[6] - out[8];//'i'只出现在数字 5、6 和 8 中
out[1] = count['n'] - out[7] - 2 * out[9];
StringBuilder output = new StringBuilder();
for(int i = 0; i < 10; i++){
for(int j = 0; j < out[i]; j++){
output.append(i);
}
}
return output.toString();
}
}
441. 排列硬币简单
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内
（-2,147,483,648 到 2,147,483,647 ）
示例 1:
n = 5
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤
因为第三行不完整，所以返回2.
示例 2:
n = 8
硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
因为第四行不完整，所以返回3.
思路一：迭代
class Solution {//执行用时：13 ms, 在所有 Java 提交中击败了9.61%的用户，2020/07/26
public int arrangeCoins(int n) {
if(n == 1) return 1;
long sum = 0;//如果是int存储sum并且n很大的话，会溢出的，所以用long存储sum
int i;
for(i = 1; i < n; i++){
sum += i;
if(sum > n){
break;
}
}
return i - 1;
}
}
思路二：等差数列
利用前 n 项和公式 sum = n(n+1)/2
对于这道题而言，是x(x+1)/2 = n,x2+x-2n=0，对一元二次方程的结果取整。
class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户，2020/07/26
public int arrangeCoins(int n) {
double res = (-1 + Math.sqrt(1 + 8 * (long)n)) / 2;
return (int) res;
}
}
思路三：二分查找
453. 最小移动次数使数组元素相等简单
给定一个长度为 n 的非空整数数组，找到让数组所有元素相等的最小移动次数。每次移动将会使 n - 1 个元素增加 1。
示例:
输入:[1,2,3]
输出:3
解释:
只需要3次移动（注意每次移动会增加两个元素的值）：
[1,2,3] => [2,3,3] => [3,4,3] => [4,4,4]
思路：
典型的数学题，还是看了评论区的解答：假设目前数组总和为sum，我们需要移动次数为m，那么整体数组总和将会增加m × (n - 1)，这里的n为数组长度，最后数组所有元素都相等为x，于是有：
sum + m × (n - 1) = x × n (1)
我们再设数组最小的元素为min_val，m = x - min_val，即 x = m + min_val带入(1)得：m = sum - min_val * n
class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了100.00%的用户,2020/07/26
public int minMoves(int[] nums) {
int min = Integer.MAX_VALUE;
for(int i=0;i<nums.length;i++){
if(min > nums[i]){
min = nums[i];
}
}
int res = 0;
for(int i=0;i<nums.length;i++){
res += nums[i] - min;
}
return res;
}
}
462. 最少移动次数使数组元素相等 II中等
给定一个非空整数数组，找到使所有数组元素相等所需的最小移动数，其中每次移动可将选定的一个元素加1或减1。 您可以假设数组的长度最多为10000。
例如:
输入:
[1,2,3]
输出:
2
说明： 只有两个动作是必要的（记得每一步仅可使其中一个元素加1或减1）：
[1,2,3] => [2,2,3] => [2,2,2]
思路：排序找中位数
其实就是求中位数，证明过程评论区很多大佬讲到了，很清楚。
class Solution {//执行用时：4 ms, 在所有 Java 提交中击败了37.79%的用户,2020/07/27
public int minMoves2(int[] nums) {
Arrays.sort(nums);
int sum = 0;
for(int num : nums){
sum += Math.abs(nums[nums.length / 2] - num);
}
return sum;
}
}
507. 完美数简单
对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”。
给定一个 **整数 **n， 如果他是完美数，返回True，否则返回False
示例：
输入: 28
输出: True
解释: 28 = 1 + 2 + 4 + 7 + 14
提示：
输入的数字n不会超过 100,000,000. (1e8)
思路一：暴力法，会超时 !
class Solution {
public boolean checkPerfectNumber(int num) {
int sum = 0;
for(int i=1;i<num;i++){
if(num % i == 0){
sum += i;
}
}
return sum == num;
}
}
思路二：优化的暴力法
正因子必然是成对出现的，故而我们只需要遍历到 num 的平方根即可
class Solution {//执行用时：1 ms, 在所有 Java 提交中击败了90.51%的用户,2020/07/27
public boolean checkPerfectNumber(int num) {
if(num == 1)
return false;
int sum = 1;
for(int i = 2; i * i < num; i++){
if(num % i == 0){
sum += i;
sum += num / i;//成对出现的因子
}
}
return sum == num;
}
}
思路三：投机取巧
完美数只有 6, 28, 496, 8128, 33550336 这几个，可以通过判断该数字是否为以下几个来解决
class Solution {//执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户,2020/07/27
public boolean checkPerfectNumber(int num) {
switch(num){
case 6:
case 28:
case 496:
case 8128:
case 33550336:
return true;
}
return false;
}
}
网友评论