力扣热题4-字符串匹配、搜索旋转排序数组（二分）
按照leetcode刷一遍：leetcode hot
前面几道可以再看看。
28. 实现 strStr()
就是字符串匹配问题。
给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。
说明：
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1：
输入：haystack = "hello", needle = "ll"
输出：2
示例 2：
输入：haystack = "aaaaa", needle = "bba"
输出：-1
背景
字符串匹配，首先会想到两个循环遍历，复杂度O(mn)。
改良：KMP算法O(m+n)，BM算法（Boyer-Moore）O(m/n)，Sunday算法，是对BM算法的进一步小幅度优化。Sunday算法相比较而言理解容易，复杂度低，平均性能O(n)，最差情况下O(mn)。
暴力超时
class Solution {
public int strStr(String haystack, String needle) {
if(needle.length()==0) return 0;
for(int i=0;i<haystack.length();i++) {
int curi = i;
int j=0;
for(;j<needle.length();j++) {
if(curi>=haystack.length()||haystack.charAt(curi)!=needle.charAt(j)) {
break;
}
curi++;
}
if(j==needle.length()) {
return curi-needle.length();
}
}
return -1;
}
}
Sunday解法
几个概念：
- 目标字符串String，文本串、长度m
- 模式串Pattern，长度n
sunday算法是从前往后匹配的，在匹配失败时关注的是文本串参与匹配的最末位字符的下一个字符。
- 如果这个字符没有在模式串出现过，直接移动：模式串长度+1
- 如果出现过，移动：模式串中该字符最右出现位置到尾部的距离+1
合理性解释：为什么不匹配段的下一个字符？
sunday算法会提前记录每个字符在模式串中最右出现的位置，如abcac，会记录为：{a:3, b:4, c:2}。
在匹配的时候，如上图，发现a、b不等，那当前匹配段bcaab和abcab配不上，那么下一个是caabc和abcab，s段的最后一个字符c顶多是p的最后一个c对应的位置。如果c在p中没有，直接跳一个p.length()
class Solution {
public int strStr(String haystack, String needle) {
// 排除特殊情况
if(needle.length()==0) {
return 0;
}
if(needle.length()>haystack.length()) {
return -1;
}
int[] lastPos = new int[26];
Arrays.fill(lastPos,-1);
// 记录模式串中字符的最后一个位置
for(int i=0;i<needle.length();i++) {
lastPos[(int)(needle.charAt(i)-'a')]=i;
}
// 目标串s和匹配串p的index
int idxS = 0;
int idxP = 0;
int nextCharPos = idxP+needle.length();
while(idxS<haystack.length()) {
//System.out.printf("%d %d\n",idxS,idxP);
if(idxP==needle.length()) {
return idxS-needle.length();
}
if(haystack.charAt(idxS)==needle.charAt(idxP)) {
idxS++;
idxP++;
} else {
// i: 第一个不匹配
// a b c d a
// b c a c
// ========
// a b c d a
// b c a
// i:变化为2
int tmp = 0;
while(true) {
// s串到末尾了
if(nextCharPos>=haystack.length()) {
return -1;
}
tmp = lastPos[(int)(haystack.charAt(nextCharPos)-'a')];
if(tmp==-1) {
nextCharPos += needle.length();
} else {
break;
}
}
idxS = nextCharPos-tmp;
idxP = 0;
nextCharPos = idxS+needle.length();
}
}
if(idxP==needle.length()) {
return idxS-needle.length();
}
return -1;
}
}
另一种写法
不单个比较，而是比较substring，效率高些，也更简洁。
class Solution {
public int strStr(String haystack, String needle) {
// 排除特殊情况
if(needle.length()==0) {
return 0;
}
if(needle.length()>haystack.length()) {
return -1;
}
int[] lastPos = new int[26];
Arrays.fill(lastPos,-1);
// 记录模式串中字符的最后一个位置
for(int i=0;i<needle.length();i++) {
lastPos[(int)(needle.charAt(i)-'a')]=i;
}
// 目标串s和匹配串p的index
int idxS = 0;
while(idxS<haystack.length()-needle.length()) {
if(haystack.substring(idxS,idxS+needle.length()).equals(needle)) {
return idxS;
} else {
int tmp = lastPos[(int)(haystack.charAt(idxS+needle.length())-'a')];
if(tmp==-1) {
idxS += needle.length()+1;
} else {
idxS = idxS+needle.length()-tmp;
}
}
}
return haystack.substring(haystack.length()-needle.length(),haystack.length()).equals(needle)?haystack.length()-needle.length():-1;
}
}
29. 两数相除
位运算问题。
class Solution {
public int divide(int dividend, int divisor) {
boolean neg = false;
int oth = 0;
if(dividend==0) return 0;
if(divisor==1) return dividend;
if(divisor==-1) {
if(dividend==Integer.MIN_VALUE) return Integer.MAX_VALUE;
else return 0-dividend;
}
if(dividend<0) {
neg = !neg;
if(dividend==Integer.MIN_VALUE) {
if(divisor==Integer.MIN_VALUE) return 1;
else {
dividend+=Math.abs(divisor);
oth = 1;
}
}
dividend = 0-dividend;
}
if(divisor<0) {
neg = !neg;
if(divisor==Integer.MIN_VALUE) return 0;
divisor = 0-divisor;
}
return neg?0-oth-divide0(dividend,divisor):oth+divide0(dividend,divisor);
}
private int divide0(int dividend,int divisor) {
System.out.printf("%d %d\n",dividend,divisor);
if(dividend<divisor) return 0;
else if(dividend==divisor) return 1;
int bit = 0;
int sum = 0;
int d = divisor;
while(true) {
if(dividend-d>d) {
bit++;
d<<=1;
}
else break;
}
System.out.printf("%d===%d\n",d>>1,1<<bit);
return (1<<bit)+divide0(dividend-d,divisor);
}
}
比较优雅的写法
class Solution {
public int divide(int dividend, int divisor) {
if(dividend==Integer.MIN_VALUE && divisor==-1) {
return Integer.MAX_VALUE;
}
long a = Math.abs((long)dividend);
long b = Math.abs((long)divisor);
int result = 0;
for(int i=31;i>=0;i--) {
if(a>=(b<<i)) {
a -= b<<i;
result += 1<<i;
}
}
return (dividend<0)==(divisor<0)?result:-result;
}
}
（再看看）33. 搜索旋转排序数组
class Solution {
public int search(int[] nums, int target) {
// 4 5 6 7 1 2 3
// 7 6 5 4 3 2 1
int left = 0;
int right = nums.length-1;
int mid;
while(left<=right) {
mid = (left+right)/2;
if(nums[mid]==target) return mid;
// 左边有序
if(nums[mid]>nums[left]) {
if(target>=nums[left]&&target<nums[mid]) right=mid-1;
else left=mid+1;
} else if(nums[mid]<nums[left]){ // 右边有序
if(target>nums[mid]&&target<=nums[right]) left=mid+1;
else right=mid-1;
} else {
// 只有一个数或者两个数的情况
left++;
}
}
//System.out.println(left);
return -1;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
二分查找。
class Solution {
public int[] searchRange(int[] nums, int target) {
//查找>=元素最左边的下标
if(nums.length==0) return new int[]{-1,-1};
int left = searchLeft(nums,target);
int right = searchLeft(nums,target+1);
//System.out.printf("%d %d\n",left,right);
if(right-1<left) return new int[]{-1,-1};
return new int[]{left,right-1};
}
private int searchLeft(int[] nums,int target) {
if(target>nums[nums.length-1]) return nums.length;
if(target<nums[0]) return 0;
int left = 0;
int right = nums.length-1;
int mid;
while(left<right) {
mid = (left+right)/2;
if(nums[mid]<target) {
left=mid+1;
} else {
right = mid;
}
}
return left;
}
}
36. 有效的数独
class Solution {
public boolean isValidSudoku(char[][] board) {
int SIZE = 9;
int[] exists = new int[SIZE+1];
int cur;
// row
for(int row=0;row<SIZE;row++) {
Arrays.fill(exists,0);
for(int col=0;col<SIZE;col++) {
cur = getNum(board,row,col);
if(cur==-1) continue;
if(exists[cur]!=0) return false;
exists[cur]=1;
}
}
// col
for(int col=0;col<SIZE;col++) {
Arrays.fill(exists,0);
for(int row=0;row<SIZE;row++) {
cur = getNum(board,row,col);
if(cur==-1) continue;
if(exists[cur]!=0) return false;
exists[cur]=1;
}
}
for(int row=0;row<SIZE;row+=3) {
for(int col=0;col<SIZE;col+=3) {
Arrays.fill(exists,0);
for(int i=0;i<3;i++) {
for(int j=0;j<3;j++) {
cur = getNum(board,row+i,col+j);
if(cur==-1) continue;
if(exists[cur]!=0) return false;
exists[cur]=1;
}
}
}
}
return true;
}
private int getNum(char[][] board,int i,int j) {
char c = board[i][j];
if(c=='.') return -1;
else return (int)(c-'0');
}
}
38. 外观数列
直接模拟。
class Solution {
public String countAndSay(int n) {
StringBuilder sb = new StringBuilder("1");
StringBuilder nextsb = new StringBuilder();
for(int k=2;k<=n;k++) {
char[] chrs = sb.toString().toCharArray();
int count = 1;
char lastChar = chrs[0];
for(int i=1;i<chrs.length;i++) {
if(chrs[i]==lastChar) {
count++;
} else {
nextsb.append(String.valueOf(count));
nextsb.append(lastChar);
count=1;
lastChar=chrs[i];
}
}
nextsb.append(String.valueOf(count));
nextsb.append(lastChar);
sb = nextsb;
nextsb = new StringBuilder();
}
return sb.toString();
}
}
41. 缺失的第一个正数
class Solution {
public int firstMissingPositive(int[] nums) {
// 归位然后遍历一遍
int n = nums.length;
for(int i=0;i<n;i++) {
if(i+1==nums[i]) continue;
int tmp;
int nextIdx = nums[i]-1;
if(nextIdx>=n||nextIdx<0) continue;
while(nums[nextIdx]!=nextIdx+1) {
tmp = nums[nextIdx]-1;
nums[nextIdx] = nextIdx+1;
if(tmp>=n||tmp<0) break;
nextIdx = tmp;
}
}
for(int i=0;i<n;i++) {
if(nums[i]!=i+1) return i+1;
}
return n+1;
}
}