【算法】每日一题——奇怪的算法（1）

三三是该溜子

发布于 2025-02-17 15:16:50

3600

代码可运行

文章被收录于专栏：该溜子的专栏该溜子的专栏

运行总次数：0

代码可运行

一：快乐数

双指针优秀解法：

class Solution1{
    public static int sumResult(int n ){
        int sum = 0;
        while( n != 0){
            sum += Math.pow(n%10 , 2);
            n = n/10;
        }
        return sum;
    }
    public boolean isHappy(int n){
        int slow = n , fast = sumResult(n);
        while(slow != fast){
            slow = sumResult(slow);
            fast = sumResult(sumResult(fast));
        }
        return slow == 1;
    }
}

哈希表代码又臭又长解法：

class Solution {
    public boolean isHappy(int n) {
        Map<Integer, Integer> map = new HashMap<>();
        boolean sign = true;
        int result = n;
        while (sign) {
            while (true) {
                result = calculate(result);
                if (result == 1)
                    return true;
                if (!map.containsKey(result)) {
                    map.put(result, 0);
                } else {
                    break;
                }
            }
            sign = false;
        }
        return false;
    }

    // 封装一个方法计算这个数的各个位的平方和，每次模10
    public int calculate(int n) {
        int ret = 0;
        while (n != 0) {
            int tem = n % 10;
            ret += Math.pow(tem, 2);
            n = n / 10;
        }
        return ret;
    }
}

二：字符串中的第一个唯一字符

387. 字符串中的第一个唯一字符

class Solution {
    public int firstUniqChar(String s) {
        int n = s.length();
        Map<Character,Integer> map = new HashMap<>();
        for(int i = 0 ; i < n  ; i++){
            char ch = s.charAt(i);
            map.put(ch , map.getOrDefault(ch,0) + 1);
        }

        for(int i = 0 ; i < n ; i++){
            int nums = map.get(s.charAt(i));
            if(nums == 1){
                return i;
            }
        }
        return -1;
    }
}

三：仅仅反转字母

思路一：

1：第一次遍历s把非字母扔进数组中

2：第二次遍历s，把字母进栈

3：出栈填充数组

麻烦！~！~

思路二：

1：双指针，left和right双指针形成包夹之势，遇到非字母就跳过

但是，不掌握Character.isLetter()这个方法，写代码就会超级啰嗦！！！~！！！！

思路一：

class Solution {
    public String reverseOnlyLetters(String s) {
        int n = s.length();
        char[] str = new char[n];
        for(int i = 0 ; i < n ; ){
            char ch = s.charAt(i);
            if( (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ){
                i++;
            }else{
                str[i] = ch;
                i++;
            }
        }
        Stack<Character> stack = new Stack<>();
        for(int i = 0 ; i < n ; ){
            char ch = s.charAt(i);
            if( (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') ){
                stack.add(ch);
                i++;
            }else{
                i++;
            }
        }
       
        for(int i = 0 ; i < n ; ){
            if(!stack.isEmpty() && str[i] == 0){
                str[i] = stack.pop();
                i++;
            }else{
                i++;
            }
        }
        StringBuilder builder = new StringBuilder();
        for(char ch : str){
            builder.append(ch);
        }
        return builder.toString();
    }
}

思路二：

class Solution {
    public String reverseOnlyLetters(String s) {
        int n = s.length();
        int left = 0, right = n - 1;
        char[] str = s.toCharArray();
        while (left < right) {
            while ((left < right && left < n - 1) && (s.charAt(left) < 'A'
                    || (s.charAt(left) > 'Z' && s.charAt(left) < 'a') || s.charAt(left) > 'z')) {
                left++;
            }
            while ((left < right && left < n - 1) && (s.charAt(right) < 'A'
                    || (s.charAt(right) > 'Z' && s.charAt(right) < 'a') || s.charAt(right) > 'z')) {
                right--;
            }
            if (left < right) {
                swap(str, left, right);
                left++;
                right--;
            }
        }
        return String.valueOf(str);
    }

    public void swap(char[] str, int left, int right) {
        char tmp = str[left];
        str[left] = str[right];
        str[right] = tmp;
    }

}

代码优化

class Solution {
    public String reverseOnlyLetters(String s) {
        int left = 0, right = s.length() - 1;
        char[] str = s.toCharArray();
        
        while (left < right) {
            // 左指针向右移动，直到找到字母
            if (!Character.isLetter(str[left])) {
                left++;
                continue;
            }
            
            // 右指针向左移动，直到找到字母
            if (!Character.isLetter(str[right])) {
                right--;
                continue;
            }
            
            // 交换字母
            char temp = str[left];
            str[left] = str[right];
            str[right] = temp;
            
            // 移动指针
            left++;
            right--;
        }
        
        return new String(str);
    }
}

四：验证回文串

LCR 019. 验证回文串 II

这道题我直接破防

看看这个用例：要分类讨论，看舍弃左边的字母或者右边的字母两种都得判断一下！！！

class Solution {
    public boolean validPalindrome(String s) {
        int n = s.length();
        int left = 0 , right = n - 1;
        while(left < right){
            char ch1 = s.charAt(left);
            char ch2 = s.charAt(right);
            
            if(ch1 == ch2){
                left++;
                right--;
            }else{
                break;
            }
        }
        boolean result1 =   validPalindrome2(s,left+1,right);
        boolean result2 =   validPalindrome2(s,left,right-1);
        if(result1 == false && result2 == false){return false;}
        return true;
        
        
    }
    public boolean validPalindrome2(String s,int left,int right){
        while(left < right){
            char ch1 = s.charAt(left);
            char ch2 = s.charAt(right);
            
            if(ch1 == ch2){
                left++;
                right--;
            }else{
                return false;
            }
        }
        return true;
    }
    
}

五：x的平方根

LCR 072. x 的平方根

心得感悟：

1：夹逼准则，注意使用long

2：Math.pow(double a, double b)用于计算 a 的 b 次幂，返回值类型是 double。

3：开任意次方：通过 Math.pow() 方法实现开任意次方的运算。将待开方的数作为底数，1 除以开方次数作为指数，即可得到开方结果。

3：思路二，使用开方Math.sqrt()，“square root” 翻译为中文是 “平方根”。

class Solution {
    public int mySqrt(int x) {
        long i = 0;
        long result = 0;
        while(true){
            long num1 = (long)Math.pow(i,2);
            long num2 = (long)Math.pow(i+1,2);
            if(num1 <= x && num2 > x){
                result = i;
                break;
            }else{
                i++;
            }
        }
        return (int)result;

    }
}

六：宝石与石头

class Solution {
    public int numJewelsInStones(String jewels, String stones) {
        Map<Character,Integer> mapJ = new HashMap<>();
        Map<Character,Integer> mapS = new HashMap<>();
        int n1 = jewels.length() , n2 = stones.length();
        for(int i = 0 ; i < n1 ; i++){
            char ch1 = jewels.charAt(i);
            mapJ.put(ch1,mapJ.getOrDefault(ch1,0)+1);
        }
        for(int i = 0 ; i < n2 ; i++){
            char ch1 = stones.charAt(i);
            mapS.put(ch1,mapS.getOrDefault(ch1,0)+1);
        }
        int result = 0;
        for(Map.Entry<Character,Integer> entry : mapS.entrySet()){
            char tmp = entry.getKey();
            if(mapJ.containsKey(tmp)){
                result += mapS.get(tmp);
            }
        }
        return result;
    }
}

七：快乐数

202. 快乐数

class Solution {
    public boolean isHappy(int n) {
        Map<Integer,Integer> map = new HashMap<>();
        int tmp = n;
        while(true){
            tmp = calculate(tmp);
            if(tmp == 1){
                return true;
            }else if(map.containsKey(tmp)){
                return false;
            }else{
                map.put(tmp,0);
            }
        }
    }
    public int calculate(int n){
        int result = 0;
        while(n != 0){
            int tmp = n % 10;
            result += Math.pow(tmp,2);
            n = n / 10;
        }
        return result;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-02-16，如有侵权请联系 cloudcommunity@tencent.com 删除

算法