牛客网算法——名企高频面试题143题（4）

题目描述

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

public class Solution {
    public int NumberOf1(int n) {
        int val = n;
        int ans = 0;
        while (val != 0) {
            ++ans;
            val = val & (val - 1);
        }
        return ans;
    }
}

题目描述

给定一个字符串的数组strs，请找到一种拼接顺序，使得所有的字符串拼接起来组成的字符串是所有可能性中字典序最小的，并返回这个字符串。

import java.util.*;


public class Solution {
    /**
     * 
     * @param strs string字符串一维数组 the strings
     * @return string字符串
     */
    public String minString (String[] strs) {
        int len = strs.length;
        Arrays.sort(strs, new Comparator() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < len; i++) {
            sb.append(strs[i]);
        }
        return sb.toString();
    }
}

题目描述

给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)。

import java.util.*;
import java.math.BigDecimal;

public class Solution {
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] A) {
        int len = A.length;
        Arrays.sort(A);
        BigDecimal max1 = new BigDecimal(A[len - 1]).multiply(new BigDecimal(A[len - 2])).multiply(new BigDecimal(A[len - 3]));
        BigDecimal max2 = new BigDecimal(A[len - 1]).multiply(new BigDecimal(A[1])).multiply(new BigDecimal(A[0]));
        //最大的三个数只可能是的最后的三个数和最后一个数前面的两个数
        if (max1.compareTo(max2)>0){
            return Long.valueOf(max1.toString());
        }else {
            return Long.valueOf(max2.toString());
        }
    }
}

题目描述

给定一个数组由一些非负整数组成，现需要将他们进行排列并拼接，使得最后的结果最大，返回值需要是string类型 否则可能会溢出

import java.util.*;
import java.math.BigDecimal;

public class Solution {
    /**
     * 最大数
     * @param nums int整型一维数组 
     * @return string字符串
     */
    public String solve (int[] nums) {
        //判断数组的安全
        if (nums.length == 0) {
            return null;
        }
        ArrayList result = new ArrayList();
        ArrayList list = new ArrayList();
        ArrayList ans = new ArrayList();
        BigDecimal maxnum = new BigDecimal(0);
        boolean[] vis = new boolean[nums.length];
        dfs(nums, list, result, vis);
        for (ArrayList a : result) {
            String res = "";
            for (int i : a) {
                res += String.valueOf(i);
            }
            maxnum = maxnum.compareTo(new BigDecimal(res)) > 0 ? maxnum : new BigDecimal(res);
        }
        return maxnum.toString();
    }
    private void dfs(int[] nums, ArrayList list, ArrayList result, boolean[] vis) {
        if (list.size() == nums.length) {
            result.add(new ArrayList(list));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (!vis[i]) {
                list.add(nums[i]);
                vis[i] = true;
                //下一个状态
                dfs(nums, list, result, vis);
                list.remove(list.size() - 1);
                vis[i] = false;
            }
        }
    }
}

题目描述

如果version1 > version2 返回1，如果 version1  b) { return 1; } else if (a < b) { return -1; } index1++; index2++; } if (index1==arr1.length&&index2