Java算法练习1

2023-12-13 17:59:47

题目来自于leetcode

12.03 递归乘法

递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。

示例1:

 输入:A = 1, B = 10
 输出:10

示例2:

 输入:A = 3, B = 4
 输出:12

提示:

  1. 保证乘法范围不会溢出
//递归乘法。 写一个递归函数,不使用 * 运算符, 实现两个正整数的相乘。可以使用加号、减号、位移,但要吝啬一些。
//法一:累加
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
  • 转换 #1262124 ? 2 + 6 + 2 + 1 + 2 + 4 ? 17
  • 转换 #217 ? 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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。