自定义字符串排序
题目：字符串S和 T 只包含小写字符。在S中，所有字符只会出现一次。S 已经根据某种规则进行了排序。我们要根据S中的字符顺序对T进行排序。更具体地说，如果S中x在y之前出现，那么返回的字符串中x也应出现在y之前返回任意一种符合条件的字符串T。
示例:
输入:
S = "cba"
T = "abcd"
输出: "cbad"
解释:
S中出现了字符 "a", "b", "c", 所以 "a", "b", "c" 的顺序应该是 "c", "b", "a".
由于 "d" 没有在S中出现, 它可以放在T的任意位置. "dcba", "cdba", "cbda" 都是合法的输出。
注意:
S的最大长度为26，其中没有重复的字符。
T的最大长度为200。
S和T只包含小写字符。
思路：我觉得这个题目还是很简单的，目前的想法是s中每一个元素作为key存map，然後值是t中这个元素出现的次数。等重组t的时候可以先把t中s没出现的写前面。然後继续按照s的顺序重组字符串。反正思路很清晰，就是不知道会不会出现性能问题。我去试试了。
第一版代码：
class Solution {
public String customSortString(String S, String T) {
Map<Character,Integer> map = new HashMap<>();
char[] arr = S.toCharArray();
for(char c : arr) map.put(c,0);
StringBuffer sb = new StringBuffer();
for(char c : T.toCharArray()){
if(map.get(c) != null){
map.put(c,map.get(c)+1);
}else {
sb.append(c);
}
}
for(char c : arr){
int n = map.get(c);
while (n>0){
sb.append(c);
n--;
}
}
return sb.toString();
}
}
思路是对的，就是性能不太好，我这里再看看怎么优化。
第二版本代码，我是觉得这里其实不用map也可以，毕竟最多就26个数组。然後上面的 代码2ms，这个代码1ms，虽然进步了但是还不是特别好。
class Solution {
public String customSortString(String S, String T) {
int[] count = new int[26];
Arrays.fill(count,-1);
char[] arr = S.toCharArray();
for(char c : arr) count[c-'a']++;//这里没出现的是-1.出现了变0
StringBuffer sb = new StringBuffer();
for(char c : T.toCharArray()){
if(count[c-'a'] > -1){
count[c-'a']++;
}else {
sb.append(c);
}
}
for(char c : arr){
int n = count[c-'a'];
while (n>0){
sb.append(c);
n--;
}
}
return sb.toString();
}
}
我去看看性能第一的代码:
class Solution {
public String customSortString(String S, String T) {
int[] count = new int[26];
for(char c:T.toCharArray()){
count[c-'a']++;
}
StringBuilder ans = new StringBuilder();
for(char c :S.toCharArray()){
for(int i=0;i<count[c-'a'];i++){
ans.append(c);
}
count[c-'a']=0;
}
for(char c ='a';c<='z';c++){
for(int i=0;i<count[c-'a'];i++){
ans.append(c);
}
}
return ans.toString();
}
}
不明白为什么这个性能更好，for循环就比while强？反正这个题比较简单，就这样了，下一题。
匹配子序列的单词数
题目：给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
示例:
输入:
S = "abcde"
words = ["a", "bb", "acd", "ace"]
输出: 3
解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。
注意:
所有在words和 S 里的单词都只由小写字母组成。
S 的长度在 [1, 50000]。
words 的长度在 [1, 5000]。
words[i]的长度在[1, 50]。
思路：这个题怎么说呢，感觉可实现的方式还是不少的，不管是每个words去对比，还是直接S的所有子串找出来。。但是问题是性能绝对是个大问题。。初步估计应该都会超时吧。总而言之我现在的想法还是用map。S中每一个字母对应的下标都记录。然後words直接去从字符开始判断，每次取尽量小的。当遇到无法取值的时候就false了。（这里的尽量小是满足上一个的后续的最小值。比如说上一个字母的下表取了11，那么当前字母可选下标6，12，16，19，因为6小于上一个所以直接pass。能取的最合适的值就是12.）我感觉思路挺清晰的，我去实现试试。
第一版本代码:
class Solution {
public int numMatchingSubseq(String s, String[] words) {
Map<Character,List<Integer>> map = new HashMap<>();
for(int i = 0;i<s.length();i++){
char c = s.charAt(i);
List<Integer> list = map.get(c);
if(list == null) list = new ArrayList<>();
list.add(i);
map.put(c,list);
}
int ans = 0;
for(String temp : words){
if(isOk(map,temp)) ans++;
}
return ans;
}
public boolean isOk(Map<Character,List<Integer>> map,String temp){
int start = -1;
for(char c:temp.toCharArray()){
List<Integer> list = map.get(c);
if(list == null) return false;
boolean flag = true;
for(int i : list){
if(i>start){
flag = false;
start = i;
break;
}
}
//如果flag为true说明根本没有合适条件的值，所以直接false
if(flag) return false;
}
return true;
}
}
勉强过了没超时，我居然还挺庆幸。。。感觉可优化的点就是这个从头开始遍历map的list。这块肯定是有问题的，极端点的情况 aaaaaaaaaaa...aa.这样到后面的判断都快n方了。但是也最多就是从遍历变成二分。。觉得还是这个方式有点问题，我去看看题解吧。
题解跟我做的都好像不是一个题目，大概思路是分桶：
因为 S 很长，所以寻找一种只需遍历一次 S 的方法，避免暴力解法的多次遍历。将所有单词根据首字母不同放入不同的桶中。例如当 words = ['dog', 'cat', 'cop']，根据首字母不同可以分为 'c' : ('cat', 'cop'), 'd' : ('dog',)。换句话说，每个桶中的单词就是该单词正在等待匹配的下一个字母。在遍历 S 的同时，将匹配到单词根据下一个需要匹配的字母移动到不同的桶中。
例如，有字符串 S = 'dcaog'：
- 初始化 heads = 'c' : ('cat', 'cop'), 'd' : ('dog',)；
- 遍历 S[0] = 'd' 后，heads = 'c' : ('cat', 'cop'), 'o' : ('og',)；
- 遍历 S[1] = 'c' 后，heads = 'a' : ('at',), 'o' : ('og', 'op')；
- 遍历 S[2] = 'a' 后，heads = 'o' : ('og', 'op'), 't': ('t',) ;
- 遍历 S[3] = 'o' 后，heads = 'g' : ('g',), 'p': ('p',), 't': ('t',)；
- 遍历 S[0] = 'g' 后，heads = 'p': ('p',), 't': ('t',)。
使用长度为 26 的数组 heads 做桶，每个字母对应一个桶。访问 S 中的每个字母时，将该字母对应桶中的所有单词，根据下一个等待匹配字母放入到不同的桶中。如果已经匹配到单词的最后一个字母，那么子序列单词数加 1。完整代码如下：
class Solution {
public int numMatchingSubseq(String S, String[] words) {
int ans = 0;
ArrayList<Node>[] heads = new ArrayList[26];
for (int i = 0; i < 26; ++i)
heads[i] = new ArrayList<Node>();
for (String word: words)
heads[word.charAt(0) - 'a'].add(new Node(word, 0));
for (char c: S.toCharArray()) {
ArrayList<Node> old_bucket = heads[c - 'a'];
heads[c - 'a'] = new ArrayList<Node>();
for (Node node: old_bucket) {
node.index++;
if (node.index == node.word.length()) {
ans++;
} else {
heads[node.word.charAt(node.index) - 'a'].add(node);
}
}
old_bucket.clear();
}
return ans;
}
}
class Node {
String word;
int index;
public Node(String w, int i) {
word = w;
index = i;
}
}
我反正是debug走了两遍才看懂这个写法。。只能说确实挺巧妙的。。而且我还觉得这种做法似曾相识，好像之前做过类似的题目。而且之前也是看题解才想到的。。算了，下一题了。
有效的“井”字游戏
题目：用字符串数组作为井字游戏的游戏板 board。当且仅当在井字游戏过程中，玩家有可能将字符放置成游戏板所显示的状态时，才返回 true。该游戏板是一个 3 x 3 数组，由字符 " "，"X" 和 "O" 组成。字符 " " 代表一个空位。以下是井字游戏的规则：
玩家轮流将字符放入空位（" "）中。
第一个玩家总是放字符 “X”，且第二个玩家总是放字符 “O”。
“X” 和 “O” 只允许放置在空位中，不允许对已放有字符的位置进行填充。
当有 3 个相同（且非空）的字符填充任何行、列或对角线时，游戏结束。
当所有位置非空时，也算为游戏结束。
如果游戏结束，玩家不允许再放置字符。
示例 1:
输入: board = ["O ", " ", " "]
输出: false
解释: 第一个玩家总是放置“X”。
示例 2:
输入: board = ["XOX", " X ", " "]
输出: false
解释: 玩家应该是轮流放置的。
示例 3:
输入: board = ["XXX", " ", "OOO"]
输出: false
示例 4:
输入: board = ["XOX", "O O", "XOX"]
输出: true
说明:
游戏板 board 是长度为 3 的字符串数组，其中每个字符串 board[i] 的长度为 3。
board[i][j] 是集合 {" ", "X", "O"} 中的一个字符。
思路：这个题怎么说呢，我觉得有两点：1.场上的符号一定是XO一样多或者X比O多一个。2.当X仅有的出现了三个连一起（如示例3），那么一定O少一个。剩下没别的了吧，我去代码试试。
第一版本代码:
class Solution {
public boolean validTicTacToe(String[] board) {
char[][] d = new char[3][3];
int x = 0;
int o = 0;
for(int i = 0;i<3;i++) {
for(int j = 0;j<3;j++) {
d[i][j] = board[i].charAt(j);
if(d[i][j] == 'X') {
x++;
}else if(d[i][j] == 'O'){
o++;
}
}
}
//一对一个的下。要么x多一个，要么一样多，不会出现第三种结果
if(o>x || x>o+1) return false;
//不足三个根本不会成型，所以一定可以。
if(x<=3 && o<3) return true;
//现在看来数目是对的，继续判断有没有赢了还继续下的
boolean x1 = isOk(d, 'X');
boolean o1 = isOk(d, 'O');
if(x1 && o1) return false;//不可能两个人都赢
if(x1) return x == o+1;//如果x要赢了，那么最后一步下的，所以x多一步
if(o1) return x == o;//o要赢最后一步是o下的，所以数目要一样
return true;
}
public boolean isOk(char[][] d,char c) {
if(d[0][0] == c && d[0][1] ==c && d[0][2] == c) return true;
if(d[1][0] == c && d[1][1] ==c && d[1][2] == c) return true;
if(d[2][0] == c && d[2][1] ==c && d[2][2] == c) return true;
if(d[0][0] == c && d[1][0] ==c && d[2][0] == c) return true;
if(d[0][1] == c && d[1][1] ==c && d[2][1] == c) return true;
if(d[0][2] == c && d[1][2] ==c && d[2][2] == c) return true;
if(d[0][0] == c && d[1][1] ==c && d[2][2] == c) return true;
if(d[0][2] == c && d[1][1] ==c && d[2][0] == c) return true;
return false;
}
}
还好只是3 * 3.这要是30 * 30还得累死我。。。这个isok我觉得直接写比for循环判断更直接。所以这个代码的性能超过百分百了，撒花~~
这个题目没啥难度，就是逻辑判断。把所有会报错的挑出来，剩下的就是正确的了。也没啥好说的，我去瞅一眼性能第一的代码：
class Solution {
public boolean validTicTacToe(String[] board) {
int xCount = 0, oCount = 0;
for (String row: board)
for (char c: row.toCharArray()) {
if (c == 'X') xCount++;
if (c == 'O') oCount++;
}
if (oCount != xCount && oCount != xCount - 1) return false;
if (win(board, 'X') && oCount != xCount - 1) return false;
if (win(board, 'O') && oCount != xCount) return false;
return true;
}
public boolean win(String[] B, char P) {
// B: board, P: player
for (int i = 0; i < 3; ++i) {
if (P == B[0].charAt(i) && P == B[1].charAt(i) && P == B[2].charAt(i))
return true;
if (P == B[i].charAt(0) && P == B[i].charAt(1) && P == B[i].charAt(2))
return true;
}
if (P == B[0].charAt(0) && P == B[1].charAt(1) && P == B[2].charAt(2))
return true;
if (P == B[0].charAt(2) && P == B[1].charAt(1) && P == B[2].charAt(0))
return true;
return false;
}
}
思路大同小异，就是写法上不太一样。这个题过了。
所有可能的路径
题目：给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a ）空就是没有下一个结点了。
示例 1：
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
示例 3：
输入：graph = [[1],[]]
输出：[[0,1]]
示例 4：
输入：graph = [[1,2,3],[2],[3],[]]
输出：[[0,1,2,3],[0,2,3],[0,3]]
示例 5：
输入：graph = [[1,3],[2],[3],[]]
输出：[[0,1,2,3],[0,3]]
提示：
结点的数量会在范围 [2, 15] 内。
你可以把路径以任意顺序输出，但在路径内的结点的顺序必须保证。
题目截图
思路：这个题我觉得思路还好吧，应该就是广搜或者深搜。而且注意这个题目上说到了是有向无环图。既然无环的话也不怕死循环了，直接就顺序往下遍历？大概思路有的，我去实现下试试。
第一版本代码：
class Solution {
int n;
List<List<Integer>> ans;
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
ans = new ArrayList<List<Integer>>();
n = graph.length-1;
dfs(graph, 0,new ArrayList<Integer>());
return ans;
}
public void dfs(int[][] graph,int temp,List<Integer> list){
list.add(temp);
if(temp == n) {
ans.add(list);
return;
}
for(int i : graph[temp]) {
dfs(graph, i, new ArrayList<Integer>(list));
}
}
}
果然这个题目比我想的还要简单。一开始看了题目我就想着要不要记忆化啥的。。但是后来仔细审了题目发现无环，所以就直接暴力遍历。代码性能还行，至于优化点不太清楚，我现在能想到的就是dfs变成显示栈调用？但是感觉不会性能差别很大啊，直接去看看性能第一的代码：
class Solution {
public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
List<Integer> tem = new ArrayList<>();
tem.add(0);
dfs(graph,0,graph.length,tem);
return ans;
}
public List<List<Integer>> ans = new ArrayList<>();
public void dfs(int [][] graph,int next ,int end ,List<Integer> tem){
//封装结果
if(next == end-1){
ans.add(new ArrayList<>(tem));
return;
}
//next 时候可以选择得路线
int graph_next[] = graph[next];
for(int i=0;i<graph_next.length;i++){
//加入路径
tem.add(graph_next[i]);
dfs(graph,graph_next[i],end,tem);
tem.remove(tem.size()-1);
}
}
}
性能第一的代码用的是回溯，虽然我觉得本质上应该差不多，但是因为就只差了1ms的时间，所以可能这么写就是性能更好吧，反正这个题比较简单，直接过了，下一题。
不同的子序列
题目：给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^
提示：
0 <= s.length, t.length <= 1000
s 和 t 由英文字母组成
思路：这个是21/3/17的每日一题，困难难度的，其实我现在对于困难难度的题目都抱着敬而远之的态度，毕竟自认为太菜。不过既然是现在每日一题做到了也要尽量啃啃。从头说这个题目，这个题目的标签有个动态规划，只要是dp肯定是有个dp公式的。暂时我的想法肯定是从左往右一次遍历，至于递推公式，我的想法是二维数组，长宽是s和t的长度。所以盲猜动态方程肯定是从角角逼近的方式填充的。
上面的思路连蒙带猜的对了，但是动态方程迟迟没有写出来，所以我决定还是直接看题解了。当然只看了下思路，然后自己去写的代码。
附上代码：
class Solution {
public int numDistinct(String s, String t) {
int lens = s.length();
int lent = t.length();
if(lens<lent) return 0;//t如果比s长，不可能有子序列
int[][] dp = new int[lens+1][lent+1];
//最后一个字符是空，空是任何字符串的子序列。所以补1
for(int i = 0;i<=lens;i++) dp[i][lent] = 1;
for(int i = lens-1;i>=0;i--) {
char cs = s.charAt(i);
for(int j = lent-1;j>=0;j--) {
char ct = t.charAt(j);
//不管当前元素能不能用上，之前已经能组成的可能都不变，所以都加下面那个数字
if(cs == ct) {
//右下是当前元素的下一个。都可以被当前元素续上，所以加上右下
dp[i][j] = dp[i+1][j+1]+dp[i+1][j];
}else {
dp[i][j] = dp[i+1][j];
}
}
}
return dp[0][0];
}
}
其实上面的猜测很大一部分都对了的，比如说二维dp数组角落逼近。我差的就是这么个思路清晰的递推公式。。
附上当时我看的递推公式推到的表述：
- 假设字符串 s和 t的长度分别为 m 和 n。如果 t 是 s 的子序列，则 s 的长度一定大于或等于 t 的长度，即只有当 m≥n 时，t 才可能是 s 的子序列。如果 m<n，则 t 一定不是 s 的子序列，因此直接返回 0。
- 当 m≥n 时，可以通过动态规划的方法计算在 s 的子序列中 t 出现的个数。
- 创建二维数组dp，其中 dp[i][j] 表示在 s[i:]的子序列中 t[j:] 出现的个数。
- 上述表示中，s[i:] 表示 s从下标 i 到末尾的子字符串，t[j:] 表示 t从下标 j 到末尾的子字符串。
- 考虑动态规划的边界情况：
- 当 j=n时，t[j:] 为空字符串，由于空字符串是任何字符串的子序列，因此对任意dp[i][n]=1；
- 当 i=m 且 j<n 时，s[i:]为空字符串，t[j:] 为非空字符串，由于非空字符串不是空字符串的子序列，因此对任意 j<n，dp[m][j]=0。
- 当 s[i]=t[j]时，dp[i][j] 由两部分组成：
如果 s[i] 和 t[j] 匹配，则考虑 t[j+1:]作为 s[i+1:] 的子序列，子序列数为dp[i+1][j+1]；
如果 s[i] 不和 t[j] 匹配，则考虑 t[j:]作为 s[i+1:] 的子序列，子序列数为 dp[i+1][j]。
因此当 s[i] = t[j]时，有dp[i][j] = dp[i+1][j+1] + dp[i+1][j]。
以上就是全部dp 的思路。也是上面代码的语言表述。由此得出这个题的答案。
本篇笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利吧~
网友评论