網(wǎng)上有很多關(guān)于智能pos機(jī)長(zhǎng)度,002 無重復(fù)最長(zhǎng)子串長(zhǎng)度的知識(shí)，也有很多人為大家解答關(guān)于智能pos機(jī)長(zhǎng)度的問題，今天pos機(jī)之家(m.afbey.com)為大家整理了關(guān)于這方面的知識(shí)，讓我們一起來看下吧!
本文目錄一覽：
智能pos機(jī)長(zhǎng)度
首先，老原則，先直接上代碼。
//// Created by tannzh on 2020/6/11.///*給定一個(gè)字符串，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度。示例 1:輸入: "abcabcbb"輸出: 3解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "abc"，所以其長(zhǎng)度為 3。示例 2:輸入: "bbbbb"輸出: 1解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "b"，所以其長(zhǎng)度為 1。示例 3:輸入: "pwwkew"輸出: 3解釋: 因?yàn)闊o重復(fù)字符的最長(zhǎng)子串是 "wke"，所以其長(zhǎng)度為 3。 請(qǐng)注意，你的答案必須是 子串 的長(zhǎng)度，"pwke" 是一個(gè)子序列，不是子串。 */#include <iostream>#include <string>#include <unordered_map>#include <algorithm>using namespace std;class Solution {public: int lengthOfLongestSubstring(string s) { size_t region = 0, start = 0; unordered_map<char, size_t> trace; for(size_t i = 0; i < s.size(); ++i){ auto found = trace.find(s[i]); if(found != trace.end() && found->second >= start) { region = std::max(region, i - start); start = found->second + 1; } trace[s[i]] = i; } return std::max(region, s.size() - start); }};int main(int argc, char **argv){ Solution s; std::string testStr1 = "abcabcbb"; std::string testStr2 = "bbbbb"; std::string testStr3 = "pwwkew"; std::cout << testStr1 << ", lengthOfLongestSubstring: " << s.lengthOfLongestSubstring(testStr1) << std::endl; std::cout << testStr2 << ", lengthOfLongestSubstring: " << s.lengthOfLongestSubstring(testStr2) << std::endl; std::cout << testStr3 << ", lengthOfLongestSubstring: " << s.lengthOfLongestSubstring(testStr3) << std::endl; return 0;}解題思路
首先，求的只是長(zhǎng)度，那么一定有一個(gè) trace 來邊記錄邊比較(max)。
其次，沒有重復(fù)字符幾乎是唯一條件，那么檢查重復(fù)顯然用 k-v mapping.
最后，要考慮一次迭代過程中，如何度量這個(gè)長(zhǎng)度。
設(shè) substr 的起點(diǎn)為 start(s), 終點(diǎn)為 last(l). 每一次迭代，記錄一張索引表。
上圖所示，last 指向 `a`, 查詢當(dāng)前表可知，`a` 的位置記錄在案，且 `pos >= start`. 故此刻誕生一個(gè) substr. 長(zhǎng)度為 `last - start`. s 更新位置為 `pos + 1`.有：
auto found = cache.find(s[last]);if (found != cache.end() && found->second >= start) { region = max(region, last - start); start = found->second + 1;}cache[s[last]] = last;
注意最終還需要比較一次，返回 max(ret, s.size() - start)
以上就是關(guān)于智能pos機(jī)長(zhǎng)度,002 無重復(fù)最長(zhǎng)子串長(zhǎng)度的知識(shí)，后面我們會(huì)繼續(xù)為大家整理關(guān)于智能pos機(jī)長(zhǎng)度的知識(shí)，希望能夠幫助到大家！
