Java算法练习1
2023-12-13 17:59:47
题目来自于leetcode
Java算法练习
12.03 递归乘法
递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。
示例1:
输入:A = 1, B = 10 输出:10
示例2:
输入:A = 3, B = 4 输出:12
提示:
- 保证乘法范围不会溢出
//递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。
//法一:累加
class Solution {
public int multiply(int A, int B) {
if(A > B){ //此步的目的是简化算法,防止栈溢出,让加法次数减少
int temp = A;
A = B;
B = temp;
}
if(A == 1) return B; //递归退出条件
else {
while(A-- > 1){
return B + multiply(A , B);
}
}
return -1;
}
}
//法二:位运算
class Solution {
public int multiply(int A, int B) {
if(A > B){ // 保证参数B大,减少递归操作
int temp = A;
A = B;
B = temp;
}
if(A == 1) return B;
//&&和&都可以表示逻辑与,但他们是有区别的,共同点是他们两边的条件都成立的时候最终结果才是true;
//不同点是&&只要是第一个条件不成立为false,就不会再去判断第二个条件,最终结果直接为false,而&判断的是所有的条件;
if((A & 1)==1){//当A为奇数时执行,保证位运算精度不会丢失
return multiply(A >> 1,B << 1) + B; //A向右移一位相当于除于2,B向左移一位相当于乘2
}
return multiply(A >> 1 ,B <<1);
}
}
12.04 实现 pow(x, n) ,即计算 x
的整数 n
次幂函数(即,xn
)
实现 pow(x, n) ,即计算
x
的整数n
次幂函数(即,xn
)。示例 1:
输入:x = 2.00000, n = 10 输出:1024.00000
示例 2:
输入:x = 2.10000, n = 3 输出:9.26100
示例 3:
输入:x = 2.00000, n = -2 输出:0.25000 解释:2-2 = 1/22 = 1/4 = 0.25
//法一
class Solution {
public double myPow(double x, int n) {
long N = n; //防止int溢出
return N >= 0 ? mul(x, N) : mul(1.0 / x, -N);
}
public double mul(double x ,long N){
double num = 1;
while(N > 0){
if((N % 2) == 1){
num = num * x;
}
x *= x;
N /= 2;
}
return num;
}
}
//法二
class Solution {
public double myPow(double x, int n) {
long N = n;
return N >= 0 ? mul(x, N) : mul(1.0 / x, -N);
}
public double mul(double x ,long N){
if (N == 0) {
return 1.0;
}
double y = mul(x, N / 2);
return N % 2 == 0 ? y * y : y * y * x;
}
}
12.05 字符串转化后的各位数字之和
给你一个由小写字母组成的字符串
s
,以及一个整数k
。首先,用字母在字母表中的位置替换该字母,将
s
转化 为一个整数(也就是,'a'
用1
替换,'b'
用2
替换,…'z'
用26
替换)。接着,将整数 转换 为其 各位数字之和 。共重复 转换 操作k
次 。例如,如果
s = "zbax"
且k = 2
,那么执行下述步骤后得到的结果是整数8
:
- 转化:
"zbax" ? "(26)(2)(1)(24)" ? "262124" ? 262124
- 转换 #1:
262124 ? 2 + 6 + 2 + 1 + 2 + 4 ? 17
- 转换 #2:
17 ? 1 + 7 ? 8
返回执行上述操作后得到的结果整数。
//区别是:由于字符串拼接耗时不同采用StringBuilder更快
//法一:
class Solution {
public int getLucky(String s, int k) {
char[] arr = s.toCharArray();
int sum = 0;
String str = "";
for(int i = 0;i < arr.length;i++){
str += arr[i] - 96 + "";
}
for(char c :str.toCharArray()){
sum += c -'0';
}
int endSum = sum;
while(k-- > 1){
endSum = 0;
while(sum > 0){
endSum += sum % 10;
sum /= 10;
}
sum = endSum;
}
return endSum;
}
}
//法二
class Solution {
public int getLucky(String s, int k) {
char[] arr = s.toCharArray();
int sum = 0;
StringBuilder str = new StringBuilder();
for(int i = 0;i < arr.length;i++){
str.append(arr[i] - 96);
}
String s1 = str.toString();
for(char c :s1.toCharArray()){
sum += c -'0';
}
int endSum = sum;
while(k-- > 1){
endSum = 0;
while(sum > 0){
endSum += sum % 10;
sum /= 10;
}
sum = endSum;
}
return endSum;
}
}
12.06 最大数
给定一组非负整数
nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。**注意:**输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
输入:nums = [10,2] 输出:"210"
示例 2:
输入:nums = [3,30,34,5,9] 输出:"9534330"
class Solution {
public String largestNumber(int[] nums) {
StringBuilder str = new StringBuilder();
Integer[] numsArr = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
numsArr[i] = nums[i];
}
Arrays.sort(numsArr,new Comparator<Integer>(){
public int compare(Integer num1,Integer num2){
int n1 = num1;
int n2 = num2;
StringBuilder str1 = new StringBuilder();
StringBuilder str2 = new StringBuilder();
str1.append(n1);
str1.append(n2);
str2.append(n2);
str2.append(n1);
if(str1.toString().compareTo(str2.toString()) > 0) {
return -1;
}
else return 1;
}
});
for(int num : numsArr) {
str.append(num);
}
return str.toString().startsWith("0") ?"0":str.toString();
}
}
12.07 各位相加
给定一个非负整数
num
,反复将各个位上的数字相加,直到结果为一位数。返回这个结果。示例 1:
输入: num = 38 输出: 2 解释: 各位相加的过程为: 38 --> 3 + 8 --> 11 11 --> 1 + 1 --> 2 由于 2 是一位数,所以返回 2。
示例 2:
输入: num = 0 输出: 0
//法一
class Solution {
public int addDigits(int num) {
int endNum = num;
while(endNum > 9 ){
num = endNum;
endNum = 0;
while(num > 0){
endNum += num % 10;
num /= 10;
}
}
return endNum;
}
}
//法二
class Solution {
public int addDigits(int num) {
return (num - 1) % 9 +1 ;
}
}
12.08快乐数
编写一个算法来判断一个数
n
是不是快乐数。「快乐数」 定义为:
- 对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1,那么这个数就是快乐数。
如果
n
是 快乐数 就返回true
;不是,则返回false
。示例 1:
输入:n = 19 输出:true 解释: 12 + 92 = 82 82 + 22 = 68 62 + 82 = 100 12 + 02 + 02 = 1
示例 2:
输入:n = 2 输出:false
class Solution {
public boolean isHappy(int n) {
Set h = new HashSet<Integer>();
int num = 0;
while(num != 1){
num = 0;
while(n > 0){
num += (n % 10) * (n % 10);
n /= 10;
}
if(h.contains(num)) return false;
h.add(num);
n = num;
}
return true;
}
}
文章来源:https://blog.csdn.net/m0_59167353/article/details/134898167
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!