题目
剑指 Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例：
输入：s = "abaccdeff" 输出：'b' 复制代码
分析一
思路从简单点的开始
使用正则匹配，对字符串从前往后遍历，只要匹配结果出现唯一个值的，就是我们所找的第一个只出现一次的字符，直接返回即可
实现
function firstUniqChar(s: string): string { for (let i of s) { const reg = new RegExp(i, "g") if (s.match(reg).length === 1) { return i } } return ' ' }; 复制代码
分析二
上面的解法实际上每一次都对整个字符串做全量匹配，现在我们来进行一下优化，看能不能减少遍历次数
一般时间优化都会想到使用哈希表来空间换时间，那么
- 我们在遍历的时候将每个字符作为key存入哈希表中，遇到相同字符时，将对应的key值加一
- 得到哈希表后，我们在对哈希表进行一次遍历（哈希表存值是有序的），找到第一个key值为1的位置，将key返回，即得到我们所求的结果
- 如果没有找到，按照题意返回空字符串
实现
function firstUniqChar(s: string): string { let map: Map<string, number> = new Map() for(let i of s) { if (map.get(i)) { map.set(i, map.get(i) + 1) } else { map.set(i, 1) } } for (let [ key, value ] of map.entries()) { if (value === 1) { return key } } return ' ' }; 复制代码
分析三
由于上述方法使用了map的迭代，可以考虑将 key 值换成 boolean 值来对逻辑进行一下优化，在判断的时候更加简洁直观点
实现
function firstUniqChar(s: string): string { let map: Map<string, boolean> = new Map() for (let key of s) { if (map.has(key)) { map.set(key, false) } else { map.set(key, true) } } for (let key of s) { if (map.get(key)) { return key } } return ' ' }; 复制代码
题目
剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
现有矩阵 matrix 如下：
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ] 复制代码
分析一
本题有一定难度，我们先用暴力破解+二分查找的方法把答案做出来先
- 遍历每一层数组
- 在数组内部使用二分查找
- 如果碰到目标值，返回 true
- 循环结束没有遇到目标值，返回 false
实现
function findNumberIn2DArray(matrix: number[][], target: number): boolean { for (let i = 0; i < matrix.length; i ++) { let left = -1 let right = matrix[i].length while(left + 1 != right) { const mid = (left + right) >> 1 if (matrix[i][mid] === target) { return true } else if (matrix[i][mid] > target) { right = mid } else { left = mid } } } return false }; 复制代码
分析二
利用该二维数组的特性，从右上角开始遍历
- 如果目标值大于右上角，那么目标值只可能在当前 y 轴上，j ++ 从上往下遍历
- 如果目标值小于右上角，么 x 轴先退一列，i -- ，后续在从上往下遍历
- 如果相等，返回 true
实现
function findNumberIn2DArray(matrix: number[][], target: number): boolean { let i = matrix.length-1 let j = 0 while( i>=0 && j <=matrix[0].length -1){ if(matrix[i][j]>target){ i-- }else if(matrix[i][j] <target){ j++ }else return true } return false };
