leetcode784
2024-09-27 05:18:55
这道题经过独立思考，通过使用二进制编码的方式来进行处理。分几个步骤一层一层的处理，最终解决了，这道题感觉应该属于medimu级别。
public class Solution
{
/// <summary>
/// 列出二进制表示
/// </summary>
/// <param name="count"></param>
/// <returns></returns>
public IList<string> GetBinaryPartten(int count)
{
var list = new List<string>();
//int count = 5;//字母数量
int N = (int)Math.Pow(, count) - ;//最大值 for (int i = ; i <= N; i++)
{
Stack<int> St = new Stack<int>();
int x = i;//
while (x != )
{
int y = x & ;
St.Push(y);
x >>= ;
} int len = St.Count;//len<=count
string result = "";
for (int j = ; j < count - len; j++)
{
result += "";
} while (St.Any())
{
int y = St.Pop();
result += y.ToString();
} list.Add(result);
}
return list;
} public IList<string> LetterCasePermutation(string S)
{
S = S.ToLower();
var dic = new List<KeyValuePair<int, string>>();
var list = new List<string>();
var numdic = new HashSet<char> { '', '', '', '', '', '', '', '', '', '' };
int count = ;
for (int i = ; i < S.Length; i++)
{
if (numdic.Any(x => x == S[i]))//是数字
{
continue;
}
else//是字母
{
count++;//记录字母的数量
dic.Add(new KeyValuePair<int, string>(i, S[i].ToString()));//记录字母的下标和字母
}
}
var list0 = GetBinaryPartten(count);
foreach (var l0 in list0)
{
string temp = S;//原格式
string map = l0;//当前格式编码
//解析编码
for (int i = ; i < map.Length; i++)
{
//按位解析，i表示dic[i]
var code = map[i];//code表示编码 var d = dic[i];//根据当前位的编码，解析出字符
var position = d.Key;//原串中的下标
var chars = d.Value;//当前字符 if (code == '')
{
chars = chars.ToLower();
}
else
{
chars = chars.ToUpper();
}
//对当前位进行处理
string prefix = temp.Substring(, position);
//string mid = temp.Substring(position, 1);
string mid = chars;//替换此位字符形式
string next = temp.Substring(position + );
temp = prefix + mid + next;
}
//这里将此格式的字符串加入list中
list.Add(temp);
}
return list;
}
}
另一种解法，使用回溯法：
public class Solution
{
List<string> list = new List<string>();
private void BackTrack(int t, string S)
{
if (t >= S.Length)
{
return;
}
for (int i = t; i < S.Length; i++)
{
var s = S[i];
if (s >= && s <= )
{
continue;//数字0到9
}
else//字母
{
string prefix = S.Substring(, i);
//string mid = temp.Substring(position, 1);
string mid = s.ToString().ToUpper();//替换此位字符形式
string next = S.Substring(i + );
string temp = prefix + mid + next;
list.Add(temp);
BackTrack(i + , temp);
}
}
} public IList<string> LetterCasePermutation(string S)
{
var numdic = new HashSet<char> { '', '', '', '', '', '', '', '', '', '' };
S = S.ToLower();
list.Add(S);
BackTrack(, S);
return list;
}
}
再提供一种回溯法的思路，使用python实现：
class Solution:
def BackTrack(self,S,l,index,string):
if index < len(S):
c = S[index]
if c.isalpha():
self.BackTrack(S,l,index+1,string+c.lower())
self.BackTrack(S,l,index+1,string+c.upper())
else:
self.BackTrack(S,l,index+1,string+c)
if index == len(S):
l.append(string) return def letterCasePermutation(self, S: 'str') -> 'List[str]':
l = list()
n = len(S)
tags = [0] * n
self.BackTrack(S,l,0,'')
return l
最新文章
- Java 线程池
- 【Mongo】Linux安装MongoDB
- hdu 4814 Golden Radio Base
- 在Fedora20上安装Oracle 12c
- 视频和音频播放的演示最简单的例子6：OpenGL广播YUV420P（T经exture，采用Shader）
- linux虚拟机网络配制方法及遇到问题的解决方法
- [BZOJ1207] [HNOI2004] 打鼹鼠 (dp)
- Java多种方式读文件，追加文件内容，等对文件的各种操作
- Java 学习笔记 IO流与File操作
- CSS3透明背景+渐变样式
- Dom操作注意事项
- SimpleDateFormat-时间格式化中的大小写字符
- Ctex中WinEdt经常弹出注册小窗口 解决办法
- iperf命令 +speedtest-cli
- centos 安装cloud foundry CLI
- MySQL 基础小技巧
- HDevelop数据类型
- 实践作业4：Web测试实践（小组作业）每日任务记录5
- VUE安装步骤
- （转）使用.NET Reflector 查看Unity引擎里面的DLL文件