数据结构与算法系列一之整数、数组及字符串
前言：由于本人不是科班出身，计算机基础相对薄弱一些，最近在工作之余想系统的学习一下数据结构与算法，主要是通过学习专项突破版的剑指Offer每一部分的典型题目，将每一部分相关的基础内容尽量掌握一下。由于没有太多时间将看过的基础内容都总结整理起来，因此先将题目根据书中的讲解和自己的理解整理一下，后续有时间再系统整理一下每一部分的基础知识。
第一章 整数
1、整数除法
题目：输入 2 个 int 型整数，他们进行除法计算并返回商，要求不得使用乘号’*’、除号’/’及求余符号’%’。当发生溢出时，返回最大的整数值。假设除数不为0。例如，输入 15 和 2 ，输出 15/2 的结果，即 7 。
import java.util.Scanner;
public class test0101 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = Integer.parseInt(sc.next());
int b = Integer.parseInt(sc.next());
if (a==0x80000000 && b==-1){
System.out.println(Integer.MAX_VALUE);
}else {
//由于正数int最大为2^31-1，负数int最小为2^31，所以将除数与被除数都转换成负数来进行计算，防止越界
//0x80000000是-2^31,0xc0000000是-2^30
int flag = 2; //使用flag来控制结果的正负符号
if (a>0){
flag--;
a=-a;
}
if (b>0){
flag--;
b=-b;
}
int result = divide(a, b);
result = flag == 1 ? -result : result; //当除数与被除数符号不同时结果为负
System.out.println(result);
}
}
//设置初始值 res=0,countNum=1,value=b,
private static int divide(int a,int b){
int res = 0; //结果初始值为0
while (a>=b){ //当被除数>除数时进入循环
int countNum = 1; //设置倍数初始值为1
int value = b; //将除数的值赋给value，用于后续处理
while (value>=0xc0000000 && a <= value+value){ //当被除数<除数的两倍时进入循环(负数)，防止2倍value越界，需要保证value>=0xc0000000
countNum+=countNum; //倍数通过相加翻倍
value+=value; //value也通过相加翻倍
}
a-=value; //当被除数>value的两倍时，被除数a-value，再进行循环
res+=countNum; //结果加上被除数减去的value的倍数countNum
}
return res;
}
}
2、二进制加法
题目：输入两个表示二进制的字符串，请计算它们的和，并以二进制字符串的形式输出。例如，输入的二进制字符串分别是”11″和”10″，则输出”101″。
import java.util.Scanner;
public class test0201 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str1 = sc.next();
String str2 = sc.next();
String s = add(str1, str2);
System.out.println(s);
}
private static String add(String str1,String str2){
StringBuilder res = new StringBuilder(); //实例化一个StringBuilder()类
int l1 = str1.length()-1; //获取输入的字符串长度，用于后续获取字符，由于字符序号是0~length-1，因此获取值为字符串长度length-1
int l2 = str2.length()-1;
int num01 = 0;
int num02 = 0;
int sum = 0;
int forward = 0;
while (l1>=0 || l2>=0){ //当两个字符串中有一个还有剩余未计算的数字时，进入循环
num01 = l1>=0?str1.charAt(l1--)-'0':0; //当字符串长度大于0时，获取当前进行计算的数值，然后将字符串长度-1；字符串长度等于0时，数值设为0
num02 = l2>=0?str2.charAt(l2--)-'0':0;
sum = num01 + num02 +forward; //计算当前位的数值及进位的数值之和
forward = sum>=2 ? 1:0; //当和大于等于2时，进位为1，否则进位为0
sum = sum>=2?sum-2:sum; //当和大于等于2时，由于已经进位，因此和-2作为当前位的数值
res.append(sum); //结果添加当前位的数值
}
if (forward==1){ //如果两个字符串所有位的数值都计算完了，那么判断进位是否还有数值1，有则在结果中添加1
res.append(1);
}
return res.reverse().toString(); //由于append是在字符串最后添加当前位数值，因此结果要进行反转才是最终结果字符串
}
}
3、前 n 个数字二进制形式中 1 的个数
题目：输入一个非负数 n ，请计算 0 到 n 之间每个数字的二进制形式中 1 的个数，并输出一个数组。例如，输入的 n 为 4，由于0、1、2、3、4 的二进制形式中 1 的个数分别为 0、1、1、2、1，因此输出数组[0,1,1,2,1]。
解法一：
import java.util.Scanner;
public class test0301 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //获取输入的数值
int in = sc.nextInt();
int[] result = count(in);
sc.close(); //输入完后不要忘了关闭Scanner降低系统资源占用
for (int i : result) { //遍历结果输出，以空格为间隔
System.out.print(i+" ");
}
}
private static int[] count(int in){
int[] res = new int[in + 1];
for (int i = 0; i <= in; i++) { //遍历0到该数值，将每次遍历到的数值转换为二进制字符串
String s = Integer.toBinaryString(i);
int contain = 0;
for (int j = 0; j < s.length(); j++) { //遍历字符串每个字符，有1则结果数组中该位置结果+1
if (s.charAt(j)=='1'){
contain++;
}
}
res[i] = contain;
}
return res;
}
}
解法二：
import java.util.Scanner;
public class test0302 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int in = sc.nextInt();
int[] result = add(in);
sc.close();
for (int i : result) {
System.out.print(i+" ");
}
}
private static int[] add(int in){
int[] res = new int[in + 1]; //初始化一个结果数组
for (int i = 0; i <= in; i++) { //遍历需要计算1个数的每一个数值
int j = i;
while (j != 0){ //当前数值不为0，则一定存在1，当前数值的结果+1
res[i]++;
j=j&(j-1); //将当前数值的最后一个1去掉，通过j&(j-1)
}
}
return res;
}
}
解法三：
import java.util.Scanner;
public class test0303 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int in = sc.nextInt();
int[] result = add(in);
sc.close();
for (int i : result) {
System.out.print(i+" ");
}
}
private static int[] add(int in){
int[] res = new int[in + 1];
for (int i = 1; i < in; i++) {
res[i] = res[i&(i-1)]+1;
}
return res;
}
}
解法四：
import java.util.Scanner;
public class test0304 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //获取输入的数值，输入完毕不要忘了关闭Scanner
int in = sc.nextInt();
int[] result = add(in);
sc.close();
for (int i : result) {
System.out.print(i+" ");
}
}
private static int[] add(int in){
int[] res = new int[in + 1]; //新建一个结果数组
for (int i = 0; i <= in; i++) { //从小到大遍历0到目标数值
//当前数值为偶数时，最后一位为0，数值中1的个数与当前数值右移一位中1的个数相等；
//当前数值为奇数时，最后一位为1，数值中1的个数=当前数值右移一位中1的个数+1；
//可以通过按位与运算 i&1 来实现奇数+1，偶数+0
res[i] = res[i>>1] + (i&1); //当前数值中1的个数，是当前数值右移1位的数值的1的个数+当前数值&1
}
return res;
}
}
4、只出现一次的数字
题目：输入一个整数数组，数组中只有一个数字出现了一次，而其他数字都出现了 3 次。请找出那个只出现一次的数字。例如，如果输入的数组为[0,1,0,1,0,1,100]，则只出现一次的数字是 100。
解法一：
import java.util.ArrayList;
import java.util.Scanner;
public class test0401 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //获取用户输入的数组
ArrayList<String> in = new ArrayList<>(); //新建数组，保存用户的输入数值
int i;
int max = 0;
String str;
while (sc.hasNextInt()){ //循环接收输入的数值
i = sc.nextInt();
str = Integer.toBinaryString(i); //把输入的整数转换为二进制字符串进行后续处理
if (str.length()>max){ //获取字符串最大长度，以便后续初始化中间数组
max=str.length();
}
in.add(str); //向数组中添加字符串
}
sc.close();
int result = query(in, max);
System.out.println(result);
}
private static int query(ArrayList<String> list,int max){
int res = 0;
StringBuilder stringBuilder = new StringBuilder(); //初始化一个可变长字符串用于后续获取结果
int[] contains = new int[max]; //新建一个数组用来保存所有输入数值每一位相加的结果
for (String s : list) { //循环遍历所有二进制字符串的每一位，并将所有字符串相同位的数值相加
for (int i = 0; i < s.length(); i++) {
contains[i] = contains[i] + (s.charAt(i)-'0');
}
}
//由于只有一个数值出现一次，其他数值都出现三次，因此所有位数值之和与3求余，为1时只出现一次的数值该位为1，为0时只出现一次的数值该位为0
for (int i = 0; i < contains.length; i++) { //遍历保存所有位数值之和的数组，每位的和%3，将所有结果进行拼接
stringBuilder.append(contains[i] % 3);
}
res = Integer.parseInt(stringBuilder.toString(),2); //将所有位与3求余拼接后的结果转换为整数
return res;
}
}
解法二：
import java.util.ArrayList;
import java.util.Scanner;
public class test0402 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //接收输入的数组
ArrayList<Integer> list = new ArrayList<>();
int i;
while (sc.hasNextInt()){ //循环接收输入的数字
i = sc.nextInt();
list.add(i);
}
System.out.println(query(list));
sc.close();
}
private static int query(ArrayList<Integer> list){
int[] contains = new int[32]; //因为整数就是32位的，所以新建一个容量32的数组，保存输入数字每一位和的结果
int res = 0;
for (Integer integer : list) { //遍历输入数组的每一个数值
for (int i = 0; i < 32; i++) { //遍历每一个数值的每一个二进制位
//通过 (integer>>(31-i))&1 来获取第i位的数值0或1，注意i为0-31，数值位数为1-32，是从左往右的顺序
contains[i] += (integer>>(31-i))&1; //i=0时，就是第一位，一定要保证运算的顺序
}
}
for (int i = 0; i < 32; i++) { //遍历保存每一位和的数组
//当前结果左移一位，使当前位数字为0，再通过 contains[i]%3 来获得当前位的数值，通过相加，把该数值放到结果res的当前位
res = (res << 1) + (contains[i] % 3);
}
return res;
}
}
5、单词长度的最大乘积
题目：输入一个字符串数组 words，请计算不包含相同字符的两个字符串 words[i] 和 words[j] 的长度乘积的最大值。如果所有字符串都包含至少一个相同字符，那么返回 0。假设字符串中只包含英文小写字母。例如，输入的字符串数组 words 为[“abcw”,”foo”,”bar”,”fxyz”,”abcdef”]，数组中的字符串”bar”与”foo”没有相同的字符，它们长度的乘积为 9。”abcw”与”fxyz”也没有相同的字符，它们长度的乘积为 16，这是该数组不包含相同字符的一对字符串的长度乘积的最大值。
解法一：
import java.util.ArrayList;
import java.util.Scanner;
public class test0501 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<String> list = new ArrayList<>();
while (sc.hasNextLine()){ //逐行循环输入字符串，连续回车两次结束输入
String s = sc.nextLine();
if (s.equals(""))break; //控制输入结束
list.add(s);
}
list.forEach(System.out::println);
// ArrayList<String> strings = new ArrayList<>();
// strings.add("abcw");
// strings.add("foo");
// strings.add("bar");
// strings.add("fxyz");
// strings.add("abcdef");
//
// int res = multiply(strings);
// System.out.println(res);
}
private static int multiply(ArrayList<String> list){
int max = 0;
//由于字符中只会出现26个小写字母，因此新建字符串个数个26空间大小的数组
Boolean[][] booleans = new Boolean[list.size()][26];
//位运算包括：与& 或| 异或^(相当于两个字符串或运算减去与运算) 取反~
for (int i = 0; i < booleans.length; i++) { //一定要给Boolean数组进行赋值，否则会报空指针异常
for (int j = 0; j < 26; j++) {
booleans[i][j] = false;
}
}
for (int i = 0; i < list.size(); i++) { //遍历每个字符串中的每个字符，按字符位于字母表中的位置，将Boolean数组中对应位置设为true
for (char c : list.get(i).toCharArray()) {
int num = c-'a'; //通过字符c-'a'来获取当前字符在字母表中的位置
booleans[i][num] = true;
}
}
for (int i = 0; i < list.size()-1; i++) { //遍历保存每个字符串中字母的数组
for (int j = i+1; j < list.size(); j++) {
int k = 0;
for (; k < 26; k++) {
if (booleans[i][k] && booleans[j][k]){ //如果两个字符串字母数组中有同为true的字母，则中止此次循环
break;
}
}
if (k==26){ //如果遍历两个字符串字母数组都没有同为true的字母，则计算字符串长度乘积，保存乘积的最大值
max = Math.max(max,list.get(i).length()*list.get(j).length());
}
}
}
return max;
}
}
解法二：
public class test0502 {
public static void main(String[] args) {
String[] str = {"abcw","foo","bar","fxyz","abcdef"};
int result = multiply(str);
System.out.println(result);
}
private static int multiply(String[] str){
int res = 0;
//由于int类型数字有32位，字母只有26个，所以可以用int类型的二进制数字来保存字符串中包含的字母信息
//后续通过按位与运算&，比较不同字符串是否有重复字符，如果有则结果不为0，没有则结果为0
int[] ints = new int[str.length]; //新建一个字符串数组长度的int数组，其中每个元素初始值都为0
for (int i = 0; i < str.length; i++) { //遍历每个字符串的每个字符
for (char c : str[i].toCharArray()) {
//通过1左移c-'a'位来使字符c对应位置的数值变为1，通过与该字符串对应的二进制数字 取或|，来使该字符串对应二进制数字中的所有字符对应的位置为1
ints[i] |= 1<<(c-'a');
}
}
for (int i = 0; i < ints.length; i++) { //遍历比较不同字符串对应的数值
for (int j = i+1; j < ints.length; j++) {
if ((ints[i] & ints[j])==0){ //如果两个字符串对应的数值按位与运算结果为0，则这两个字符串不包含相同字符
res = Math.max(res,str[i].length()*str[j].length()); //计算这两个字符串长度的乘积，保存乘积的最大值
}
}
}
return res;
}
}
第二章 数组
6、排序数组中的两个数字之和
题目：输入一个递增排序的数组和一个值 k，请问如何在数组中找出两个和为 k 的数字并返回他们的下标？假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。例如，输入数组[1,2,4,6,10]，k的值为 8，数组中的数字 2 与 6 的和为 8，它们的下标分别为 1 与 3。
解法一：
public class test0101 {
public static void main(String[] args) {
int[] in = {1,2,4,6,10};
int k = 8;
int[] result = binarySearch(in, k);
for (int i : result) {
System.out.println(i);
}
}
private static int[] binarySearch(int[] in,int k){
int[] res = new int[2];
int target = 0;
for (int i : in) {
target = k-i;
//int j = select01(in, 0, in.length - 1, target);
int j = select02(in, target);
if (j != 0 ){
res[0] = i;
res[1] = j;
break;
}
}
return res;
}
private static int select01(int[] input, int start, int end, int target){ //递归方式二分查找
int mid = (start + end)/2;
if (start<=end){
if (target == input[mid]){
return target;
}else if (target>input[mid]){
return select01(input, mid+1, end, target); //下一层函数的输入值起始点，一定要为mid加1或减1，否则栈溢出
}else if (target<input[mid]){
return select01(input, start, mid-1, target);
}
}
return 0;
}
private static int select02(int[] input,int target){
int n = input.length;
int low = 0;
int high = n-1;
while (low<=high){
int mid = low + ((high-low)>>1);
if (input[mid] == target){
return input[mid];
}else if (input[mid] > target){
high = mid-1;
}else {
low = mid+1;
}
}
return 0;
}
}
解法二：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Scanner;
public class test0102 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
HashMap<Integer, String> map = new HashMap<>();
while (sc.hasNextLine()){
String s = sc.nextLine();
if (s.equals(""))break;
int i = Integer.parseInt(s);
list.add(i);
}
Integer k = list.get(list.size()-1);
list.remove(list.size()-1);
for (Integer i : list) {
map.put(i,"");
}
int[] result = hashQuery(map, k);
for (int i : result) {
System.out.println(i);
}
}
private static int[] hashQuery(HashMap<Integer,String> map,int k){
int[] res = new int[2];
String s = map.get(map.size() - 1);
for (Integer i : map.keySet()) {
if (map.containsKey(k-i)){
res[0] = i;
res[1] = k-i;
break;
}
}
return res;
}
}
解法三：
import java.util.ArrayList;
import java.util.Scanner;
public class test0103 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
while (sc.hasNextLine()){
String s = sc.nextLine();
if (s.equals(""))break;
int i = Integer.parseInt(s);
list.add(i);
}
Integer k = list.get(list.size()-1);
list.remove(list.size()-1);
int[] result = pointerQuery(list, k);
for (int i : result) {
System.out.println(i);
}
}
private static int[] pointerQuery(ArrayList<Integer> list, int k){
int[] res = new int[2];
int p1 = 0;
int p2 = list.size()-1;
while (p1<p2){
if (list.get(p1)+list.get(p2) == k){
res[0] = list.get(p1);
res[1] = list.get(p2);
break;
}else if (list.get(p1)+list.get(p2) > k){
p2--;
}else if (list.get(p1)+list.get(p2) < k){
p1++;
}
}
return res;
}
}
7、数组中和为 0 的 3 个数字
题目：输入一个数组，如何找出数组中所有和为 0 的 3 个数字的三元组？需要注意的是，返回值中不得包含重复的三元组。例如，在数组[-1,0,1,2,-1,-4]中有两个三元组的和为 0，它们分别是[-1,0,1]和[-1,-1,2]。
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
public class test0201 {
public static void main(String[] args) {
int[] input = {-1,0,1,2,-1,-4};
int target = 0;
List<List<Integer>> lists = threeSum(input, target);
lists.forEach(System.out::println);
}
private static List<List<Integer>> threeSum(int[] list,int target){
List<List<Integer>> result = new LinkedList<>();
Arrays.sort(list); //先对数组进行排序，方便后续查找
//先遍历数组，指定当前的值为第一个值，再查找另外两个值，使三个数之和为目标值
for (int i = 0; i < list.length-2; ) {
int goal = target - list[i]; //计算需要查找的其他两个值的和
List<List<Integer>> res = twoSum(list, goal, i+1); //传入twoSum函数，数组、目标值、查找的起始下标
res.forEach(System.out::println);
if (!res.isEmpty()){ //当其他两个值查找的结果集不为空时，遍历结果集，每一个结果都与当前遍历的第一个数字组成一个最终结果数组
for (int j = 0; j < res.size(); j++) {
result.add(res.get(j));
}
}
int temp = list[i];
while (list[i]==temp && i<list.length-2){ //保证下一个便遍历的值一定跟当前的值不同，并且一定至少会执行一次
i++;
}
}
return result;
}
//可以将最终结果数组传入twoSum函数中，每次查找到符合要求的三个值直接放入最终的结果数组，这样twoSum就不需要返回值
private static List<List<Integer>> twoSum(int[] list,int goal,int i){ //一个数字确定后，查找另外两个数字
List<List<Integer>> res = new LinkedList<>();
int m = i-1;
int j = list.length-1;
while (i<j){ //从确定的那一个数字后面的子数组中查找，从子数组的第一位和最后一位开始查找
if (list[i] + list[j] == goal){ //当两个数字之和是目标值时，将这两个数字构建成数组，放到结果集中
res.add(Arrays.asList(list[m],list[i],list[j]));
int temp = list[i]; //为了去重，跳过与当前下标小的数字相同的数字，需保证小的下标小于大的坐标
while (list[i]==temp && i<j){
i++;
}
}else if (list[i] + list[j] > goal) { //当两个数值大于目标值，大的下标减1
j--;
}else if (list[i] + list[j] < goal){ //当两个数值小于目标值，小的下标加1
i++;
}
}
return res;
}
}
8、和大于或等于 k的最短子数组
题目：输入一个正整数组成的数组和一个正整数 k，请问数组中和大于或等于 k 的连续子数组的最短长度是多少？如果不存在所有数字之和大于或等于 k 的子数组，则返回 0。例如，输入数组[5,1,4,3]，k 的值为 7，和大于或等于 7 的最短连续子数组是[4,3]，因此输出它的长度 2。
public class test0301 {
public static void main(String[] args) {
int[] in = {5,1,4,3};
int k = 7;
int res = queryCount(in, k);
System.out.println(res);
}
private static int queryCount(int[] in,int k){
int minCount = Integer.MAX_VALUE;
int sum = 0;
int left = 0;
for (int right = 0; right < in.length; right++) {
sum += in[right];
while (sum>=k && left<=right){ //当sum>=k时，满足要求，计算当前子字符串长度并取最小值，同时需要满足左指针小于等于右指针
minCount=Math.min(minCount,right-left+1); //判断时只考虑当前左右指针中间的子数组，不要考虑左指针右移一位后的结果
//当左指针超过右指针一位时，不会再进入循环计算子数组最小长度
sum -= in[left++]; //每次先将sum和减去当前左指针指向的值，再将左指针右移一位
}
}
return minCount==Integer.MAX_VALUE ? 0:minCount;
}
}
9、乘积小于 k的子数组
题目：输入一个由正整数组成的数组和一个正整数 k，请问数组中有多少个数字乘积小于 k 的连续子数组？例如，输入数组[10,5,2,6]，k 的值为100，有 8 个子数组的所有数字的乘积小于 100，它们分别是[10]、[][][][][][][5]、[2]、[6]、[10,5]、[5,2]、[2,6]和[5,2,6]。
public class test0401 {
public static void main(String[] args) {
int[] in = {10,5,2,6};
int k = 100;
int res = queryMultiply(in, k);
System.out.println(res);
}
private static int queryMultiply(int[] in,int k){
int product = 1; //保存当前子数组乘积结果
int left = 0; //左指针
int count = 0; //记录目前有多少子数组符合要求
for (int right = 0; right < in.length; right++) { //循环遍历输入的数组，当前下标为右指针
product *= in[right]; //计算到当前右指针的子数组的乘积
while (product>=k && left<=right){ //当子数组乘积大于等于k值同时左指针小于等于右指针时，当前子数组乘积除以左指针指向的数值，左指针右移一位
product /= in[left++]; //当前右指针指向的数值大于k时，左右指针都指向该数值，之后product=1，左指针会比右指针+1，跳出循环
}
//计算符合条件连续子数组数量时，只有以当前右指针指向数值为起始值的子数组是不重复的子数组，其余包含的子数组都在之前计算中包含
//因此，计算当前子数组中满足条件的所有与之前不重复数组，只需计算右指针-左指针+1
count += left<=right ? right-left+1:0; //当左指针大于右指针，说明当前右指针指向的数值大于k，此时count数值不变
}
return count;
}
}
10、和为 k的子数组
题目：输入一个整数数组和一个整数 k，请问数组中有多少个数字之和等于 k 的连续子数组？例如，输入数组[1,1,1]，k 的值为 2，有 2 个连续子数组之和等于 2。
import java.util.HashMap;
public class test0501 {
public static void main(String[] args) {
int[] in = {1,1,1};
int k = 2;
int res = queryMultiply(in, k);
System.out.println(res);
}
//计算从第一个数到当前下标位置累加和，从当前下标位置开始累加和为k，那么从数组第一个数到找到的目标位置累加和为sum-k
//计算从第一个数开始到当前下标位置的累加和，key为累加和结果，value为+1，放到哈希表中
//要特殊考虑以下k=sum和k=0的情况
private static int queryMultiply(int[] in,int k){
int sum = 0;
int count = 0;
HashMap<Integer, Integer> map = new HashMap<>();
//先给哈希表放入一个初始值(0,1)，因为当前下标sum=k时，则有一个满足条件的数组，而前面保存的数组累加和中没有这个结果（即使有sum=0，也会少计数一次）
map.put(0,1);
for (int i = 0; i < in.length; i++) { //遍历数组
sum += in[i]; //计算当前下标的累加和
count += map.getOrDefault(sum-k,0); //获取哈希表中有没有记录sum-k的值，有的话则有对应value数量个满足条件的数组
//要查找完sum-k的值后，再把当前sum值放入哈希表中，因为如果先放入sum的值时，当k=0时，sum-k=sum，此时count+1，而数组中没有k=0的子数组
map.put(sum,map.getOrDefault(sum,0)+1); //把到当前下标累加和放入哈希表中
}
return count;
}
}
11、0 和 1 个数相同的子数组
题目：输入一个只包含 0 和 1 的数组，请问如何求 0 和 1 的个数相同的最长连续子数组的长度？例如，在数组[0,1,0]中有两个子数组包含相同个数的 0 和 1，分别是[0,1]和[1,0]，它们的长度都是 2，因此输出 2。
import java.util.HashMap;
public class test0601 {
public static void main(String[] args) {
int[] in = {0,1,0};
int res = queryMaxlength(in);
System.out.println(res);
}
private static int queryMaxlength(int[] in){
int max = 0;
int sum = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < in.length; i++) {
in[i] = in[i]==0 ? -1:1; //简单的判断使用三元运算符使代码更易读
//当数组中0和1数量相等时，子数组为从0下标到当前下标的所有数组，当哈希表中没有key为0时，则不能计算这个子数组的长度，因此要先放入(0,1)
map.put(0,-1);
sum+=in[i]; //计算到当前下标的数组数字累加和
if (map.containsKey(sum)){ //如果哈希表中已经包含该累加和sum，那么从上一次放入累加和的位置后一位到现在的下标位置累加和为0
max=Math.max(max,i-map.get(sum));
}else {
//哈希表中只放入某个sum值第一次出现的位置，以计算0与1相同的最长子数组
map.put(sum,i);
}
}
return max;
}
}
12、左右两边子数组的和相等
题目：输入一个整数数组，如果一个数字左边的子数组的数字之和等于右边的子数组的数字之和，那么返回该数字的下标。如果存在多个这样的数字，则返回最左边一个数字的下标。如果不存在这样的数字，则返回 -1。例如，在数组[1,7,3,6,2,9]中，下标为 3 的数字（值为6）的左边 3 个数字 1、7、3 的和与右边两个数字 2 和 9 的和相等，都是 11，因此正确的输出值是 3。
public class test0701 {
public static void main(String[] args) {
int[] in = {1,7,3,6,2,9};
int res = queryEqual(in);
System.out.println(res);
}
private static int queryEqual(int[] in){
int total = 0;
int sum = 0;
int target = -1;
for (int i : in) { //计算数组综合，方便后续遍历计算右侧数组之和
total += i;
}
for (int i = 0; i < in.length; i++) { //遍历数组，计算数组中每个数值左侧数组之和及右侧数组之和
//先把in[i]放进sum也可以
//sum += in[i];
//if (i>=1 && sum-in[i] == total-sum){
// target = i;
//}
//空数组不是子数组，子数组是从一个数组中取出一些元素所构成的新的数组，而空数组没有元素，因此要保证下标i>=1才能保证in[i]左右两侧都有子数组
if (i>=1 && sum == total-in[i]-sum){ //右侧数组之和为数组综合-当前下标数值-到当前下标之前数字之和，判断右侧数组之和与左侧数组之和是否相等
target = i;
}
sum += in[i];
}
return target;
}
}
13、二维子矩阵的数字之和
题目：输入一个二维矩阵，如何计算给定左上角坐标和右下角坐标的子矩阵的数字之和？对于同一个二维矩阵，计算子矩阵的数字之和的函数可能由于输入不同的坐标而被反复调用多次。例如，输入下图中的二维矩阵，以及左上角坐标为(2,1)和右下角坐标为(4,3)的子矩阵，该函数输出 8。
说明：左上角坐标为(2,1)，右下角坐标为(4,3)的子矩阵（有灰色背景部分）的数字之和等于 8
import java.util.HashMap;
public class test0801 {
public static void main(String[] args) {
}
private static int matrixSum(int[][] in, HashMap<Integer,Integer> scale){
int[][] sums = new int[in.length+1][in[0].length+1]; //新建一个比输入数组长宽都大1的二维数组，保存从0点到输入矩阵每个点的子矩阵中所有数字之和
int addSum = 0;
int res = 0;
int left_x = -1,left_y = -1,right_x = -1,right_y = -1;
for (Integer x : scale.keySet()) { //遍历输入的两个点坐标哈希表，通过设置初始值-1来判断当前遍历的使左上角坐标还是右下角坐标
left_x = left_x == -1 ? x : left_x;
right_x = left_x == -1 ? right_x : x;
left_y = left_y == -1 ? scale.get(x) : left_y;
right_y = left_y == -1 ? right_y : scale.get(x);
}
for (int i = 0; i < in.length; i++) { //构建工具矩阵，保存0点到数组每个点的子矩阵的所有数字之和
addSum = 0;
for (int j = 0; j < in[0].length; j++) { //每个点矩阵之和可以看作横坐标-1的子矩阵+当前行起始点到该点的一维子数组之和
addSum += in[i][j];
sums[i+1][j+1] = sums[i][j+1] + addSum;
}
}
//目标子矩阵数字之和 = 0点到目标矩阵右下角的子矩阵 - 0点到目标矩阵左侧的子矩阵 - 0点到目标矩阵上侧的子矩阵 + 0点到目标矩阵左上方的子矩阵
res = sums[right_x][right_y] - sums[right_x][left_y-1] - sums[left_x-1][right_y] + sums[left_x-1][left_y-1];
return res;
}
}
第三章 字符串
14、字符串中的变位词
题目：输入字符串 s1 和 s2，如何判断字符串 s2 中是否包含字符串的某个变位词？如果字符串 s2 中包含字符串 s1 的某个变位词，则字符串 s1 至少有一个变位词是字符串 s2 的子字符串。假设两个字符串中只包含英文小写字母。例如，字符串 s1 为”ac”，字符串 s2 为”dgcaf”，由于字符串 s2 中包含字符串 s1 的变位词 “ca”，因此输出为 true。如果字符串 s1 为 “ab”，字符串 s2 为”dgcaf”，则输出为 false。
public class test0101 {
public static void main(String[] args) {
String str1 = "ac";
String str2 = "dgcaf";
System.out.println(anagram(str1,str2));
}
//判读字符串2是否包含字符串1的变位词
private static boolean anagram(String str1, String str2){
if (str1.length() > str2.length()){
return false;
}
int[] charSum = new int[26]; //数组每个位置的初始值为0
//循环遍历字符串str1，每出现一个字母就把数组中对应位置的值+1
//先把str1字符串的字母信息添加到charSum数组中，再将str2字符串中第一个子数组的字母信息减去，这里将两步合并到一起，简化代码
//把str2中第一个子字符串的字母信息减去后，后续只需要在str2字符串中循环移动第一个子字符串的最左侧和最右侧指针进行判断即可
for (int i = 0; i < str1.length(); i++) { //从字符串str2的0点开始，遍历与字符串相同长度的子字符串，每出现一个字母就把数组中对应位置的值-1
charSum[str1.charAt(i) - 'a']++;
charSum[str2.charAt(i) - 'a']--;
}
//判断数组中每个位置的值是否都为0，如果都为0，则表示str2字符串当前位置对应的与str1字符串长度相同的子字符串是str1的变位词
if (judgeZero(charSum)){
return true;
}
//当前放入数组的str2中的子字符串是从0到str1.length()-1，按位逐渐向字符串str2右移
//每右移一位则在数组中子字符串最左侧对应字母位置+1，最右侧+1对应字母位置-1
int left = 0; //初始化一个左指针left=0，右指针i初始值为str1.length()，右指针i的最大值为str2.length()-1，进行循环遍历
//str2字符串中向右循环遍历子字符串，只需在数组中将子字符串右移一位的右侧指针指向的字母信息减去，左侧指针指向的字母信息加上即可
for (int i = str1.length(); i < str2.length(); i++) {
charSum[str2.charAt(i) - 'a']--; //最右侧指针右移一位后，数组减去当前指针指向的字母信息
//也可以不初始化左指针left，直接用 i-str1.length() 代替，因为i是右侧指针的下一位，而要减去的是当前的左侧指针指向的字母
charSum[str2.charAt(left++) - 'a']++; //因为遍历子字符串时将最左侧字母信息在数组中减去了，所以，向右移动指针时，要把最左侧字母信息再加上
//str2中遍历的子字符串每右移一位，都要判断一次当前子字符串对应的数组值是否全为0，全为0则表示当前子字符串为str1字符串的变位词
if (judgeZero(charSum)){
return true;
}
}
return false;
}
//判断保存26个小写字母数组中有没有不为0
private static boolean judgeZero(int[] in){
for (int i : in) {
if (i != 0){
return false;
}
}
return true;
}
}
15、字符串中的所有变位词
题目：输入字符串 s1 和 s2，如何找出字符串 s2 的所有变位词在字符串 s1 中的起始下标？假设两个字符串中只包含英文小写字母。例如，字符串 s1 为”cbadabacg”，字符串 s2 为”abc”，字符串 s2 的两个变位词”cba”和”bac”是字符串 s1 中的子字符串，输出它们在字符串 s1 中的起始下标 0 和 5。
import java.util.LinkedList;
public class test0201 {
public static void main(String[] args) {
String s1 = "cbadabacg";
String s2 = "abc";
LinkedList<Integer> result = queryAnagram(s1, s2);
result.forEach(System.out::println);
}
//查找str2在str1中的变位词
private static LinkedList<Integer> queryAnagram(String str1,String str2){
LinkedList<Integer> res = new LinkedList<>();
if (str1.length() < str2.length()){
return res;
}
int[] charSum = new int[26];
for (int i = 0; i < str2.length(); i++) {
charSum[str2.charAt(i) - 'a']++; //str2中每出现一个字符就把charSum数组中对应位置+1
charSum[str1.charAt(i) - 'a']--; //str1中每出现一个字符就把charSum数组中对应位置-1
}
if (judgeZero(charSum)){
res.add(0);
}
for (int i = str2.length(); i < str1.length(); i++) {
charSum[str1.charAt(i) - 'a']--;
charSum[str1.charAt(i-str2.length()) - 'a']++;
if (judgeZero(charSum)){
res.add(i-str2.length()+1);
}
}
return res;
}
private static boolean judgeZero(int[] in){
for (int i : in) {
if (i != 0){
return false;
}
}
return true;
}
}
16、不含重复字符的最长子字符串
题目：输入一个字符串，求该字符串中不含重复字符的最长子字符串的长度。例如，输入字符串”babcca”，其最长的不含重复字符的子字符串是”abc”，长度为 3。
解法一：
public class test0301 {
public static void main(String[] args) {
String in = "babcca";
int res = queryLongest(in);
System.out.println(res);
}
private static int queryLongest(String in){
int[] countNum = new int[256]; //新建一个256大小的数组保存字符串中字符信息，因为没有说明字符全为小写字母，所以假设输入字符为ASCII码范围内
int max = 0;
//当前子字符串为左指针右一位到右指针指向的位置
int left = -1; //初始化左指针为-1，右指针为0
int right = 0;
for (;right<in.length();right++) { //右指针按位右移遍历字符串
countNum[in.charAt(right)]++; //当前右指针字符所在数组位置+1，遍历数组，如果有等于2的数值，则左指针右移一位，当前左指针指向的字符所在数组位置-1
while (queryZero(countNum)) {
left++;
countNum[in.charAt(left)]--;
}
max = Math.max(max, right - left); //获取已保存子字符串长度的最大值与当前子字符串长度中较大的数值
}
return max;
}
private static boolean queryZero(int[] countNum){ //遍历数组，判断是否有等于2的数值，有则当前子字符串中有重复字符
for (int i : countNum) {
if (i == 2){
return true;
}
}
return false;
}
}
解法二：
public class test0302 {
public static void main(String[] args) {
String in = "babcca";
int res = queryLongest(in);
System.out.println(res);
}
private static int queryLongest(String in){
int[] countNum = new int[256];
int max = 0;
int left = -1;
int right = 0;
//由于每次右指针右移时都会保证当前子字符串中没有重复字符，因此出现的重复字符只会是右指针右移一位后指向的字符
//只需要右移左指针保证当前右指针指向的字符在子字符串中无重复即可保证子字符串中无重复字符
for (;right<in.length();right++){
countNum[in.charAt(right)]++;
while (countNum[in.charAt(right)]==2){ //当前右指针指向的字符在数组中对应数值为2时，左指针按位右移使右指针指向的字符对应数组数值为1
left++;
countNum[in.charAt(left)]--;
}
max = Math.max(max,right-left);
}
return max;
}
}
17、包含所有字符的最短字符串
题目：输入两个字符串 s 和 t，请找出字符串 s 中包含字符串 t 的所有字符的最短子字符串。例如，输入的字符串 s 为”ADDBANCAD”，字符串 t 为”ABC”，则字符串 s 中包含字符’A’、’B’和’C’的最短子字符串是”BANC”。如果不存在符合条件的子字符串，则返回空字符串””。如果存在多个符合条件的子字符串，则返回任意一个。
import java.util.HashMap;
public class test0401 {
public static void main(String[] args) {
String s = "ADDBANCAD";
String t = "ABC";
String res = containsAll(s, t);
System.out.println(res);
}
private static String containsAll(String s,String t){
HashMap<Character, Integer> map = new HashMap<>(); //初始化一个hashmap保存字符串t中的字符信息
int count = 0; //初始化一个count记录字符串t中出现多少种字符
for (char c : t.toCharArray()) {
map.put(c,map.getOrDefault(c,0)+1);
if (map.get(c)==1){
count++;
}
}
//使用两个指针start和end控制字符串s中子字符串的起始终止位置，minStart和minEnd记录满足条件的最小长度子字符串的起始终止位置
int start = 0;
int end = 0;
int minStart = 0;
int minEnd = 0;
int minLength = Integer.MAX_VALUE;
//如果字符串s最后一个字符刚好是字符串t最后一个字符，那么进入循环后count=0，end=s.length()，此时start到end的子字符串满足要求
while (end < s.length() || (count==0 && end==s.length())){
//当count>0时，判断当前end指针指向的字符是否包含在map中，如果包含则value-1，如果value=0则count-1，end指针+1
//因为子字符串是start到end前一位，因此先判断当前end指针指向的字符，再将end指针+1
if (count>0){
char i = s.charAt(end);
if (map.containsKey(i)){
map.put(i,map.get(i)-1);
if (map.get(i)==0){
count--;
}
}
end++;
}else {
//当count=0时，当前子字符串满足条件，判断end-start长度是否为最小，保存最小长度子字符串的起始终止位置
minLength = Math.min(minLength,end-start);
minEnd = end;
minStart = start;
//判断map中是否包含当前start指针指向的字符，如果包含则value+1，如果value=1则count+1，start指针+1
char j = s.charAt(start);
if (map.containsKey(j)){
map.put(j,map.get(j)+1);
if (map.get(j)==1){
count++;
}
}
start++;
}
}
//substring方法截取字符串为起始下标start到终止下标end前一位的子字符串
System.out.println(minStart+"and"+minEnd);
return minLength == Integer.MAX_VALUE ? null:s.substring(minStart,minEnd);
}
}
18、有效的回文
题目：给定一个字符串，请判断它是不是回文。假设只需要考虑字母和数字字符，并忽略大小写。例如，”Was it a cat I saw?”是一个回文字符串，而”race a car”不是回文字符串。
public class test0501 {
public static void main(String[] args) {
String s1 = "Was it a cat I saw?";
String s2 = "race a car";
System.out.println(judgePalindrome(s1));
System.out.println(judgePalindrome(s2));
}
private static boolean judgePalindrome(String s){
int left = 0;
int right = s.length()-1;
while (left<right){ //当左右指针指向的字符不是字母或数字时，则跳过该字符
if (!Character.isLetterOrDigit(s.charAt(left))){
left++;
}else if (!Character.isLetterOrDigit(s.charAt(right))){
right--;
}else { //当两个指针指向的字符都是字母或数字时，将两个指针指向的字符全部转换为小写字符再判断是否相等，数字字符转换小写后还是本身
if (Character.toLowerCase(s.charAt(left))!=Character.toLowerCase(s.charAt(right))){
return false;
}
left++;
right--;
}
}
return true;
}
}
19、最多删除一个字符得到回文
题目：给定一个字符串，请判断如果最多从字符串中删除一个字符能不能得到一个回文字符串。例如，如果输入字符串”abca”，由于删除字符’b’或’c’就能得到一个回文字符串，因此输出为 true。
public class test0601 {
public static void main(String[] args) {
String s = "abca";
System.out.println(judgePalindrome(s));
}
//因为要满足最多删除一个字符，保证剩余字符串是回文字符串
//因此可以使左右指针从两端逐渐向内移动，找到不同的字符后，分别删除左右指针指向的字符来判断剩余字符串是否是回文字符串
private static boolean judgePalindrome(String s){
int left = 0;
int right = s.length()-1;
//当s.length()为奇数时，s.length()/2为字符串s中间字符的下标；当s.length()为偶数时，s.length()/2为字符串s中间右一位字符下标
//字符串中字符下标是从0开始的
for (;left<s.length()/2;left++,right--){
//左指针按位右移，右指针按位左移，当左指针指向字符与右指针指向的字符不相等时，在当前位置中止循环
if (s.charAt(left)!=s.charAt(right)){
break;
}
}
//在中止循环的位置将左指针右移一位或将右指针左移一位继续判断剩下的子字符串是否为回文字符串
//当循环完全执行没有中止时，左指针最终的值为s.length()/2
return left==s.length()/2 || judgePartial(s,left,right-1) || judgePartial(s,left+1,right);
}
private static boolean judgePartial(String s,int start,int end){
for (;start<end;start++,end--){
if (s.charAt(start)!=s.charAt(end)){
return false;
}
}
return true;
}
}
20、回文子字符串的个数
题目：给定一个字符串，请问该字符串中有多少个回文连续子字符串？例如，字符串”abc”有 3 个回文子字符串，分别为”a”、”b”和”c”；而字符串”aaa”有 6 个回文子字符串，分别为”a”、”a”、”a”、”aa”、”aa”和”aaa”。
public class test0701 {
public static void main(String[] args) {
String s1 = "abc";
String s2 = "aaa";
System.out.println(totalPalindrome(s1));
System.out.println(totalPalindrome(s2));
}
private static int totalPalindrome(String s){
int count = 0;
//回文字符串分为奇数个字符和偶数个字符两种，判断字符串是否是回文字符串可以从字符串中间位置
//奇数个字符的字符串中间字符只有一个，偶数个字符的字符串中间字符有两个
//将start指针和end指针逐渐同时向前一位和后一位遍历，如果两个指针指向的字符相同，那么两个指针中间部分为回文字符串，此时回文字符串个数count+1
//遍历字符串s的每个字符，分别判断以当前字符为中心字符的奇数个字符的字符串和偶数个字符的字符串中有多少个回文字符串
for (int i = 0; i < s.length(); i++) {
count += countPalindrome(s,i,i);
count += countPalindrome(s,i,i+1);
}
return count;
}
private static int countPalindrome(String s,int start,int end){
int count = 0;
//可以将while循环修改为以下判断方式，可以减少一条判断语句及break的书写
//while (start>=0 && end<s.length() && s.charAt(start)==s.charAt(end)){
// count++;
// start--;
// end++;
//}
while (start>=0 && end<s.length()){
if (s.charAt(start)==s.charAt(end)){
count++;
start--;
end++;
}else {
break;
}
}
return count;
}
}
