每日OJ题_牛客_重排字符串_贪心_C++_Java

目录

牛客_重排字符串_贪心

题目解析

C++代码

Java代码

---

牛客_重排字符串_贪心

重排字符串 (nowcoder.com)

描述：

        小红拿到了一个只由小写字母组成的字符串。她准备把这个字符串重排（只改变字母的顺序，不改变数量）
        重排后小红想让新字符串不包含任意两个相同的相邻字母。你能帮帮她吗？

---

题目解析

C++代码

#include <climits>
#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;string str;cin >> n >> str;vector<int> hash(26, 0);int sz = str.size();for (int i = 0; i < sz; ++i){hash[str[i] - 'a']++;}int maxCnt = 0, maxIndex = 0;for (int i = 0; i < 26; ++i) // 先放第一大{if (hash[i] > maxCnt){maxCnt = hash[i];maxIndex = i;}}if (maxCnt > (sz + 1) / 2)cout << "no";else{cout << "yes" << endl;vector<char> res(n);int i = 0;while (maxCnt--){res[i] = (maxIndex + 'a');i += 2;}// cout << maxIndex << endl;for (int j = 0; j < 26; ++j){if (j != maxIndex && hash[j] != 0) // 找到一个后往后找{while(hash[j]--){if(i >= n)i = 1;res[i] = j + 'a';i += 2;}}}for (auto& e : res){cout << e;}cout << endl;}return 0;
}

Java代码

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt();char[] s = in.next().toCharArray();char maxChar = '0';int maxCount = 0;int[] hash = new int[26];// 找出现次数最多的字符以及次数for(int i = 0; i < n; i++){char ch = s[i];if(++hash[ch - 'a'] > maxCount){maxChar = ch;maxCount = hash[ch - 'a'];}}// 判断是否能重排if(maxCount > (n + 1) / 2){System.out.println("no");}else{System.out.println("yes");char[] ret = new char[n];int i = 0;// 重新排列// 1. 先处理出现次数最多的字符while(maxCount-- != 0){ret[i] = maxChar;i += 2;}// 2. 处理剩下的字符for(int j = 0; j < 26; j++){if(hash[j] != 0 && (char)(j + 'a') != maxChar){while(hash[j]-- != 0){if(i >= n){i = 1;}ret[i] = (char)(j + 'a');i += 2;}}}for(int j = 0; j < n; j++){System.out.print(ret[j]);}}}
}