给定一个有序数组arr，从左到右依次表示X轴上从左往右点的位置，给定一个正整数K，返回如果有一根长度为K的绳子，最多能盖住几个点，绳子的边缘点碰到X轴上的点，也算盖住。
- 滑动窗口，规定L,R判断此时R -> L是否大于给定的长度K ，一直增大R，直到找到此时以L开头时的最大长度记录此时的值。然后向右移动L继续上面的步骤。
/**
给定一个有序数组arr，从左到右依次表示X轴上从左往右点的位置，给定一个正整数K，
返回如果有一根长度为K的绳子，最多能盖住几个点，绳子的边缘点碰到X轴上的点，也算盖住。
*/
public class CoverNum {
public static int coverNum(int[] arr,int k){
if(arr == null || arr.length == 0 || k < 0){
return 0;
}
int n = arr.length;
int L = 0;
int R = 0;
int max = 0;
// 枚举所有开头
while (L < n){
while (R < n && (arr[R] - arr[L] <= k)){
R++;
}
max = Math.max(max,R - L);
L++;
}
return max;
}
}
括号有效配对是指：1）任何一个左括号都能找到和其正确配对的右括号，2）任何一个右括号都能找到和其正确配对的左括号有效的： (()) ()() (()()) 等无效的： (() )( 等。
问题一：怎么判断一个括号字符串有效？
问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效
/**
* 括号有效配对是指：
* 1）任何一个左括号都能找到和其正确配对的右括号
* 2）任何一个右括号都能找到和其正确配对的左括号
* 有效的： (()) ()() (()()) 等
* 无效的： (() )( 等
* 问题一：怎么判断一个括号字符串有效？
* 问题二：如果一个括号字符串无效，返回至少填几个字符能让其整体有效
*/
public class Parentheses {
public static boolean isValid(String str){
if(str == null || str.length() == 0){
// 规定空串无效
return false;
}
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
for (int i = 0; i < n; i++) {
// 遇到左括号count++
if(c[i] == '('){
count ++;
}else {
count --;
}
// 遇到右括号count--
if(count < 0){
return false;
}
}
return count == 0;
}
public static int needParentheses(String str){
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
int need = 0;
for (int i = 0; i < n; i++) {
if(c[i] == '('){
count ++;
}else {
count --;
}
if(count == -1){
// 需要一个左括号来配对
need++;
count = 0;
}
}
// 最后count>=0;
// 如果count为正数，则是需要几个右括号来配对，加上需要几个左括号need
return need + count;
}
public static int needParentheses2(String str){
char[] c = str.toCharArray();
int n = c.length;
int count = 0;
int need = 0;
for (int i = 0; i < n; i++) {
if(c[i] == '('){
count ++;
}else {
if(count == 0){
need++;
}else {
count --;
}
}
}
// 最后count>=0;
// 如果count为正数，则是需要几个右括号来配对，加上需要几个左括号need
return need + count;
}
}
括号有效配对是指：1）任何一个左括号都能找到和其正确配对的右括号,2）任何一个右括号都能找到和其正确配对的左括号,返回一个括号字符串中，最长的括号有效子串的长度。
- 动态规划，生成一个记录位置结尾的形成的最长子串的数组。假设我们现在求i位置的最长有效子串的长度，我们已经知道i-1位置的最长有效子串长度为l，如果此时i位置时左括号，那么此时以i位置结尾不可能形成有效子串，则有效子串长度为0，若是以右括号结尾的那么我们可以看此时从i位置向前推l的长度的前一个位置是否是一个左括号，若不是则以i位置结尾的最长子串长度为0，若是那么我们可以确定以i位置结尾的最长子串的最小长度是l+2，还能不能更长我们要看此时最少形成的子串的开头位置的前一个位置为结尾的子串的长度相加。
/**
* 有效的最长子串
*/
public class MaxParenthesesLen {
public static int maxParenthesesLen(String str){
if(str == null || str.length() == 0){
return 0;
}
char[] c = str.toCharArray();
int n = c.length;
int[] dp = new int[n];
dp[0] = 0;
int max = 0;
for (int i = 1; i < n; i++) {
if(c[i] == ')'){
/**
* 下面两个if可以用这个替换
* int index = i - dp[i-1]-1;
* if(index >=0 && dp[index] =='('){
* dp[i] = dp[i-1]+2 +(index >0 ? dp[index-1] :0);
* }
*/
if(i-dp[i-1]-1 >= 0){
dp[i] = c[i-dp[i-1]-1] == '('? dp[i-1]+2:0;
}
if(i-dp[i-1]-2 >= 0){
dp[i] = dp[i] + dp[i-dp[i-1]-2];
}
}
max = Math.max(max,dp[i]);
}
return max;
}
// 求括号嵌套的深度,前提是括号字符串一定有效
// 一个变量count左括号加，右括号减，抓取遍历过程中的最大值
public static int deep(String str){
char[] c = str.toCharArray();
int max = 0;
int count = 0;
for (int i = 0; i < c.length; i++) {
count = c[i] == '('?count+1 : count-1;
max = Math.max(max,count);
}
return max;
}
public static void main(String[] args) {
String str = "((()))((()))()";
System.out.println(maxParenthesesLen(str));
System.out.println(deep(str));
}
}
有一些排成一行的正方形。每个正方形已经被染成红色或者绿色。现在可以选择任意一个正方形然后用这两种颜色的任意一种进行染色,这个正方形的颜色将 会被覆盖。目标是在完成染色之后,每个红色R都比每个绿色G距离最左侧近。 返回最少需要涂染几个正方形。如样例所示: s = RGRGR 我们涂染之后变成RRRGG满足要求了,涂染的个数为2,没有比这个更好的涂染方案。
- 题意就是要求红色在左边绿色在右边。我们可以在内个位置作一个分界线，计算满足要求的最少的便函个数，分割后会分成两个部分，左边部分需要把绿色变成红色，右边部分需要把红色变成绿色，没分一次统计此时的变换次数然后选出次数最少的。如果不优化每一次都会重新计算左边G的个数，右边R的个数，我们可以用预处理技巧收集每个位置左边个数，右边R的个数。
155-2731-8020