LeetCode 27移除元素&28实现strStr()&29两数相除
维护幸苦，如有打卡欢迎关注公众号
bigsai回复进群，如有帮助欢迎点赞支持！
移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
说明:
为什么返回数值是整数，但输出的答案是数组呢?
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:
// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);
// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}
分析：
用一个index标记当前真正的位置，在遍历的过程中如果当前位置数值和目标数值不相等那么就赋值，如果和待删除数据相等那么跳过不赋值。这就是遍历一次重新赋值的过程。
ac代码为：
public int removeElement(int[] nums, int val) {
int index=0; for(int i=0;i<nums.length;i++)
{ if(nums[i]==val) continue; nums[index++]=nums[i];
}
return index;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
实现 strStr()
题目描述：
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例 1:
输入: haystack = “hello”, needle = “ll”
输出: 2
示例 2:
输入: haystack = “aaaaa”, needle = “bba”
输出: -1
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符
分析
由于数据量的问题，本题使用KMP算法效率并不是很好(KMP需要预处理)，相反使用普通方法效率就很高.使用sunday算法效果也比较普通，就很神奇。
普通的匹配又称双指针啥的其实就是一个暴力匹配，但是同为暴力匹配官方给的方法速度要快很多，个人写法为：
public int strStr(String haystack, String needle) { if(needle==null||"".equals(needle)) return 0; char a[]=haystack.toCharArray(); char b[]=needle.toCharArray(); for(int i=0;i<a.length-b.length+1;i++) { int j=-1; while(j++<b.length) { if(a[i+j]!=b[j]) { break; } if(j==b.length-1) return i; } } return -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
官方给的简洁写法：
public int strStr(String haystack, String needle) { int L = needle.length(), n = haystack.length(); for (int start = 0; start < n - L + 1; ++start) { if (haystack.substring(start, start + L).equals(needle)) { return start; } } return -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
kmp方法笔者也实现了，但是由于数据问题效果一般般，当然kmp算法这里就不作详细介绍：
public int[] getNext(String needle) { char[] p = needle.toCharArray(); int[] next = new int[p.length]; next[0] = -1; int j = 0; int k = -1; while (j < p.length - 1) { if (k == -1 || p[j] == p[k]) { next[++j] = ++k; } else { k = next[k]; } } return next;
} public int KMP(String haystack, String needle) { char[] t = haystack.toCharArray(); char[] p = needle.toCharArray(); int i = 0; // 主串的位置 int j = 0; // 模式串的位置 int[] next = getNext(needle); while (i < t.length && j < p.length) { if (j == -1 || t[i] == p[j]) { // 当j为-1时，要移动的是i，当然j也要归0 i++; j++; } else { // i不需要回溯了 // i = i - j + 1; j = next[j]; // j回到指定位置 } if(j==p.length) {return i-j;} } return -1;
} public int strStr(String haystack, String needle) { if(needle==null||"".equals(needle)) return 0; return KMP(haystack, needle);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
同样使用sunday算法 (后面会专门讲解)效果也是一般般
public int strStr(String haystack, String needle) { if(needle==null||"".equals(needle)) return 0; int lastchar[]=new int [200]; char a[]=haystack.toCharArray(); char p[]=needle.toCharArray(); for(int i=0;i<p.length;i++) { lastchar[p[i]]=i+1; } int i=0; int j=0; int len=a.length-p.length+1; while (i<a.length) { int index=i-(lastchar[a[i]]-1);//a[i] 字符 if(lastchar[a[i]]!=0&&index>=0&&index<len)//可以匹配 { while (j<p.length) {//尝试匹配 if(p[j]!=a[index+j]) break; j++; } if(j==p.length) { return index; } else { i=index+p.length; j=0; } } else { i++; }
} return -1;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
两数相除
题目描述
给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
返回被除数 dividend 除以除数 divisor 得到的商。
整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333…) = truncate(3) = 3
示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333…) = -2
提示：
被除数和除数均为 32 位有符号整数。
除数不为 0。
假设我们的环境只能存储 32 位有符号整数，其数值范围是[−2^31, 2^31 − 1]。本题中，如果除法结果溢出，则返回2^31 − 1。
分析
需要计算除法的数值是多少，并且还遇到以下问题：
- 数值可能越界
- 不能使用乘除法
数值越界问题可以特殊情况考虑即可。但是不能使用乘除法怎么去知道除法的结果是多少呢？
法一：加法累加
这可能是最笨的方法了，除以几，就用这个数去叠加找到结果。
当然这样如果数字很大，除数为1，2这种的会很慢，只能勉强ac。
public static int divide(int dividend, int divisor) {
int zhengfu=1;
long divd=dividend,divs=divisor;
if(dividend>0&&divisor<0)
{ divs=-divisor;zhengfu=-1;
}
else if(dividend<0&&divisor>0)
{ divd=-divd;zhengfu=-1;
}
else if (dividend<0&&divisor<0) { divd=-divd;divs=-divs;
} if(Math.abs(divd)<Math.abs(divs))return 0;
long i=0,index=0;
if(divs==1)i=divd+1;
else
while (index<=divd) { i++;index+=divs;
}
long va=(zhengfu==1?(i-1):(1-i));
if(va>Integer.MAX_VALUE)return Integer.MAX_VALUE;
if(va<Integer.MIN_VALUE)return Integer.MIN_VALUE;
return (int) va; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
用什么方法可以优化算法呢？这就涉及到二进制的问题了。在二进制中：
- 2=0010 表示有2个1
- 4=0100表示有4个1
- 6=0110表示有4+2个1
同样任何一个数都可以用二进制来表示，1101表示8+4+1.同理我们将这种思想带到本题进行计算，只不过基础单位不为1而已：
因为我们使用加法实现数值乘以二的效果，所以利用这个每次找到范围内的最大个数(数值叠加同时需要其他变量统计次数)。然后处理完这部分数据继续操作剩下的数值直到停止。当然具体实现上可以考虑剪枝(除数为±1的时候，同时要妥善解决正负数和越界问题，这里就用long处理，全部转成正数然后用一个标记正负)。
实现代码为：
public static int divide(int dividend, int divisor)
{
if(divisor==1)return dividend;
if(divisor==-1)return dividend==Integer.MIN_VALUE?Integer.MAX_VALUE:-dividend; long value=0;//记录总次数结果
int time=1;//临时每次的次数
long divd=dividend,divs=divisor;//转成long处理 int zhengfu=1;//判断是正数还是负数
if(divd<0)
{ divd=-divd;zhengfu=-zhengfu;
} if(divs<0) { divs=-divs;zhengfu=-zhengfu; } long team=divs;//临时数据2倍叠加
while (team<=divd) { if(team+team>divd) { value+=time; divd-=team; team=divs; time=1; continue; } team+=team; time+=time; }
return (int) (zhengfu==1?value:-value);
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
结语
好吧，本次打卡结束，欢迎点赞支持，如果打卡欢迎关注公众号bigsai回复进群即可加入打卡。
文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。
原文链接：bigsai.blog.csdn.net/article/details/108680259
- 点赞
- 收藏
- 关注作者
评论（0）