成对的69匹配序列定义为：
1、 空串""是一个成对的69序列；
2、如果"X"和"Y"是成对的69序列，那么"XY"也是成对的69序列；
3、如果"X"是一个成对的69序列，那么"6X9"也是一个成对的69序列；
4、每个成对的69序列都可以由以上规则生成。 例如，"", "69", "6699", "6969"都是成对的。
现在给出一个序列S，允许你的操作是： 在S的开始和结尾出添加一定数量的6或者9，使序列S变为一个成对的69序列。输出添加最少的6或者9之后成对的69序列是什么。
[编程题]成对的69
与生成有效括号的方式相同，不断平衡成对的69，缺6往前补6，缺9往后补9
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
public String Paired69 (String S) {
// write code here
Stack<Character> stack = new Stack<>();
StringBuilder sb = new StringBuilder();
for(char c: S.toCharArray()){
if(c == '6'){
stack.push(c);
}else{
if(!stack.isEmpty())
stack.pop(); // 还有6就弹出来与9配对
else
sb.insert(0, '6'); // 否则缺6，需要在前面补
}
sb.append(c);
}
while(!stack.isEmpty()){ // 6有余，往后补9
stack.pop();
sb.append('9');
}
return sb.toString();
}
}
发表于 2021-08-30 10:19:26
回复(0)
```
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
string Paired69(string S) {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
string Paired69(string S) {
//栈中保存字符串S中6的个数
//主要思路：从头遍历字符串，当遍历到6时就把6入栈，遍历到9时，就判断栈是否为空，若不为空，则说明可以和现有字符串S的6
//匹配，否则说明当前S中不存在与9匹配的6 那么就需要在开头插入一个6
//当遍历完整个字符串后，如果栈不为空，则说明还有剩余的6 那么只需要在答案字符串填上对应的6即可
stack<int> st;
string ans;
for(int i = 0;i < S.size();i ++){
if(S[i] == '6'){
st.push(6);
ans += to_string(6);
}else{
if(st.empty()){
ans = to_string(6) + ans;
ans += to_string(9);
}else{
ans += to_string(9);
st.pop();
}
}
}
while(!st.empty()){
st.pop();
ans += to_string(9);
}
return ans;
}
};
stack<int> st;
string ans;
for(int i = 0;i < S.size();i ++){
if(S[i] == '6'){
st.push(6);
ans += to_string(6);
}else{
if(st.empty()){
ans = to_string(6) + ans;
ans += to_string(9);
}else{
ans += to_string(9);
st.pop();
}
}
}
while(!st.empty()){
st.pop();
ans += to_string(9);
}
return ans;
}
};
```
发表于 2021-08-26 22:07:07
回复(0)
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param S string字符串
# @return string字符串
#
classSolution:
defPaired69(self, S):
# write code here
stack =[]
foritem inS:
iflen(stack) ==0:
stack.append(item)
else:
ifitem =='9'andstack[-1] =='6':
stack.pop()
else:
stack.append(item)
left =''
right =''
foritem instack[::-1]:
ifitem =='6':
right +='9'
else:
left ='6'+left
returnleft+S+right
发表于 2022-08-23 22:33:58
回复(0)
classSolution {
public:
string Paired69(string S) {
intn6 = 0, n9 = 0;
for(charc : S) {
if(c == '6') {
n6++;
}
if(c == '9') {
if(n6)n6--;
elsen9++;
}
}
S = string(n9, '6') + S + string(n6, '9');
returnS;
}
};
发表于 2022-08-23 21:21:11
回复(0)
我是fw，没有想到用栈，直接回溯了
import java.util.*;
public class Solution {
// 变成69序列-感觉能回溯爆搜
public String Paired69 (String s) {
int cnt = 0;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (c == '6') cnt++;
else cnt--;
}
back(s, cnt);
return res;
}
// 回溯爆搜
String res;
boolean flag = false;
public void back(String s, int cnt) {
if (valid(s)) { // 是69序列就直接返回
flag = true;
res = s;
return;
}
if (!flag) {
if (cnt > 0) back(s + '9', cnt-1); // 6多补9
else if (cnt < 0) back('6' + s, cnt+1); // 9多补6
else { // 一样多但是是96的形式 都补
back('6' + s, cnt+1);
back(s + '9', cnt-1);
}
}
}
// 判断是否为69序列
public boolean valid(String s) {
if (s.length() % 2 != 0) return false;
if (s.length() == 0 || s.equals("69")) return true;
if (s.length() > 2) {
if (s.charAt(0) == '6' && s.charAt(s.length()-1) == '9'
&& valid(s.substring(1, s.length()-1))) return true;// 左右拼接
for (int i = 2; i < s.length(); i+= 2) { // 中间拼接
if (valid(s.substring(0, i)) && valid(s.substring(i))) return true;
}
}
return false;
}
}
发表于 2022-07-02 17:49:08
回复(0)
golang, 还是栈匹配
package main
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
func Paired69( S string ) string {
// write code here
if len(S)==0 {
return S
}
stack,res := []rune{},""
for i:=0;i<len(S);i++{
if rune(S[i]) == '6' {
stack, res = append(stack, '9'),res+"6"; continue
}
if rune(S[i]) == '9' {
if len(stack) == 0 {
res = "6" + res + "9"; continue
} else {
res ,stack = res + "9", stack[1:]; continue
}
}
res = res + string(S[i])
}
for i:=0;i<len(stack);i++ {
res = res + "9"
}
return res
}
发表于 2022-04-04 23:14:33
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
public String Paired69 (String S) {
// write code here
if (S.equals(""))
return "";
int str_len = S.length();
Stack<Character> six = new Stack<Character>();
Stack<Character> nine = new Stack<Character>();
for (int i = 0; i < str_len; i++) {
if ( S.charAt(i) == '6' ) {
six.push('6');
}
else if ( !six.empty() ) {
six.pop();
}
else {
nine.push('9');
}
}
StringBuilder output = new StringBuilder();
int six_size = six.size();
int nine_size = nine.size();
for ( int i = 0; i < nine_size; i++ )
output.append('6');
output.append(S);
for ( int i = 0; i < six_size; i++ )
output.append('9');
return output.toString();
}
}
发表于 2022-03-05 16:32:17
回复(0)
function Paired69( S ) {
let s=S;
let left='';
let right='';
while(s.includes('69')){ //去除‘69’
let ind=s.indexOf('69');
s=s.slice(0,ind)+s.slice(ind+2);
}
let len=s.length;
console.log(len)
if(len){ //判断最后有剩下
if(s=='6'.repeat(len)){ //剩下单6
right="9".repeat(len);
}else if(s=='9'.repeat(len)){ //剩下单9
left='6'.repeat(len);
}else{
left='6'.repeat(num(s,'9'));
right='9'.repeat(num(s,'6'))
}
}
return left+S+right;
}
function num(str,s){
let arr=str.split('');
return arr.reduce((pre,item)=>pre+=item==s?1:0,0)
};
module.exports = {
Paired69 : Paired69
};
let s=S;
let left='';
let right='';
while(s.includes('69')){ //去除‘69’
let ind=s.indexOf('69');
s=s.slice(0,ind)+s.slice(ind+2);
}
let len=s.length;
console.log(len)
if(len){ //判断最后有剩下
if(s=='6'.repeat(len)){ //剩下单6
right="9".repeat(len);
}else if(s=='9'.repeat(len)){ //剩下单9
left='6'.repeat(len);
}else{
left='6'.repeat(num(s,'9'));
right='9'.repeat(num(s,'6'))
}
}
return left+S+right;
}
function num(str,s){
let arr=str.split('');
return arr.reduce((pre,item)=>pre+=item==s?1:0,0)
};
module.exports = {
Paired69 : Paired69
};
发表于 2021-09-07 16:21:04
回复(0)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
string Paired69(string S) {
// write code here
int strSize = S.size();
if(strSize == 0) return S;
stack<int> handle;
string start="",end="";
for(int i=0; i< strSize;i++){
if(S[i]=='6'){
handle.push(6);
}else{
if(!handle.empty()&&handle.top()==6){
handle.pop();
}else{
start+="6";
}
}
}
while(!handle.empty()){
end+="9";
handle.pop();
}
return start+S+end;
}
};
发表于 2021-09-01 06:16:20
回复(0)
//C++
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
string Paired69(string S) {
// write code here
int count = 0;
int minAdd = 0;
for (char& ch : S) {
if (ch == '6')
count++;
else {
count--;
if (-count>minAdd) {
minAdd = -count;
}
}
}
count = count + minAdd;
string ans = "";
string pre = "";
pre.append(minAdd, '6');
if (count == 0) return pre + S;
if (count < 0) {//9多
count = -count;
while (count--) {
ans += '6';
}
ans = pre + ans + S;
}
else {
while (count--) {
ans += '9';
}
ans = pre+S + ans;
}
return ans;
}
};
发表于 2021-08-31 20:14:14
回复(0)
function Paired69( S ) {
// write code here
if(S.length === 0) return ''
let arr = S.split('')
let n = arr.length
let stack = []
for(let i = 0; i < n;i++){
if(S[i] === '6'){
stack.push(S[i])
}else{
if(stack.length === 0){
arr.unshift('6')
}else{
stack.pop()
}
}
}
console.log(stack)
for(let i = 0;i < stack.length;i++) arr.push('9')
return arr.join('')
}
发表于 2021-08-27 01:24:42
回复(0)
import java.util.*;
import java.util.Stack;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
public static String Paired69 (String S) {
// write code here
int n = S.length();
if(n==0) return "";
char[] arr = S.toCharArray();
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<>();
int i = 0;
while(i<n || !stack.isEmpty()){
if(i<n && arr[i] == '6'){
sb.append('6');
stack.push('6');
}else{
if(!stack.isEmpty()){
sb.append('9');
stack.pop();
}else{
sb.insert(0,'6');
sb.append('9');
}
}
i++;
}
return sb.toString();
}
}
发表于 2021-08-26 16:21:57
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param S string字符串
* @return string字符串
*/
public String Paired69 (String S) {
// write code here
if (S == null) {
return null;
}
char[] arr = S.toCharArray();
Stack<Character> stack = new Stack<>();
for (char c : arr) {
if (!stack.isEmpty()) {
char top = stack.peek();
//栈顶元素为6则弹出6，不添加；否则加入栈
if (top == '6' && c == '9') {
stack.pop();
continue;
}
}
stack.push(c);
}
StringBuilder res = new StringBuilder(S);
while (!stack.isEmpty()) {
char c = stack.pop();
//栈顶元素为6，在S最后面添一个9
//栈顶元素为9，在S最前面添一个6
if (c == '6') {
res.append('9');
} else if (c == '9') {
res.insert(0, '6');
}
}
return res.toString();
}
}
发表于 2021-08-24 18:06:51
回复(0)
问题信息
通过挑战的用户
-
2023-03-07 08:20:53 -
2023-02-24 11:47:39
-
2022-10-07 21:47:54
-
2022-10-07 16:30:43
-
2022-09-27 21:55:57
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
