给定一个字符串 s ，找出这样一个子串：
1）该子串中的任意一个字符最多出现2次；
2）该子串不包含指定某个字符；
请你找出满足该条件的最长子串的长度。
输入描述：第一行为要求不包含的指定字符，为单个字符，取值范围0-9a-zA-Z
第二行为字符串s，每个字符范围0-9a-zA-Z，长度范围1,10000
输出描述：一个整数，满足条件的最长子串的长度；如果不存在满足条件的子串，则返回0
示例
示例1
输入：
D
ABC123
输出：6
示例2
输入：
D
ABACA123D
输出：7
解题思路
我们定义left和right两个指针,左右指针代表当前考察的子串的左右边界。
在移动右指针时,如果新加入的字符没有出现过,或者出现次数没有超过2次,我们就扩大窗口,并更新最大长度。
如果新加入的字符已经出现过2次,我们就收缩窗口的左侧边界,直到移除了一个重复出现的字符。
我们重复这个过程,直到right指针遍历完整个字符串,就可以得到满足条件的最长子串长度。
时间复杂度:O(n)O(n),n为字符串长度。
空间复杂度:O(1)O(1)。
Java实现
import java.util.HashSet;
import java.util.Set;
public class LongestSubstring {
public int lengthOfLongestSubstring(String s, char excluded) {
Set<Character> set = new HashSet<>();
int left = 0, right = 0;
int max = 0;
while (right < s.length()) {
if (set.add(s.charAt(right))) {
max = Math.max(max, right - left + 1);
right++;
} else {
set.remove(s.charAt(left++));
}
}
return max;
}
public static void main(String[] args) {
LongestSubstring solution = new LongestSubstring();
String s = "ABC123";
char c = 'D';
System.out.println(solution.lengthOfLongestSubstring(s, c));
}
}python
class LongestSubstring:
def lengthOfLongestSubstring(self, s, excluded):
s = list(s)
set = set() # 创建一个空集合
left = 0 # 初始化左指针
right = 0 # 初始化右指针
max = 0 # 初始化最大子串长度
while right < len(s):
if s[right] not in set: # 如果当前字符不在集合中
set.add(s[right]) # 将当前字符加入集合
max = max(max, right - left + 1) # 更新最大子串长度
right += 1 # 右指针右移
else:
set.remove(s[left]) # 将左指针指向的字符从集合中移除
left += 1 # 左指针右移
return max # 返回最大子串长度
solution = LongestSubstring()
s = "ABC123"
c = 'D'
print(solution.lengthOfLongestSubstring(s, c)) # 输出最大子串长度C++
#include <iostream>
#include <unordered_set>
using namespace std;
class LongestSubstring {
public:
int lengthOfLongestSubstring(string s, char excluded) {
unordered_set<char> set; // 创建一个无序集合
int left = 0, right = 0; // 初始化左右指针
int max = 0; // 初始化最大长度
while (right < s.length()) { // 当右指针小于字符串长度时
if (set.insert(s[right]).second) { // 如果插入成功
max = std::max(max, right - left + 1); // 更新最大长度
right++; // 右指针右移
} else { // 如果插入失败
set.erase(s[left++]); // 左指针右移
}
}
return max; // 返回最大长度
}
};
int main() {
LongestSubstring solution; // 创建一个 LongestSubstring 类的实例
string s = "ABC123"; // 初始化字符串
char c = 'D'; // 初始化排除字符
cout << solution.lengthOfLongestSubstring(s, c) << endl; // 输出最大长度
return 0;
}go
// 将给定字符串s转换为字符数组
s := []rune(s)
// 创建一个空map，用于存储字符出现的位置
set := make(map[rune]int)
// 初始化左指针和最大子串长度
left, max := 0, 0
// 遍历字符串
for right, char := range s {
// 如果字符已经在map中出现过，并且出现位置在左指针右侧
if _, ok := set[char]; ok && set[char] >= left {
// 将左指针移动到该字符出现位置的右侧
left = set[char] + 1
}
// 更新最大子串长度
max = int(math.Max(float64(max), float64(right-left+1)))
// 将字符出现位置存入map中
set[char] = right
}
// 返回最大子串长度
return maxrust
// 将给定字符串s转换为字符数组
let s: Vec<char> = s.chars().collect();
// 创建一个空map，用于存储字符出现的位置
let mut set: HashMap<char, usize> = HashMap::new();
// 初始化左指针和最大子串长度
let (mut left, mut max) = (0, 0);
// 遍历字符串
for right in 0..s.len() {
let char = s[right];
// 如果字符已经在map中出现过，并且出现位置在左指针右侧
if let Some(&pos) = set.get(&char) {
if pos >= left {
// 将左指针移动到该字符出现位置的右侧
left = pos + 1;
}
}
// 更新最大子串长度
max = max.max(right - left + 1);
// 将字符出现位置存入map中
set.insert(char, right);
}
// 返回最大子串长度
max- 实现一个函数,判断一棵二叉树是否对称。例如:下面这棵树是对称的。
1/ \
2 2
/ \ / \
3 4 4 3
伪代码思路
定义一个函数判断二叉树是否对称，需要传入根节点和父节点。
如果当前节点是左子树的根节点，则递归判断右子树是否对称。
如果当前节点是右子树的根节点，则递归判断左子树是否对称。
如果左右子树都不对称，则返回false。
如果左右子树都对称，则返回true。
在主函数中调用该函数，传入根节点和父节点进行测试。
java
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return check(root.left, root.right) && isSymmetric(root.left) && isSymmetric(root.right);
}
private boolean check(TreeNode left, TreeNode right) {
if (left == null && right == null) return true; // 如果左右子树都为空，则对称
if (left == null || right == null) return false; // 如果左右子树有一个为空，则不对称
if (left.val != right.val) return false; // 如果左右子树的值不相等，则不对称
return check(left.left, right.right) && check(left.right, right.left); // 分别递归检查左右子树是否对称
}
public static void main(String[] args) {
// 创建一棵二叉树并测试对称性
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(2);
root.right.left = new TreeNode(3);
root.right.right = new TreeNode(4);
root.right.left.right = new TreeNode(4);
boolean result = isSymmetric(root);
System.out.println(result); // 输出true,表示该二叉树是对称的
}python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def isSymmetric(root: TreeNode) -> bool:
if root is None:
return True
return check(root.left, root.right) and isSymmetric(root.left) and isSymmetric(root.right)
def check(left: TreeNode, right: TreeNode) -> bool:
if left is None and right is None:
return True # 如果左右子树都为空，则对称
if left is None or right is None:
return False # 如果左右子树有一个为空，则不对称
if left.val != right.val:
return False # 如果左右子树的值不相等，则不对称
return check(left.left, right.right) and check(left.right, right.left) # 分别递归检查左右子树是否对称
c++
class TreeNode{
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int val=0, TreeNode* left=nullptr, TreeNode* right=nullptr){
this->val = val;
this->left = left;
this->right = right;
}
};
bool isSymmetric(TreeNode* root){
if(root == nullptr){
return true;
}
return check(root->left, root->right) && isSymmetric(root->left) && isSymmetric(root->right);
}
bool check(TreeNode* left, TreeNode* right){
if(left == nullptr && right == nullptr){
return true;
// 如果左右子树都为空，则对称
}
if(left == nullptr || right == nullptr){
return false;
// 如果左右子树有一个为空，则不对称
}
if(left->val != right->val){
return false;
// 如果左右子树的值不相等，则不对称
}
return check(left->left, right->right) && check(left->right, right->left);
// 分别递归检查左右子树是否对称
}go
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
func isSymmetric(root *TreeNode) bool {
if root == nil {
return true
}
return check(root.left, root.right) && isSymmetric(root.left) && isSymmetric(root.right)
}
func check(left *TreeNode, right *TreeNode) bool {
if left == nil && right == nil {
return true
// 如果左右子树都为空，则对称
}
if left == nil || right == nil {
return false
// 如果左右子树有一个为空，则不对称
}
if left.val != right.val {
return false
// 如果左右子树的值不相等，则不对称
}
return check(left.left, right.right) && check(left.right, right.left)
// 分别递归检查左右子树是否对称
}
rust
type TreeNode struct {
val: i32,
left: Option<Box<TreeNode>>,
right: Option<Box<TreeNode>>,
}
fn is_symmetric(root: Option<&Box<TreeNode>>) -> bool {
match root {
None => true,
Some(node) => check(&node.left, &node.right) && is_symmetric(node.left.as_ref()) && is_symmetric(node.right.as_ref())
}
}
fn check(left: &Option<Box<TreeNode>>, right: &Option<Box<TreeNode>>) -> bool {
match (left, right) {
(None, None) => true,
(None, _) | (_, None) => false,
(Some(l), Some(r)) => l.val == r.val && check(&l.left, &r.right) && check(&l.right, &r.left)
}
}
js
type TreeNode = class {
constructor(val, left=null, right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
function isSymmetric(root) {
function check(left, right) {
if (!left && !right) {
return true;
}
if (!left || !right) {
return false;
}
return left.val == right.val && check(left.left, right.right) && check(left.right, right.left);
}
if (!root) {
return true;
}
return check(root.left, root.right) && isSymmetric(root.left) && isSymmetric(root.right);
}
- 实现单例模式,要求线程安全。
- 实现冒泡排序,选择排序,插入排序。并分析三种排序算法的时间复杂度。
- 给你两个有序整数数组nums1 和 nums2,请你将 nums2 合并到nums1中,使得nums1 成为一个有序数组。
- 给定一个链表,判断是否有环。如果有环,返回入环节点,否则返回null。
- 编写一个函数,输入是一个无序链表,输出一个从小到大排序的有序链表。
- 实现一个LRU cache,要求get和set方法的时间复杂度为O(1)。
- 给出两个字符串s1和s2,请实现一个函数判断s2是否是s1的变位词。
- 实现队列的入队和出队操作,要求出队操作pop的时间复杂度为O(1)。
11.给定一个32位整数,返回该整数中1的个数。例如:给定整数11,返回2。给定整数128,返回1。
利用n & (n - 1)会将n的最后一个1变为0的特性。
每循环一次,就找到一个1,并将其变为0。循环终止的条件是n变为0,count的值就是n中1的个数。例如:
n = 11,
11 & (11 - 1) = 11 & 10 = 10 // 找到一个1,count变为1
10 & (10 - 1) = 10 & 9 = 8 // 找到一个1,count变为2
8 & (8 - 1) = 8 & 7 = 0 // n变为0,循环终止,count值为2 n = 128
128 & (128 - 1) = 128 & 127 = 0 // 找到一个1,count变为1,n变为0,循环终止,count值为1所以时间复杂度是O(k),k是n中1的个数。空间复杂度O(1)。
java
public int countOnes(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}python
def countOnes(n):
count = 0
while n != 0:
n &= (n - 1)
count += 1
return countc++
public:
int countOnes(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1);
count++;
}
return count;
}go
public:
func countOnes(n int) int {
count := 0
for n != 0 {
n &= (n - 1)
count++
}
return count
} rust
pub fn count_ones(n: i32) -> i32 {
let mut count = 0;
let mut m = n;
while m != 0 {
m &= m - 1;
count += 1;
}
count
}