上海网站设计开发,网站备案产品信息错误,个人注册一个小公司要多少钱,安卓开发快速入门重新排列字符串s中的字母#xff0c;使得任意两个相邻的字母都不相同。
思路#xff1a;
让相邻字母不同#xff0c;能想到的办法是先把相同的字母排列#xff0c; 然后在相同字母的缝隙中插入另一种字母。 比如aab, 先把a a排出来#xff0c;再… 重新排列字符串s中的字母使得任意两个相邻的字母都不相同。
思路
让相邻字母不同能想到的办法是先把相同的字母排列 然后在相同字母的缝隙中插入另一种字母。 比如aab, 先把a a排出来再在2个a的缝隙中插入b得到aba.
那么就需要统计每个字母出现的次数。 为了让能插入字母的缝隙排列时中间空一位也就是先把出现最多的字母放在偶数位 如果不够放就折回来到奇数位所以字母出现次数不能超过s长度的一半 不然折回来就是相同字母了。字母的出现次数超过s一半的直接返回“”。
而且一定要先排出现最多的字母可以试试example1中先排b。
可以用一个优先队列按字母出现的次数从大到小排列。然后一一取出排列。 也可以只找到出现次数最多的字母先排列再直接按顺序排剩下的。
优先队列 public String reorganizeString(String s) {HashMapCharacter,Integer map new HashMap();char[] chs s.toCharArray();//按字母出现的次数倒序排列PriorityQueueCharacter pq new PriorityQueue((a,b)-(map.get(b)-map.get(a)));char[] res new char[s.length()];for(char c : chs) {map.put(c, map.getOrDefault(c, 0)1);}pq.addAll(map.keySet());//出现频率最多的字母多于字符串长度的一半if(map.get(pq.peek()) (s.length()1)/2) return ;int i 0;while(!pq.isEmpty()) {char c pq.poll();for(int j 0; j map.get(c); j) {if(i s.length()) i 1; //偶数位放满开始放奇数位res[i] c;i 2;}}return new String(res);}只先排出现次数最多的剩下的按顺序排。此方法更快。 public String reorganizeString(String s) {int[] cnt new int[26];char[] chs s.toCharArray();int n chs.length;char[] res new char[n];for(int i 0; i n; i) cnt[chs[i]-a];//找到出现次数最多的字母和次数int maxCnt 0;int freqCh 0;for(int i 0; i 26; i) {if(cnt[i] maxCnt) {maxCnt cnt[i];freqCh i;}}if(maxCnt (n1)/2) return ;//先排出现最多的字母不然可能会出现奇数位和偶数位是同一字母的情况int idx 0;while(cnt[freqCh] 0) {res[idx] (char)(freqCh a);idx 2;cnt[freqCh] --;}for(int i 0; i 26; i) {while(cnt[i] 0) {if(idx n) idx 1;res[idx] (char)(ia);idx 2;cnt[i] --;}}return new String(res);}
