Table of Contents
[Case 1 Greedy attempt]
[Title description]
[Analysis of ideas]
【Code】
[Case 2: Trial model in scope]
[Title description]
[Analysis of ideas]
【Code】
[Case 3: Trial model in scope]
[Title description]
[Analysis of ideas]
【Code】
[Case 4: Model tried from left to top + model tried in range]
[Title description]
[Analysis of ideas]
【Code】
[Case 5: Trial model in scope]
[Title description]
[Analysis of ideas]
【Code】
If you think you can write well, you can join the QQ group 907575059 to discuss algorithm knowledge.
[Case 1 Greedy Try]
[Title Description]
[Idea Analysis]
First sort the entire array. If the value of the last position is greater than the limit, Integer.MAX_VALUE is returned, indicating that it is impossible to cross the shore.
arr[arr.length – 1] <= limit / 2 If this condition is met, any two people can be paired on a ship
arr[0] > limit / 2 If this condition is met, only one person can wear it.
Otherwise, find the rightmost position left that is less than or equal to limit/2, and then use two pointers, p to traverse from left to 0, and q to traverse from left + 1 to arr.lenth.
(1) If p + q <= limit, at this time q + + (when q + +, count the length of q traversal) until p + q>limit. At this time, the corresponding lengths on the left side of p all satisfy the corresponding p + q < limit. If the left side of p is not long enough, all of p will be used to solve q.
(2) If p + q > limit, p–.
After the traversal is completed, each person remaining on the right arranges a separate ship, and the remaining people on the left arrange (leftNum + 1)/2; arrange as many ships as the number of q’s solved.
[Code Implementation]
package AdvancedPromotion5;
import java.util.Arrays;
/**
* @ProjectName: study3
* @FileName: Ex1
* @author:HWJ
* @Data: 2023/9/24 16:18
*/
public class Ex1 {
public static void main(String[] args) {
int[] arr = {1,2,2,3,4,4,5,5,5,6,6,6,6,7,7,7,8,8,8,9,9,9, 11,10,11,12};
System.out.println(need(arr, 13));
}
public static int need(int[] arr, int limit) {
Arrays.sort(arr);
if (arr[arr.length - 1] > limit) {
return Integer.MAX_VALUE;
}
if (arr[arr.length - 1] <= limit / 2) { // If this condition is met, any two people can be paired on a ship
return (arr.length + 1) / 2;
}
if (arr[0] > limit / 2) { // If this condition is met, only one person can wear it.
return arr.length;
}
int left = -1;
for (int i = arr.length - 1; i >= 0; i--) {
if (arr[i] <= limit / 2) {
left = i;
break;
}
}
int p = left;
int q = left + 1;
int unSolved = 0;
while (p >= 0) {
int solve = 0;
while (q < arr.length & amp; & amp; arr[p] + arr[q] <= limit) {
solve + + ;
q + + ;
}
if (solve > 0) {
p = Math.max(p - solve, -1); // If it can be solved, solve it all
// If you can't, just assign -1 directly and exit the loop.
} else {
unSolved + + ;
p--;
// We only need to record the unsolved quantity on the left, and then we can get the solved quantity on the left through the total number on the left
//The quantity solved on the left is equal to the quantity solved on the right. Through this, the quantity not solved on the right can be obtained. This gives us all the information we need
}
}
int leftNum = left + 1;
int right = arr.length - leftNum;
return right + (unSolved + 1) / 2;
}
}
[Case 2 Trial Model on Range]
[Title description]
[Analysis of ideas]
For the method of finding common subsequences, see Case 6 Zuoshen Advanced Class 4 (Nim game problem, k pseudo-ary system, recursion to dynamic programming, recursive routines of priority combination, recursive routines of subsequences, recursion of subsequences Routines, compression techniques of dynamic programming)_Studying~’s blog-CSDN blog
The first method is to find the longest common subsequence of the string str and its reverse unStr, which is their longest palindrome subsequence.
The second approach is to give a definition dp[i][j] to represent str[i. . . The length of the longest palindrome subsequence on j].
Then the possibilities of the longest palindrome subsequence include:
(1) Contains the i position, includes the j position, only str[i] == str[j]
(2) Includes i position but does not include j position
(3) Does not include the i position, but includes the j position
(4) Does not include the i position and does not include the j position.
[Code implementation]
package AdvancedPromotion5;
/**
* @ProjectName: study3
* @FileName: Ex2
* @author:HWJ
* @Data: 2023/9/24 16:59
*/
public class Ex2 {
public static void main(String[] args) {
String str = "123akmk321";
System.out.println(getMax(str));
}
public static int getMax(String s){
char[] str = s.toCharArray();
int[][] map = new int[str.length][str.length];
for (int i = 0; i < str.length; i + + ) { // Fill in the situation where i == j and j == i + 1, this is a good judgment, no need to consider the possibility
map[i][i] = 1;
if (i < str.length - 1){
map[i][i + 1] = str[i] == str[i + 1] ? 2 : 1;
}
}
for (int i = str.length - 3; i >= 0; i--) {
for (int j = i + 2; j < str.length; j + + ) {
int p1 = map[i][j - 1];
int p2 = map[i + 1][j];
int p3 = map[i + 1][j - 1] + (str[i] == str[j] ? 2 : 0);
map[i][j] = Math.max(p1, Math.max(p2, p3));
}
}
return map[0][str.length - 1];
}
}
[Case 3 Trial Model on Range]
[Title description]
[Analysis of ideas]
The construction result dp[i][j] indicates the minimum number of additional characters required to turn str[i….j] into a palindrome string.
(1) str[i] != str[j], there are two strategies at this time. First get str[i…j-1] to turn it into a palindrome string, and then convert the second palindrome string Adding a str[j] to the left side of the string will make the whole string a palindrome. Or first fix str[i + 1…j] to turn it into a palindrome string, and then add a str[i] to the right side of the second palindrome string, and the whole will be a palindrome string.
(2) str[i] == str[j], at this time just change str[i + 1…j-1] into a palindrome string, and the whole is a palindrome string.
Minimizing the last three possibilities will give us the answer we need. After filling in the table through dynamic programming, we get the returned answer by inverting the table.
[Code implementation]
package AdvancedPromotion5;
/**
* @ProjectName: study3
* @FileName: Ex3
* @author:HWJ
* @Data: 2023/9/24 17:10
*/
public class Ex3 {
public static void main(String[] args) {
String s = "123afga1321";
System.out.println(record(s));
}
public static String record(String s) {
int[][] map = recordMap(s);
String ans = recordStr(map, s.toCharArray());
return ans;
}
public static int[][] recordMap(String s) {
char[] str = s.toCharArray();
int len = str.length;
int[][] map = new int[len][len];
for (int i = 0; i < len; i + + ) {
map[i][i] = 0;
if (i < len - 1) {
map[i][i + 1] = (str[i] == str[i + 1] ? 0 : 1);
}
}
for (int i = len - 3; i >= 0; i--) {
for (int j = i + 2; j < len; j + + ) {
int p1 = map[i + 1][j] + 1;
int p2 = map[i][j - 1] + 1;
map[i][j] = Math.min(p1, p2);
if (str[i] == str[j]) {
map[i][j] = Math.min(map[i][j], map[i + 1][j - 1]);
}
}
}
return map;
}
public static String recordStr(int[][] map, char[] str) {
int len = map.length;
int need = map[0][len - 1];
int p = 0;
int q = len - 1;
char[] ans = new char[len + need];
int i = 0;
int j = ans.length - 1;
while (p <= q) {
if (p == q) {
ans[i] = str[p];
break;
}
if (str[p] == str[q]) {
int p1 = map[p + 1][q - 1];
int p2 = map[p + 1][q];
if (map[p][q] == p1) {
ans[i + + ] = str[p + + ];
ans[j--] = str[q--];
} else if (map[p][q] == p2 + 1) {
ans[i + + ] = str[p];
ans[j--] = str[p + + ];
} else {
ans[i + + ] = str[q];
ans[j--] = str[q--];
}
} else {
int p1 = map[p + 1][q];
if (map[p][q] == p1 + 1) {
ans[i + + ] = str[p];
ans[j--] = str[p + + ];
} else {
ans[i + + ] = str[q];
ans[j--] = str[q--];
}
}
}
return String.valueOf(ans);
}
}
[Case 4: Model tried from left to top + model tried on the range]
[Title description]
[Analysis of ideas]
Because we want to cut them all into the minimum number of cuts of palindrome substrings, we can traverse each possibility from left to right. When traversing the possibilities, we will judge whether the current cut is reasonable. If the current cut is guaranteed to be a reasonable palindrome substring, skewers, that is, continue to cut down. The time complexity of this kind of traversal is O(N^2), and because each traversal requires a judgment process, the judgment time complexity is O(N), so the overall time complexity is O(N^3). At this time, the time complexity is too high, and we need to speed up the judgment process through a range of models.
To count a table, map[i][j] indicates whether str[i….j] is a palindrome substring. The palindrome substring must satisfy str[i] == str[j], and str[i + 1 ][j – 1] is also a palindrome substring.
[Code implementation]
package AdvancedPromotion5;
/**
* @ProjectName: study3
* @FileName: Ex4
* @author:HWJ
* @Data: 2023/9/25 8:32
*/
public class Ex4 {
public static void main(String[] args) {
String str = "ABA";
boolean[][] map = judge(str);
System.out.println(getMin(str.toCharArray(), 0, map));
}
public static int getMin(char[] str, int index, boolean[][] map){
if (index == str.length){
return -1;
}
int res = Integer.MAX_VALUE;
for (int i = index; i < str.length; i + + ) {
if (map[index][i]){
res = Math.min(res, 1 + getMin(str, i + 1, map));
}
}
return res;
}
public static boolean[][] judge(String s){
boolean[][] map = new boolean[s.length()][s.length()];
char[] str = s.toCharArray();
for (int k = 0; k < str.length; k + + ) {
map[k][k] = true;
if (k < str.length - 1){
map[k][k + 1] = str[k] == str[k + 1];
}
}
for (int k = str.length - 3; k >= 0 ; k--) {
for (int l = k + 2; l < str.length; l + + ) {
if (str[k] == str[l]){
map[k][l] = map[k + 1][l - 1];
}else {
map[k][l] = false;
}
}
}
return map;
}
}
[Case 5 Trial Model on Range]
[Title Description]
[Analysis of ideas]
Construct a two-dimensional table, map[i][j] represents how many palindromic subsequences str[i…j] has.
Then the palindrome subsequence is divided into the following possibilities:
(1) Contains the i position and includes the j position.
(2) Includes the i position but does not include the j position.
(3) Does not include the i position, but includes the j position.
(4) Does not include the i position and does not include the j position.
map[i + 1][j] represents the number of all palindrome subsequences that do not contain the i position, which may or may not contain the j position, representing the possibility of (3) (4). j
map[i][j – 1] represents the number of all palindrome subsequences that do not contain the j position, which may or may not contain the i position, representing the possibilities of (2) (4).
map[i + 1][j-1] represents the number of all palindrome subsequences that do not contain j position and do not contain j position, representing the possibility of (4).
(1) The possibility is only possible when str[i] == str[j], and the value is equal to map[i + 1][j-1] + 1. Because if these two are removed, it is a palindrome number, plus it is still a palindrome number, and there is one more case where there are only these two sequences.
[Code implementation]
package AdvancedPromotion5;
/**
* @ProjectName: study3
* @FileName: Ex5
* @author:HWJ
* @Data: 2023/9/25 9:05
*/
public class Ex5 {
public static void main(String[] args) {
String str= "ABA";
System.out.println(getNum(str));
}
public static int getNum(String s){
char[] str = s.toCharArray();
int len = str.length;
int[][] map = new int[len][len];
for (int i = 0; i < len; i + + ) {
map[i][i] = 1;
if (i < len - 1){
map[i][i + 1] = (str[i] == str[i + 1] ? 3 : 2);
}
}
for (int i = len - 3; i >= 0; i--) {
for (int j = i + 2; j < len; j + + ) {
map[i][j] = map[i + 1][j] + map[i][j - 1] - map[i + 1][j - 1];
if (str[i] == str[j]){
map[i][j] + = (map[i + 1][j - 1] + 1);
}
}
}
return map[0][len - 1];
}
}