剑指offer 数组专题刷题记录（2）-阿里云开发者社区

剑指offer 数组专题刷题记录（2）

2022-01-28 100

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 剑指offer 数组专题刷题记录（2）

剑指Offer（二十八）：数组中出现次数超过一半的数字

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer,Integer> list=new HashMap<Integer,Integer>();
        for(int i=0;i<array.length;i++){
            if(!list.containsKey(array[i])){
                list.put(array[i],1);
                if(2>array.length){
                    return array[i];
                }
            }else{
                int count=list.get(array[i]);
                count++;
                if(count*2>array.length){
                    return array[i];
                }
                list.put(array[i],count);
            }
        }
        return 0;
    }
}

import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
      Arrays.sort(array);
        int count=0;
        for(int i=0;i<array.length;i++){
            if(array[i]==array[array.length/2]){
                count++;
            }
        }
        if(count>array.length/2){
            return array[array.length/2];
        }else{
            return 0;
        }
    }
}

冒泡排序：

 public int[] reOrderArray (int[] array) {
        // write code here
        int[] result = new int[array.length];
        for (int i = 0; i < array.length; i ++) {
            for  (int j = 0; j < array.length-i-1; j ++) {
                if (array[j]%2 == 0 && array[j+1]%2 == 1) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
        return array;
    }

剑指Offer（三十）：连续子数组的最大和

暴力破解方法

import java.util.Collections;
import java.util.ArrayList;
import java.util.List;
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        ArrayList<Integer> list=new ArrayList<Integer>();  
        for(int i=0;i<array.length;i++){      /这个方法使用暴力破解
            int sum=0;                        /ArrayList的使用
            for(int j=i;j<array.length;j++){  / 得到大小用size；
                sum+=array[j];                //得到某个值，用get(X)坐标
                list.add(sum);
            }
        }
        if(list.size()<0){
            return 0;
        }
        Collections.sort(list);
        return list.get(list.size()-1);          
    }
}

///分析数组规律的方法

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array==null||array.length==0){
            return 0;
        }
        int maxValue=0x80000000;
        int countValue=0;
        for(int i=0;i<array.length;i++){
            if(countValue<=0){
                countValue=array[i];
            }else{
                countValue+=array[i];
            }
            if(countValue>maxValue){
                maxValue=countValue;
            }
        }
        return maxValue;
    }
}

剑指Offer（三十二）：把数组排成最小的数

暴力破解：比较两个字符串的大小 s1>s2

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        String str = "";
    for (int i=0; i<numbers.length; i++){
      for (int j=i+1; j<numbers.length; j++){
        int a = Integer.valueOf(numbers[i]+""+numbers[j]);
        int b = Integer.valueOf(numbers[j]+""+numbers[i]);
        if (a > b){
          int t = numbers[i];
          numbers[i] = numbers[j];
          numbers[j] = t; 
        }
      }
    }
    for (int i = 0; i < numbers.length; i++) {
      str += String.valueOf(numbers[i]);
    }
    return str;
    }
}