给定一个由小写字母组成的字符串 s ,请你把这个字符串尽可能多地划分,相同的字母只出现在一个的区间。
例如 "anfjaklii" ,可以把 "anfja" 和 "k","l","ii" 划成四个区间, 'a' 'n' 'f' 'j' 只出现在第一个区间 ,'k' 'l' 'i' 分别出现在第二、三、四个区间。
即输出 5 1 1 2。
数据范围:字符串长度满足 ,字符串中仅出现小写字母。
"anfjaklii"
[5,1,1,2]
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型ArrayList */ public ArrayList<Integer> splitString (String s) { // write code here Map<Character,Integer> map = new HashMap<>(); ArrayList<Integer> res = new ArrayList<>(); int end = -1; int start = 0; //存储每个字母最后的位置 for(int i = 0 ;i<s.length();i++){ map.put(s.charAt(i),i); } for(int i = 0;i<s.length();i++){ end = Math.max(end,map.get(s.charAt(i))); if(end == i ){ res.add(end - start + 1); start = i+1; } } return res; } }
package main import _"fmt" /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param s string字符串 * @return int整型一维数组 */ func splitString( s string ) []int { ends:=map[byte]int{} for i,ch:=range []byte(s){ ends[ch]=i } ans:=[]int{} var l,r int for i:=0;i<len(s);i++{ r=max(r,ends[s[i]]) if i==r{ ans=append(ans,r-l+1) l=i+1 } } return ans } func max(a,b int)int{ if a>b{ return a } return b }
# -*- coding: utf-8 -*- # # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # # # @param s string字符串 # @return int整型一维数组 # class Solution: """ 题目: https://www.nowcoder.com/practice/3a54a4f5bfa14891adb55484519210be?tpId=196&tqId=40445&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3Fpage%3D8%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=undefined&tags=&title= 参考: 大神:牛客683289936号 算法: 本题要求对字符串进行尽可能多的划分,但是要求如果出现相同字符,那么该字符所包含的区间必须划分到一起,比如"abba", 划分后为[4] 首次遍历字符串s: 建立哈希表hashMap,键为s中的字符,值为该字符最后一次出现的下标 再次遍历字符串s: 使用start、end分别记录待截取区间的左右边界,其中end更新为包含重复元素的最远右边界 当i与end相遇,就需要进行区间截取,同时更新start 复杂度: 时间复杂度:O(n), n为字符串s的长度 空间复杂度:O(m), m为不重复的字符数量 """ def splitString(self, s): # write code here n, hashMap = len(s), {} for i in range(n): # 哈希表记录每个字符最后一次出现的下标 hashMap[s[i]] = i # print hashMap start, end, res = 0, -1, [] for i in range(n): end = max(end, hashMap[s[i]]) # end更新为包含重复元素的最远边界 if i == end: # 访问到右边界,需要进行区间截取 res.append(end - start + 1) start = i + 1 return res if __name__ == "__main__": sol = Solution() s = "anfjaklii" # s = "abba" # s = "abcabc" # s = "abcac" res = sol.splitString(s) print res