CSDN话题挑战赛第2期
参赛话题：学习笔记
题目一、面试题 01.02. 判定是否互为字符重排
题目描述：
给定两个字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
/
示例 1：
输入: s1 = “abc”, s2 = “bca”
输出: true
/
示例 2：
输入: s1 = “abc”, s2 = “bad”
输出: false
/
说明：
0 <= len(s1) <= 100
0 <= len(s2) <= 100
解题思路：
给定了两个字符串，要求其中一个字符串的字符重新排序后获得另一个字符。
我们可以得到的信息就是，重排前后的字符串差距在于字符排列的顺序不一样，也就是说重排前后两个字符串包含的字符是一样的。
那么我们现在需要解决的问题就转换成了：判断两个字符串中包含的字符是否完全相同。这与判断两个字符串是否互为字符重排是等价的。
为了对比两个字符串中包含的字符，我们需要先将两个字符串中包含的字符给提取出来，我通过使用String类型的toCharArray()方法，分别将两个字符串中包含的字符提取出来，组成了两个字符数组。
为了方便比较两个字符数组中的元素是否完全相同，我使用了借助了List集合。
首先遍历其中一个字符数组，将其中的元素都存放到List集合中，之后再遍历剩下一个字符数组的元素，每遍历一个元素，就使用List集合的contains()方法来判断此元素是否在集合中存在。
如果遇到遍历的元素不存在于List集合中，就代表当前字符只存在于其中一个字符串，也就是两个字符串不为字符重排，直接返回false即可。
如果存在于List集合，我们就继续遍历，但是为了不让当前元素影响后续的判断，需要删除List集合中于当前遍历字符相同的一个字符元素。这里使用到的有获取元素下标的：indexOf()方法，根据下标删除集合元素得到remove()方法。
当我们将字符串遍历完后，就可以返回true了，也说明两个字符串互为字符重排。
提交代码：
class Solution { public boolean CheckPermutation(String s1, String s2) { char[] S1 = s1.toCharArray(); //获取s1的字符数组S1 char[] S2 = s2.toCharArray(); //获取s2的字符数组S2 List<Character> list = new ArrayList<>(); //创建ArrayList集合 for(char a : S1){ //遍历集合S1 list.add(a); //集合元素存入数组 } for(char a : S2){ //遍历集合S2 if(!list.contains(a)) //如果S2存在元素是S1中没有的 return false; //无法字符重排，返回false else{ //存在对应元素 list.remove(list.indexOf(a)); //将集合集合中对应的字符删除 } } return true; //S1、S2所有字符都对应上，可以重排 }}提交结果：
题目二、62. 不同路径
原题链接：62. 不同路径
题目描述：
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
/
示例 1：
输入：m = 3, n = 7
输出：28
/
示例 2：
输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
向右 -> 向下 -> 向下
向下 -> 向下 -> 向右
向下 -> 向右 -> 向下
/
示例 3：
输入：m = 7, n = 3
输出：28
示例 4：
输入：m = 3, n = 3
输出：6
解题思路：
类似于爬楼梯问题，依旧是用动态规划的思路：
我们遍历网格的第一行和第一列，给第一行和第一列赋值上一个路径，每到一个网格，只需要考虑其上位置和左位置的路径数量。
移动到最后终点时，累计的路径数便是总路径数目。
提交代码：
class Solution { public int uniquePaths(int m, int n) { int[][] step = new int[m][n]; //创建m×n网络 for(int i = 0;i < m;++i){ //给第一列赋值一个路径 step[i][0] = 1; } for(int i = 0;i < n;++i){ //给第一行赋值一个路径 step[0][i] = 1; } for(int i = 1;i < m;++i){ //动态规划地将前面两个位置存在路径累加起来 for(int j = 1;j < n;++j){ step[i][j] =step[i-1][j] + step[i][j-1] ; } } return step[m-1][n-1]; //返回抵达终点的所有路径 }}提交结果：
题目三、205. 同构字符串
原题链接：205. 同构字符串
题目描述：
给定两个字符串 s 和 t ，判断它们是否是同构的。
如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
示例 1
输入：s = “egg”, t = “add”
输出：true
示例 2：
输入：s = “foo”, t = “bar”
输出：false
示例 3：
输入：s = “paper”, t = “title”
输出：true
解题思路：
使用Map集合来存放键值对，遍历集合中的键值对，当出现于之前存在的键值对起冲突的情况，就代表无法重构了。具体看注释：
提交代码：
class Solution { public boolean isIsomorphic(String s, String t) { //使用Map集合来存储映射关系 Map <Character,Character> s2t = new HashMap<Character,Character>(); Map <Character,Character> t2s = new HashMap<Character,Character>(); //获取字符串的字符长度 int length = s.length(); char x,y; for(int i = 0;i < length; ++i){//遍历 //分别遍历两个字符串，取相同位置的字符 x = s.charAt(i); y = t.charAt(i); //两个集合的键值对分别反向存储两个取得的字符 //在不断遍历过程中，如果发现新的键值对与已存在的键值对的关系不同，就代表不能同构了 if(s2t.containsKey(x)&&s2t.get(x)!=y||t2s.containsKey(y)&&t2s.get(y)!=x){return false;} //两个集合的键值对分别反向存储两个取得的字符 s2t.put(x,y); t2s.put(y,x); } return true; //若两个集合键值对没有发生冲突,返回真 }}提交结果：
⚽
求关注⚽ 作者? .29. ? 的✔博客主页✔
⚽来刷题⚽ 记录每日LeetCode✔刷题专栏✔
您的点赞，收藏以及关注是对作者最大的鼓励喔 ~~
