月度归档:2018年09月

算法 – 字符串包含[+++]

题目简介

给定一长字符串a -> ABCD,短字符串b -> BAD, 短字符串c -> BCE,则字符串b中的字母都在字符串a中,b是a的真子集,所以对于a,返回true,对于b,返回false,因为字符串b的元素E不在a中。
注意:都是大写字母

解法1,暴力轮询

拿出字符串b的每个元素,分别查询是否在a中出现,若一旦有一个不出现,则返回false,如果所有元素都出现,则返回true
时间复杂度O(nm),其中n和m为字符串a,b的长度。

package chapter2_String_Contains;

/**
 * @Author: codefog
 * @email: at20s@sina.com
 * @Date: 2018/9/18 1:52 PM
 */
public class Solution1 {

    /**
     * 暴力轮询
     *
     * @param args
     */
    public static void main(String[] args) {

        String a = "HelloWorld"; //j
        String b = "ldWor"; // i
        String c = "ABC";

        System.out.println(isContains1(a, b));
        System.out.println(isContains1(a, c));

    }

    public static boolean isContains(String a, String b) {
        char[] aStr = a.toCharArray();
        char[] bStr = b.toCharArray();

        //固定字符串b
        for (int i = 0; i < bStr.length; i++) {
            int flag = 0;
            for (int j = 0; j < aStr.length; j++) {
                if (bStr[i] == aStr[j]) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 相同算法,第二种写法
     * @param a
     * @param b
     * @return
     */
    public static boolean isContains1(String a, String b) {
        char[] aStr = a.toCharArray();
        char[] bStr = b.toCharArray();

        //固定字符串b
        for (int i = 0; i < bStr.length; i++) {
            for (int j = 0; j < aStr.length; j++) {
                if (bStr[i] == aStr[j]) {
                    break;
                }
                //字符串b移动到最后一位,a也是最后一位,仍然没有找到相同的,就返回false
                if (bStr[i] != aStr[j] && i == bStr.length - 1 && j == aStr.length - 1) {
                    return false;
                }
            }
        }
        return true;
    }
}


解法2,排序后再轮询

排序时间复杂度O(mlogm)+O(nlogn)+O(m+n),即两次排序和线性扫描的复杂度。与第一种解法类似,改进不大。

package chapter2_String_Contains;

import java.util.Arrays;

/**
 * @Author: codefog
 * @email: at20s@sina.com
 * @Date: 2018/9/18 4:59 PM
 */
public class Solution2 {

    /**
     * 排序轮询
     * @param args
     */
    public static void main(String[] args) {

        String a = "HelloWorld"; //j
        String b = "ldWor"; // i
        String c = "ABC";

        System.out.println(isContains(a, b));
        System.out.println(isContains(a, c));

    }

    public static boolean isContains(String a, String b) {

        char[] aStr = a.toCharArray();
        char[] bStr = b.toCharArray();
        Arrays.sort(aStr);
        Arrays.sort(bStr);

        //固定字符串b
        for (int i = 0; i < bStr.length; i++) {
            int flag = 0;
            for (int j = 0; j < aStr.length; j++) {
                if (bStr[i] == aStr[j]) {
                    flag = 1;
                    break;
                }
            }
            if (flag == 0) {
                return false;
            }
        }
        return true;

    }
}

解法3,素数相乘

时间复杂度O(m+n),最好情况O(n)。巧妙的利用了素数,非常聪明。缺点是获取的素数乘积会可能超过int的最大值,造成溢出。
证明: 每个正整数都可以唯一表示成素数的乘积.在本算法中,利用字母在编码中对应的数字,可以把字母当作一个正整数,获取到他们的乘积后,可以为一表示字符串。

首先证明存在性,  
用数学归纳法,n=2很显然,假设n<k时成立,当n=k时,如果k为素数,显然成立;如果k是合数,则至少有一个素因数p1,k=p1*a,而由归纳假设a<k能分解为素数乘积,所以n=k也成立.所以对于任意大于1的整数n都存在.  
然后证明唯一性,  
如果有两个分解式,2^p1*3^p2*5^p3*…=2^q1*3^q2*5^q3*…,则  
2^p1|2^q1*3^q2*5^q3*…,所以p1≤q1,同理q1≤p1,所以p1=q1,  
后边的类似证明.  

代码:

package chapter2_String_Contains;

/**
 * @Author: codefog
 * @email: at20s@sina.com
 * @Date: 2018/9/18 10:33 PM
 */
public class Solution3 {

    public static void main(String[] args) {

        String a = "HELLOWORLD"; //j
        String b = "LDWOR"; // i
        String c = "ABC";

        System.out.println(isContains(a, b));
        System.out.println(isContains(a, c));
    }


    public static boolean isContains(String a, String b) {

        final int[] pr = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};

        long muti = 1;
        char[] aStr = a.toCharArray();
        char[] bStr = b.toCharArray();
        //遍历字符串a,获取到它所对应的全部素数的乘积
        for (int i = 0; i < aStr.length; i++) {
            //都是大写字母,所以直接相减就在26的范围内,即可确定索引值
            int index = aStr[i] - 'A';
            muti *= pr[index];
        }

        //遍历字符串b,然后让第一步获得的乘积和短字符串所对应的素数取余数,如果由余数,返回false
        for (int i = 0; i < bStr.length; i++) {
            int index = bStr[i] - 'A';
            if (muti % pr[index] > 0) {
                return false;
            }
        }
        return true;
    }

}

解法4,位运算法(HASH)

这个方法和解法3类似,只不过把算出的素数乘积换成了HASH值,然后在用b查询,所有操作使用位运算完成。时间复杂度同上O(n+m),空间复杂度为O(1),对空间友好。

package chapter2_String_Contains;

/**
 * @Author: codefog
 * @email: at20s@sina.com
 * @Date: 2018/9/19 12:06 AM
 */
public class Solution4 {

    public static void main(String[] args) {

        String a = "HELLOWORLD"; //j
        String b = "LDWOR"; // i
        String c = "ABC";

        System.out.println(isContains(a, b));
        System.out.println(isContains(a, c));
    }

    public static boolean isContains(String a, String b) {
        char[] aStr = a.toCharArray();
        char[] bStr = b.toCharArray();

        int HASH = 0;

        //遍历a字符串,为每个字符计算HASH值
        for (int i = 0; i < aStr.length; i++) {
            HASH |= (1 << (aStr[i] - 'A'));
        }
        //把b的每个字符放到a中查找
        for (int i = 0; i < bStr.length; i++) {
            if ( (HASH & (1 << (bStr[i] - 'A')) ) == 0) {
                return false;
            }
        }

        return true;
    }
}

其他资料算法

参考:
https://www.cnblogs.com/tgycoder/p/5241157.html
http://blog.jobbole.com/99205/

算法 – java常见算法题输入输出

字符串和数字相同道理,本文都适用于字符串。

输入一行数字

Scanner sc = new Scanner(System.in);

        System.out.println("读取一行数字:");
        String oneLine = sc.nextLine();
        String[] cs = oneLine.split(" ");
        for (String x : cs) {
        	int intValue = Integer.valueOf(x);
            System.out.print(intValue + " ");
        }

输入n行数字,行数确定

如果需要获得每行数字的值,用String的split方法分割为char[]后,再使用Integer.valueOf()转换成int即可,同上

System.out.println("读取n行数字:");
        int lines = 3;
        String[] mutiLines = new String[3];
        int i = 0;
        while (i < lines) {
            mutiLines[i++] = sc.nextLine();
        }
        for (String s : mutiLines) {
            System.out.println(s);
        }

输入多行数字,未知行数

没有对一行多数字做处理,处理方法和上述但行输入相同。

System.out.println("输入多行数字:");
        List<String> list = new ArrayList<>();

        String input = "";
        while (true) {
            input = sc.nextLine();
            if (!input.equals("q")) {
                list.add(input);
            }else {
                break;
            }
        }
        for (String s : list) {
            //只能转换一行一个数字,多个数字需要额外同上的操作
            //int intValue = Integer.valueOf(s);
            System.out.println(s);
        }

遇到其他情况再补充

算法 – 字符串旋转

题目简介

字符串反转,字符串旋转,例如abcdef旋转为defabc

解法1,暴力

时间复杂度O(nm),空间O(1) (长度为n,移动m个字符)

坑:

java如果想覆盖字符串的值,不能和c/c++一样,直接传入指针就能修改原值,而是需要old = opeartion(old)这样子把旧的引用覆盖掉才行。

package string_reverse;

/**
 * @Author: codefog
 * @email: at20s@sina.com
 * @Date: 2018/9/17 10:44 PM
 */
public class Solution1 {


    /**
     * 暴力一次一个字符的移动
     * 时间复杂度O(nm),空间O(1) (长度为n,移动m个字符)
     * @param args
     */
    public static void main(String[] args) {
        String str = "hello world!";
        System.out.println(rotateString(str,3));

    }

    public static String shifting(String str) {

        char[] strs = str.toCharArray();
        char temp = strs[0];
        for (int i = 1; i < strs.length; ++i) {
            //从第一个开始,一次被后一个字符覆盖
            strs[i - 1] = strs[i];
        }
        strs[strs.length - 1] = temp;
        return String.valueOf(strs);
    }

    public static String rotateString(String string, int m) {
        while (m > 0) {
            string = shifting(string);
            m--;
        }
        return string;
    }



}

解法2,三步反转

时间复杂度O(n),空间复杂度O(1)

  1. 分割原字符串
  2. 分别反转
  3. 整体反转
public class Solution2 {

    /**
     * 三步反转
     * @param args
     */
    public static void main(String[] args) {
        String str = "hello world!";
        System.out.println(rotateString(str,4));

    }

    /**
     * 把字符串m到n的位置反转
     * @param string
     * @return
     */
    public static String reverseString(String string,int m, int n) {
        char[] cString = string.toCharArray();

        while (m < n) {
            char temp = cString[m];
            //第一个值被最后一个覆盖,然后移动m到下一个值
            cString[m++] = cString[n];
            //最后一个值被第一个覆盖,向前移动
            cString[n--] = temp;
        }
        return String.valueOf(cString);
    }

    public static String rotateString(String str, int m) {
        //m = m % length, 如果移动的位置数量超过长度,则相当于一个环旋转
        // 3 % 5 = 3, 小于字符串长度则没有问题
        m %= str.length();
        //反转第一部分
        str = reverseString(str,0, m);
        //反转第二部分
        str = reverseString(str, m, str.length() - 1);
        //整体反转
        str = reverseString(str, 0, str.length() - 1);

        return str;

    }
}

举一反三

反转句子中单词的位置,比如i am a student., 反转后student. a am i,标点符号作为单词的一部分处理.

思路

  1. 以空格分割句子为n(单词数量)部分
  2. 分别反转
  3. 总体反转
public class Others {

    /**
     * 反转句子中的单词
     * @param args
     */
    public static void main(String[] args) {
        String str = "i am quite a student.";
        System.out.println(rotateString(str));

    }

    /**
     * 把字符串m到n的位置反转
     * @param string
     * @return
     */
    public static String reverseString(String string,int m, int n) {
        char[] cString = string.toCharArray();

        while (m < n) {
            char temp = cString[m];
            //第一个值被最后一个覆盖,然后移动m到下一个值
            cString[m++] = cString[n];
            //最后一个值被第一个覆盖,向前移动
            cString[n--] = temp;
        }
        return String.valueOf(cString);
    }

    public static String rotateString(String str) {
        //以空格分割,正则表达
        String[] spString = str.split("\\s+");
        str = "";
        //分别反转分割后的字符串
        if (spString.length > 0) {
            for (int i = 0; i < spString.length; ++i) {
                spString[i] = reverseString(spString[i],0,spString[i].length() - 1);
                //拼接完整字符串
                str += " " + spString[i];
            }
        }
        //总体旋转
        str = reverseString(str, 0, str.length() - 1);

        return str;
    }

}

复杂度同上.