AC剩余

AC13. 找出数组中重复的数字

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {2, 3, 5, 4, 3, 2, 6, 7};

        int res = duplicateInArray(nums);
        System.out.println(res);
    }

    // 方法一：Time:O(N) Space:O(1)
    public static int duplicateInArray(int[] nums) {
        if (nums.length == 0) return -1;
        for (int x : nums) if (x > nums.length || x < 0) return -1;

        for (int i = 0; i < nums.length; i ++) {
            while (i != nums[i] && nums[i] != nums[nums[i]])
                swap(nums, i, nums[i]); // 这里必须这样写交换函数
            if (i != nums[i]) return nums[i];
        }
        return -1;
    }

    public static void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }

   /*
    // 方法二：将nums数组排序
    public static int duplicateInArray(int[] nums) {
        int n = nums.length;
        for (int x : nums) if (x >= n || x < 0) return -1;

        Arrays.sort(nums);
        for (int i = 1; i < n; i ++) 
            if (nums[i] == nums[i - 1]) return nums[i];
        return -1;
    }*/

    /*
    // 方法三：基于计数排序的算法
    public static int duplicateInArray(int[] nums) {
        int n = nums.length;
        for (int x : nums) if (x >= n || x < 0) return -1;
        int[] temp = new int[n];
        for (int i = 0; i < n; i ++)
            if (temp[nums[i]] ++ != 0) return nums[i];

        return -1;
    }*/

    /*
    // 方法四：哈希法，Time:O(N) Space:O(N)
    public static int duplicateInArray(int[] nums) {   
        int n = nums.length;
        HashMap<Integer, Boolean> hash = new HashMap<>();
        for (int x : nums) if (x >= n || x < 0) return -1;
        for (int x : nums) {
            if (hash.containsKey(x) && hash.get(x)) return x;
            hash.put(x, true);
        }

        return -1;
    }*/
}

AC15. 二维数组中的查找

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[][] array = {
            {1, 2, 8, 9},
            {2, 4, 9, 12},
            {4, 7, 10, 13},
            {6, 8, 11, 15}
        };

        int target = 7; // true;
        // int target = 5; // false;

        boolean res = searchArray(array, target);
        System.out.println(res);
    }

    public static boolean searchArray(int[][] array, int target) {
        if (array.length == 0 || array[0].length == 0) return false;

        int i = 0, j = array[0].length - 1;
        while (i < array.length && j >= 0) {
            if (array[i][j] == target) return true;
            if (target < array[i][j]) j --;
            else i ++;
        }

        return false;
    }

}

AC16. 替换空格

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        String str = "We are happy.";
        StringBuffer s = new StringBuffer(str);

        String res = replaceSpaces(s);
        System.out.println(res); // We%20are%20happy.
    }

    // 方法四：推荐

    public static String replaceSpaces(StringBuffer str) {
        char[] c = str.toString().toCharArray();
        int len = c.length - 1;
        int count = 0;
        for (char x : c) 
            if (x == ' ') count ++;

        int newlen = 2 * count + len;
        char[] new_c = new char[newlen + 1];
        while (count > 0 || len >= 0) {
            if (c[len] == ' ') {
                new_c[newlen --] = '0';
                new_c[newlen --] = '2';
                new_c[newlen --] = '%';
                len --; count --;
            }
            else {
                new_c[newlen --] = c[len --];
            }
        }

        return String.valueOf(new_c);
    }

    /*    
    // 方法五：也是推荐的，需要用到StringBuffer的API
    public static String replaceSpaces(StringBuffer str) {
        int len = str.length();
        int count = 0;
        for (int i = 0; i < len; i ++) if (str.charAt(i) == ' ') count ++;

        int newlen = len + 2 * count;
        str.setLength(newlen);
        int indexOld = len - 1;
        int indexNew = newlen - 1;
        while (indexOld >= 0) {
            if (str.charAt(indexOld) != ' ')
                str.setCharAt(indexNew --, str.charAt(indexOld));
            else {
                str.setCharAt(indexNew-- , '0');
                str.setCharAt(indexNew-- , '2');
                str.setCharAt(indexNew-- , '%');
            }
            indexOld --;
        }

        return str.toString();
    }

    */
    // 方法一：直接调用replaceAll() 的 API
    /*public static String replaceSpaces(StringBuffer str) {
        return str.toString().replaceAll(" ", "%20");
    }*/

    // 方法二：也是不推荐的方法
/*    public static String replaceSpaces(StringBuffer str) {
        if (str == null) return null;
        StringBuffer res = new StringBuffer();
        for (int i = 0; i < str.length(); i ++) {
            if (str.charAt(i) == ' ') res.append("%20");
            else res.append(str.charAt(i));
        }

        return String.valueOf(res);
    }*/

    /*    
    // 方法三：双指针，空间仍然是O(N)
    public static String replaceSpaces(StringBuffer str) { 
        String res = "";
        for (int i = 0; i < str.length(); i ++) {
            int j = i;
            while (j < str.length() && str.charAt(j) != ' ') j ++;
            res += str.substring(i, j);
            if (j < str.length()) res += "%20";
            i = j;
        }

        return res;
    }
    */
}

AC20. 用两个栈实现队列

AC21. 斐波那契数列 (如果面试出了可以看我这个题的的题解)

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 6;
        int res = Fibonacci(n);

        System.out.println(res); // 8
    }

   public static int Fibonacci(int n) {
        int a = 0, b = 1;
        while (n -- != 0) {
            int c = a + b;
            a = b; b = c;
        }

        return a;
   }
}

AC 25. 剪绳子

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 8;
        int res = maxProductAfterCutting(n);

        System.out.println(res); // 18
    }

    /*  
    // 方法1：数学奥数做法
    public static int maxProductAfterCutting(int n) {
        if (n <= 3) return 1 * (n - 1);
        int res = 1;
        if (n % 3 == 1) {res = 4; n -= 4; }
        else if (n % 3 == 2) {res = 2; n -= 2; }
        while (n != 0) {res *= 3; n -= 3; }

        return res;
    }*/

   // 方法2：DP
   public static int maxProductAfterCutting(int n) {
       int[] dp = new int[n + 1];
       for (int i = 2; i <= n; i ++) 
            for (int j = 1; j < i; j ++)
                dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));

        return dp[n];
   }

}

AC26. 二进制中1的个数

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 9;
        int res = NumberOf1(n);

        System.out.println(res); // 2
    }

    // 方法一：lowbit运算
    public static int NumberOf1(int n) {
        int cnt = 0;
        while (n != 0) {
            n -= lowbit(n);
            cnt ++;
        }

        return cnt;
    }

    public static int lowbit(int x) {
        return x & -x;
    }



/*  方法二：使用String的API，把int转成二进制的String，然后统计1个数

    public static int NumberOf1(int n) {
        int count = 0;
        String s = Integer.toBinaryString(n);
        for (int i = 0; i < s.length(); i ++)
            if (s.charAt(i) == '1') count ++;

        return count;
    }*/
}

AC27. 数值的整数次方

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        double base = 10;
        int e = -2;
        double res = Power(base, e);

        System.out.println(res); // 0.01
    }
/*    
    // 方法一：普通做法
    public static double Power(double base, int exponent) {
        double res = 1;
        for (int i = 0; i < Math.abs(exponent); i ++) res *= base;
        if (exponent < 0) res = 1 / res;

        return res;
    }*/

    // 方法二：快速幂---非递归,时间复杂度为O(log2n),空间复杂度为O(1)
    public static double Power(double x, int n) {
        double res = 1.0, var = x;
        int exp = n;
        while (exp != 0)
        {
            //如果对应位置上是1，就乘
            if((exp & 1) == 1) res *= var;
            //这个var相当于下次要用到的数字
            var *= var;
            exp = exp / 2;
        }
        return n < 0 ? 1 / res : res;
    }

/*    // 方法三:快速幂---递归，时间复杂度为O(log2n),空间复杂度为O(log2n)
    public static double Power(double x, int n) {
        if(n == 0) return 1;
        if(n == 1) return x;
        //如果n为int最小值，取反后还是int的最小值。所以就先+1，这样整体就少了1，再乘1/x
        if(n < 0) return Power(1 / x, -(n + 1)) / x;
        if(n % 2 == 0) return Power(x * x, n / 2);
        return Power(x * x, n / 2) * x;
    }*/
}

AC40. 顺时针打印矩阵

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[][] matrix = {
            {1, 2, 3, 4},
            {5, 6, 7, 8},
            {9,10,11,12}
        };

        int[] res = printMatrix(matrix);

        for (int i : res) {
            System.out.print(i); 
            System.out.print(" "); // 1 2 3 4 8 12 11 10 9 5 6 7 
        }
    }


    public static int[] printMatrix(int[][] matrix) {
        int n = matrix.length;
        if (n == 0) return new int[]{};
        int m = matrix[0].length;

        int[] res = new int[n * m];

        boolean[][] st = new boolean[n][m];
        int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

        int x = 0, y = 0, d = 1;

        for (int i = 0; i < n * m; i ++) {
            res[i] = matrix[x][y];
            st[x][y] = true;
            int a = x + dx[d], b = y + dy[d];
            if (a < 0 || a >= n || b < 0 || b >= m || st[a][b]) {
                d = (d + 1) % 4;
                a = x + dx[d]; b = y + dy[d];
            }
            x = a; y = b;
        }

        return res;
    }

}

AC41. 包含min函数的栈

AC42. 栈的压入、弹出序列

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] pushV = {1, 2, 3, 4, 5}, popV = {4, 5, 3, 2, 1};

        boolean res = isPopOrder(pushV, popV); 

        System.out.print(res);  // true
    }


    public static boolean isPopOrder(int[] pushV, int[] popV) {
        if (pushV.length != popV.length) return false;
        Stack<Integer> stk = new Stack<>();
        int i = 0;
        for (int x : pushV) {
            stk.push(x);
            while (!stk.isEmpty() && stk.peek() == popV[i]) {
                stk.pop();
                i ++;
            }
        }

        return stk.isEmpty();
    }

}

AC49. 二叉搜索树与双向链表 (跳过–看看LC原题)

AC51. 数字排列（同LC47. 全排列II）

AC52. 数组中出现次数超过一半的数字（LC原题吧）

import java.util.*;

public class Main {
    public static void main(String[] args) {
        int[] nums = {1, 2, 1, 1, 3};

        int res = moreThanHalfNum_Solution(nums);
        System.out.println(res);
    }

    // 最推荐的写法
    public static int moreThanHalfNum_Solution(int[] nums) {
        int count = 1, val = nums[0];
        for (int i = 1; i < nums.length; i ++) {
            if (nums[i] == val) count ++;
            else count --;
            if (count == 0) {
                val = nums[i];
                count = 1;
            }
        }

        return val;
    }z

/*    public static int moreThanHalfNum_Solution(int[] nums) {
        int cnt = 0, val = -1;
        for (int x : nums) {
            if (cnt == 0) {
                val = x; cnt = 1;
            }
            else {
                if (x == val) cnt ++;
                else cnt --;
            }
        }

        return val;
    }*/


    // 使用排序的方式
/*  public static int moreThanHalfNum_Solution(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }*/


}

AC53. 最小的k个数

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] input = {1, 2, 3, 4, 5, 6, 7, 8};
        int k = 4;

        List<Integer> res = getLeastNumber_Solution(input, k); 

        for (int r : res) {
            System.out.print(r);  // 1 2 3 4 
            System.out.print(" ");
        }
    }


    public static List<Integer> getLeastNumber_Solution(int[] input, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b)->(b - a)); 
        for (int x : input) {
            heap.offer(x);
            if (heap.size() > k) heap.poll();
        }

        List<Integer> res = new ArrayList<>();
        while (!heap.isEmpty()) {
            res.add(heap.poll());
        }

        Collections.reverse(res);
        return res;
    }

   /* //除了像上面的Collections.reverse(res);还可以使用
   //LinkedList的addFirst()进行头插，就不用reverse了

    public static List<Integer> getLeastNumber_Solution(int[] input, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b)->(b - a)); 
        for (int x : input) {
            heap.offer(x);
            if (heap.size() > k) heap.poll();
        }

        LinkedList<Integer> res = new LinkedList<>();
        while (!heap.isEmpty()) {
            res.addFirst(heap.poll());
        }

        return res;
    }*/

}

AC54. 数据流中的中位数（暂时空着）

AC55. 连续子数组的最大和

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, -2, 3, 10, -4, 7, 2, -5};

        int res = maxSubArray(nums); 
        System.out.println(res); // 18
    }

    // y总剑指offer视频中的代码
    public static int maxSubArray(int[] nums) {
        int res = Integer.MIN_VALUE, s = 0;
        for (int x : nums) {
            if (s < 0) s = 0;
            s += x;
            res = Math.max(res, s);
        }

        return res;
    }

    /*
    public static int maxSubArray(int[] nums) {
         int sum = 0, maxv = -0x3f3f3f3f;
         for (int i = 0; i < nums.length; i ++) {
             sum += nums[i];
             maxv = Math.max(maxv, sum);
             if (sum < 0) sum = 0;
         }

         return maxv;
     }*/
}

AC56. 从1到n整数中1出现的次数(同LC233. 数字1的个数 )

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 13; // 6
        // int n = 12; // 5
        int res = countDigitOne(n); 
        System.out.println(res); 
    }

    public static int countDigitOne(int n) {
        if (n <= 0) return 0;
        List<Integer> nums = new ArrayList<>();

        while (n != 0) {
            nums.add(n % 10);
            n /= 10;
        }

        Collections.reverse(nums);

        int res = 0;
        for (int i = 0; i < nums.size(); i ++) {
            int d = nums.get(i);
            int left = 0, right = 0, p = 1;

            for (int j = 0; j < i; j ++) left = left * 10 + nums.get(j);

            for (int j = i + 1; j < nums.size(); j ++) {
                right = right * 10 + nums.get(j);
                p = p * 10;
            }

            if (d == 0) res += left * p;
            else if (d == 1) res += left * p + right + 1;
            else res += (left + 1) * p;
        }

        return res;
    }

}

AC57. 数字序列中某一位的数字(类似LC400. 第N个数字)

AC58. 把数组排成最小的数

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {3, 32, 321};

        String res = printMinNumber(nums); 
        System.out.println(res);  // 321323
    }

    public static String printMinNumber(int[] nums) {
        List<Integer> list = new ArrayList<>();
        String res = "";
        int n = nums.length;
        for (int i = 0; i < n; i ++) list.add(nums[i]);

        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer str1, Integer str2) {
                String s1 = str1 + "" + str2;
                String s2 = str2 + "" + str1;
                return s1.compareTo(s2);
            }
        });

        for (int j : list) res += j;

        return res;
    }

}

AC62. 丑数

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 5;

        int res = getUglyNumber(n); 
        System.out.println(res);  // 5
    }

    public static int getUglyNumber(int n) {
        int[] q = new int[n];
        q[0] = 1;
        int i = 0, j = 0, k = 0;

        for (int m = 1; m < n; m ++) {
            int t = Math.min(q[i] * 2, Math.min(q[j] * 3, q[k] * 5));
            q[m] = t;

            if (q[i] * 2 == t) i ++;
            if (q[j] * 3 == t) j ++;
            if (q[k] * 5 == t) k ++;
        }

        return q[n - 1];
    }

}

AC65. 数组中的逆序对

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 3, 4, 5, 6, 0};

        int res = inversePairs(nums); 
        System.out.println(res);  // 6
    }

    public static int inversePairs(int[] nums) {
        return merge_sort(nums, 0, nums.length - 1);
    }

    public static int merge_sort(int[] nums, int l, int r) {
        if (l >= r) return 0;
        int mid = l + r >> 1;
        int res = merge_sort(nums, l, mid) + merge_sort(nums, mid + 1, r);
        // int[] temp = new int[nums.length];
        List<Integer> temp = new ArrayList<>();

        int i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) temp.add(nums[i ++]);
            else {
                temp.add(nums[j ++]);
                res += mid - i + 1;
            }
        }

        while (i <= mid) temp.add(nums[i ++]);
        while (j <= r) temp.add(nums[j ++]);
        int k = l;
        for (int x : temp) nums[k ++] = x;
        return res;
    }

}

AC73. 数组中只出现一次的两个数字

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 3, 3, 4, 4};

        int[] res = findNumsAppearOnce(nums); 
        for (int i : res) {
            System.out.print(i);  // 1 2
            System.out.print(" ");
        }
    }

    // 方法二：分组异或
    public static int[] findNumsAppearOnce(int[] nums) {
        int xy = 0;
        for (int num : nums) xy ^= num;

        int k = 0;
        while (0 == (xy >> k & 1)) k ++;
        int x = 0;
        for (int num : nums) 
            if (1 == (num >> k & 1)) x ^= num;

        int y = xy ^ x;
        return new int[]{x, y};
    }

    // 方法一：哈希表 O(N) ，O(1)

   /* public static int[] findNumsAppearOnce(int[] nums) {
        int[] ans = new int[2];
        HashMap<Integer, Integer> hash = new HashMap<>();

        for (int x : nums) {
            if (hash.containsKey(x)) {
                hash.put(x, hash.get(x) + 1);
                continue;
            }
            hash.put(x, 1);
        }

        for (int i = 0; i < nums.length; i ++)
            if (hash.get(nums[i]) == 1) 
                ans[i] = nums[i];
        return ans;
    }*/
}

AC74. 数组中唯一只出现一次的数字

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 1, 1, 2, 2, 2, 3, 4, 4, 4};

        int res = findNumsAppearingOnce(nums); 
        System.out.println(res);  // 3

    }

    public static int findNumsAppearingOnce(int[] nums) {
        int ans = 0;
        for (int i = 31; i >= 0; i --) {
            int cnt = 0;

            for (int x : nums) 
                if ((x >> i & 1) == 1) cnt ++;

            if (cnt % 3 == 1) ans = (ans * 2) + 1;
            else ans = ans * 2;
        }

        return ans;
    }
}

AC75. 和为S的两个数字 (同LC1. 两数之和)

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {1, 2, 3, 4};
        int sum = 7;

        int[] res = findNumbersWithSum(nums, sum); 
        for (int i : res) {
            System.out.print(i);  // 3 4
            System.out.print(" ");
        }


    }

    public static int[] findNumbersWithSum(int[] nums, int target) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            if (set.contains(target - x)) return new int[]{target - x, x};
            set.add(x);
        }

        return new int[0];
    }


    // 暴力方法  
/*    public static int[] findNumbersWithSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i ++)
            for (int j = 0; j < i; j ++)
                if (nums[i] + nums[j] == target) 
                    return new int[]{nums[i], nums[j]};
        return new int[]{};
    }*/
}

AC79. 滑动窗口的最大值（LC239. 滑动窗口最大值）

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {2, 3, 4, 2, 6, 2, 5, 1};
        int k = 3;

        int[] res = maxInWindows(nums, k);
        for (int i : res) {
            System.out.print(i);
            System.out.print(" "); // 4 4 6 6 6 5 
        }
    }

/*    public static int[] maxInWindows(int[] nums, int k) {
        int n = nums.length;
        int[] res = new int[n - k + 1];
        Deque<Integer> q = new LinkedList<>();
        for (int i = 0; i < n; i ++) {
            if (!q.isEmpty() && q.peekFirst() < i - k + 1) q.pollFirst();
            while (!q.isEmpty() && nums[i] >= nums[q.peekLast()]) q.pollLast();
            q.offerLast(i);
            if (i - k + 1 >= 0) res[i - k + 1] = nums[q.peekFirst()];
        }

        return res;
    }*/

    // 滑动窗口内的最大值，队列是单调递减的
    public static int[] maxInWindows(int[] nums, int k) { 
        int n = nums.length;
        int[] res = new int[n - k + 1];

        int idx = 0;
        int[] q = new int[n];
        int hh = 0, tt = -1;

        for (int i = 0; i < n; i ++) {
            if (hh <= tt && q[hh] < i - k + 1) hh ++;
            //如果当前元素比队列中后面的若干个元素大，就把这些元素从队列中删除，并把当前元素加入队列中
            while (hh <= tt && nums[q[tt]] <= nums[i]) tt --; 
            q[ ++ tt] = i;

            if (i >= k - 1) res[idx ++] = nums[q[hh]];
        }

        return res;
    }
}

AC81. 扑克牌的顺子

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] nums = {8, 9, 10, 11, 12}; // true
        // int[] nums = {0, 8, 9, 11, 12}; // true

        boolean res = maxInWindows(nums);
        System.out.println(res); // true
    }

    public static boolean maxInWindows(int[] nums) { 
        if (nums.length == 0) return false;
        Arrays.sort(nums);
        int k = 0;
        while (nums[k] == 0) k ++;
        for (int i = k + 1; i < nums.length; i ++) 
            if (nums[i] == nums[i - 1]) return false;
        return (nums[nums.length - 1] - nums[k]) <= 4;
    }
}

AC82. 圆圈中最后剩下的数字

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 5, m = 3;

        int res = lastRemaining(n, m);
        System.out.println(res); // 3
    }
/*
    方法一：数组模拟过程
    public static int lastRemaining(int n, int m) { 
        if (n == 1) return 0;
        boolean[] res = new boolean[n];
        for (int i = 0; i < n; i ++) res[i] = true;

        int t = m - 1, s = 1;
        while (s ++ < n) {
            res[t % n] = false;
            int k = m;
            while (k != 0) {
                t ++;
                if (res[t % n] == true) k --;
            }
        }

        return t % n;
    }*/

    /*// 方法三：找规律+反向模拟
    public static int lastRemaining(int n, int m) { 
        int ans = 0;
        for (int i = 2; i <= n; i ++)
            ans = (ans + m) % i;
        return ans;
    }
    */

   /* 
    // 方法四：DP递推写法
    public static int lastRemaining(int n, int m) { 
        if (n == 1) return 0;
        int[] f = new int[n + 1];
        f[1] = 0;
        for (int i = 2; i <= n; i ++) f[i] = (f[i - 1] + m) % i;

        return f[n];
    }*/

    // 方法五：递归写法
    public static int lastRemaining(int n, int m) { 
        if (n == 1) return 0;
        return (lastRemaining(n - 1, m) + m) % n;
    }
}

AC84. 求1+2+…+n

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int n = 10;

        int res = getSum(n);
        System.out.println(res); // 55
    }

    public static int getSum(int n) {
        int res = n;
        boolean flag = res > 0 && (res += getSum(n - 1)) > 0;
        return res;
    }

}

AC85. 不用加减乘除做加法

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int num1 = 1, num2 = 2;

        int res = add(num1, num2);
        System.out.println(res); // 3
    }

    public static int add(int num1, int num2) {
        while (num2 != 0) {
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1;
            num1 = sum; num2 = carry;
        }

        return num1;
    }

}

AC86. 构建乘积数组

import java.util.*;

public class Main {
    public static void main (String[] args) { 
        int[] A = {1, 2, 3, 4, 5};

        int[] res = multiply(A);
        for (int r : res) {
            System.out.print(r); // 120 60 40 30 24 
            System.out.print(" ");
        }
    }

    public static int[] multiply(int[] A) {
        if (A.length == 0) return new int[]{};
        int n = A.length;
        int[] B = new int[n];
        for (int i = 0, p = 1; i < n; i ++) {
            B[i] = p;
            p *= A[i];
        }
        for (int i = n - 1, p = 1; i >= 0; i --) {
            B[i] *= p;
            p *= A[i];
        }

        return B;
    }

}