第 111 场力扣夜喵双周赛

统计和小于目标的下标对数目

使用排序 + 双指针优化。如果 \(nums[lo]+nums[hi]<target\)，那么 \([lo+1,hi]\) 范围内的数都能与 \(nums[lo]\) 组成对，\(lo\) 加一；反之，\([lo,hi-1]\) 范围内的数都不能与 \(nums[hi]\) 组成对，\(hi\) 减一。

Java

class Solution {
    public int countPairs(List<Integer> nums, int target) {
        Collections.sort(nums);
        int lo = 0, hi = nums.size() - 1, ans = 0;
        while (lo < hi) {
            if (nums.get(lo) + nums.get(hi) < target) {
                ans += hi - lo;
                lo++;
            } else {
                hi--;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 0;
        for (int i = 0, j = n - 1; i < j; ) {
            if (nums[i] + nums[j] < target) {
                ans += j - i;
                i++;
            } else {
                j--;
            }
        }
        return ans;
    }
};

循环增长使字符串子序列等于另一个字符串

贪心取就行。

Java

class Solution {
    public boolean canMakeSubsequence(String str1, String str2) {
        int m = str1.length(), n = str2.length(), j = 0;
        for (int i = 0; i < m && j < n; i++) {
            if (str1.charAt(i) == str2.charAt(j) || (str1.charAt(i) + 1 - 'a') % 26 == str2.charAt(j) - 'a') {
                j++;
            }
        }
        return j == n;
    }
}

C++

class Solution {
public:
    bool canMakeSubsequence(string str1, string str2) {
        int m = str1.size(), n = str2.size(), j = 0;
        for (int i = 0; i < m && j < n; i++) {
            if (str1[i] == str2[j] || (str1[i] + 1 - 'a') % 26 == str2[j] - 'a') {
                j++;
            }
        }
        return j == n;
    }
};

将三个组排序

要将 \(nums\) 变为美丽数组，就要将 \(nums\) 变为非递减的形式，所以问题就变为求最长非递减子序列。

Java

动态规划：

class Solution {
    public int minimumOperations(List<Integer> nums) {
        int n = nums.size(), ans = 1;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums.get(i) >= nums.get(j)) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return n - ans;
    }
}

贪心 + 二分：

class Solution {
    public int minimumOperations(List<Integer> nums) {
        int n = nums.size(), maxLen = 0;
        int[] aux = new int[n];
        for (int x : nums) {
            int lo = 0, hi = maxLen - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (aux[mid] <= x) lo = mid + 1;
                else hi = mid - 1;
            }
            aux[lo] = x;
            if (lo == maxLen) maxLen++;
        }
        return n - maxLen;
    }
}

状态机 DP：

有点妙啊，\(dp[i][j]\) 表示将子数组 \([0,i]\) 变为以 \([1,j]\) 为结尾的美丽数组所需的最小修改次数，然后可以空间优化。

class Solution {
	public int minimumOperations(List<Integer> nums) {
		int[] dp = {Integer.MAX_VALUE, 0, 0, 0};
		for (int x : nums) {
			for (int i = 1; i <= 3; i++) {
				dp[i] = Math.min(dp[i - 1], dp[i] + (x == i ? 0 : 1));
			}
		}
		return dp[3];
	}
}

C++

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int dp[4] = {INT_MAX, 0, 0, 0};
        for (int x : nums) {
            for (int i = 1; i <= 3; i++) {
                dp[i] = min(dp[i - 1], dp[i] + (x != i));
            }
        }
        return dp[3];
    }
};

范围中美丽整数的数目

经典数位 DP 没什么好说的，主要是记忆化取模，边乘边取模。

Java

class Solution {
    public int numberOfBeautifulIntegers(int low, int high, int k) {
        return f(0, 10, 0, true, false, high + "", k, new Integer[10][20][k])
                - f(0, 10, 0, true, false, low - 1 + "", k, new Integer[10][20][k]);
    }
    
    private int f(int i, int diff, int mod, boolean isLimit, boolean isNum, String s, int k, Integer[][][] dp) {
        if (i == s.length()) {
            return isNum && diff == 10 && mod == 0 ? 1 : 0;
        }
        if (!isLimit && isNum && dp[i][diff][mod] != null) {
            return dp[i][diff][mod];
        }
        int res = 0;
        if (!isNum) res += f(i + 1, diff, mod, false, false, s, k, dp);
        int lo = isNum ? 0 : 1, hi = isLimit ? s.charAt(i) - '0' : 9;
        for (int d = lo; d <= hi; d++) {
            res += f(i + 1, diff + d % 2 * 2 - 1, (mod * 10 + d) % k, isLimit && d == hi, true, s, k, dp);
        }
        if (!isLimit && isNum) {
            dp[i][diff][mod] = res;
        }
        return res;
    }
}

C++

class Solution {
public:
    int numberOfBeautifulIntegers(int low, int high, int k) {
        string s;
        const int BASE = 10;
        int dp[10][20][k];
        
        auto f = [&](auto self, int i, int diff, int mod, bool isLimit, bool isNum) {
            if (i == s.size()) {
                return isNum && diff == 0 && mod == 0 ? 1 : 0;
            }
            if (!isLimit && isNum && dp[i][diff + BASE][mod] != -1) {
                return dp[i][diff + BASE][mod];
            }
            int res = 0;
            if (!isNum) res += self(self, i + 1, diff, mod, false, false);
            int lo = isNum ? 0 : 1, hi = isLimit ? s[i] - '0' : 9;
            for (int d = lo; d <= hi; d++) {
                res += self(self, i + 1, diff + d % 2 * 2 - 1, (mod * 10 + d) % k, isLimit && d == hi, true);
            }
            if (!isLimit && isNum) dp[i][diff + BASE][mod] = res;
            return res;
        };

        auto calc = [&](int x) {
            s = to_string(x);
            memset(dp, -1, sizeof(dp));
            return f(f, 0, 0, 0, true, false);
        };

        return calc(high) - calc(low - 1);
    }
};