【算法】五道大学生必备平价精致小众松弛感宝藏好题平替x

​ 刚学了Java就想用来写算法题的我：

​ 借着几道算法题，熟悉一下Java中Stack类，String类的用法。

925.长按键入

原题链接：

925. 长按键入

​ 用来测试与练习String类自带的方法，具体思路就是双指针遍历，若相同则向前移动，不同时判断是否是长按输入，若不是，返回false，若是，继续向下判断。

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int i = 0, j = 0;
        while (j < typed.length()) {
            if (i < name.length() && typed.charAt(j) == name.charAt(i)) {
                i++;
                j++;
            } else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) {
                j++;
            } else {
                return false;
            }
        }
        return i == name.length();
    }
}

SN	方法描述
1	char charAt(int index) 返回指定索引处的 char 值。
2	int length() 方法用于返回字符串的长度。

844.比较含退格的字符串

原题链接：

844. 比较含退格的字符串

​ 本题作为对Java的stack类的上手题放入其中，真正遇到这样的题，建议使用模拟栈直接进行操作，此处使用Stack类进行操作。

​ 解题思想很简单，遇到字符入栈，遇到井号将栈顶字符出栈即可。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack<Character> sst = new Stack<Character>();
        Stack<Character> tst = new Stack<Character>();
        int i = 0;
        while(i != s.length()){
            if(s.charAt(i) != '#'){
                sst.push(s.charAt(i));
                i++;
                continue;
            }else{
                if(sst.empty()){
                    i++;
                    continue;
                }else{
                    sst.pop();
                    i++;
                }
            }
        }
        i = 0;
        while(i != t.length()){
            if(t.charAt(i) != '#'){
                tst.push(t.charAt(i));
                i++;
                continue;
            }else{
                if(tst.empty()){
                    i++;
                    continue;
                }else{
                    tst.pop();
                    i++;
                }
            }
        }
        while(!sst.empty() && !tst.empty()){
            if(sst.pop() != tst.pop()){
                return false;
            }
        }
        if(!sst.empty() || !tst.empty()){
            return false;
        }
        return true;
    }
}

​ 第一次接触Stack类，这里做一些小笔记吧。

​ 创建栈对象的指令：

Stack<泛型> 对象名 = new Stack<泛型>();

​ （还没学到泛型，等学了再发新的笔记解释）

​ Stack是Vector的子方法，所以继承了Vector类中定义的所有方法（太多了这里就不写了），放一些Stack类自己定义的方法：

序号	方法描述
1	boolean empty() 测试堆栈是否为空。
2	Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
3	Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
4	Object push(Object element) 把项压入堆栈顶部。
5	int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。

5.最长回文子串

原题链接：

5. 最长回文子串

class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() == 1) {
            return s;
        }
        int strLen = s.length();
        int maxStart = 0;  //最长回文串的起点
        int maxEnd = 0;    //最长回文串的终点
        int maxLen = 1;  //最长回文串的长度

        boolean[][] dp = new boolean[strLen][strLen];

        for (int r = 1; r < strLen; r++) {
            for (int l = 0; l < r; l++) {
                if (s.charAt(l) == s.charAt(r) && (r - l <= 2 || dp[l + 1][r - 1])) {
                    dp[l][r] = true;
                    if (r - l + 1 > maxLen) {
                        maxLen = r - l + 1;
                        maxStart = l;
                        maxEnd = r;
                    }
                }
            }
        }
        return s.substring(maxStart, maxEnd + 1);
    }
}

​ 两层for循环遍历n平方次，建立一个二维的dp数组，保存left到right这一范围内的串是否为回文子串。

​ 如果前一个状态时判定为true，则只要最外围两个字母相等，则可以判定最外围是回文串。

557.反转字符串中的单词

原题链接：

557. 反转字符串中的单词 III

class Solution {
    public String reverseWords(String s) {
        char[] array = s.toCharArray();
        int start = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == ' ') {
                reverse(array, start, i - 1);
                start = i + 1; // 更新start为下一个单词的左索引
                continue;
            }
            if (i == array.length - 1) {
                reverse(array, start, i);
            }
        }
        return new String(array);
    }
    public void reverse(char[] arr,int left,int right){
        while(left < right){
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }
}

​ 本题思路依旧不难，先写一个reverse函数用于将两个索引之间的字符反转，遇到空格就把空格之前的单词反转，最后一个特判即可，这里提一嘴toCharArray()方法。

​ toCharArray() 方法用于将字符串转换为字符数组。其实现方式通常是在内部创建一个新的字符数组，然后将字符串中的每个字符复制到该数组中。

​ 写个伪代码放在这里：

public char[] toCharArray() {
    int len = length(); // 获取字符串的长度
    char[] charArray = new char[len]; // 创建一个与字符串长度相同的字符数组
    for (int i = 0; i < len; i++) {
        charArray[i] = charAt(i); // 将字符串中的每个字符复制到字符数组中
    }
    return charArray; // 返回字符数组
}

​ 在实际的Java实现中，可能会有一些优化或其他细节，但基本思想是类似的：创建一个新的字符数组，并将字符串中的每个字符复制到该数组中。这确保了返回的字符数组与原始字符串具有相同的字符序列。

454.四数相加||

原题链接：

454. 四数相加 II

class Solution {
    public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for(int i = 0;i<A.length;i++){
            for(int j= 0;j<B.length;j++){
                int sumAB = A[i]+B[j];
                if(map.containsKey(sumAB)) map.put(sumAB,map.get(sumAB)+1);
                else map.put(sumAB,1);
            }
        }

        for(int i = 0;i<C.length;i++){
            for(int j = 0;j<D.length;j++){
                int sumCD = -(C[i]+D[j]);
                if(map.containsKey(sumCD)) res += map.get(sumCD);
            }
        }
        return res;
    }
}

​ 建立哈希表，记录前两个数组和以及出现的次数。

​ 第二个for循环，首先计算后两个数组相加之和，然后从哈希表中寻找是否有四数之和相加等于0的，找到则将次数相加，最终返回答案。

​ 用这道题来认识一下啊HashMap的用法：

方法	描述
clear()	删除 hashMap 中的所有键/值对
clone()	复制一份 hashMap
isEmpty()	判断 hashMap 是否为空
put()	将键/值对添加到 hashMap 中
remove()	删除 hashMap 中指定键 key 的映射关系
containsKey()	检查 hashMap 中是否存在指定的 key 对应的映射关系。
containsValue()	检查 hashMap 中是否存在指定的 value 对应的映射关系。
get()	获取指定 key 对应的 value
getOrDefault()	获取指定 key 对应的 value，如果找不到 key ，则返回设置的默认值
merge()	添加键值对到 hashMap 中

参考文献：

https://www.runoob.com/java/java-string.html

https://www.runoob.com/java/java-hashmap.html