【算法】【优选算法】字符串

发布于:2024-12-07 ⋅ 阅读:(122) ⋅ 点赞:(0)


一、14.最⻓公共前缀

题目链接:14.最⻓公共前缀
题目描述:

解题思路:

  • 思路一:
    • 我们直接两两求一下公共前缀,记录在ret字符串中,然后ret与后续继续求公共前缀,最后的ret就是结果
    • 求公共前缀,我们就求一下在字符串中的公共前缀的最后一个字符 的下一个下标即可。
  • 思路二:
    • 我们就将第一个字符串作为基准,遍历字符串,每个字符再与字符串数组中剩下的字符串,对应下标的字符比较即可。
    • 当超出某个字符串长度或者字符不同了,就可以返回了。
    • 最后第一个字符串都遍历完了,还没找到,那么第一个字符串就是结果。

解题代码:

思路一:
//时间复杂度:O(m*n)
//空间复杂度:O(1)
class Solution {
    public String longestCommonPrefix(String[] strs) {
        //两两比较
        String ret = strs[0];
        for(int i = 1; i < strs.length; i++) {
            ret = commonPrefix(ret, strs[i]);
        }
        return ret;
    }
    //返回两个字符串的公共前缀
    public String commonPrefix(String s1, String s2) {
        int last = 0;
        while(last < s2.length() && last < s1.length() && s2.charAt(last) == s1.charAt(last)) last++;
        return s1.substring(0,last);
    }
}
思路一:
//时间复杂度:O(m*n)
//空间复杂度:O(1)
class Solution {
    public String longestCommonPrefix(String[] strs) {
        //一起比较
        for(int i = 0; i < strs[0].length(); i++) {
            char ch  = strs[0].charAt(i);
            for(int j = 1; j < strs.length; j++) {
                if(i >= strs[j].length() || ch != strs[j].charAt(i))
                    return strs[0].substring(0,i);
            }
        }
        return strs[0];
    }
}

二、5.最⻓回⽂⼦串

题目链接:5.最⻓回⽂⼦串
题目描述

解题思路:

  • 中⼼扩散:从回⽂串的中⼼开始,往左读和往右读。从中⼼向两边扩展,如果两边的字⺟相同,我们就可以继续扩展;如果不同,我们就停⽌扩展。
  • 我们还需要将回文子串的长度是奇数和偶数都要考虑。

解题代码:

//时间复杂度:O(n^2)
//空间复杂度:O(1)
class Solution {
    public String longestPalindrome(String s) {
        String ret = "";
        for(int i = 0; i < s.length(); i++) {
            //奇数长度
            int left = i;
            int right = i;
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if(right - left - 1 > ret.length()) ret = s.substring(left+1, right);

            //偶数长度
            left = i;
            right = i+1;
            while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            }
            if(right - left - 1 > ret.length()) ret = s.substring(left+1, right);
        }
        return ret;
    }
}

三、67.⼆进制求和

题目链接:67.⼆进制求和
题目描述:

题目解析:

解题思路:

  • 模拟竖式加法过程,从后向前遍历两个字符串,
  • 定义一个变量,将对应位的相加,和对2取余就是结果对应位的数字,考虑进位就是除以2
  • 当两个字符串都遍历结束,并且变量为0,就得到了结果逆序后的字符串了
  • 最后逆序返回就可以

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(1)
class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ret = new StringBuffer();
        int cruA = a.length() - 1;
        int cruB= b.length() - 1;
        int tmp = 0;
        while(cruA >= 0 || cruB >= 0 || tmp != 0) {
            if(cruA >= 0) tmp += a.charAt(cruA--) - '0';
            if(cruB >= 0) tmp += b.charAt(cruB--) - '0';
            ret.append((char)(tmp % 2 + '0'));
            tmp /= 2; 
        }
        return ret.reverse().toString();
    }
}

四、43.字符串相乘

题目链接:43.字符串相乘
题目描述:

题目解析:

  • 就相当于每个字符串就是一个数,让我们求乘积,乘积也放在字符串中。

解题思路:

  • 还是使用小学的竖式运算规则,
  • 但是有所不同的是,我们先不进位(就是如果3*8=24,先不进2),在最后的结果中来进位。
  • 我们竖式计算过程是从末尾先开始的,所以我们先将两个字符串逆序。
  • 通过竖式计算过程,每个位计算结果在结果中的下标就是原来两个字符串的下标之和
  • 在进位的时候,我们只需要将每位数字 ,除以10的结果记录在一个变量中,然后这个变量就是进位的数。
  • 现在得到的结果还可能会有前导零:前导零就是指152 * 0 = 000 这就有两个前导零。
  • 由于现在的结果是逆序的,所以从最后开始检验,有就删,注意极端情况全为0的时候,还要保留一位。

解题代码:

//时间复杂度:O(n)
//空间复杂度:O(n)
class Solution {
    public String multiply(String num1, String num2) {
        int[] arr = new int[num1.length() + num2.length()-1];

        //逆序
        char[] n1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] n2 = new StringBuffer(num2).reverse().toString().toCharArray();


        //无进位相乘,相加
        for(int i = 0; i < n1.length; i++) {
            for(int j = 0; j < n2.length; j++) {
                arr[i+j] += (n1[i] - '0') * (n2[j] - '0'); 
            }
        }
        // 进位
        int tmp = 0;
        int cur = 0;
        StringBuffer ret = new StringBuffer();
        while(cur < arr.length || tmp > 0) {
            if(cur < arr.length) tmp += arr[cur++];
            ret.append((char)(tmp % 10 + '0'));
            tmp /= 10;
        }
        //处理前导零
        while(ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') ret.deleteCharAt(ret.length() - 1);

        return ret.reverse().toString();
    }
}

网站公告

今日签到

点亮在社区的每一天
去签到