据红星新闻报道，字节跳动于3月6日下午在内部发布了《企业纪律与职业道德委员会通报》。通报显示，2024年字节跳动共辞退违规员工353人，并将39人移交司法机关追究刑事责任。
果然公司大了就容易出现管理漏洞，去年11月字节跳动还发布了当年第四份《企业纪律与职业道德委员会通报》。当时的通报显示，有103人因违法违规行为被辞退（含外包及实习生），其中11人因涉嫌构成刑事犯罪，被公安机关立案侦查。希望今年大家还是知法守法，被辞退是小事，涉及刑事犯罪就属于自毁前程了。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第763. 划分字母区间，难度是中等。
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。例如，字符串 "ababcc" 能够被分为 ["abab", "cc"]，但类似 ["aba", "bcc"] 或 ["ab", "ab", "cc"] 的划分是非法的。
示例1：
输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
-
1 <= s.length <= 500
-
s 仅由小写英文字母组成
问题分析
这题是让把字符串划分为尽可能多的片段，其中相同的字母只能出现的同一个片段中，最后返回每个片段的长度。
这题比较简单，我们可以使用map记录字符串中每一个字符最后出现的位置，然后遍历字符串中的所有字符，因为相同的字符必须在同一个片段中，所以一个字符第一次出现和最后一次出现所构成的片段是不能再分的。
比如字符串abcadeaf中，字符 a 第一次出现和最后一次出现所构成的子串是abcadea，这个子串是不能再分的。在这个子串中我们还要查找所有字符最后一次出现的位置end，取所有字符end的最大值。直到这个片段中所有字符最后一次出现的位置都不大于end的时候，这个片段就是不能在拆分的片段。
JAVA：
public List<Integer> partitionLabels(String s) { ArrayList<Integer> ans = new ArrayList<>(); // 记录每个字符最后出现的位置。 Map<Character, Integer> mp = new HashMap<>(); int n = s.length(); for (int i = 0; i < n; i++)// 记录字符出现的位置。 mp.put(s.charAt(i), i); int i = 0; while (i < n) { char ch = s.charAt(i); int end = mp.get(ch);// 当前字符最后出现的位置。 // 在这个范围内，计算所有字符最后出现位置的最大值。 for (int j = i + 1; j < end; j++) { ch = s.charAt(j); end = Math.max(end, mp.get(ch)); } // 片段的区间是[i,end]，长度是 end - i + 1 。 int len = end - i + 1; ans.add(len); i = end + 1;// 下一个片段开始的位置 } return ans;}
C++：
public: vector<int> partitionLabels(string s) { vector<int> ans; // 记录每个字符最后出现的位置。 unordered_map<char, int> mp; int n = s.length(); for (int i = 0; i < n; i++)// 记录字符出现的位置。 mp[s[i]] = i; int i = 0; while (i < n) { char ch = s[i]; int end = mp[ch];// 当前字符最后出现的位置。 // 在这个范围内，计算所有字符最后出现位置的最大值。 for (int j = i + 1; j < end; j++) { ch = s[j]; end = max(end, mp[ch]); } // 片段的区间是[i,end]，长度是 end - i + 1 。 int len = end - i + 1; ans.push_back(len); i = end + 1;// 下一个片段开始的位置 } return ans; }
