rust练习-2

总结

string 遍历，char比较
vec 当做stack使用，出栈 入栈
vec 变量 修改数据，usize 索引
不支持++, 只能+=
位运算符 >>, 二分查找算法

1. https://leetcode.cn/problems/valid-parentheses/submissions/

pub fn match_str(c1:char,c2:char) -> bool {
        return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')  || (c1 == '[' && c2 == ']')
}

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

        if s.len() < 2 {
            return false
        }
        let mut stack:Vec<char> = Vec::new();
        for c in s.chars(){
          let stack_len = stack.len();
           if stack_len == 0 {
               stack.push(c);
            } else {
               if match_str(stack[stack_len-1], c) {
                   stack.pop();
               } else {
                   stack.push(c);
               }
            }
        }
        stack.len() == 0
        
    }   
}

or 
========

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

        if s.len() < 2 {
            return false
        }
        let mut stack:Vec<char> = Vec::new();
        for c in s.chars(){
          let stack_len = stack.len();
           if stack_len == 0 {
               stack.push(c);
            } else {
               if Solution::match_str(stack[stack_len-1], c) {
                   stack.pop();
               } else {
                   stack.push(c);
               }
            }
        }
        stack.len() == 0
        
    }

    pub fn match_str(c1:char,c2:char) -> bool {
        return (c1 == '(' && c2 == ')') || (c1 == '{' && c2 == '}')  || (c1 == '[' && c2 == ']')
}
}

2. https://leetcode.cn/problems/remove-duplicates-from-sorted-array/submissions/

impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        let total = nums.len();
        if total < 2 as usize {
            return total as i32
        }
        let mut head:usize = 0;
        let mut tail:usize = 1;
        while tail < total {
            if nums[tail] != nums[head] {
                head += 1;
                nums[head] = nums[tail];
            }
            tail += 1;
        }
        let result = head+1 ;
        result as i32

    }
}

3. https://leetcode.cn/problems/search-insert-position/submissions/

impl Solution {
    // 找到第一个 >=target的下标
    pub fn search_insert(nums: Vec<i32>, target: i32) -> i32 {

        
        let n = nums.len() as i32;
        let mut result = n;
        let mut leftnum = 0;
        let mut right = n - 1;
        let mut midddle = 0;
        while leftnum <= right {
              midddle = leftnum +  ((right-leftnum)>>1) ;// 必须加() ((right-leftnum)>>1) 
              if nums[midddle as usize] >= target {
                  result = midddle;
                  right = midddle - 1;
              } else {
                  leftnum = midddle + 1;
              }
              
        }
        result

    }
}

4. https://leetcode.cn/problems/maximum-subarray/submissions/

const MAX_NUM:usize = 100001;

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

        // dp[i] = max(dp[i-1]+nums[i],  nums[i])  包含第i个的元素的最大和
        let n = nums.len();
        let mut dp:Vec<i32> = vec![0;MAX_NUM];
        dp[0] = nums[0];
        let mut idx:usize = 1;
        let mut sum= 0;
        while idx < n {
            sum = dp[idx-1] + nums[idx] ;
            if sum > nums[idx] {
                dp[idx] = sum;
            } else {
                dp[idx] = nums[idx];
            }
            idx += 1;
        }
        let mut result = dp[0];
        idx = 1;
        while idx < n {
            if dp[idx] > result {
                result = dp[idx];
            }
            idx += 1;
        }
        result
    }

    pub fn max_num(n:i32, m:i32) ->i32 {
        if n > m {
            return n
        }
        m
    }

    pub fn max_sub_array_v2(nums: Vec<i32>) -> i32 {


        let n = nums.len();
        // dp[i] = max(dp[i-1]+nums[i],  nums[i])  包含第i个的元素的最大和
        let mut dp = nums[0]; // dp 滚动数组
        let mut result = dp;
        let mut idx:usize = 1;
        while idx < n {
            dp = Solution::max_num(dp + nums[idx], nums[idx]);
            if result < dp {
                result = dp;
            }
            idx += 1;
        }
        
        result
    }
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {

        // dp[i] = max(dp[i-1]+nums[i],  nums[i])  包含第i个的元素的最大和
        let n = nums.len();
        let mut dp:Vec<i32> = Vec::with_capacity(n);
        // let mut dp: [i32; n] = [0; n];
        dp.push(nums[0]);
        // dp[0] = nums[0];
        let mut idx:usize = 1;
        let mut sum= 0;
        let mut result = dp[0];
        while idx < n {
            // dp[idx] = Solution::max_num(dp[idx-1] + nums[idx], nums[idx]);
            dp.push(Solution::max_num(dp[idx-1] + nums[idx], nums[idx]));
            // if dp[idx] > result {
            //     result = dp[idx];
            // }
            idx += 1;
            
        }
        
        idx = 1;
        for num in dp {
            if num > result {
                result = num;
            }
        }
        // while idx < n {
        //     if dp[idx] > result {
        //         result = dp[idx];
        //     }
        //     idx += 1;
        // }
        result
    }
}