刷题笔记:力扣第763题-划分字母区间
1.本题考查贪心算法有点类似于力扣第45题-跳跃游戏Ⅱ不同之处在于45题是尽可能少跳而本题是满足区间条件后多跳。可以设置一个哈希数组先遍历一遍字符串s记录其中每个字母出现的区间之后再遍历一遍当遍历的位置超出了前面字符的最远右边界后即可划分一次。2.基于以上思想写出的完整代码如下1. /** 2. * Note: The returned array must be malloced, assume caller calls free(). 3. */ 4. int* partitionLabels(char* s, int* returnSize) { 5. int len strlen(s); 6. // start记录字符串首字符用于首次字符判断 7. char start s[0]; 8. // hash[26][0]字母第一次出现下标hash[26][1]字母最后一次出现下标 9. int hash[26][2]; 10. // 初始化hash数组全部置0 11. for (int i 0; i 26; i){ 12. memset(hash[i], 0, sizeof(hash[i])); 13. } 14. 15. // 第一次遍历字符串记录每个字母首尾出现位置 16. for (int i 0; i len; i){ 17. // 处理第一个字符直接初始化其首尾下标为0 18. if (i 0){ 19. hash[s[i] - a][0] 0; 20. hash[s[i] - a][1] 0; 21. continue; 22. } 23. // 当前字母从未记录过起始位置且不是首字符记录首次出现下标 24. if (hash[s[i] - a][0] 0 s[i] ! start){ 25. hash[s[i] - a][0] i; 26. hash[s[i] - a][1] i; 27. } else { 28. // 字母重复出现更新末尾下标为当前i 29. hash[s[i] - a][1] i; 30. } 31. } 32. 33. // 当前片段最远右边界初始为第一个字符最后出现位置 34. int end hash[s[0] - a][1]; 35. int cnt 1; // 当前分割片段字符计数 36. int cur 0; // 结果数组填充下标 37. // 最多分割len段开辟长度为len的结果数组 38. int* res (int*)malloc(sizeof(int) * len); 39. 40. // 第二次遍历滑动窗口分割字符串 41. for (int i 1; i len; i){ 42. // 遍历下标超过当前片段最远边界说明可以分割 43. if (i end){ 44. res[cur] cnt; 45. // 开启新片段更新边界与计数 46. end hash[s[i] - a][1]; 47. cnt 1; 48. } else { 49. // 仍在当前片段内更新片段最大右边界 50. end fmax(end, hash[s[i] - a][1]); 51. cnt; 52. } 53. } 54. // 存入最后一段的长度 55. res[cur] cnt; 56. 57. // 返回数组有效长度 58. *returnSize cur; 59. return res; 60. }该算法时间复杂度为O(n)空间复杂度为O(1)。3.本题实际上只关心字符的右边界所以可以将哈希数组简化为一维且因为i的值一直在递增遍历的时候该字符的最大右边界不需要进行额外的判断直接更新对应哈希数组的右边界值即可。优化后的完整代码如下1. /** 2. * Note: The returned array must be malloced, assume caller calls free(). 3. */ 4. int* partitionLabels(char* s, int* returnSize) { 5. // 获取字符串总长度 6. int len strlen(s); 7. // hash数组存储每个小写字母最后一次出现的下标 8. int hash[26] {0}; 9. 10. // 第一次遍历记录每个字母最靠右的位置 11. for (int i 0; i len; i){ 12. hash[s[i] - a] i; 13. } 14. 15. // 分配结果数组最多分割len段 16. int* res (int*)malloc(sizeof(int) * len); 17. int cnt 1; // 当前片段字符个数初始第一个字符 18. int cur 0; // 结果数组写入下标 19. int end hash[s[0] - a]; // 当前片段能延伸到的最右边界 20. 21. // 从第二个字符开始遍历分割字符串 22. for (int i 1; i len; i){ 23. // 遍历位置超出当前片段最大边界代表可以分割 24. if (i end){ 25. res[cur] cnt; 26. // 开启新片段更新右边界、重置计数 27. end hash[s[i] - a]; 28. cnt 1; 29. } else { 30. // 仍在当前片段内更新片段最远右边界片段长度1 31. end fmax(end, hash[s[i] - a]); 32. cnt; 33. } 34. } 35. // 存入最后一段的长度 36. res[cur] cnt; 37. 38. // 设置返回数组有效元素个数 39. *returnSize cur; 40. return res; 41. }该算法时间复杂度为O(n)空间复杂度为O(1)
)
