算法学习之剑指offer（六）

题目1

题目描述

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

import java.util.*;

public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> list = new ArrayList<Integer>();

        if(input.length<k||k==0)

            return list;

        for(int i=0;i<k;i++){

			list.add(input[i]);

        }

        for(int i=k;i<input.length;i++)

        {

            int max_index = getMax(list);

            int max_val = list.get(max_index);

            if(max_val>input[i])

            {

                list.set(max_index,input[i]);

            }

        }

        return list;

    }

    public int getMax(ArrayList<Integer> list){

        int max_index = 0;

        for(int i=0;i<list.size();i++){

            if(list.get(max_index)<list.get(i))

                max_index=i;

        }

        return max_index;

    }

}

题目2

题目描述

输入一个整型数组，数据元素有正数也有负数，求元素组合成连续子数组之和最大的子数组，要求时间复杂度为O(n)。

找规律得到的算法：

public class Solution {

    public int FindGreatestSumOfSubArray(int[] array) {

        if(array==null||array.length==0)

            return 0;

        int result = array[0],num=0;

        for(int i=0;i<array.length;i++){

            if(num<=0)

                num=array[i];

            else

                num+=array[i];

            if(num>result)

                result=num;

        }

        return result;

    }

}

题目3

题目描述

求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数。

纯属找数字规律的题。提供一种最一般的解法

public class Solution {

    public int NumberOf1Between1AndN_Solution(int n) {

    	 int count=0;

        while(n>0){

            String str=String.valueOf(n);

            char [] chars=str.toCharArray();

            for(int i=0;i<chars.length;i++){

                if(chars[i]=='1')

                    count++;

            }

            n--;

        }

        return count;

    }

}

题目4

题目描述

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

import java.util.ArrayList;

import java.util.*;

public class Solution {

    public String PrintMinNumber(int [] numbers) {

		ArrayList<Integer> list = new ArrayList<Integer>();

        for(int i=0;i<numbers.length;i++){

			list.add(numbers[i]);

        }

        Collections.sort(list,new Comparator<Integer>(){

            public int compare(Integer a,Integer b){

                int s1 = Integer.parseInt(a+""+b);

                int s2 = Integer.parseInt(b+""+a);

                return s1>s2?1:-1;

            }

        });

        StringBuilder sb = new StringBuilder();

        for(Integer i:list)

            sb.append(i+"");

        return sb.toString();

    }

}

题目5

题目描述

把只包含因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

import java.util.*;

public class Solution {

    public int GetUglyNumber_Solution(int index) {

        if(index==0)

        	return 0;

        Queue<Integer> q2 = new LinkedList<Integer>();

        Queue<Integer> q3 = new LinkedList<Integer>();

        Queue<Integer> q5 = new LinkedList<Integer>();

        q2.add(2);q3.add(3);q5.add(5);

        int num=1,min,ugly=1;

        while(num!=index){

            ugly = Math.min(q2.peek(),Math.min(q3.peek(),q5.peek()));

			if(ugly==q2.peek()){

               q2.add(ugly*2);q3.add(ugly*3);q5.add(ugly*5);q2.poll();

           }

           if(ugly==q3.peek()){

               q3.add(ugly*3);q5.add(ugly*5);q3.poll();

           }

           if(ugly==q5.peek()){

               q5.add(ugly*5);q5.poll();

           }

           num++;

        }

        return ugly;

    }

}

题目6

题目描述

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

import java.util.*;

public class Solution {

    public int FirstNotRepeatingChar(String str) {

        if(str.length()==0)

            return -1;

        HashMap<Character,Integer> hm = new LinkedHashMap<Character,Integer>();

        char[] chars = str.toCharArray();

        for(Character c:chars){

            int times;

            Integer i = hm.get(c);

            times=(i==null)?1:i.intValue()+1;

            hm.put(c,times);

        }

        int index=0;;

        for(Character c:hm.keySet()){

            int k = hm.get(c);

            if(hm.get(c)==1){

                index = str.lastIndexOf(c);

                break;

            }

        }

        return index;

    }

}

巴特西

算法学习之剑指offer（六）

题目描述

题目描述

题目描述

题目描述

题目描述

题目描述

最新文章

热门文章