6144. Minimum number of replacements to sort an array

Give you an array of integers nums starting at 0 in the following table.In each operation, you can replace any element of the array with any two and the number for that element.

• For example, nums = [5,6,7].In one operation, we can replace nums[1] with 2 and 4, and nums into numscode>[5,2,4,7] .

Please perform the above operation to turn the array into an array of elements in non-decreasing order, and return the minimum number of operations required.

Example 1:

Input:nums = [3,9,3]Output:2Explanation: Here are the steps to turn the array into non-decreasing order:- [3,9,3] , turn 9 into 3 and 6 , get array [3,3,6,3]- [3,3,6,3] , turn 6 into 3 and 3 , get array [3,3,3,3,3]It takes a total of 2 steps to turn the array into non-decreasing order, so we return 2 .

Example 2:

Input:nums = [1,2,3,4,5]Output:0Explanation: The array is already in non-decreasing order, so we return 0 .

Tip:

• 1 <= nums.length <= 1e5
• 1 <= nums[i] <= 1e9

Source: LeetCode
Link: https://leetcode.cn/problems/maximum-employees-to-be-invited-to-a-meeting
Copyright ownershipNetwork all.For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.

Results of the questions

Failed, I was stuck by writing a case [2,7,3] by myself, and the replacement strategy for the second 7 could not be figured out

Method: Greedy

1. Look from the back to the front

2. If it is larger than the latter, divide it equally according to the latter number to see how many parts it can be divided into. If it is divisible, the subsequent number remains unchanged and divided into part-1 parts (the watermelon is cut in half with only one knife)

3. If it is not divisible, divide as much as possible and increase the number at the beginning. Since it is not divisible, divide an extra copy of next+1, and make the number at the beginning as large as possible.

class Solution {public long minimumReplacement(int[] nums) {int n = nums.length;long ans = 0L;int next = nums[n-1];for(int i = n-2; i >= 0; i--){if(nums[i]>next){int part = nums[i]/next;if(nums[i]%next==0) {ans += part-1;}else{ans += part;next = nums[i]/(part+1);}}else next = nums[i];}return ans;}}

6138. Longest Ideal Subsequence

You are given a string of lowercase letters s , and an integer k .The string t can be considered a ideal string if the following conditions are met:

• t is a subsequence of the string s.
The absolute difference between every two adjacent letters in
• t in the alphabet is less than or equal to k .

Returns the length of the longest desired string.

A subsequence of a string is also a string, and the subsequence also satisfies: it can be obtained by deleting some characters (or not deleting) from other strings without changing the order of the remaining characters.

Note: The alphabetical order does not cycle.For example, the absolute difference between 'a' and 'z' in the alphabet is 25 , not 1 .

Example 1:

Input:s = "acfgbd", k = 2Output:4Explanation: The longest ideal string is "acbd" .The string length is 4 , so 4 is returned.Note that "acfgbd" is not an ideal string because 'c' and 'f' differ in alphabetical order by 3 .

Example 2:

Input:s = "abcd", k = 3Output:4Explanation: The longest ideal string is "abcd" , which is 4 in length, so 4 is returned.

Tip:

• 1 <= s.length <= 105
• 0 <= k <= 25
• s consists of lowercase English letters

Source: LeetCode
Link: https://leetcode.cn/problems/longest-ideal-subsequence
The copyright belongs to LeetCode.For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.

Results of the questions

Success, this question is medium, just seconds away

Method: Dynamic Programming

The previous range from max(index-k) to min(index+k 25) can be extended by one to the current letter. Select the longest one and connect it to yourself. Note that if your length is 1, you need to add an additional one.

class Solution {public int longestIdealString(String s, int k) {int[] dp = new int[26];int n = s.length();int ans = 0;for(int i = 0; i < n; i++){int v =0 ;int index = s.charAt(i)-'a';for(int start = Math.max(index-k,0); start<=Math.min(index+k,25);start++){v=Math.max(dp[start],v);}dp[index] = v+1;ans = Math.max(v+1,ans);}return ans;}}