数据结构与算法系列一之整数、数组及字符串

前言:由于本人不是科班出身,计算机基础相对薄弱一些,最近在工作之余想系统的学习一下数据结构与算法,主要是通过学习专项突破版的剑指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 =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 

解法二:

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 

解法三:

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 

解法四:

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 >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 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 list,int max){

        int res = 0;
        StringBuilder stringBuilder = new StringBuilder();  //初始化一个可变长字符串用于后续获取结果

        int[] contains = new int[max];  //新建一个数组用来保存所有输入数值每一位相加的结果
        for (String s : list) {  //循环遍历所有二进制字符串的每一位,并将所有字符串相同位的数值相加
            for (int i = 0; i 

解法二:

import java.util.ArrayList;
import java.util.Scanner;

public class test0402 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  //接收输入的数组

        ArrayList 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 list){

        int[] contains = new int[32];  //因为整数就是32位的,所以新建一个容量32的数组,保存输入数字每一位和的结果
        int res = 0;

        for (Integer integer : list) {  //遍历输入数组的每一个数值
            for (int i = 0; i >(31-i))&1 来获取第i位的数值0或1,注意i为0-31,数值位数为1-32,是从左往右的顺序
                contains[i] +=  (integer>>(31-i))&1;  //i=0时,就是第一位,一定要保证运算的顺序
            }
        }
        for (int i = 0; i 

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 list = new ArrayList();

        while (sc.hasNextLine()){  //逐行循环输入字符串,连续回车两次结束输入
            String s = sc.nextLine();
            if (s.equals(""))break;  //控制输入结束
            list.add(s);
        }

        list.forEach(System.out::println);

//        ArrayList 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 list){

        int max = 0;
        //由于字符中只会出现26个小写字母,因此新建字符串个数个26空间大小的数组
        Boolean[][] booleans = new Boolean[list.size()][26];

        //位运算包括:与& 或| 异或^(相当于两个字符串或运算减去与运算) 取反~
        for (int i = 0; i 

解法二:

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 

第二章 数组

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 (startinput[mid]){
                return select01(input, mid+1, end, target);  //下一层函数的输入值起始点,一定要为mid加1或减1,否则栈溢出
            }else if (target>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 list = new ArrayList();
        HashMap 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 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 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 list, int k){

        int[] res = new int[2];
        int p1 = 0;
        int p2 = list.size()-1;

        while (p1 k){
                p2--;
            }else if (list.get(p1)+list.get(p2) 

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> lists = threeSum(input, target);

        lists.forEach(System.out::println);

    }

    private static List> threeSum(int[] list,int target){

        List> result = new LinkedList();

        Arrays.sort(list);  //先对数组进行排序,方便后续查找

        //先遍历数组,指定当前的值为第一个值,再查找另外两个值,使三个数之和为目标值
        for (int i = 0; i > res = twoSum(list, goal, i+1);  //传入twoSum函数,数组、目标值、查找的起始下标
            res.forEach(System.out::println);
            if (!res.isEmpty()){  //当其他两个值查找的结果集不为空时,遍历结果集,每一个结果都与当前遍历的第一个数字组成一个最终结果数组
                for (int j = 0; j > twoSum(int[] list,int goal,int i){  //一个数字确定后,查找另外两个数字

        List> res = new LinkedList();
        int m = i-1;
        int j = list.length-1;

        while (i goal) {  //当两个数值大于目标值,大的下标减1
                j--;
            }else if (list[i] + list[j] 

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 =k && left=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 =k && left

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 map = new HashMap();

        //先给哈希表放入一个初始值(0,1),因为当前下标sum=k时,则有一个满足条件的数组,而前面保存的数组累加和中没有这个结果(即使有sum=0,也会少计数一次)
        map.put(0,1);
        for (int i = 0; i 

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 map = new HashMap();

        for (int i = 0; i 

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 =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 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 

第三章 字符串

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 

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 result = queryAnagram(s1, s2);

        result.forEach(System.out::println);

    }

    //查找str2在str1中的变位词
    private static LinkedList queryAnagram(String str1,String str2){

        LinkedList res = new LinkedList();

        if (str1.length() 

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

解法二:

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

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 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 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

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

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 =0 && end=0 && end

文章来源于互联网:数据结构与算法系列一之整数、数组及字符串

THE END
分享
二维码