每日一刷《剑指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;
}我正在参与2023腾讯技术创作特训营第三期有奖征文，组队打卡瓜分大奖！
腾讯云开发者
