20220807 leetcodez周赛

本次周赛只做出来两题。前路漫漫，还要继续加油呀！

第三题总结：

 思路：当时的思路是dfs，结果超时了。

正确的思路是用动态规划。dp[i] = true, 表示以从第0个到第i-1个数结尾的数组可以进行有效划分。

boolean a = (nums[i-1] == nums[i-2] && dp[i-2])

boolean b = ((nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) || (nums[i-1] == nums[i-2]+1 && nums[i-3] == nums[i-2]-1)) && dp[i-3]

dp[i] = a || b;

还有一个注意点，注意不要排序！！！！

代码：

class Solution {
    public boolean validPartition(int[] nums) {
        // Arrays.sort(nums);
        boolean[] dp = new boolean[nums.length+1];
        dp[0] = true;
        dp[1] = false;
        for(int i = 2; i <= nums.length; i++) {
            if(i == 2) {
                if(nums[i-1] == nums[i-2]) {
                    dp[i] = true;
                } else {
                    dp[i] = false;
                }
            } else {
                boolean a = false,b = false;
                if(nums[i-1] == nums[i-2]) {
                    a = true && dp[i-2];
                } 
                if((nums[i-1] == nums[i-2] && nums[i-2] == nums[i-3]) || (nums[i-1] == nums[i-2]+1 && nums[i-3] == nums[i-2]-1)) {
                    b = true && dp[i-3];
                } 
                dp[i] = a || b;
            }
            // System.out.println(i+":"+dp[i]);
        }
        return dp[nums.length];
        
    }
}

当然，如果这个题变成有几种划分方法，可以用dfs。

dfs代码也奉上：

class Solution {
    public boolean validPartition(int[] nums) {
        return backTrack(0, nums);
        
    }
    public boolean backTrack(int index, int[] nums) {
        if(index == nums.length) {
            return true;
        }
        if(index == nums.length-1) {
            return false;
        }
        if(nums[index] == nums[index+1] && backTrack(index+2, nums)) {
            return true;
        } 
        if(index == nums.length-2) {
            return false;
        } 
        if((nums[index] == nums[index+1] && nums[index+1] == nums[index+2]) || (nums[index] == nums[index+1]-1 && nums[index+1] == nums[index+2]-1)) {
            if(backTrack(index+3, nums)) {
                return true;
            }
        }
        return false;
        
    }
}

第四题总结：

力扣https://leetcode.cn/problems/longest-ideal-subsequence/

 思路：从当前元素往前找，找到符合条件的s.charAt(j), 使得当前的dp[i] = Math.max(dp[i],dp[j]+1);

双层for循环，但是这么做的话，时间复杂度（0（n*n））会超时。

因此，可以用一个HashMap记录下字母的位置，直接使用HashMap寻找符合条件的字母的位置。注意，不需要用一个LinkedList记录字母出现的所有位置，只要记录下最新的就可以了。

代码奉上：

class Solution {
    public int longestIdealString(String s, int k) {
        int[] dp = new int[s.length()];
        HashMap map = new HashMap<>();
        int max = 1;
        map.put(s.charAt(0) - 'a', 0);
        dp[0] = 1;
        for(int i = 1; i < s.length(); i++) {
            dp[i] = 1;
            for(int j = -k ; j <= k; j++) {
                int num = map.getOrDefault(s.charAt(i)-'a'+j, -1);
                if(num!= -1) {
                    dp[i] = Math.max(dp[i],dp[num]+1);
                }
            }
            max = Math.max(dp[i], max);
            map.put(s.charAt(i)-'a', i);
                
        }
        return max;
    }
}