头像

Ccc1Z


访客:2519

离线:2小时前



Ccc1Z
16小时前

思路:(区间DP 同石子合并)

  • 状态表示:dp[i][j]表示切分[i,j]的最小花费
  • 状态计算:枚举[i,j]之间的切点mid
    • dp[l][r] = Math.min(dp[l][r],dp[l][mid]+dp[mid+1][r]+cost)

时间复杂度(状态数量:N^2,状态转移:O(N)->O(N^3))

代码:

class Solution {
    public int minCost(int n, int[] cuts) {
        List<Integer> list = new ArrayList<>();
        for(int item : cuts){
            list.add(item);
        }
        //加入0和n避免边界条件
        list.add(0);list.add(n);
        Collections.sort(list);
        int m = list.size()-1;
        int[][] dp = new int[m+1][m+1];
        for(int len = 2 ; len <= m ; len++){
            for(int i = 1 ; i + len -1 <=m ;i++){
                int left = i,right = i + len - 1;
                dp[left][right] = Integer.MAX_VALUE;
                for(int k = left ; k <= right-1 ; k++){
                    dp[left][right] = Math.min(dp[left][right],dp[left][k]+dp[k+1][right]+list.get(right)-list.get(left-1));
                }
            }
        }
        return dp[1][m];
    }
}



Ccc1Z
16小时前

题目描述

给你一个数组nums和一个整数target

请你返回非空不重叠子数组的最大数目,且每个子数组中数字和都为target

示例 1:

输入:nums = [1,1,1,1,1], target = 2
输出:2
解释:总共有 2 个不重叠子数组(加粗数字表示) [1,1,1,1,1] ,它们的和为目标值 2 。
示例 2:

输入:nums = [-1,3,5,1,4,2,-9], target = 6
输出:2
解释:总共有 3 个子数组和为 6 。
([5,1], [4,2], [3,5,1,4,2,-9]) 但只有前 2 个是不重叠的。
示例 3:

输入:nums = [-2,6,6,3,5,4,1,2,8], target = 10
输出:3
示例 4:

输入:nums = [0,0,0], target = 0
输出:3

提示:

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
0 <= target <= 10^6

思路:(dp+前缀和)

  • 状态表示:dp[i]表示以i结尾的和为目标值的最大数目不重叠非空子数组数目
  • 状态计算: 以是否选择i来划分
  • 1.如果i无法与前面的某一个子数组构成一个满足题意得子数组 dp[i] = dp[i-1]
  • 2.s[j…i]是一个满足题意的子数组 dp[i] = dp[j-1]+1
  • 分析状态表示和状态计算我们发现关键点在于如何快速的判断s[j...i]是否满足题意
  • 这里我们通过前缀和来判断 如果s[j...i] = target
  • s[j...i] = s[i] - s[j-1] == target->s[j-1] = s[i] - target
  • 再分析因为我们要求的是最大数目所以,我们对于每个i都应该找尽量“后面”j来进行匹配
  • [j,i]越小那么我们可能产生的子数组数量就会越多

  • 通过一个HashMap<Integer,Integer>,{key}->前缀和,{val}->该前缀和"最后一次"出现的位置来记录前缀和消息和位置消息

时间复杂度(状态个数:N,状态转移:O(1)->O(N))

代码:

/**
* dp[i]:表示以i结尾的和为目标值的最大数目不重叠非空子数组数目
* 状态计算:由是否选择第i个字符来划分
*   1.不选:dp[i] = dp[i-1]
*   2.选 : dp[i] = dp[p-1] + 1; p表示离i最近的满足条件的位置
* 关键点:如何快速确定S[l...r]==target->前缀和
*   
*/
class Solution {
    public int maxNonOverlapping(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[n+1];
        //{key}->前缀和,{val}->"最后一次出现该前缀和"的位置
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(0,0);
        int sum = 0;
        for(int i = 1 ; i <= n ; i++){
            sum += nums[i-1];
            int need = sum - target;
            if(hash.containsKey(need)){
                dp[i] = Math.max(dp[i-1],dp[hash.get(need)]+1);
            }else{
                dp[i] = dp[i-1];
            }
            hash.put(sum,i);
        }
        return dp[n];
    }
}



Ccc1Z
16小时前

题目描述

给你两个正整数nk,二进制字符串Sn的形成规则如下:

S1= "0"
当 i > 1 时,Si = Si-1 + "1" + reverse(invert(Si-1))
其中 + 表示串联操作,reverse(x) 返回反转 x 后得到的字符串,而 invert(x) 则会翻转 x 中的每一位(0 变为 1,而 1 变为 0)

例如,符合上述描述的序列的前 4 个字符串依次是:

S1="0"
S2="011"
S3="0111001"
S4="011100110110001"
请你返回Sn的 第k位字符 ,题目数据保证k一定在Sn长度范围以内。


示例 1:

输入:n = 3, k = 1
输出:"0"
解释:S3 为 "0111001",其第 1 位为 "0" 。
示例 2:

输入:n = 4, k = 11
输出:"1"
解释:S4 为 "011100110110001",其第 11 位为 "1" 。
示例 3:

输入:n = 1, k = 1
输出:"0"
示例 4:

输入:n = 2, k = 3
输出:"1"

提示:

1 <= n <= 20
1 <= k <= 2n - 1

思路(dfs逆推) 同ACWING.786(第K个数)

  • 根据题意我们要找的是S_n的第k位 一种方式是我们直接生成S_n另一中是通过S_n去找它的第k位是怎么来的
  • 通过分析我们得出以下两点结论:
  • 1.S_n的长度len = (2^n)-1
  • 2.S_n的前半部分是S_{n-1}中间部分(idx:len/2+1)是1后半部分是S_{n-1}先invertreverse`
  • 因此我们可以根据上面的结论去反推S_n的第k位是几
  • if(k==len/2+1) return ‘1’
  • if(k<len/2)[k在前半部分] return dfs(len/2,k)
  • else [k在后半部分]->因为是先invertreverse所以我们逆推的时候需要先reverseinvert
    • char c = dfs(len/2,len-k+1) return c ==‘1’ ? ‘0’ : ‘1’;

时间复杂度(每次递归减少一半 <= O(2N))

代码

class Solution {
    public char findKthBit(int n, int k) {
        int len = (1<<n)-1;
        return dfs(len,k);
    }

    private char dfs(int n,int k){
        if(n == 1) return '0';
        if(k == n/2+1) return '1';
        if(k <= n/2) return dfs(n/2,k);
        char c = dfs(n/2,n-k+1);
        return c == '1' ? '0' : '1';
    }
}



Ccc1Z
17小时前

题目描述

给你一个由大小写英文字母组成的字符串s

一个整理好的字符串中,两个相邻字符s[i]s[i + 1]不会同时满足下述条件:

0 <= i <= s.length - 2
s[i] 是小写字符,但 s[i + 1] 是相同的大写字符;反之亦然。
请你将字符串整理好,每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除,直到字符串整理好为止。

请返回整理好的 字符串 。题目保证在给出的约束条件下,测试样例对应的答案是唯一的。

注意:空字符串也属于整理好的字符串,尽管其中没有任何字符。

示例 1:

输入:s = "leEeetcode"
输出:"leetcode"
解释:无论你第一次选的是 i = 1 还是 i = 2,都会使 "leEeetcode" 缩减为 "leetcode" 。
示例 2:

输入:s = "abBAcC"
输出:""
解释:存在多种不同情况,但所有的情况都会导致相同的结果。例如:
"abBAcC" --> "aAcC" --> "cC" --> ""
"abBAcC" --> "abBA" --> "aA" --> ""
示例 3:

输入:s = "s"
输出:"s"

提示:

1 <= s.length <= 100
s 只包含小写和大写英文字母

思路:(模拟)

  • 直接按照题意进行模拟
  • 准备一个索引idx,如果idx和idx+1是要删除的两个对象就删除,且删除完之后idx=0
  • 如果idx不是要删除的数则idx+1

时间复杂度(?)

代码:

class Solution {
    public String makeGood(String s) {
        StringBuilder sb = new StringBuilder(s);
        int idx = 0;
        while(idx < sb.length()-1 && sb.length() > 0){
            char idx1 = sb.charAt(idx);
            char idx2 = sb.charAt(idx+1);
            if(idx1 != idx2 && Character.toLowerCase(idx1) == Character.toLowerCase(idx2)){
                sb.deleteCharAt(idx);
                sb.deleteCharAt(idx);
                idx = 0;
            }else{
                idx++;
            }
        }
        return sb.toString();
    }
}



Ccc1Z
21小时前

题目描述

给你一个字符串s。请返回s中最长的超赞子字符串的长度。

「超赞子字符串」需满足满足下述两个条件:

该字符串是 s 的一个非空子字符串
进行任意次数的字符交换重新排序后,该字符串可以变成一个回文字符串


示例 1:

输入:s = "3242415"
输出:5
解释:"24241" 是最长的超赞子字符串,交换其中的字符后,可以得到回文 "24142"
示例 2:

输入:s = "12345678"
输出:1
示例 3:

输入:s = "213123"
输出:6
解释:"213123" 是最长的超赞子字符串,交换其中的字符后,可以得到回文 "231132"
示例 4:

输入:s = "00"
输出:2

提示:

1 <= s.length <= 10^5
s 仅由数字组成

思路:(对子串的奇偶性进行状态压缩 思路参考:zerotrac2)

一个字符串是否能够通过位置交换变成一个回文串

  • 取决于该字符串中每个字符出现次数的奇偶性
  • 要么全部出现偶数次,要么当且仅当只有一个字符出现奇数次,其他字符串出现偶数次

如何统计一个子串S[i…j]间每个字符出现的次数是奇数还是偶数

  • 我们用二进制来表示这个字符的出现次数是偶数(0)还是奇数(1)
  • 记录一个前缀和prefix[i]:表示以i结尾的子串每个字符出现次数的奇偶性
  • 那么S[i…j]之间字符出现次数的奇偶性就是 prefix[j] ^ prefix[i-1]
    • 异或操作刚好满足:奇-奇=偶(1^1 = 0),奇-偶=奇(1^0=1),偶-偶=偶(0^0=0)
  • 我们用一个HashMap[HTML_REMOVED] hash 来记录{key}->prefix[i],{val}->第一次出现该前缀和的位置i
    • 本题中也可以使用一个长度为1<<10的数组来存,但是如果改成26个字母数组就存不下了
  • 遍历字符串,对于当前i找到第一个满足条件的j来更新答案
  • 找答案的时候分两种情况(prefix[i]和prefix[j-1]最多只有一位不同)
    • 1.prefix[i] == prefix[j] 那么异或后全为偶数
    • 2.S[i…j]中某一个字符出现了奇数次(依次翻转每一位进行判断)
  • 注意事项:
    • 我们需要初始化hash.put(0,-1) 因为计算S[0…i]的时候需要用到-1,此时-1没字符视为0

时间复杂度(扫描一次字符串O(N))

代码

class Solution {
    public int longestAwesome(String s) {
        int n = s.length();
        Map<Integer,Integer> hash = new HashMap<>();
        //初始化
        hash.put(0,-1);
        int prefix = 0;
        int ans = 0;
        for(int i = 0 ; i < n ; i++){
            int d = s.charAt(i) - '0';
            //计算以i结尾的前缀
            prefix ^= (1<<d);
            if(hash.containsKey(prefix)){
                //说明前面有相同的prefix进行匹配
                ans = Math.max(ans,i-hash.get(prefix));
            }else{
                //说明该prefix第一次出现
                hash.put(prefix,i);
            }
            for(int j = 0 ; j < 10 ; j++){
                //计算情况2:只有一个字符出现了奇数次
                prefix ^= (1<<j);
                if(hash.containsKey(prefix)){
                    ans = Math.max(ans,i - hash.get(prefix));
                }
                prefix ^= (1<<j);
            }
        }
        return ans;
    }
}



Ccc1Z
22小时前

题目描述

给你一个括号字符串s,它只包含字符'(' 和’)’`。一个括号字符串被称为平衡的当它满足:

任何左括号'('必须对应两个连续的右括号'))'
左括号'('必须在对应的连续两个右括号'))'之前。
比方说"())",”())(())))” 和"(())())))"都是平衡的,")()",”()))” 和"(()))"都是不平衡的。

你可以在任意位置插入字符 ‘(‘ 和 ‘)’ 使字符串平衡。

请你返回让s平衡的最少插入次数。

示例 1:

输入:s = "(()))"
输出:1
解释:第二个左括号有与之匹配的两个右括号,但是第一个左括号只有一个右括号。我们需要在字符串结尾额外增加一个 ')' 使字符串变成平衡字符串 "(())))" 。
示例 2:

输入:s = "())"
输出:0
解释:字符串已经平衡了。
示例 3:

输入:s = "))())("
输出:3
解释:添加 '(' 去匹配最开头的 '))' ,然后添加 '))' 去匹配最后一个 '(' 。
示例 4:

输入:s = "(((((("
输出:12
解释:添加 12 个 ')' 得到平衡字符串。
示例 5:

输入:s = ")))))))"
输出:5
解释:在字符串开头添加 4 个 '(' 并在结尾添加 1 个 ')' ,字符串变成平衡字符串 "(((())))))))" 。

提示:

1 <= s.length <= 10^5
s只包含'(' 和’)’`。

思路:括号匹配(类似LC.921)

  • 我们用一个变量cnt来统计当前还未匹配的(
  • 在遍历字符串时分情况讨论:
  • 1.遇到(时 cnt++
  • 2.遇到)
    • 2.1 当前)的下一个括号仍然是)->i++
    • 2.2 当前)的下一个括号不是)->我们需要添加一个)来匹配 ans++
  • 3.结算(经过第二步操作此时有两个)待匹配)
    • 3.1 cnt>0说明有(待匹配 此时cnt--
    • 3.2 cnt == 0说明当前没有(待匹配 此时我们加一个(来匹配 ans++
    1. 如果遍历完成后cnt > 0那么此时需要2*cnt)来进行匹配

时间复杂度(O(N)) 只会遍历字符串一次

代码

/**
* 用一个cnt来记录当前还未匹配的'('的个数
*   1.当前遍历到'(' cnt++
*   2.当前遍历到')' 
*    2.1 1个')' 增加一个右括号
*       2.1.1 cnt == 0 添加一个左括号
*       2.1.2 cnt > 0 有左括号匹配 cnt--
*    2.2 2个')' i++;
*    如果结束过后还有左括号没有匹配 ans += cnt * 2;   
*/
class Solution {
    public int minInsertions(String s) {
        int n = s.length();
        int cnt = 0,ans = 0;
        for(int i = 0 ; i < n ; i++){
            char c = s.charAt(i);
            if(c == '('){
                cnt++;
            }else{
                if(i + 1 < n && s.charAt(i+1) == ')'){
                    i++;
                }else{
                    ans++;
                }
                if(cnt > 0){
                    cnt--;
                }else{
                    ans++;
                }
            }
        }
        return ans + cnt*2;
    }
}



Ccc1Z
22小时前

题目描述

给你两个字符串st,你的目标是在k次操作以内把字符串s转变成t

在第i次操作时(1 <= i <= k),你可以选择进行如下操作:

选择字符串s中满足1 <= j <= s.length且之前未被选过的任意下标j(下标从 1 开始),并将此位置的字符切换 i次。
不进行任何操作。
切换 1 次字符的意思是用字母表中该字母的下一个字母替换它(字母表环状接起来,所以'z'切换后会变成'a')。

请记住任意一个下标j最多只能被操作1次。

如果在不超过k次操作内可以把字符串s转变成t,那么请你返回true,否则请你返回false

示例 1:

输入:s = "input", t = "ouput", k = 9
输出:true
解释:第 6 次操作时,我们将 'i' 切换 6 次得到 'o' 。第 7 次操作时,我们将 'n' 切换 7 次得到 'u' 。
示例 2:

输入:s = "abc", t = "bcd", k = 10
输出:false
解释:我们需要将每个字符切换 1 次才能得到 t 。我们可以在第 1 次操作时将 'a' 切换成 'b' ,但另外 2 个字母在剩余操作中无法再转变为 t 中对应字母。
示例 3:

输入:s = "aab", t = "bbb", k = 27
输出:true
解释:第 1 次操作时,我们将第一个 'a' 切换 1 次得到 'b' 。在第 27 次操作时,我们将第二个字母 'a' 切换 27 次得到 'b' 。

提示:

1 <= s.length, t.length <= 10^5
0 <= k <= 10^9
st只包含小写英文字母。

思路:

  • 在本题题意下(环形)一个字符a转换到另一个字符b的最少次数为(b-a+26)%26
  • 那么我们可以用一个数组int[] cnt = new int[26]来记录下每个字符变换所需要的次数
  • cnt[i]表示的就是需要转换i次得到的结果的原字符的总个数
  • 又因为每次操作我们只能对一个字符进行操作,对于需要相同操作次数的字符而言我们就需要在原基础上加上26的操作次 数进行操作
  • 所以在k次内能否完成操作的关键点就在于 对于每个cnt[i]能否都在k次操作内完成(cnt[i] - 1)*26 + i < k)

时间复杂度(O(N))

  • 我们只需要对字符串遍历一次得到cnt数组 这一步操作为O(N)
  • 判断操作数是否满足的时间复杂度为O(25)

代码

class Solution {
    public boolean canConvertString(String s, String t, int k) {
        if(s.length() != t.length()) return false;
        int n = s.length();
        int[] cnt = new int[26];
        for(int i = 0 ; i < n ; i++){
            cnt[(t.charAt(i) - s.charAt(i) + 26)%26]++;
        }
        for(int i = 1 ; i < 26 ; i++){
            if(cnt[i] == 0) continue;
            if(k < (cnt[i] - 1)*26+i) return false;
        }
        return true;
    }
}



Ccc1Z
22小时前

题目描述:

给你一个 严格升序排列的正整数数组 arr和一个整数k

请你找到这个数组里第k个缺失的正整数。

示例 1:

输入:arr = [2,3,4,7,11], k = 5
输出:9
解释:缺失的正整数包括 [1,5,6,8,9,10,12,13,...] 。第 5 个缺失的正整数为 9 。
示例 2:

输入:arr = [1,2,3,4], k = 2
输出:6
解释:缺失的正整数包括 [5,6,7,...] 。第 2 个缺失的正整数为 6 。

提示:

1 <= arr.length <= 1000
1 <= arr[i] <= 1000
1 <= k <= 1000
对于所有 1 <= i < j <= arr.length 的 i 和 j 满足 arr[i] < arr[j] 

思路:双指针

  • 一个指针从1开始指向每一个正整数 miss
  • 一个指针从下标0开始指向数组 arr[i]
  • 当i < arr.length && arr[i] == miss时->说明此时miss已经在数组中出现过了 i++
  • 当i >= arr.length || arr[i] != miss时->说明此时miss是一个未在数组中出现过的正整数 k–
  • 当k=0时此时的miss就是第k个缺失的正整数

时间复杂度 最坏O(NK)

/**
* 双指针
*/
class Solution {
    public int findKthPositive(int[] arr, int k) {
        int n = arr.length;
        int miss = 1;
        int idx = 0;
        while(k > 0){
            if(idx < n && arr[idx] == miss){
                idx++;
            }else{
                k--;
            }
            miss++;

        }
        return miss-1;
    }
}


活动打卡代码 LeetCode 1537. 最大得分

Ccc1Z
1天前
class Solution {
    public int maxSum(int[] nums1, int[] nums2) {
        int mod = 1_000_000_007;
        long ans = 0;
        long t1 = 0 , t2 = 0;
        int i = 0, j = 0;
        int n = nums1.length, m = nums2.length;
        while(i < n && j < m){
            if(nums1[i] < nums2[j]){
                t1 += nums1[i++];
            }else if(nums1[i] > nums2[j]){
                t2 += nums2[j++];
            }else{
                long maxv = Math.max(t1,t2)+nums1[i];
                t1 = t2 = maxv;
                i++;
                j++;
            }
        }
        while(i < n){
            t1 += nums1[i++];
        }
        while(j < m){
            t2 += nums2[j++];
        }
        ans = Math.max(t1,t2);
        return (int) (ans % mod);
    }
}



Ccc1Z
1天前
class Solution {
    public int minSwaps(int[][] grid) {
        int n = grid.length;
        int[] cnt = new int[n];
        //拿到每一行从末尾开始数的0的个数
        for(int i = 0 ; i < n ;i++){
            for(int j = n -1 ; j >= 0 ; j--){
                if(grid[i][j] != 0) break;
                cnt[i]++;
            }
        }
        int ans = 0;
        for(int i = 0 ; i < n ; i++){
            //如果要转成符合条件的矩阵每一行所需要的0的个数
            int need = n - i - 1;
            //System.out.println(need);
            int p = -1;
            if(cnt[i] >= need){
                //如果当前行符合条件
                //System.out.println(i);
                continue;
            }
            //不符合条件,找到最近的符合条件的行进行交换
            for(int j = i + 1 ; j < n ; j++){
                if(cnt[j] >= need){
                    p = j;
                    break;
                }
            }
            if(p == -1){
                //无法组成这样的矩阵
                return -1;
            }
            //开始交换
            for(int j = p ; j > i ; j--){
                ans++;
                swap(cnt,j,j-1);
            }
        }
        return ans;
    }
    private void swap(int[] cnt,int a,int b){
        int tmp = cnt[a];
        cnt[a] = cnt[b];
        cnt[b] = tmp;
    }
}