java中常用的算法
文章目录
去重1.1 去重
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
//去重复,需要额外定义一个List
public static void RemoveRepeat(List<Integer> arrs) {
List<Integer> tmp = new ArrayList<Integer>();
Iterator<Integer> it = arrs.iterator();
while (it.hasNext()) {
int a = it.next();
if (tmp.contains(a))
it.remove();
else
tmp.add(a);
}
}
1.2 去不重
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
public static void RemoveNotRepeat(List<Character> arrs)
{
Map<Character,Integer> tmp=`new HashMap();`
for`(`char c:arrs)
{
if`(tmp.containsKey(c))`
tmp.put(c,tmp.get(c)+`1`);
else
tmp.put(c,`1`);
}
Iterator<Character> it=arrs.iterator();
while (it.hasNext())
{
Character c=it.next();
if`(tmp.get(c)==1)`
it.remove();
}
}
2 随机分配
定义方法实现,把两个List中的内容随机配对,并保存到Map中。
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
public static Map<String, String> TicketDispatch(List<String> customers, List<String> tickets) {
Map<String, String> result = new HashMap<String, String>();
Random r = new Random();
int iCustomer;
int iTicket;
for (`int i = customers.size(); i > 0`; i--) {
// 取值范围[0,i)
iCustomer = r.nextInt(i);
iTicket = r.nextInt(tickets.size());
result.put(customers.get(iCustomer), tickets.get(iTicket));
customers.remove(iCustomer);
tickets.remove(iTicket);
}
return result;
}
3 递归
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
//Java递归删除一个目录下文件和文件夹
private static void deleteDir(File dir) {
if (dir.isDirectory()) {
String[] children = dir.list();
// 递归删除目录中的子目录下
for (`int i=0; i<children.length; i++) {`
deleteDir(`new File(dir, children[i])); `
}
}
dir.delete();
}
_
4 内部排序变形
4.1 取数组中未出现的最小整数
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static Integer GetNotExitMinInteger(Integer[] arr)
{
Integer minIndex;
Integer tmp;
Integer first=`0`;
for`(int` `i=0`;i<arr.length;i++)
{
minIndex=i;
for`(int` `j=i+1`;j<arr.length;j++)
{
if`(arr[minIndex]>arr[j])`
minIndex=j;
}
if`(arr[minIndex]-first>1)`
return first+`1`;
else
{
first=arr[minIndex];
}
if`(minIndex!=i)`
{
tmp=arr[i];
arr[i]=arr[minIndex];
arr[minIndex]=tmp;
}
}
return arr[arr.length-`1]+1`;
}
上面问题其他解决方案:
也可先排序(快速排序,若范围可确定,且不到,可用桶排序),在先后比较arr[next]-arr[one]>1
HashMap实现
_
_
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public static Integer GetNotExitMinIntegerByHashMap(Integer[] arr) {
Integer minKey=Integer.MAX_VALUE;
Integer maxKey=Integer.MIN_VALUE;
Map<Integer,Integer> map=`new HashMap<Integer,Integer>();`
for`(int` `i=0`;i<arr.length;i++)
{
map.put(arr[i],arr[i]);
if`(minKey>arr[i])`
minKey=arr[i];
if`(maxKey<arr[i])`
maxKey=arr[i];
}
Integer pre=minKey;
if`(minKey>1)`
return minKey-`1`;
while`(pre<=maxKey) {`
if`(map.get(pre+1)==null)`
return pre+`1`;
else
++pre;
}
return maxKey+`1`;
}
_
______5 字符串
5.1 全排序___
思路:
n个字符
_
- 前n-1个固定,第n个,不能再互换,打印排列
- 前n-2个固定,第n-1个和n位置互换,得到排列
- 前n-3个固定,第n-2个分别和最后两个位置互换
- ...
_
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class FullPermutation {
public static void main(String[] args)
{
char`[] arr=new` `char[]{'A','B','C','D'};`
Permutatition(arr);
}
public static void Permutatition(`char`[] arr)
{
recursivePermutation(arr,`0,arr.length-1`);
}
private static void recursivePermutation(`char[] arr,int start,`int end)
{
if`(start==end) {`
for (`int i = 0`; i <= end; i++)
System.out.print(arr[i]);
System.out.println();
}
else {
for (`int i = start; i <= end; i++) {`
swap(arr, start, i);
recursivePermutation(arr, start+`1`, end);
swap(arr, start, i);
}
}
}
private static void swap(`char[] arr,int left,`int right)
{
char tmp=arr[left];
arr[left]=arr[right];
arr[right]=tmp;
}
}
5.2 出现频率最高10位数___
_______hashmap按值,按排序
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put(`"c",` `"ccccc");`
map.put(`"a",` `"aaaaa");`
map.put(`"b",` `"bbbbb");`
map.put(`"d",` `"ddddd");`
List<Map.Entry<String,String>> list = new ArrayList<Map.Entry<String,String>>(map.entrySet());
Collections.sort(list,`new Comparator<Map.Entry<String,String>>() {`
//升序排序
public int compare(Entry<String, String> o1,
Entry<String, String> o2) {
return o1.getValue().compareTo(o2.getValue());
}
});
for`(Map.Entry<String,String> mapping:list){`
System.out.println(mapping.getKey()+`":"`+mapping.getValue());
}
}
Lambda简化版
[Java]纯文本查看__复制代码
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
public static void main(String[] args)
{
Map<String, String> map = new HashMap<String, String>();
map.put(`"c",` `"ccccc");`
map.put(`"a",` `"daaaa");`
map.put(`"b",` `"bbbbb");`
map.put(`"d",` `"ddddd");`
List<Map.Entry<String, String>> list=`new ArrayList<Map.Entry<String,String>>(map.entrySet());`
list.sort((o1,o2)-> o1.getValue().compareTo(o2.getValue()));
for`(Map.Entry<String,String> mapping:list){`
System.out.println(mapping.getKey()+`":"`+mapping.getValue());
}
}
_
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论