fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
二分查找高效判定子序列 :: labuladong的算法小抄
可以用HashMap做。把一系列字符串的第一个字符加入HashMap并且记录是哪个字符串。然后遍历t，对于匹配到的字符串，把它们的下一个字符加入HashMap直到末尾。时间复杂度是O(M*N)。M是字符串数量，N是t的长度。
防止大家对这边的 index[c] 这种表达形式转不过弯来， 这边使用HashMap实现了一下
class Solution {
public boolean isSubsequence(String s, String t) {
TreeMap<Character,LinkedList<Integer>> map = new TreeMap<>();//存储t中所有 与s中字符相同的字符的索引位置
// char - list[字符索引]
for(int i = 0; i<t.length();i++){
LinkedList<Integer> list = new LinkedList<>();
if(map.containsKey(t.charAt(i))){//如果存在 直接在list末尾添加
map.get(t.charAt(i)).add(i);
}else{
list.addLast(i);//如果不存在需要创建一个键值映射
map.put(t.charAt(i),list);
}
}
int j = 0;//t中的游标位置
for(int i = 0; i< s.length();i++){
char c = s.charAt(i);// 当前s中需要匹配的字符
if(!map.containsKey(c)){//t中没有这个字符 直接返回false
return false;
}
//如果存在，找到比当前游标位置 大的 最小的索引
int pos = leftBound(map.get(c),j);
// System.out.println(pos); debug位置
// System.out.println("---");
if(pos == map.get(c).size()) return false;
j = map.get(c).get(pos) +1; //t上的指针
// System.out.println(j);debug 位置
}
return true;
}
//寻找s中字符 在t中字符索引 的 左边界
//list中存储的是 s中c字符对应的 所有索引 从小到大排序
//我们要找的是list中比 当前t上指针 j/tar 大的那个索引 直接跳过去
//这里得出的 左边界是 存储 对应字符索引的 list 的索引 所以，如果想要得到 对应t上的实际位置 还需要使用get(pos)
private int leftBound(LinkedList<Integer> list,int j){
int left = 0;
int right = list.size();
while(left < right){
int mid = (right - left)/2 + left;
if(j>list.get(mid)){
left = mid+1;
}else{
right = mid;
}
}
return left;
}
}
贴个C++的用哈希表的代码
class Solution {
public:
bool isSubsequence(string s, string t) {
// 二分查找
int m = s.size(), n = t.size();
// 将较长的字符串保存到map里去
unordered_map<char,vector<int>> map_t(256);
for(int i = 0; i < n; i++){
map_t[t[i]].push_back(i);
}
// a 0
// h 1
// b 2
// g 3
// d 4
// c 5
// 串t指针
int j = 0;
// 借助map查找s[i]
for(int i = 0; i < m; i++){
if(!map_t.count(s[i])){
// s[i]不在t里，直接返回
return false;
}
// 如果存在，在map[s[i]]中搜索比j大的最小索引即可：即二分搜索左侧边界的结果值
int pos = leftBound(map_t[s[i]], j); // 传入的是s[i]在t中对应出现的所有下标索引
if(pos == map_t[s[i]].size()){
// 二分搜索区间中没有找到s[i]
return false;
}
j = map_t[s[i]][pos] + 1; // j 移动到二分搜索返回的pos处 后一位
}
return true;
}
int leftBound(vector<int>& vec_t, int j){
// 二分查找 搜索左侧边界 搜索j
int left = 0, right = vec_t.size();
// 左闭右开
while(left < right){
int mid = left + (right - left)/2;
if(vec_t[mid] < j){
left = mid + 1;
}else if(vec_t[mid] >j){
right = mid;
}else{
right = mid;
}
}
return left;
}
};
