北京网站建设亿玛酷适合5,手机项目工作室,wordpress字体设置,页面设计免费交换字符使得字符串相同
题目描述
有两个长度相同的字符串 s1 和 s2#xff0c;且它们其中 只含有 字符 “x” 和 “y”#xff0c;你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候#xff0c;你都可以在两个字符串中各选一个字符进行交换。
…交换字符使得字符串相同
题目描述
有两个长度相同的字符串 s1 和 s2且它们其中 只含有 字符 “x” 和 “y”你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个不同的字符串之间绝对不能发生在同一个字符串内部。也就是说我们可以交换 s1[i] 和 s2[j]但不能交换 s1[i] 和 s1[j]。
最后请你返回使 s1 和 s2 相同的最小交换次数如果没有方法能够使得这两个字符串相同则返回 -1 。
样例
样例输入 s1 “xx”, s2 “yy” s1 “xy”, s2 “yx” s1 “xx”, s2 “xy” s1 “xxyyxyxyxx”, s2 “xyyxyxxxyx” 样例输出 1 解释 交换 s1[0] 和 s2[1]得到 s1 “yx”s2 “yx”。 2 解释 交换 s1[0] 和 s2[0]得到 s1 “yy”s2 “xx” 。 交换 s1[0] 和 s2[1]得到 s1 “xy”s2 “xy” 。 注意你不能交换 s1[0] 和 s1[1] 使得 s1 变成 “yx”因为我们只能交换属于两个不同字符串的字符。 -1 4 提示
1 s1.length, s2.length 1000s1, s2 只包含 ‘x’ 或 ‘y’。
思路
先给x,y计数如果x的数量或者y的数量不能整除2那么可直接返回-1。 然后后面的结论就是把玩数据而推出来的结论因为要使s1[i]与s2[i]相等就不需要改变进行转变就会相等那么就只有s1[i] x 且 s2[i] y后面简称为xy || s1[i] y 且 s2[i] x后面简称为yx的情况。又通过把玩数据可知xy与xy消除只需要一次交换yx与yx同理而xy与yx消除需要两次交换。 贪心的想能使相同的两种类型交换就尽可能的两种相同类型进行交换。
代码实现
class Solution {public int minimumSwap(String s1, String s2) {int n s1.length();int c1 0, c2 0;int top 0, bottom 0;for(int i 0; i n; i){c1 (s1.charAt(i) x ? 1 : 0) (s2.charAt(i) x ? 1: 0);c2 (s1.charAt(i) y ? 1 : 0) (s2.charAt(i) y ? 1: 0);if(s1.charAt(i) ! s2.charAt(i)){if(s1.charAt(i) x) top;else bottom;}}if(c1 % 2 ! 0 || c2 % 2 ! 0) return -1;int ans 0;ans top / 2;ans bottom / 2;top % 2;bottom % 2;if(top 1 bottom 1) ans 2;return ans;}
}单词搜索 II
题目描述
给定一个 m x n 二维字符网格 board 和一个单词字符串列表 words 返回所有二维网格上的单词 。
单词必须按照字母顺序通过 相邻的单元格 内的字母构成其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
样例
样例输入 board [[“o”,“a”,“a”,“n”],[“e”,“t”,“a”,“e”],[“i”,“h”,“k”,“r”],[“i”,“f”,“l”,“v”]], words [“oath”,“pea”,“eat”,“rain”] board [[“a”,“b”],[“c”,“d”]], words [“abcb”] 样例输出 [“eat”,“oath”] [] 提示
m board.lengthn board[i].length1 m, n 12board[i][j] 是一个小写英文字母1words.length3∗1041 words.length 3 * 10^41words.length3∗1041 words[i].length 10words[i] 由小写英文字母组成words 中的所有字符串互不相同
思路
矩阵范围很小可直接上暴力回溯能过。但现在还是学习更优的加法才好。因为是字符串的检索可使用字典树进行优化。
代码实现
回溯
class Solution {int m, n;HashSetString set new HashSet();ListString ans new ArrayList();char[][] board;boolean[][] vis new boolean[15][15];int[][] dir {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};public ListString findWords(char[][] board, String[] words) {m board.length;n board[0].length;this.board board;for(String w : words) set.add(w);StringBuilder sb new StringBuilder();for(int i 0; i m; i){for(int j 0; j n; j){vis[i][j] true;sb.append(board[i][j]);dfs(i, j, sb);sb.deleteCharAt(sb.length()-1);vis[i][j] false;}}return ans;}private void dfs(int i, int j, StringBuilder sb){if(sb.length() 10) return ;if(set.contains(sb.toString())){ans.add(sb.toString());set.remove(sb.toString());}for(var d : dir){int x d[0] i, y d[1] j;if(x 0 || x m || y 0 || y n || vis[x][y]) continue;vis[x][y] true;sb.append(board[x][y]);dfs(x, y, sb);sb.deleteCharAt(sb.length() - 1);vis[x][y] false;}}
}字典树优化
class Solution {class TreeNode{String s;TreeNode[] next new TreeNode[26]; }void insert(String s){TreeNode p root;for(int i 0; i s.length(); i){int u s.charAt(i) - a;if(p.next[u] null) p.next[u] new TreeNode();p p.next[u]; }p.s s;}int m, n;HashSetString set new HashSet();TreeNode root new TreeNode();char[][] board;int[][] dir {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};boolean[][] vis new boolean[15][15];public ListString findWords(char[][] board, String[] words) {m board.length;n board[0].length;this.board board;for(String w : words) insert(w);StringBuilder sb new StringBuilder();for(int i 0; i m; i){for(int j 0; j n; j){int u board[i][j] - a;if(root.next[u] ! null){vis[i][j] true;dfs(i, j, root.next[u]);vis[i][j] false;}}}ListString ans new ArrayList();for(var s : set) ans.add(s);return ans;}private void dfs(int i, int j, TreeNode node){if(node.s ! null) set.add(node.s);for(var d : dir){int x d[0] i, y d[1] j;if(x 0 || x m || y 0 || y n || vis[x][y]) continue;int u board[x][y] - a;if(node.next[u] ! null){vis[x][y] true;dfs(x, y, node.next[u]);vis[x][y] false;}}}
}
