每日一刷《剑指offer》字符串篇之第一个只出现一次的字符
第一个只出现一次的字符
难度：简单
描述
在一个长为 字符串中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
举例
解题思路
方法一：哈希表；既然要找第一个只出现一次的字符，那只要我们统计每个字符在字符串中出现的次数，后续不就可以找到第一个只出现一次的字符了吗？
统计频率可以建立一个哈希表，遍历字符串的同时，统计每个字符出现的频率，然后再从头遍历一次字符串，在哈希表中查看每个字符串的频率，找到第一个只出现一次的字符串，返回位置，如果没找到返回-1即可。
方法二：队列+哈希表统计位置；上述方法一遍历了两次，有些繁琐，我们能不能在统计频率的过程中就找到第一个只出现一次的字符呢？利用先进先出的队列找到第一个位置！
首先我们还是利用了哈希表，但是这次我们不是统计频率，而是统计每个字符出现位置。遍历字符串，如果遇到哈希表中没有的字符，我们入哈希表，同将字符和位置同时各自入队，后续如果遇到了哈希表中出现的字符，那么这个字符势必不可能是我们要找的只出现一次的字符，在哈希表中将其位置置为-1：
//位置置为-1 mp[str[i]] = -1;
然后弹出队列中在前面的哈希表中位置为-1的字符。因为队列是先进先出，因此队列头记录的字符一定是第一次只出现一次的字符。
while(!q.empty() && mp[q.front().first] == -1) q.pop();
空队列则代表没有找到。
实现代码（java）
方法一：
import java.util.*; public class Solution { public int FirstNotRepeatingChar(String str) { HashMap<Character, Integer> mp = new HashMap<>(); //统计每个字符出现的次数 for(int i = 0; i < str.length(); i++) mp.put(str.charAt(i), mp.getOrDefault(str.charAt(i), 0) + 1); //找到第一个只出现一次的字母 for(int i = 0; i < str.length(); i++) if(mp.get(str.charAt(i)) == 1) return i; //没有找到 return -1; } }
方法二：
import java.util.*; public class Solution { public int FirstNotRepeatingChar(String str) { //统计字符出现的位置 HashMap<Character, Integer> mp = new HashMap<>(); Queue<Character> q1 = new LinkedList<>(); Queue<Integer> q2 = new LinkedList<>(); for(int i = 0; i < str.length(); i++){ //没有出现过的字符 if(!mp.containsKey(str.charAt(i))){ mp.put(str.charAt(i), i); q1.offer(str.charAt(i)); q2.offer(i); //找到重复的字符 }else{ //位置置为-1 mp.put(str.charAt(i), -1); //弹出前面所有的重复过的字符 while(!q1.isEmpty() && mp.get(q1.peek()) == -1){ q1.poll(); q2.poll(); } } } return q2.isEmpty() ? -1 : q2.poll(); } }
学习完本题的思路你可以解决如下题目：
矩阵中的路径
难度：中等
描述
请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如
矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。
举例
解题思路
方法一：递归（推荐使用）；要在矩阵中找到从某个位置开始，位置不重复的一条路径，路径为某个字符串，那我们肯定是现在矩阵中找到这个位置的起点。没办法直观的找出来，只能遍历矩阵每个位置都当作起点试一试。
找到起点后，它周围的节点是否可以走出剩余字符串子串的路径，该子问题又可以作为一个递归。因此，可以用递归来解决。
- 终止条件： 到了矩阵的边界或者是下一个字符与这个位置的字符不匹配，或者字符串匹配完成，都需要返回，
- 返回值： 将每条查询路径是否有这样的字符串返回，即true or false。
- 本级任务： 检查这个位置的字符与字符串中这个字符是否匹配，并向与它相邻的四个方向（且不是来的方向）延伸子问题。
dfs(matrix, n, m, i - 1, j, word, k + 1, flag) ||dfs(matrix, n, m, i + 1, j, word, k + 1, flag) ||dfs(matrix, n, m, i, j - 1, word, k + 1, flag) ||dfs(matrix, n, m, i , j + 1, word, k + 1, flag)
同时，在走的过程中，要设置一个和矩阵大小相同的bool矩阵表示是否已经访问，如果某个结点访问了，在同一条路线上就不能再访问了，其他路线依旧可以访问，所以若是某条路线不达标，需要回溯，将其改回来。
flag[i][j] = true; ...//递归 //没找到经过此格的，此格未被占用 flag[i][j] = false;
实现代码（java）
import java.util.*; public class Solution { private boolean dfs(char[][] matrix, int n, int m, int i, int j, String word, int k, boolean[][] flag){ if(i < 0 || i >= n || j < 0 || j >= m || (matrix[i][j] != word.charAt(k)) || (flag[i][j] == true)) //下标越界、字符不匹配、已经遍历过不能重复 return false; //k为记录当前第几个字符 if(k == word.length() - 1) return true; flag[i][j] = true; //该结点任意方向可行就可 if(dfs(matrix, n, m, i - 1, j, word, k + 1, flag) ||dfs(matrix, n, m, i + 1, j, word, k + 1, flag) ||dfs(matrix, n, m, i, j - 1, word, k + 1, flag) ||dfs(matrix, n, m, i , j + 1, word, k + 1, flag)) return true; //没找到经过此格的，此格未被占用 flag[i][j] = false; return false; } public boolean hasPath (char[][] matrix, String word) { //优先处理特殊情况 if(matrix.length == 0) return false; int n = matrix.length; int m = matrix[0].length; //初始化flag矩阵记录是否走过 boolean[][] flag = new boolean[n][m]; //遍历矩阵找起点 for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ //通过dfs找到路径 if(dfs(matrix, n, m, i, j, word, 0, flag)) return true; } } return false; } }
学习完本题的思路你可以解决如下题目：
机器人的运动范围
难度：困难
描述
地上有一个 rows 行和 cols 列的方格。坐标从 [0,0] 到 [rows-1,cols-1] 。一个机器人从坐标 [0,0] 的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于 threshold 的格子。 例如，当 threshold 为 18 时，机器人能够进入方格 [35,37] ，因为 3+5+3+7 = 18。但是，它不能进入方格 [35,38] ，因为 3+5+3+8 = 19 。请问该机器人能够达到多少个格子？
举例
解题思路
方法一：DFS（深度优先搜索）
这道题说的是一个机器人从左上角开始，他可以沿着上下左右四个方向走，并且走到的每个格子坐标的数字和不大于k，问可以走多少个格子。我们先来画个图看一下
这里统计的是能走多少个格子，所以统计肯定是不能有重复的，题中说了，机器人是可以沿着上下左右四个方向走的。但你想一下，任何一个格子你从任何一个方向进来（比如从上面进来），那么他只能往其他3个方向走，因为如果在往回走就重复了。但实际上我们只要沿着两个方向走就可以了，一个是右边，一个是下边，也就是上面图中红色的箭头。
实现代码（java）
public int movingCount(int threshold, int rows, int cols) { //临时变量visited记录格子是否被访问过 boolean[][] visited = new boolean[rows][cols]; return dfs(0, 0, rows, cols, threshold, visited); } public int dfs(int i, int j, int rows, int cols, int threshold, boolean[][] visited) { //i >= rows || j >= cols是边界条件的判断，threshold < sum(i, j)判断当前格子坐标是否 // 满足条件，visited[i][j]判断这个格子是否被访问过 if (i >= rows || j >= cols || threshold < sum(i, j) || visited[i][j]) return 0; //标注这个格子被访问过 visited[i][j] = true; //沿着当前格子的右边和下边继续访问 return 1 + dfs(i + 1, j, rows, cols, threshold, visited) + dfs(i, j + 1, rows, cols, threshold, visited); } //计算两个坐标数字的和 private int sum(int i, int j) { int sum = 0; //计算坐标i所有数字的和 while (i != 0) { sum += i % 10; i /= 10; } //计算坐标j所有数字的和 while (j != 0) { sum += j % 10; j /= 10; } return sum; }
