给定一个字符串 s
,计算具有相同数量 0 和 1 的非空(连续)子字符串的数量,并且这些子字符串中的所有 0 和所有 1 都是连续的。
重复出现的子串要计算它们出现的次数。
示例 1 :
输入: "00110011"
输出: 6
解释: 有6个子串具有相同数量的连续1和0:“0011”,“01”,“1100”,“10”,“0011” 和 “01”。
请注意,一些重复出现的子串要计算它们出现的次数。
另外,“00110011”不是有效的子串,因为所有的0(和1)没有组合在一起。
class Solution {
public int countBinarySubstrings(String s) {
int ans = 0;
int start = 0;
int last = 0;
int n = s.length();
while (start < n) {
int c = s.charAt(start);
int count = 0;
while (start < n && c == s.charAt(start)) {
count++;
start++;
}
ans += Math.min(last, count);
last = count;
}
return ans;
}
}
给定二叉搜索树(BST)的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在,则返回 NULL。
例如,
给定二叉搜索树:
4
/ \
2 7
/ \
1 3
和值: 2
你应该返回如下子树:
2
/ \
1 3
class Solution {
public TreeNode searchBST(TreeNode root, int val) {
if (root == null || root.val == val) {
return root;
}
return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
}
}
给你一个整数数组 nums
,请编写一个能够返回数组 “中心下标” 的方法。
数组 中心下标 是数组的一个下标,其左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心下标,返回 -1
。如果数组有多个中心下标,应该返回最靠近左边的那一个。
**注意:**中心下标可能出现在数组的两端。
示例 1:
输入:nums = [1, 7, 3, 6, 5, 6]
输出:3
解释:
中心下标是 3 。
左侧数之和 (1 + 7 + 3 = 11),
右侧数之和 (5 + 6 = 11) ,二者相等。
class Solution {
public int pivotIndex(int[] nums) {
int total = 0;
int sum = 0;
for (int n : nums) {
total += n;
}
for (int i = 0; i < nums.length; i++) {
if (sum + sum + nums[i] == total) {
return i;
}
sum += nums[i];
}
return -1;
}
}
给定一个可包含重复数字的序列 nums
,按任意顺序 返回所有不重复的全排列。
示例 1:
输入:nums = [1,1,2]
输出:
[[1,1,2],
[1,2,1],
[2,1,1]]
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
backTrace(nums, used);
return ans;
}
public void backTrace(int[] nums, boolean[] used) {
if (path.size() == nums.length) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i - 1] == nums[i] && used[i - 1] == false) {
continue;
}
if (used[i] == false) {
path.add(nums[i]);
used[i] = true;
backTrace(nums, used);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
}