rust练习-4

总结

string的字符比较和遍历
HashMap统计
HashSet判重
滑动窗口

1、https://leetcode.cn/problems/valid-palindrome/

impl Solution {
    pub fn is_palindrome(s: String) -> bool {

        if s=="" {
            return true
        } 
        let  ls = s.to_lowercase();
        let mut v2 = Vec::with_capacity(ls.len());
        for c in ls.chars() {
            if (c >= '0' && c <= '9' ) || (c>='a' && c<='z') {
                v2.push(c);
            }
            
        }
        let total = v2.len();
        if total == 0 {
            return true
        }
        let mut left :usize = 0;
        let mut right:usize = total - 1;
        while left < right {
            
            if  v2[left] != v2[right] {
                return false
            }
            left +=1;
            right -=1;
        }
        return true
    }
}

2、https://leetcode.cn/problems/single-number/submissions/

impl Solution {
    pub fn single_number(nums: Vec<i32>) -> i32 {

        let mut ret = 0;
        for num in nums {
            ret ^= num;
        }
        ret

    }
}

3、https://leetcode.cn/problems/majority-element/submissions/

use std::collections::HashMap;

impl Solution {
    pub fn majority_element(nums: Vec<i32>) -> i32 {
        
        // 摩尔投票
        let mut result = 0;
        let mut count = 0;
        for num in nums {
            if count == 0 {
                result = num;
                count = 1;
            } else if result != num {
                count -= 1;
            } else {
                count +=1;
            }
        }
        result

        
    }

    pub fn majority_element_v1(nums: Vec<i32>) -> i32 {
        
        // hash 统计
        let mut statis = HashMap::with_capacity(nums.len()/2+1);

        for &num in &nums {
             let count = statis.entry(num).or_insert(0);
              *count += 1;
        }
        let mut result = nums[0];
        let mut max = 0;
        for (key, val) in statis.iter() {
            if max < *val {
                max = *val;
                result = *key;
            }
        }
        result
    }
}

4、https://leetcode.cn/problems/contains-duplicate-ii/

use std::collections::HashSet;

impl Solution {



    //     // 滑动窗口算法  ，窗口容量最多K+1 ,在数组上滑动
    pub fn contains_nearby_duplicate(nums: Vec<i32>, k: i32) -> bool {
            let mut window = HashSet::new();
            let mut idx:usize = 0;
            let mut kusize = k as usize;
            let total  = nums.len() as usize;
            while idx < total  {
                if idx >= kusize + 1 {
                    window.remove(&nums[idx-kusize-1]);
                }
                if window.contains(&nums[idx]) {
                    return true;
                }
                window.insert(nums[idx]);
                idx += 1;
            }
            return false;
    }

    pub fn contains_nearby_duplicate_v1(nums: Vec<i32>, k: i32) -> bool {
            let total = nums.len();
           
            let  diff:usize = k as usize;
            let mut first:usize = 0;
            let mut second:usize ;
            while first < total {
                second = first + 1;
                while second < total &&  second <= first + diff {
                    if nums[first] == nums[second] {
                        return true;
                    }
                    second +=1;
                } 
                first += 1;
            }
            
            return false;
    }
}

5、https://leetcode.cn/problems/contains-duplicate/submissions/

use std::collections::HashSet;
impl Solution {
    pub fn contains_duplicate(nums: Vec<i32>) -> bool {

       
        let mut set = HashSet::with_capacity(nums.len());

        for num in nums {
            if set.contains(&num) {
                    return true;
            }
            set.insert(num);
        }
        return false;

    }
}