算法训练——剑指offer(其他综合)

摘要

一、其他综合算法的原理与解题方法

二、其他综合算法练习题目 2.1 构建乘积数组

构建乘积数组_牛客题霸_牛客网

package 其他算法;

import java.util.Arrays;

public class JZ66构建乘积数组 {

    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        Arrays.fill(B, 1);
        for (int i = 1; i < A.length; i++) {
            B[i] = B[i-1] * A[i - 1];
        }
        int tmp = 1;
        for (int i = A.length - 2; i >= 0; i--) {
            tmp *= A[i + 1];
            B[i] *= tmp;
        }
        return B;
    }
}

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

第一个只出现一次的字符_牛客题霸_牛客网

import org.junit.Test;

import java.util.HashMap;

public class test {

    public static void main(String[] args) {

    }

    /**
     * 只出现一次的字符
     *
     * @param str
     * @return
     */
    public int FirstNotRepeatingChar(String str) {
        if (str.length() == 0) {
            return -1;
        }
        HashMap map = new HashMap();
        for (int i = 0; i < str.length(); i++) {
            if (!map.containsKey(str.charAt(i))) {
                map.put(str.charAt(i), 1);
            } else {
                map.put(str.charAt(i), map.get(str.charAt(i)) + 1);
            }
        }
        for (int i = 0; i < str.length(); i++) {
            if (map.get(str.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 利用的是前后索引是否一致
     *
     * @param str
     * @return
     */
    public int FirstNotRepeatingChar1(String str) {
        for (int i = 0; i < str.length(); i++) {
            char cur = str.charAt(i);
            System.out.println(str.indexOf(cur)+"=="+str.lastIndexOf(cur));
            // 前索引是否和后索引一致
            if (str.indexOf(cur) == str.lastIndexOf(cur)) {
                return str.indexOf(cur);
            }
        }
        return -1;
    }


    @Test
    public void test() {
        int google = FirstNotRepeatingChar1("gooogle");
        System.out.println(google);
    }
}

2.3 替换空格

替换空格_牛客题霸_牛客网

import org.junit.Test;

import java.util.HashMap;

public class test {

    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }

}

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

调整数组顺序使奇数位于偶数前面(一)_牛客题霸_牛客网

调整数组顺序使奇数位于偶数前面(二)_牛客题霸_牛客网

package 其他算法;

public class JZ21调整数组顺序使奇数位于偶数前面 {

    public int[] reOrderArray(int[] array) {
        int[] res = new int[array.length];
        int index = 0;
        for (int i : array) {
            if (i % 2 != 0) {
                res[index++] = i;
            }
        }
        for (int i : array) {
            if (i % 2 == 0) {
                res[index++] = i;
            }
        }
        return res;
    }


}

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

数组中出现次数超过一半的数字_牛客题霸_牛客网

利用hashmap方法和数组排序的算法 但是的时间和空间复杂度不一样

package 其他算法;

/**
 * @Classname JZ39数组中出现次数超过一半的数字
 * @Description TODO
 * @Date 2022/2/8 22:13
 * @Created by xjl
 */
public class JZ39数组中出现次数超过一半的数字 {

    public int MoreThanHalfNum_Solution(int[] array) {
        int count = 0, value = 0;
        for (int i : array) {
            if (count == 0) {
                value = i;
                count++;
            } else if (value == i) {
                count++;
            } else {
                count--;
            }
        }
        return value;
    }
}

2.6 整数中1出现的次数

整数中1出现的次数（从1到n整数中1出现的次数）_牛客题霸_牛客网

package 其他算法;

import org.junit.Test;

/**
 * @Classname JZ43整数中1出现的次数
 * @Description TODO
 * @Date 2022/2/7 22:11
 * @Created by xjl
 */
public class JZ43整数中1出现的次数 {
    int count = 0;

    public int NumberOf1Between1AndN_Solution(int n) {
        // 分别计算每一个数字带有的1的个数
        if (n == 0) {
            return 0;
        }
        for (int i = 1; i  getValue(numbers[j + 1], numbers[j])) {
                    int temp = numbers[j];
                    numbers[j] = numbers[j + 1];
                    numbers[j + 1] = temp;
                }
            }
        }
        StringBuffer sb = new StringBuffer();
        // 将字符串型数组中每个元素拼接起来
        for (String num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }

    public long getValue(int a, int b) {
        return Long.parseLong("" + a + b);
    }

    public String PrintMinNumber2(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
        int n = numbers.length;
        String[] nums = new String[n];
        // 先将整型数组转化为字符串型数组
        for (int i = 0; i < n; i++) {
            nums[i] = numbers[i] + "";
        }
        // 用定义的排序规则对字符串型数组进行排序
        Arrays.sort(nums, new Comparator() {
            @Override
            public int compare(String s1, String s2) {
                return (s1 + s2).compareTo(s2 + s1);
            }
        });
        StringBuffer sb = new StringBuffer();
        // 将字符串型数组中每个元素拼接起来
        for (String num : nums) {
            sb.append(num);
        }
        return sb.toString();
    }

    @Test
    public void test() {
        String s = PrintMinNumber3(new int[]{1,2,3,4,5,6,7,8,9,10});
        System.out.println(s);
    }

    ArrayList list;
    boolean[] vis;

    public String PrintMinNumber3(int[] numbers) {
        if (numbers == null || numbers.length == 0) {
            return "";
        }
        String[] arr = new String[numbers.length];
        int index = 0;
        for (int i : numbers) {
            arr[index++] = String.valueOf(i);
        }
        StringBuilder sb = new StringBuilder();
        vis = new boolean[numbers.length];
        list=new ArrayList();
        dfs(arr, sb, 0, vis, list);
        ArrayList ans = new ArrayList(new HashSet(this.list));
        //判断 list中的最小的字符
        String min = ans.get(0);
        for (int i = 1; i < ans.size(); i++) {
            if (new BigDecimal(ans.get(i)).compareTo(new BigDecimal(min)) < 0) {
                min = ans.get(i);
            }
        }
        return min;
    }

    private void dfs(String[] arr, StringBuilder sb, int index, boolean[] vis, ArrayList list) {
        if (index == arr.length) {
            if (!list.contains(sb.toString())){
                list.add(sb.toString());
            }
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (!vis[i]) {
                vis[i] = true;
                sb.append(arr[i]);
                int len=arr[i].length();
                dfs(arr, sb, index + 1, vis, list);
                while (len>0){
                    sb.deleteCharAt(sb.length() - 1);
                    len--;
                }
                vis[i] = false;
            }
        }
    }
}

2.8 丑数问题

丑数_牛客题霸_牛客网

package 其他算法;

import java.util.ArrayList;

public class JZ49丑数 {

    /**
     * 三个指针的算法
     *
     * @param index
     * @return
     */
    public int GetUglyNumber_Solution(int index) {
        if (index < 6) {
            return index;
        }
        int i2 = 0, i3 = 0, i5 = 0;
        int[] res = new int[index];

        res[0] = 1;
        for (int i = 1; i < index; i++) {
            res[i] = Math.min(res[i2] * 2, Math.min(res[i3] * 3, res[i5] * 5));
            if (res[i] == res[i2] * 2) {
                i2++;
            }
            if (res[i] == res[i3] * 3) {
                i3++;
            }
            if (res[i] == res[i5] * 5) {
                i5++;
            }
        }
        return res[index - 1];
    }

    /**
     * 暴力破解的方法 一般是会超时的
     *
     * @param idx
     * @return
     */
    public int GetUglyNumber_Solution2(int idx) {
        int now = 1;
        ArrayList list = new ArrayList();
        list.add(1);
        while (true) {
            if (list.size() == idx) {
                return list.get(list.size() - 1);
            }
            now++;
            if (check(now)) {
                list.add(now);
            }
        }
    }

    public boolean check(int num) {
        while (num % 2 == 0) {
            num /= 2;
        }
        while (num % 3 == 0) {
            num /= 3;
        }
        while (num % 5 == 0) {
            num /= 5;
        }
        return num == 1;//如果x此时不为1，则说明x还含有其他的质因数
    }
}

2.9 和为S的连续正数序列

和为S的连续正数序列_牛客题霸_牛客网

import java.util.ArrayList;
public class Solution {
    public ArrayList FindContinuousSequence(int sum) {
       ArrayList ans = new ArrayList();
        if (sum == 0) {
            return ans;
        }
        int l = 1;
        int r = 2;

        while (l < r) {
            if (cal(l, r) == sum) {
                ArrayList list1 = new ArrayList();
                // 表示的这个区间的就是
                for (int i = l; i  sum) {
                right--;
            } else if ((array[left] + array[right]) < sum) {
                left++;
            } else {
                list.add(array[left]);
                list.add(array[right]);
                break;
            }
        }
        return list;
    }


}

2.11 左旋转字符串

左旋转字符串_牛客题霸_牛客网

package 其他算法;

import org.junit.Test;

/**
 * @Classname JZ58左旋转字符串
 * @Description TODO
 * @Date 2022/2/8 21:26
 * @Created by xjl
 */
public class JZ58左旋转字符串 {

    public String LeftRotateString(String str, int n) {
        if (str.length() == 0 || n == 0) {
            return str;
        }
        if (str.length()