删除无效的括号(广度优先搜索、字符串)
给你一个由若干括号和字母组成的字符串 s ，删除最小数量的无效括号，使得输入的字符串有效。 返回所有可能的结果。答案可以按 任意顺序 返回。
示例 1： 输入：s = "()())()" 输出：["(())()","()()()"] 示例 2： 输入：s = "(a)())()" 输出：["(a())()","(a)()()"] 示例 3： 输入：s = ")(" 输出：[""]
提示：
- 1 <= s.length <= 25
- s 由小写英文字母以及括号 '(' 和 ')' 组成
- s 中至多含 20 个括号
解答：
public class Solution {
private Set<String> set;
private String input;
private int maxLen = 0;
public List<String> removeInvalidParentheses(String s) {
set = new HashSet<>();
input = s;
removeInvalidParentheses(0, "", 0, 0);
return new ArrayList<>(set);
}
private void removeInvalidParentheses(int index, String valid, int leftCount, int rightCount) {
if (leftCount < rightCount) {
return;
}
if (index == input.length()) {
if (leftCount == rightCount) {
if (maxLen < valid.length()) {
maxLen = valid.length();
set.clear();
set.add(valid);
} else if (maxLen == valid.length()) {
set.add(valid);
}
}
return;
}
char c = input.charAt(index);
if (c == '(') {
removeInvalidParentheses(index + 1, valid, leftCount, rightCount);
removeInvalidParentheses(index + 1, valid + c, leftCount + 1, rightCount);
} else if (c == ')') {
removeInvalidParentheses(index + 1, valid, leftCount, rightCount);
removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount + 1);
} else {
removeInvalidParentheses(index + 1, valid + c, leftCount, rightCount);
}
}
}
计算右侧小于当前元素的个数(树状数组、线段树)
给你`一个整数数组 nums_ ，按要求返回一个新数组 counts _。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。
示例 1：
输入：nums = [5,2,6,1]
输出：[2,1,1,0]
解释： 5 的右侧有 2 个更小的元素 (2 和 1) 2 的右侧仅有 1 个更小的元素 (1) 6 的右侧有 1 个更小的元素 (1) 1 的右侧有 0 个更小的元素
示例 2：
输入：nums = [-1] 输出：[0]
示例 3：
输入：nums = [-1,-1] 输出：[0,0]
提示：
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
解答：
class Solution {
public static List<Integer> countSmaller(int[] nums) {
if (nums.length == 0) {
return new ArrayList<>();
}
int min = Integer.MAX_VALUE;
for (int value : nums) {
if (value < min) {
min = value;
}
}
for (int i = 0; i < nums.length; i++) {
nums[i] = nums[i] - min + 1;
}
int max = Integer.MIN_VALUE;
for (int value : nums) {
if (value > max) {
max = value;
}
}
int[] BITree = new int[max + 1];
BITree[0] = 0;
int[] countArr = new int[nums.length];
for (int i = nums.length - 1; i >= 0; i--) {
int count = getSum(nums[i] - 1, BITree);
countArr[i] = count;
update(nums[i], BITree);
}
List<Integer> result = new ArrayList<>();
for (int value : countArr) {
result.add(value);
}
return result;
}
public static int getSum(int value, int[] BITree) {
int sum = 0;
while (value > 0) {
sum += BITree[value];
value -= (value & -value);
}
return sum;
}
public static void update(int value, int[] BITree) {
while (value <= BITree.length - 1) {
BITree[value] += 1;
value += (value & -value);
}
}
}
Excel表列名称(数学、字符串)
给你一个整数 columnNumber ，返回它在 Excel 表中相对应的列名称。 例如： A -> 1 B -> 2 C -> 3 ... Z -> 26 AA -> 27 AB -> 28 ...
示例 1： 输入：columnNumber = 1 输出："A" 示例 2： 输入：columnNumber = 28 输出："AB" 示例 3： 输入：columnNumber = 701 输出："ZY" 示例 4： 输入：columnNumber = 2147483647 输出："FXSHRXW"
提示：
- 1 <= columnNumber <= 231 - 1
解答：
class Solution {
public String convertToTitle(int n) {
if (n <= 0) {
return "";
}
StringBuilder sb = new StringBuilder();
while (n > 0) {
n--;
sb.append((char) (n % 26 + 'A'));
n = n / 26;
}
return sb.reverse().toString();
}
}
本文内容到此结束了， 如有收获欢迎点赞
标签：nums,int,示例,Excel,表列,value,valid,字符串,rightCount From： https://blog.51cto.com/zhanjq/6192248