课外运动项目数据库ER图

1. 剑指offer专项突破版

1.1. 整数除法，不使用* / %

思路：使用减法来代替除法，注意的点：是否会超出范围，符号判断

// 整数除法，不用* 和 / 和 %
public class _001 {

    public static void main(String[] args) {
        int a = -2147483648;
        int b = 1;
        System.out.println(divide(a,b));
    }
    public static int divide(int dividend, int divisor) {

        if(dividend == Integer.MAX_VALUE && divisor == -1){
            return Integer.MIN_VALUE+1;
        }
        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        if(dividend == Integer.MIN_VALUE && divisor == 1){
            return Integer.MIN_VALUE;
        }
        if(dividend == Integer.MAX_VALUE && divisor == 1){
            return Integer.MAX_VALUE;
        }

        if(dividend == 0) return 0;
        int result = 0;
        boolean nav = (dividend < 0 && divisor > 0) || (dividend > 0 && divisor < 0);
        long dividend1 = Math.abs((long) dividend);
        long divisor1 = Math.abs((long) divisor);
        while(dividend1 >= divisor1){
            dividend1 = dividend1 - divisor1;
            result++;
        }
        if(nav){
            result = -result;
        }
        return result;
    }
}

1.2. 二进制加法

思路：模仿全加器

public class _002 {
    public static void main(String[] args) {
        String a = "111";
        String b = "101";
        System.out.println(addBinary(a,b));
    }

    public static Result add(char a, char b, char c) {
        // c 为进位
        Result result = new Result();
        if (a == '1' && b == '1') {
            result.setFlag(true);
            result.setResult(c);
        } else if ((a == '1' && b == '0') || (a == '0' && b == '1')) {

            if (c == '1') {
                result.setFlag(true);
                result.setResult('0');
            } else {
                result.setFlag(false);
                result.setResult('1');
            }
        } else {
            result.setResult(c);
            result.setFlag(false);
        }
        return result;
    }

    public static String addBinary(String str1, String str2) {
        StringBuilder stringBuilder = new StringBuilder();
        int length1 = str1.length();
        int length2 = str2.length();
        if (length1 < length2) {
            for (int i = length1; i < length2; i++) {
                str1 = new StringBuilder(str1).insert(0, '0').toString();
            }
        } else if (length1 > length2) {
            for (int i = length2; i < length1; i++) {
                str2 = new StringBuilder(str2).insert(0, '0').toString();
            }
        }
        char c = '0';
        Result result = new Result();
        for (int i = str1.length() -1; i >= 0; i--) {
           result = add(str1.charAt(i), str2.charAt(i), c);
            stringBuilder.insert(0, result.getResult());
            if (result.isFlag()) {
                c = '1';
            } else {
                c = '0';
            }
        }
        if(result.isFlag()){
            stringBuilder.insert(0,'1');
        }
        return stringBuilder.toString();
    }
    static class Result {
        private boolean flag;
        private char result;
        public boolean isFlag() {
            return flag;
        }
        public void setFlag(boolean flag) {
            this.flag = flag;
        }
        public char getResult() {
            return result;
        }
        public void setResult(char result) {
            this.result = result;
        }
    }
}

1.3. 前n个数字的二进制中1的数量

思路：转化为二进制，然后统计其中1的数量

public class _003 {
    //转二进制
    public static String toBinary(int a){
        return Integer.toBinaryString(a);
    }
    //判断二进制数有几个1
    public static int oneCount(String str){
        int count = 0;
        for(int i = 0 ; i < str.length() ; i ++){
            if(str.charAt(i) == '1') count++;
        }
        return count;
    }

    public static int[] getOneCount(int n ){
        int[] result = new int[n+1];
        for(int i = 0 ; i <= n ; i ++){
            result[i] = oneCount(toBinary(i));
        }
        return result;
    }
    public static void main(String[] args) {
        int[] oneCount = getOneCount(3);
        for (int i : oneCount) {
            System.out.println(i);
        }
    }
}

太慢了。题解中使用动态规划。

看不懂啊。

1.4. 只出现一次的数字，其他数字都出现了三次

一般：循环遍历，hashmap去重

import java.util.HashMap;

public class _004 {
    public static int singleNumber(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for( int num : nums){
            if(map.containsKey(num)){
                map.replace(num,map.get(num)+1);
            }else {
                map.put(num,1);
            }
        }
        for (Integer integer : map.keySet()) {
            if(map.get(integer) == 1){
                return integer;
            }
        }
        return -1;
    }
}

快速：位运算

1.5. 单词长度的最大乘积（没有重复字母的两个单词的最大长度乘积）

使用遍历的方法超时

2. 牛客必刷101题

2.1. 001反转链表

2.2. 002反转局部链表

2.3. 003链表中的节点每k个一组翻转

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。也可以邮件至 2738430398@qq.com