编程题
题目描述
1.数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
package com.ustc.algorithm;
/**
* @author 王聪
* @version 创建时间：2017年3月17日 上午11:32:35
* 类说明
*/
public class MaxNumbers {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public int MoreThanHalfNum_Solution(int [] array) {
// 1.检验数组的合法性
if (array == null || array.length == 0) {
return 0;
}
// 2.思路主要是如果数组中有一个数的次数超过数组长度的一半，那么它出现的次数比其他数组出现的
// 数字之和还要多，遍历数组可以保存两个值，一个是数组中的一个数字，一个是次数，如果次数为0，重新选择
int result = array[0];
int times = 1;
for (int i = 1; i < array.length; i++) {
if (times == 0) {
result = array[i];
times = 1;
} else if (array[i] == result) {
times++;
} else {
times--;
}
}
// 3.检查下这个数是否超过一半
if (!checkMoreThanHalf(array, result)) {
return 0;
}
return result;
}
public boolean checkMoreThanHalf(int[] array, int result) {
int times = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == result) {
times++;
}
}
boolean isMoreThanHalf = true;
if (times * 2 <= array.length) {
isMoreThanHalf = false;
}
return isMoreThanHalf;
}
}
2.输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
package com.ustc.algorithm;
import java.util.ArrayList;
import java.util.TreeSet;
/**
* @author 王聪
* @version 创建时间：2017年3月17日 上午11:45:59
* 类说明
*/
public class MinKNumbers {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] input = {4,5,1,6,2,7,3,8};
ArrayList<Integer> arrayList = new MinKNumbers().GetLeastNumbers_Solution(input, 4);
System.out.println(arrayList.toString());
}
// 本题解法适合处理海量数据
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
// 1.非空判断
if (k > input.length || k <= 0) {
return new ArrayList<>();
}
// 2.Java中TreeSet底层基于TreeMap实现，TreeMap底层基于红黑树实现，因此对于删除，查找，添加的时间复杂度都是基于logn的
TreeSet<Integer> results = new TreeSet<Integer>();
for (int i = 0; i < input.length; i++) {
if (results.size() < k) { // 存的数小于K
results.add(input[i]);
} else {
Integer maxValue = results.last();
if (input[i] < maxValue) {
results.remove(maxValue);
results.add(input[i]);
}
}
}
return new ArrayList<>(results);
}
}
题目描述
3.HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。你会不会被他忽悠住？(子向量的长度至少是1)
package com.ustc.algorithm;
/**
* @author 王聪
* @version 创建时间：2017年3月3日 下午4:28:03
* 类说明
*/
public class MaxSubArray {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
public int FindGreatestSumOfSubArray(int[] array) {
// 1.judge is null
if (array == null || array.length == 0) {
return 0;
}
// 2.如果前面的和小于等于0，则将sum设为当前值，反之加上当前数
int nsum = 0;
int nGreastestSum = -1;
for (int i = 0; i < array.length; i++) {
if (nsum <=0) {
nsum = array[i];
} else {
nsum += array[i];
}
if (nsum > nGreastestSum) {
nGreastestSum = nsum;
}
}
return nGreastestSum;
}
}
4.输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
package com.ustc.algorithm;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
/**
* @author 王聪
* @version 创建时间：2017年3月17日 下午3:59:02
* 类说明
*/
public class PrintMinNumber {
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] numbers = {3,352,321};
System.out.println(new PrintMinNumber().PrintMinNumber(numbers));
}
public String PrintMinNumber(int [] numbers) {
ArrayList<Integer> arrayList = new ArrayList<>();
StringBuffer sBuffer = new StringBuffer();
for (int i = 0; i < numbers.length; i++) {
int value = numbers[i];
arrayList.add(value);
}
// 对其中两个数进行排序，按照两个数比较的顺序
Collections.sort(arrayList, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
String str1 = o1+""+o2;
String str2 = o2+""+o1;
return str1.compareTo(str2);
}
});
for (Iterator iterator = arrayList.iterator(); iterator.hasNext();) {
Integer value = (Integer) iterator.next();
sBuffer.append(value);
}
return sBuffer.toString();
}
}
题目概述
5.在一个字符串(1<=字符串长度<=10000，全部由大写字母组成)中找到第一个只出现一次的字符,并返回它的位置
package com.ustc.algorithm;
import java.util.HashMap;
/**
* @author 王聪
* @version 创建时间：2017年3月17日 下午4:52:29
* 类说明
*/
public class FindNoRepeatingChar {
public static void main(String[] args) {
// TODO Auto-generated method stub
String string = "hasahdjsa";
System.out.println(new FindNoRepeatingChar().FirstNotRepeatingChar(string));
}
// 使用HashMap存储字符串的每个字符出现的长度
public int FirstNotRepeatingChar(String str) {
if (str.length() == 0 || str == null) {
return -1;
}
HashMap<Character, Integer> map = new HashMap<>();
char[] strArray = str.toCharArray();
for (char c : strArray) {
Character key = new Character(c);
Integer count = map.get(key);
if (count != null) {
map.put(key, count+1);
} else {
map.put(key, 1);
}
}
int number = 0;
for (char c : strArray) {
Character key = new Character(c);
Integer count = map.get(key);
if (count == 1) {
return number;
}
number++;
}
return 0;
}
}
