每日刷题记录 (十二)

第一题: 剑指 Offer II 012. 左右两边子数组的和相等

LeetCode: 剑指 Offer II 012. 左右两边子数组的和相等

描述:
给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

解题思路:

1. 这里直接记录所有的总和, 给 rightTotal
2. 遍历数组.
3. 让leftTotal记录左侧的所有元素的和, rightTotal 记录右侧所有元素的和.
4. 如果当前 leftTotal 和 rightTotal 值相等. 返回当前下标.

代码实现:

class Solution {
    
    public int pivotIndex(int[] nums) {
    
        int rightTotal = 0;
        int leftTotal = 0;
        for(int num : nums) {
    
            rightTotal += num;
        }
        for(int i = 0; i < nums.length; i++) {
    
        	// 注意这里先右边减了 再判断了 然后左边加.
            rightTotal -= nums[i];
            if (leftTotal == rightTotal) return i;
            leftTotal += nums[i];
        }
        return -1;
    }
}

第二题: 剑指 Offer II 014. 字符串中的变位词

LeetCode: 剑指 Offer II 014. 字符串中的变位词

描述:
给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。

换句话说，第一个字符串的排列之一是第二个字符串的 子串 。

解题思路:

1. 使用滑动窗口来解决.
2. 首先使用一个数组记录s1中 字符串出现的次数
3. 然后将所有的没出现的字符变成-1
4. 建立一个范围为 [left,right] 的滑动窗口.
5. 如果当前right下标的元素在数组中存在
   • 如果当前次数大于0, 则让该元素对应的数组下标减1, 窗口变大一个(right++).
   • 如果当前次数等于0, 如果当前left和right下标元素不相同, 就需要左边窗口变小(left++). 如果相同了, 就让窗口往右滑动一个(left++,right++)
6. 如果当前right下标的元素在数组中不存在.如果当前left和right不在同以下标,则表示当前已经进行窗口变化,且当前元素又不存在,就需要重新初始化窗口,

代码实现:

class Solution {
    
    public boolean checkInclusion(String s1, String s2) {
    
        int[] arr = new int[26];
        for(char ch : s1.toCharArray()) {
    
            arr[ch-'a']++;
        }
        for (int i = 0; i < 26; i++) {
    
            if (arr[i] == 0) arr[i] = -1;
        }
        int left = 0;
        int right = 0;
        int total = s1.length();
        while (total > 0 && right < s2.length()) {
    
            int tmp = arr[s2.charAt(right)-'a'];
            if (tmp == -1) {
    
                while (left < right) {
    
                    arr[s2.charAt(left) - 'a']++;
                    total++;
                    left++;
                }
                left = right + 1;
                right = left;
            } else {
    
                if (tmp > 0) {
    
                    total--;
                    arr[s2.charAt(right)-'a']--;
                    right++;
                }else {
    
                    while(s2.charAt(left) != s2.charAt(right)) {
    
                        total++;
                        arr[s2.charAt(left) - 'a']++;
                        left++;
                    }
                    left++;
                    right++;
                }
            }
        }
        return total == 0;
    }
}

第三题: 剑指 Offer II 016. 不含重复字符的最长子字符串

LeetCode: 剑指 Offer II 016. 不含重复字符的最长子字符串

描述:
给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。

解题思路:

1. 这里是使用滑动窗口解题.
2. 范围为 [left,right]的滑动窗口. 将字符串加入list记录
3. 如果当前right下标的元素存在, 就删除list中首元素, 让left++, 直到right下标元素在list中不存在.
4. 将right下标的元素加入list中, 记录下当前滑动窗口的大小(right-left+1)
5. 遍历结束,返回最大的滑动窗口大小.

代码实现:

class Solution {
    
    public int lengthOfLongestSubstring(String s) {
    
        int left = 0;
        int right = 0;
        int ans = 0;
        List<Character> list = new ArrayList<>();
        while (right < s.length()) {
    
            while(left < right && list.contains(s.charAt(right))) {
    
                list.remove(0);
                left++;
            }
            list.add(s.charAt(right));
            ans = Math.max(ans,right-left+1);
            right++;
        }
        return ans;
    }
}

第四题: 剑指 Offer II 018. 有效的回文

LeetCode: 剑指 Offer II 018. 有效的回文

描述:
给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。

本题中，将空字符串定义为有效的 回文串 。

解题思路:

1. 遍历字符串, 只要字符串是数字和字符就把他变成一个新的字符串.
2. 使用双指针遍历字符串.
3. 如果 left 下标和 right 下标的字的内容一样, 就 left++. right--;
4. 如果不一样,直接返回 false ;
5. 遍历结束返回 true ;

代码实现:

class Solution {
    
    public boolean isPalindrome(String s) {
    
        String ret = "1234567890abcdefghijklmnopqlstuvwxyz";
        StringBuilder sb = new StringBuilder();
        s = s.toLowerCase();
        for (int i = 0; i < s.length(); i++) {
    
            if(ret.contains(s.charAt(i)+"")){
    
                sb.append(s.charAt(i));
            }
        }
        int left = 0;
        int right = sb.length()-1;
        while(left <= right) {
    
            if(sb.charAt(left) == sb.charAt(right)) {
    
                left++;
                right--;
            }else{
    
                return false;
            }
        }
        return true;
    }
}

第五题: 剑指 Offer II 019. 最多删除一个字符得到回文

LeetCode: 剑指 Offer II 019. 最多删除一个字符得到回文

描述:
给定一个非空字符串 s，请判断如果 最多 从字符串中删除一个字符能否得到一个回文字符串。

解题思路:

1. 这里首先进行判断, 当前是否是回文字符串
2. 如果是就返回true;
3. 如果不是就去判断当前[left,right-1] 或 [left+1,right]是否是回文字符串.只要有一个是就是true;

代码实现:

class Solution {
    
    public boolean validPalindrome(String s) {
    
        int left = 0;
        int right = s.length()-1;
        while(left <= right) {
    
            if(s.charAt(left) == s.charAt(right)){
    
                left++;
                right--;
            }else{
    
                return isHui(s,left,right-1) || isHui(s,left+1,right);
            }
        }
        return true;
    }
    public boolean isHui(String s, int left, int right) {
    
        while(left <= right) {
    
            if(s.charAt(left) == s.charAt(right)) {
    
                left++;
                right--;
            }else{
    
                return false;
            }
        }
        return true;
    }
}

第六题: 剑指 Offer II 020. 回文子字符串的个数

LeetCode: 剑指 Offer II 020. 回文子字符串的个数

描述:
给定一个字符串 s ，请计算这个字符串中有多少个回文子字符串。

具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

解题思路:

1. 这里使用动态规划解题.
2. 状态 F(i,j) : 表示 i~j是否是回文串
3. 状态转移方程: 当前 j == i 时, F(i,j) = true; 当 j - i == 1时,F(i,j)=s.charAt(i) == s.charAt(j);当 j-i > 1时, F(i,j) = s.charAt(i) == s.charAt(j) && dp[i+1][j-1] (dp[i+1][j-1] ,就是[i+1,j-1]是否是回文串)
4. 初始状态: 单个字符是 true;
5. 返回结果: dp[i][j] 为true的个数

代码实现:

class Solution {
    
    public int countSubstrings(String s) {
    
        boolean[][] dp = new boolean[s.length()][s.length()];
        int count = 0;
        for(int i = s.length()-1; i >= 0; i--) {
    
            for(int j = s.length()-1; j>=i; j--){
    
                if(j == i) dp[i][j] = true;
                else if(j - i == 1) {
    
                    dp[i][j] = s.charAt(i) == s.charAt(j);
                }else{
    
                    dp[i][j] = s.charAt(i) == s.charAt(j) && dp[i+1][j-1];
                }
                if(dp[i][j]) count++;
            }
        }
        return count;
    }
}