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());

}

}

_

评论

暂无评论