- 前言
- 1. BM87 合并两个有序的数组
- 2.BM88 判断是否为回文字符串
- 3.BM91 反转字符串
- 4.BM92 最长无重复子数组
- 5.BM93 盛水最多的容器描述
- 总结
今天学习牛客网的二分查找算法，还是那句话：不断刷类似的题目，让我们能够更快的掌握这种方法。
1. BM87 合并两个有序的数组描述
给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组
注意：
1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印
3. A 数组在[0,m-1]的范围也是有序的
示例1：
输入： [4,5,6],[1,2,3] 返回值： [1,2,3,4,5,6]`说明： A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组
示例2：
输入： [1,2,3],[2,5,6] 返回值： [1,2,2,3,5,6]
我的答案：
import java.util.*;
public class Solution {
public void merge(int A[], int m, int B[], int n) {
//指向A,B两个数组的末尾
int i = m - 1;
int j = n - 1;
//指向合并后A数组的末尾
int k = m + n - 1;
//进行遍历
//将较大的元素放在最后
while(i >=0 && j>= 0){
if(A[i] > B[j]){
A[k--] = A[i--];
}
else{
A[k--] = B[j--];
}
}
//因为考虑到B数组合并到A数组里面，所以有可能B数组还有剩余
if(i < 0){
while(j >= 0){
A[k--] = B[j--];
}
}
}
}
2.BM88 判断是否为回文字符串
描述
给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。
字符串回文指该字符串正序与其逆序逐字符一致。
数据范围：0 < n le 10000000
示例1
输入： "absba" 返回值： true
示例2
输入： "ranko" 返回值： false
示例3
输入： "yamatomaya" 返回值： false
我的答案：
import java.util.*;
public class Solution {
public boolean judge (String str) {
//定义两个指针，指向一前一后
int left = 0;
int right = str.length() - 1;
while(left <= right){
//比较开头和末尾的字母是否一样
if (str.charAt(left++) != str.charAt(right--)){
return false;
}
}
return true;
}
}
3.BM91 反转字符串
描述
写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）
数据范围： 0 le n le 10000≤n≤1000
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)
示例1
输入： "abcd" 返回值： "dcba"
示例2
输入： "" 返回值： ""
我的答案：
import java.util.*;
public class Solution {
public String solve (String str) {
StringBuffer sb = new StringBuffer(str);
return sb.reverse().toString();
}
}
4.BM92 最长无重复子数组
描述
给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。
子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组
示例1：
输入： [2,3,4,5] 返回值： 4 说明： [2,3,4,5]是最长子数组
示例2：
输入： [2,2,3,4,3] 返回值： 3 说明： [2,3,4]是最长子数组
示例3：
输入： [9] 返回值： 1
我的答案：
import java.util.*;
public class Solution {
public int maxLength (int[] arr) {
//判断特殊情况
if(arr.length == 0){
return 0;
}
//可以用map中containskey方法来判断有无重复，所以要先创建map
//key代表值，value代表的是下标
HashMap map = new HashMap<>();
int j = 0;
int max = 0;
//遍历数组
for (int i = 0; i < arr.length; i++){
if(map.containsKey(arr[i])){
//如果有重复数字，更新起始的下标
j = Math.max(j, map.get(arr[i]) + 1);
}
//比较是这两次的无重复子数组谁比较长
max = Math.max(max, i - j + 1);
}
return max;
}
}
5.BM93 盛水最多的容器描述
给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水
1.你不能倾斜容器
2.当n小于2时，视为不能形成容器，请返回0
3.数据保证能容纳最多的水不会超过整形范围，即不会超过231-1
如输入的height为[1,7,3,2,4,5,8,2,7]，那么如下图:
示例1
输入： [1,7,3,2,4,5,8,2,7] 返回值： 49
示例2
输入： [2,2] 返回值： 2
示例3
输入： [5,4,3,2,1,5] 返回值： 25
我的答案:
import java.util.*;
public class Solution {
public int maxArea (int[] height) {
//定义左右两个指针，一个放头部，一个放尾部
int i = 0;
int j = height.length - 1;
//定义容器容量最大值
int max = 0;
//排除特殊情况
if(height.length < 2){
return 0;
}
//遍历
while (i < j){
//取出i和j位置上的较小值，来计算容器容量
int min = Math.min(height[i] , height[j]);
max = Math.max(max, min*(j - i));
if(height[i] > height[j]){
j--;
}
else{
i++;
}
}
return max;
}
}
总结
双指针的使用其实还是要根据情况来看，一般用于判断填充的是快慢指针，用来元素比较的是前后指针。一般用在数组上。
