面试算法题系列(1)

发表于 | 分类于
9个基础面试算法题，未完待续...

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
package pers.yijin.demo;
import java.util.HashMap;
import java.util.Map;
/**
 * 统计字符串中，字符出现的次数
 *
 * @author Administrator
 *
 */
public class CountWords {
    /**
     * 利用map的键不能重复的特性来实现
     *
     * @param str
     */
    public static void count(String str) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        for (int i = 0; i < str.length(); i++) {
            char key = str.charAt(i);
            if (!map.containsKey(key)) {
                map.put(key, 1);
            } else {
                int value = map.get(key);
                map.put(key, value + 1);
            }
        }
        for (Map.Entry<Character, Integer> m : map.entrySet()) {
            System.out.println(m.getKey() + "的次数为：" + m.getValue());
        }
    }
    public static void main(String[] args) {
        CountWords.count("askadklfjalkjflfaflkdnmcnvkjfklasdj");
    }
}

2.递归调用系列（不完整。。。）

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
package pers.yijin.demo;
import java.math.BigInteger;
/**
 * 递归调用
 *
 * @author Administrator
 *
 */
public class Fibonacci {
    /**
     * 斐波那契数列：求1,1,2,3,5,8,13....的第100位的值
     *
     * @param n
     * @return
     */
    public static int fibonacci(int n) {
        if (n <= 2) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    /**
     * 求N的阶乘
     *
     * @param n
     * @return
     */
    public static int factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }
    /**
     * 求最大公约数
     *
     * @param p
     * @param q
     * @return
     */
    public static int gcb(int p, int q) {
        if (q == 0) {
            return p;
        }
        int r = p % q;
        return gcb(q, r);
    }
    public static void main(String[] args) {
        System.out.println(BigInteger.valueOf(fibonacci(10)));
        System.out.println(factorial(10));
        System.out.println(gcb(5, 10));
    }
}

3.荷兰国旗问题

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
41
42
43
44
45
46
47
48
package pers.yijin.demo;
import java.util.Arrays;
/**
 * 荷兰国旗问题
 *  将0、1、2三个数排列，0在左边，1在中间，2在右边
 *
 * @author Administrator
 *
 */
public class FlagOfNetherland {
    public static void sort(int[] arr, int low, int high) {
        int begin = low;//开始索引
        int end = high;//结尾索引
        int current = low;//遍历索引
        while (current <= end) {
            if (arr[current] < 1) {
                //当前值==0则与开始索引交换，遍历索引和开始索引+1，则开始索引左边的数据就固定好了(除了开始时，begin永远指向1)
                swap(arr, begin, current);
                begin++;
                current++;
            } else if (arr[current] > 1) {
                swap(arr, current, end);
                end--;
            } else {
                current++;
            }
        }
    }
    // 交换算法
    private static void swap(int[] arr, int current, int next) {
        int temp = arr[current];
        arr[current] = arr[next];
        arr[next] = temp;
    }
    public static void main(String[] args) {
        int[] arr = { 0, 1, 2, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 1, 2, 0, 2, 1, 0, 2, 0, 1, 2,
                1, 2, 0, 2, 1, 0, 2, 0, 1, 2, 1, 2, 0, 2, 1, 0, 2 };
        sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

4.判断一个数是否为素数

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
package pers.yijin.demo;
/**
 * 判断一个数是否为素数
 * @author Administrator
 *
 */
public class IsPrime {
    /**
     * Math.sqrt()求一个数的非负平方根
     * 以平方为界
     * @param num
     * @return
     */
    public static boolean isPrime(int num) {
        // 素数最小为2
        if (num < 2) {
            return false;
        }
        for (int i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }
    public static void main(String[] args) {
        for (int i = 101; i < 201; i++) {
            if(isPrime(i)){
                System.out.println(i);
            }
        }
    }
}

5.约瑟环问题

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
41
42
43
44
45
46
package pers.yijin.demo;
/**
 * 约瑟环问题 实现30个人轮流报数，9出局，循环，剩下15个人。
 *
 * @author Administrator
 *
 */
public class JosephRing {
    public static void main(String[] args) {
        // 创建一个约瑟环
        boolean[] people = new boolean[30];
        for (int i = 0; i < people.length; i++) {
            people[i] = true;
        }
        //用于循环的人数
        int personSum = people.length;
        //计数的个数
        int countNum = 0;
        //索引数
        int index = 0;
        while (personSum > 15) {
            //如果当前index已经出局，则让下一个出局
            if(people[index]){
                countNum++;
                //如果数到9，则9出局
                if (countNum == 9) {
                    countNum = 0;
                    people[index] = false;//index=8时people[index]是第九个人
                    personSum--;
                }
            }
            index++;
            //循环结束，重新开始
            if (index == people.length) {
                index = 0;
            }
        }
        for (int i = 0; i < people.length; i++) {
            System.out.println("第" + i + "个的状态是：" + people[i]);
        }
    }
}

6.给定一串数字，把它以中文的形式输出

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
package pers.yijin.demo;
/**
 * 给定一串数字，把它以中文的形式输出
 * @author Administrator
 *
 */
public class NumberParseString {
    public static void convert(int number) {
        //数字对应的汉字
        String[] num = {"零","一","二","三","四","五","六","七","八","九"};
        //单位
        String[] unit = {"","十","百","千","万","十万","百万","千万","亿","十","百","千","万亿"};
        //将输入数字转换为字符串
        String strNum = String.valueOf(number);
        //判断0出现了几次
        boolean zeroFlag = true;
        //结果 字符串
        String str = "";
        int length = strNum.length();
        for (int i = 0; i < length; i++) {
            //两个字符做运算，自动转换为数字
            int c = strNum.charAt(i)-'0';
            if(c != 0) {
                str += num[c]+unit[length-i-1];
                zeroFlag = true;
            }
            if(c==0 && zeroFlag && i!=length-1){
                str += num[c];
                zeroFlag = false;
            }
        }
        System.out.println(str);
    }
    public static void main(String[] args) {
        convert(120);
    }
}

7.不使用parseInt把字符串转换为数字

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
package pers.yijin.demo;
/**
 * 不使用parseInt把字符串转换为数字
 *
 * @author Administrator
 *
 */
public class ParseInt {
    /**
     * 利用两个char型运算自动转换为int的特性
     *
     * @param str
     * @return
     */
    public static int parseInt(String str) {
        int res = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if ((c >= '0') && (c <= '9')) {
                res = res * 10 + (c - '0');
            }
        }
        return res;
    }
    public static void main(String[] args) {
        System.out.println(parseInt("123456789"));
    }
}

8.数字反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package pers.yijin.demo;
/**
 * 数字反转
 *
 * @author Administrator
 *
 */
public class Reverse {
    public static int reverse(int num) {
        StringBuilder builder = new StringBuilder();
        String str = builder.append(num).reverse().toString();
        return Integer.parseInt(str);
    }
    public static void main(String[] args) {
        System.out.println(reverse(852147963));
    }
}

9.水仙花数问题

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
package pers.yijin.demo;
/**
 * 求100~999之间的水仙花数
 * 水仙花数：例如153是1的3次方+5的3次方+3的3次方的和。
 * @author Administrator
 *
 */
public class Shuixianhuashu {
    /**
     * 分解出个位，十位，和百位
     * @param num
     * @return
     */
    public static boolean isShuiXianHuaShu(int num) {
        int i = num / 100;
        int j = (num % 100) / 10;
        int k = num % 10;
        if (num == i * i * i + j * j * j + k * k * k) {
            return true;
        }
        return false;
    }
    public static void main(String[] args) {
        for (int i = 100; i < 1000; i++) {
            if(isShuiXianHuaShu(i)){
                System.out.println(i);
            }
        }
    }
}