华为OD 2023机试题java python c++ go rust ,javascript

原创

疯狂的KK

修改于 2023-05-08 14:41:22

2040

修改于 2023-05-08 14:41:22

文章被收录于专栏：Java项目实战Java项目实战

给定一个字符串 s ，找出这样一个子串：

1）该子串中的任意一个字符最多出现2次；

2）该子串不包含指定某个字符；

请你找出满足该条件的最长子串的长度。

输入描述：第一行为要求不包含的指定字符，为单个字符，取值范围0-9a-zA-Z

第二行为字符串s，每个字符范围0-9a-zA-Z，长度范围1,10000

输出描述：一个整数，满足条件的最长子串的长度；如果不存在满足条件的子串，则返回0

示例

示例1

输入：

ABC123

输出：6

示例2

输入：

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;
}

// 将给定字符串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 max

rust

// 将给定字符串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);
    // 分别递归检查左右子树是否对称
}

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)
    }
}

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 count

c++

public:
    int countOnes(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }

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
}

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

华为