原创

数组问题

一、求数组中的子数组累加和最大的

    public int FindGreatestSumOfSubArray(int[] array) {
         int res = Integer.MIN_VALUE; 
         int sum = 0;
         for(int i = 0; i < array.length; i++){
             sum += array[i];
             res = Math.max(res, sum);
             sum = sum < 0 ? 0 : sum;
         }
        return res;
    }

最小的k个数

     public void swap(int []arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public int partition(int[] arr, int left, int right){
        int less = left - 1;
        int more = right;
        int cur = left;
        while(cur < more){
            if(arr[cur] < arr[right]){
                swap(arr, ++less, cur++);
            }else if(arr[cur] == arr[right]){
                cur++;
            }else{
                swap(arr, --more, cur);
            }
        }
        swap(arr, right, more);
        return more;
    }


    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(input == null || k < 1 || k > input.length) return res;
        int index = partition(input, 0, input.length - 1);
        while(index != k - 1){
            if(index > k - 1){
                index = partition(input, 0, index - 1);

            }else{
                index = partition(input, index + 1, input.length - 1);
            }
        }

        for(int i = 0; i < k; i++){
            res.add(input[i]);
        }
        return res;
    }

public static boolean VerifySquenceOfBST(int [] sequence) {
    if (sequence == null || sequence.length < 1) return false;
    return helper3(sequence, 0, sequence.length - 1);
}
public static boolean helper3(int [] arr, int left, int right){
    int i = left;
    int root = arr[right];
    for(i = left; i < right; i++){
        if (arr[i] > root){
            break;
        }
    }
    int j = i;
    for(; j < right; j++){
        if (arr[j] < root){
            return false;
        }
    }
    return  (i >= 1 ? helper3(arr, left,i - 1) : true )&& (i < right ? helper3(arr, i, j) : true);
}

输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。

   class PrintMinNumberCom implements Comparator<String> {
       @Override
       public int compare(String o1, String o2) {
           return (o1 + o2).compareTo(o2 + o1);
       }
   }

    public String PrintMinNumber(int [] numbers) {
        if (numbers == null || numbers.length ==0) return "";
        String[] strings = new String[numbers.length];
        for (int i = 0 ;i < numbers.length; i++)
            strings[i] = String.valueOf(numbers[i]);
        Arrays.sort(strings,new PrintMinNumberCom());
        String res ="";
        for (int i = 0; i < strings.length; i++){
            res += strings[i];
        }
        return res;

    }

uglynum

 public int nthUglyNumber(int n) {
        int [] res =new int[n];
        res[0] = 1;
        int index2 = 0, index3 = 0, index5 = 0;
        int factor2 = 2, factor3 = 3, factor5 = 5;
        for (int i = 1 ;i < n;i++){
            int min = Math.min(Math.min(factor2,factor3),factor5);
            res[i] = min;
            if (min == factor2 ){
                index2++;
                factor2 = 2*res[index2];
            }

            if (min == factor3 ){
                index3++;
                factor3 = 3*res[index3];
            }

            if (min == factor5 ){
                index5++;
                factor5 = 5*res[index5];
            }
        }

        return res[n-1];
    }

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 给定一个数组,求子数组的最大异或和

    大学里的混子
  • LeetCode <dp>343. Integer Break

    Given a positive integer n, break it into the sum of at least two positive integ...

    大学里的混子
  • LeetCode SingleNumber I,II,III

    Given a non-empty array of integers, every element appears twice except for one....

    大学里的混子
  • Search in Rotated Sorted Array

    问题:找出某个元素的位置 朴素的暴力方法 class Solution { public: int search(int A[], int n, int...

    用户1624346
  • 素数相关问题练习 C++

    辗转相除 #include <iostream> using namespace std; int gcb(int a,int b) { if(b==...

    kalifa_lau
  • loj#2542. 「PKUWC2018」随机游走(MinMax容斥 期望dp)

    设\(f[i][sta]\)表示从\(i\)到集合\(sta\)中任意一点的最小期望步数

    attack
  • 洛谷P4781 【模板】拉格朗日插值(拉格朗日插值)

    \[f(x) = \sum_{i = 1}^n y_i \prod_{j \not = i} \frac{k - x[j]}{x[i] - x[j]}\]

    attack
  • 1089 狼人杀-简单版 (20 分)

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

    韩旭051
  • Stirling数

    第一类: 定义 第一类Stirling数表示表示将 n 个不同元素构成m个圆排列的数目。又根据正负性分为无符号第一类Stirling数 ? 和带符号第一类...

    attack
  • HDU-5584-LCM Walk

    ACM模版 描述 ? 题解 image.png 代码 #include <iostream> using namespace std; int gcd(in...

    f_zyj

扫码关注云+社区

领取腾讯云代金券