牛客NC179 长度为 K 的重复字符子串【simple 哈希，滑动窗口 C++、Java、Go、PHP】

题目

在这里插入图片描述

题目链接：
https://www.nowcoder.com/practice/eced9a8a4b6c42b79c95ae5625e1d5fd

思路

哈希统计每个字符出现的次数。没在窗口内的字符要删除

参考答案C++

class Solution {public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @param k int整型* @return int整型*/int numKLenSubstrRepeats(string s, int k) {//哈希统计int n = s.size();map<int, int> mymap;int cnt = 0;for (int i = 0; i < n; i++) {int x = s[i];// 在map中查找元素auto it = mymap.find(x);if (it != mymap.end()) {int t = it->second;mymap.erase(x); //更新值，先删除原来的keymymap.insert(pair<int, int>(x, t + 1)); //往map中新增k,v} else {mymap.insert(pair<int, int>(x, 1)); //往map中新增k,v}if (i >= k - 1) {if (i >= k) { //要移除左边的过期的窗口int delk = s[i - k];auto it = mymap.find(delk);int tmp = it->second;mymap.erase(delk); //更新值，先删除原来的keymymap.insert(pair<int, int>(delk, tmp - 1)); //往map中新增k,vit = mymap.find(delk);if (it->second == 0) {mymap.erase(it); //map中删除key}}if (mymap.size() < k) { //map的大小cnt++;}}}return cnt;}
};

参考答案Java

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @param k int整型* @return int整型*/public int numKLenSubstrRepeats (String s, int k) {//哈希来统计Map<Character,Integer> map = new HashMap<>();int n = s.length();int cnt=0;for (int i = 0; i <n ; i++) {char c = s.charAt(i);if(map.containsKey(c)){map.put(c,map.get(c)+1);}else{map.put(c,1);}if(i>=k-1){if(i>=k){ //需要删除左边窗口外的char delchar = s.charAt(i-k);map.put(delchar,map.get(delchar)-1);if(map.get(delchar) ==0){map.remove(delchar);}}if(map.size()<k){cnt++;}}}return cnt;}
}

参考答案Go

package main/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param s string字符串* @param k int整型* @return int整型*/
func numKLenSubstrRepeats(s string, k int) int {//哈希来统计n := len(s)cnt := 0map1 := map[byte]int{}for i := 0; i < n; i++ {char := s[i]_, ok := map1[char]if !ok {map1[char] = 1} else {map1[char] += 1}if i >= k-1 {if i >= k { //需要移除左边过期的窗口chardel := s[i-k]map1[chardel] -= 1if map1[chardel] == 0 {delete(map1, chardel)}}if len(map1) < k {cnt++}}}return cnt
}

参考答案PHP

<?php/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param s string字符串 * @param k int整型 * @return int整型*/
function numKLenSubstrRepeats( $s ,  $k )
{//哈希来统计$cnt = 0;$map = [];$n = strlen($s);for($i=0;$i<$n;$i++){$c = $s[$i];if(!isset($map[$c])){$map[$c] =1;}else{$map[$c]+=1;}if($i>=$k-1){if($i>=$k){$delkey = $s[$i-$k];$map[$delkey]-=1;if($map[$delkey] ==0){unset($map[$delkey]);}}if(count($map) <$k){$cnt++;}}}return $cnt;
}