2021-11-12

[Zheaoli]

2021-11-12

[MILIFIRE]

/*
 * @lc app=leetcode.cn id=3 lang=rust
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start
use std::collections::HashSet;
impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let len = s.len() as i32;
        if len <= 1{
            return len;
        }
        let ary = s.as_bytes();
        let mut res = 0;
        let mut index = 0;
        let mut left = 0;
        let mut set = HashSet::new();
        while  left < len{
            let item = &ary[left as usize];
            if None != set.get(&item){
                res = res.max(set.len()as i32);
                index += 1;
                left = index;
                set.clear();
            }else{
                set.insert(item);
                left += 1;
            }
        }
        println!("len:{}",set.len() );
        if res< set.len() as i32{
            res = res.max(set.len() as i32);
        }
        res
    }
}
// @lc code=end

---

微信id: mili 来自 vscode 插件

[MILIFIRE]

/*
 * @lc app=leetcode.cn id=3 lang=rust
 *
 * [3] 无重复字符的最长子串
 */

// @lc code=start
use std::collections::HashSet;
impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        let len = s.len() as i32;
        let ary = s.as_bytes();
        let mut res = 0;
        let mut right = 0;
        let mut set = HashSet::new();
        for i in 0..len {
            if i != 0 {
                let item = &ary[(i-1) as usize];
                set.remove(&item);
            }
            while  right < len {
                let item = &ary[right as usize];
                if set.contains(&item){
                    break;
                }
                set.insert(item);
                right += 1;
            }
            res = res.max(set.len() as i32);
        }
       res
    }
}
// @lc code=end

/* 在上面的流程中，我们还需要使用一种数据结构来判断 是否有重复的字符，常用的数据结构为哈希集合（即 C++ 中的 std::unordered_set，Java 中的 HashSet，Python 中的 set, JavaScript 中的 Set）。在左指针向右移动的时候，我们从哈希集合中移除一个字符，在右指针向右移动的时候，我们往哈希集合中添加一个字符。

至此，我们就完美解决了本题。

---

微信id: mili 来自 vscode 插件

[sishenhei7]

function getMoneyAmount(n: number): number {
    const dp = Array(n).fill(0).map(_ => Array(n).fill(0))
    for (let i = 0; i < n; i += 1) {
        dp[i][i] = 0
        if (i + 1 < n) {
            dp[i][i + 1] = i + 1
        }
    }

    for (let i = 2; i < n; i += 1) {
        for (let j = 0; j < n; j += 1) {
            let min = Infinity
            // [j, j + k, j + i]
            // [j, j + k - 1] (j + k) [j + k + 1, j + i]
            // dp[j][j + k - 1] (j + k + 1) dp[j + k + 1][j + i]
            if (j + i < n) {
                for (let k = 1; k < i; k += 1) {
                    min = Math.min(min, j + k + 1 + Math.max(dp[j][j + k - 1], dp[j + k + 1][j + i]))
                }
                dp[j][j + i] = min
            }
        }
    }

    return dp[0][n - 1]
}

[MILIFIRE]