百度智能小程序怎么优化排名,嘉兴网站排名优化报价,wordpress 数据库搬家,网站做多大的宽高介绍
枚举算法也叫暴力算法#xff0c;是一种简单直接的问题求解方法#xff0c;它通过逐一列举问题的所有可能解#xff0c;并检查每个可能解是否符合问题的条件#xff0c;直到找到正确的解或者遍历完所有可能的情况。 对于一个问题#xff0c;首先确定解的范围#x…介绍
枚举算法也叫暴力算法是一种简单直接的问题求解方法它通过逐一列举问题的所有可能解并检查每个可能解是否符合问题的条件直到找到正确的解或者遍历完所有可能的情况。 对于一个问题首先确定解的范围然后在这个范围内逐个尝试所有可能的值例如在寻找一个整数 n 的所有因数时枚举算法会从1开始逐个检查到 n 判断每个数是否能整除 n 。
枚举几乎可以用于解决任何类型的问题只要能够确定解的范围但缺点也很明显当问题规模增大时需要检查的可能解数量会迅速增加这会导致程序运行效率低下为了克服枚举算法的这个缺点需要对其进行优化通过数学推导发现问题的规律减少不必要的计算。
题目1
对于给定的整数 n需进行如下判断若存在三个不同的正整数当它们分别与特定整数相乘时结果均为 n则返回 true若无法找到这样恰好三个正整数满足该情形便返回 false。 举例而言设存在整数 k若 n k * m这里的 m 即为 n 的一个除数。当 n 2 时仅能以 1×2 表示即其除数只有 1 和 2所以此情形下应返回 false而当 n 4 时可写成 1×4 与 2×2其除数有 1、2 和 4这种情况下则返回 true。
解题思路
从1到 n 遍历每个数字 i满足条件能整除三次就返回true。
代码实现
public class Main {public boolean isThree(int n) {int count 0;for (int i 1; i n; i) {if (n % i 0) {count;}}return count 3;}public static void main(String[] args) {boolean result new Main().isThree(4);System.out.println(result);}
}检查 n 是否能被 i 整除如果可以那么 i 就是 n 的一个除数将count 加1全部执行完成后检查 count 是否等于3如果是则返回 true 否则返回 false 。
优化思路
当一个数有三个除数时它一定不是质数 对于每个 p 检查 n 是否可以整除p如果是那么 n 就有三个除数1、 p 、 n 。
public class Main {public boolean isThree(int n) {if(n3){return false;}for(int p2;p*pn;p){if(n%p0){return true;}}return false;}public static void main(String[] args) {boolean result new Main().isThree(11);System.out.println(result);}
}
从2开始遍历到 n如果它有平方根p那么返回 true如果遍历完都没有找到这样的 p 则返回 false 。
(取自leedcode1952)
题目2
给定一个正整数 n返回 连续正整数满足所有数字之和为 n 的组数 。
示例 1:输入: n 5 输出: 2 解释: 5 2 3共有两组连续整数([5],[2,3])求和后为 5。
示例 2:输入: n 9 输出: 3 解释: 9 4 5 2 3 4
示例 3:输入: n 15 输出: 4 解释: 15 8 7 4 5 6 1 2 3 4 5
解题思路
可以采取等差数列的公式如果存在它的等差数列就将总数加1。
代码实现
public class Main {public static void main(String[] args) {int result Sum(15);System.out.println(result);}public static int Sum(int n) {int count 0;n *2;for (int i 1; i * i n; i) {if (n % i ! 0) {continue;}int a n / i - i 1;boolean res a % 2 0;if (res) {count;}}return count;}
}
对于连续正整数序列a,a 1,a2 , a 3 , ak其和S(2a k)(k 1)/2我们要推导出2a。 将等式两边同时乘以2得到2S(2a k)(k 1)。 所以2a 2S - k(k 1) / k 1将项数减去 1就是 2a 2S - k(k - 1) / k 也就是2a 2S/ k - k 1演变成我们公式里的 n*2int a n / i - i 1; 和 a % 2 0; 即可得出答案
取自leedcode829 题目3
给定一个非负的整数变量 num需确定是否存在这样一个非负整数 k使得 k 与其各位数字反转后所形成的整数相加的结果恰好等于 num若存在这样的 k则返回 true若不存在则返回 false。
解题思路
枚举从零到num的所有k数判断它们反转相加的结果是否等于 num。
示例
输入num 443 输出true 解释172 271 443 所以返回 true。
输入num 63 输出false 解释63 不能表示为非负整数及其反转后数字之和返回 false 。
代码实现
public class Main {public static void main(String[] args) {int num 443;boolean flag true;for (int i 0; i num; i) {int rev reverseNumber(i);if (revinum) {flag false;}}if (flag) {System.out.println(false);}else {System.out.println(true);}}public static int reverseNumber(int n) {int rev 0;while (n ! 0) {rev rev * 10 n % 10;n / 10;}return rev;}
}
在以上代码中使用了 for 循环从0开始每次递增1直到 i 小于num在每次循环中 都调用了reverseNumber 方法对当前的整数 i 进行反转然后判断rev i是否等于num如果相等说明找到了满足条件的整数 i 此时将flag的值设置为false。
(取自leedcode2443)
以上就是枚举的应用示例在实际应用中对于复杂或大规模问题通常需要结合问题特性对枚举进行优化如利用数学规律减少不必要的枚举次数或者借助更高效的数据结构来存储和处理数据以提升效率。总之枚举是算法学习的重要基石理解其优劣有助于在不同场景下合理运用或优化算法为解决更复杂的编程和数学问题奠定基础。
