[剑指offer] 其他算法[上]篇

JZ66 构建乘积数组

/* 暴力 */
public class JZ66_1
{
    public static int[] multiply(int[] A)
    {
        int[] res = new int[A.length];
        Arrays.fill(res, 1);
        for (int i = 0; i < A.length; i++)
        {
            for (int j = 0; j < A.length; j++)
            {
                if (j == i) continue;
                res[i] *= A[j];
            }
        }
        return res;
    }
}

/* 根据 i 分成两部分 */
public class JZ66_2
{
    public static int[] multiply(int[] A)
    {
        int[] res = new int[A.length];
        int temp = 1;
        res[0] = 1;
        for (int i = 1; i < A.length; i++)
            res[i] = res[i - 1] * A[i - 1];
        for (int i = A.length - 1; i >= 0; i--)
        {
            res[i] *= temp;
            temp *= A[i];
        }
        return res;
    }
}

JZ50 第一个只出现一次的字符

/* hashmap */
public class JZ50_1
{
    public static int FirstNotRepeatingChar(String str)
    {
        HashMap<Character, Integer> map = new HashMap<>();
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < str.length(); i++)
        {
            if (!map.containsKey(str.charAt(i)))
                map.put(str.charAt(i), i);
            else
                map.remove(str.charAt(i));
        }
        Set<Character> characters = map.keySet();
        for (char ch : characters)
        {
            int idx = map.get(ch);
            if (idx < res)
                res = idx;
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

JZ5 替换空格

public class JZ5_1
{
    public static String replaceSpace(String s)
    {
        return s.replace(" ", "%20");
    }
}

/* 双指针 */
public class JZ5_2
{
    public static String replaceSpace(String s)
    {
        int spaceNum = 0, newLen, oldLen = s.length();
        for (int i = 0; i < oldLen; i++)
            if (s.charAt(i) == ' ') spaceNum++;
        newLen = s.length() + spaceNum * 2;

        StringBuilder str = new StringBuilder(s);
        str.setLength(newLen);
        newLen--;
        for (oldLen--; oldLen >= 0; oldLen--)
        {
            if (s.charAt(oldLen) == ' ')
            {
                str.setCharAt(newLen--, '0');
                str.setCharAt(newLen--, '2');
                str.setCharAt(newLen--, '%');
            }
            else
                str.setCharAt(newLen--, s.charAt(oldLen));
        }
        return str.toString();
    }
}

JZ21 调整数组顺序使奇数位于偶数前面(一)

/* 双指针 */
public class JZ21_1
{
    public static int[] reOrderArray(int[] array)
    {
        int[] res = new int[array.length];
        int left = 0, right = array.length - 1, l = left, r = right;
        while (left < array.length && right >= 0)
        {
            if (array[left] % 2 != 0)
                res[l++] = array[left];
            left++;
            if (array[right] % 2 == 0)
                res[r--] = array[right];
            right--;
        }
        return res;
    }
}

/* 遇到奇数,就把他按顺序放到前面 */
public class JZ21_2
{
    public static int[] reOrderArray(int[] array)
    {
        int left = 0;
        for (int i = 0; i < array.length; i++)
        {
            if (array[i] % 2 == 0) continue;
            int temp = array[i];
            for (int j = i; j > left; j--)
                array[j] = array[j - 1];
            array[left] = temp;
            left++;
        }
        return array;
    }
}

JZ39 数组中出现次数超过一半的数字

/* ⭐摩尔投票算法⭐ */
public class JZ39_1
{
    public static int MoreThanHalfNum_Solution(int[] numbers)
    {
        int count = 0, res = -1;
        for (int num : numbers)
        {
            if (count == 0)
            {
                res = num;
                count++;
            }
            else
            {
                if (res == num) count++;
                else
                    count--;
            }
        }
        return res;
    }
}

/* 快排 */
public class JZ39_2
{
    public static int MoreThanHalfNum_Solution(int[] numbers)
    {
        int mid = numbers.length / 2, s = 0, e = numbers.length - 1;
        int index = partition(numbers, s, e);
        while (index != mid)
        {
            if (index > mid)
                e = index - 1;
            else
                s = index + 1;
            index = partition(numbers, s, e);
        }
        return numbers[mid];
    }

    public static int partition(int[] numbers, int left, int right)
    {
        int pivot = numbers[right];
        while (left < right)
        {
            while (left < right && numbers[left] <= pivot) left++;
            numbers[right] = numbers[left];
            while (right > left && numbers[right] >= pivot) right--;
            numbers[left] = numbers[right];
        }
        numbers[left] = pivot;
        return left;
    }
}

JZ43 整数中1出现的次数（从1到n整数中1出现的次数）⭐

/* 个位 + 十位 + 百位 + ... */
public class JZ43_1
{
    public static int NumberOf1Between1AndN_Solution(int n)
    {
        int round = n, weight, extra, base = 1, res = 0;
        while (round != 0)
        {
            weight = round % 10;
            round /= 10;
            extra = n % base;
            res += round * base;
            if (weight == 1) res += 1 + extra;
            if (weight > 1) res += base;
            base *= 10;
        }
        return res;
    }
}

/* 最高位1的个数 + 其他位1的个数(左神) */
public class JZ43_2
{
    public static int NumberOf1Between1AndN_Solution(int n)
    {
        if (n < 1)
            return 0;
        int len = getLenOfNum(n);
        if (len == 1)
            return 1;
        int tmp = (int) Math.pow(10, len - 1);
        int first = n / tmp;
        int firstOneNum = first == 1 ? n % tmp + 1 : tmp;
        int otherOneNUm = first * (len - 1) * (tmp / 10);
        System.out.println(firstOneNum);
        System.out.println(otherOneNUm);
        return firstOneNum + otherOneNUm + NumberOf1Between1AndN_Solution(n % tmp);
    }

    public static int getLenOfNum(int n)
    {
        int len = 0;
        while (n != 0)
        {
            len++;
            n /= 10;
        }
        return len;
    }
}

/* 数位DP */
public class JZ43_3
{
    public static int[] num = new int[20];
    public static int[][] dp = new int[25][20];

    public static int NumberOf1Between1AndN_Solution(int n)
    {
        for (int[] dps : dp) Arrays.fill(dps, -1);
        int k = 0;
        while (n != 0)
        {
            num[++k] = n % 10;
            n /= 10;
        }
        return dfs(k, 0, true);
    }

    public static int dfs(int pos, int cnt, boolean limit)
    {
        if (pos == 0) return cnt;
        if (!limit && dp[pos][cnt] != -1) return dp[pos][cnt];
        int top = limit ? num[pos] : 9, res = 0;
        for (int i = 0; i <= top; i++)
            res += dfs(pos - 1, cnt + (i == 1 ? 1 : 0), limit && (i == top));
        if (!limit) dp[pos][cnt] = res;
        return limit ? res : dp[pos][cnt];
    }
}

JZ45 把数组排成最小的数⭐

/* (o1 + o2).compareTo(o2 + o1); */
public class JZ45_1
{
    public static String PrintMinNumber(int[] numbers)
    {
        String[] temp = new String[numbers.length];
        for (int i = 0; i < numbers.length; i++)
            temp[i] = Integer.toString(numbers[i]);
        Arrays.sort(temp, new Comparator<String>()
        {
            @Override
            public int compare(String o1, String o2)
            {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuilder res = new StringBuilder();
        for (String str : temp)
            res.append(str);
        return res.toString();
    }
}

JZ49 丑数⭐

/* 模拟 */
public class JZ49_1
{
    public static int GetUglyNumber_Solution(int index)
    {
        if (index == 0) return 0;
        int[] res = new int[index];
        int idx = 1, twoIdx = 0, threeIdx = 0, fiveIdx = 0;
        res[0] = 1;
        while (idx < index)
        {
            int val = Math.min(res[twoIdx] * 2, Math.min(res[threeIdx] * 3, res[fiveIdx] * 5));
            res[idx++] = val;
            while (2 * res[twoIdx] <= res[idx - 1])
                twoIdx++;
            while (3 * res[threeIdx] <= res[idx - 1])
                threeIdx++;
            while (5 * res[fiveIdx] <= res[idx - 1])
                fiveIdx++;
        }
        return res[index - 1];
    }
}

JZ74 和为S的连续正数序列

/* 滑动窗口 */
public class JZ74_1
{
    public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum)
    {
        int left = 0, right = 0, s = 0;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        while (right < sum)
        {
            if (s == sum)
            {
                ArrayList<Integer> temp = new ArrayList<>();
                for (int i = left + 1; i <= right; i++)
                    temp.add(i);
                res.add(temp);
            }
            if (s < sum)
            {
                right++;
                s += right;
            }
            else
            {
                left++;
                s -= left;
            }
        }
        return res;
    }
}

JZ57 和为S的两个数字

/* 双指针 */
public class JZ57_1
{
    public static ArrayList<Integer> FindNumbersWithSum(int[] array, int sum)
    {
        int left = 0, right = array.length - 1;
        ArrayList<Integer> res = new ArrayList<>();
        while (left < right)
        {
            if (array[left] + array[right] < sum)
                left++;
            else if (array[left] + array[right] > sum)
                right--;
            else
            {
                res.add(array[left]);
                res.add(array[right]);
                break;
            }
        }
        return res;
    }
}

/* hashmap */
public class JZ57_2
{
    public static ArrayList<Integer> FindNumbersWithSum(int[] array, int sum)
    {
        HashMap<Integer, Integer> map = new HashMap<>();
        ArrayList<Integer> res = new ArrayList<>();
        for (int num : array)
        {
            if (map.containsKey(num))
            {
                res.add(num);
                res.add(map.get(num));
                break;
            }
            map.put(sum - num, num);
        }
        return res;
    }
}