java算法技巧

1. 数组转集合

   int[] nums = new int[]{0,1,2,1};
   Set<Integer> set = new HashSet<>();
   for(int v : nums){
       set.add(v);
   } 

2. 引用类型数组转集合

   //利用Arrays工具类中的asList方法
   Integer[] arr = {1,2,3};
   ArrayList<Integer> list = new ArrayList<>(Arrays.asList(arr));
   
   //利用Collections工具类中的addAll方法
   Integer[] arr = {1,2,3};
   ArrayList<Integer> list = new ArrayList<>(array.length);
   Collections.addAll(list, arr);

3. 集合转数组

   Integer[] arrs = set.toArray(new Integer[set.size()]);

4. 增强/普通 for循环

当使用增强 for 循环时，循环变量（这里是 num）实际上是集合中元素的一个副本，而不是对集合中元素本身的直接引用。也就是说，在循环体内对 num 进行的任何修改操作（如 num++），都只会影响这个副本，而不会对集合中的原始元素产生任何影响。

普通for循环，可以修改

4. 排序
   return -1 ： 不交换位置
   return 1 ： 交换位置
   return 0:不交换位置，不排序

   Arrays.sort(res,new Comparator<Integer>(){
       public int compare(Integer a,Integer b){
           if(a<=b) return -1;
           return 1;
       }
   });

5. 字符串和数字

   // 字符串转数字
   		String str = "123";
   		int number = Integer.parseInt(str);		
   		System.out.println(number);
   
   // 数字转字符串 method1
   		int number = 5;
   		String str = String.valueOf(number);
   		System.out.println(str);
   
   // 数字转字符串 method2
   		int number = 5;
   		Integer itr = number;  //int装箱为对象，再调用对象的toString方法
   		String str = itr.toString(); //或者直接 String str = Integer.toString(number);
   		System.out.println(str);

6. 运算向上取整

   int t = (int)Math.ceil((double)n / (2*k)); 
   //向上取整(不能直接➕1，因为如果是除法结果恰好是整数的话会多一次)

字符串

1. 去除空白

   String[] arr = s.trim().split(" +"); 
   //先用trim去除首尾空白；
   /*
   对于中间的多个空格，使用split(" +")来进行匹配：
   这里的 + 表示匹配一个或多个空格，这样连续的空格就会被当作一个分隔符来处理
   */

栈和队列

1. stack类
   它继承自java.util.Vector，这意味着它包含了一些在栈操作中通常不需要的同步方法，可能会导致性能开销。在单线程环境下，这些同步操作是不必要的。

• pop()
• push()
• peek()

  import java.util.Stack;
  public class StackExample {
      public static void main(String[] args) {
          Stack<Integer> stack = new Stack<>();
          stack.push(1);
          stack.pop();
          stack.push(3);
          int topElement = stack.peek();
          System.out.println(topElement); // 输出3
          System.out.println(stack.size()); // 输出1
      }
  }

2. Deque接口
   该双端队列可以实现栈和队列；
   Deque的实现类有许多，但是我们平时用不考虑多线程，使用ArrayDeque、LinkedList就足够了

栈的对应方法：

使用java.util.ArrayDeque实现栈（推荐）

import java.util.ArrayDeque;
public class StackUsingArrayDeque {
    public static void main(String[] args) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(1);
        stack.push(2);
        System.out.println(stack.pop());
    }
}

队列的对应方法：

使用java.util.ArrayDeque作为队列（推荐）

import java.util.ArrayDeque;
import java.util.Queue;
public class QueueUsingArrayDeque {
    public static void main(String[] args) {
        Deque<Integer> queue = new ArrayDeque<>();
        queue.add(1);
        queue.add(2);
        System.out.println(queue.poll());
    }
}

3. 优先队列

基于元素自身的 Comparable 接口实现：
Integer/Double：按照数值大小从小到大排序

import java.util.PriorityQueue;

public class PriorityQueueWithComparableExample {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(5);
        pq.add(3);
        pq.add(8);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

通过自定义比较器（Comparator）确定优先级:

• 实现Comparator 接口
• 重写compare方法

  import java.util.Comparator;
  import java.util.PriorityQueue;
  
  class Student {
      String name;
      int score;
  
      public Student(String name, int score) {
          this.name = name;
          this.score = score;
      }
  
      @Override
      public String toString() {
          return "Student{" +
                  "name='" + name + "' +
                  ", score=" + score +
                  '}';
      }
  }
  
  class ScoreComparator implements Comparator<Student> {
      @Override
      public int compare(Student s1, Student s2) {
          return s1.score - s2.score;
      }
  }
  
  public class PriorityQueueWithComparatorExample {
      public static void main(String[] args) {
          PriorityQueue<Student> pq = new PriorityQueue<>(new ScoreComparator());
          pq.add(new Student("Alice", 80));
          pq.add(new Student("Bob", 90));
          pq.add(new Student("Charlie", 70));
  
          while (!pq.isEmpty()) {
              System.out.println(pq.poll());
          }
      }
  }

Map的排序

Map.entrySet() 转换成 List 进行排序
tips:排序之后的list是有序的，而原来的map还是无序的

List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());
Collections.sort(list,new Comparator<Map.Entry<Integer,Integer>>(){
    @Override
    public int compare(Map.Entry<Integer,Integer> o1, Map.Entry<Integer,Integer> o2){
        return o1.getValue().compareTo(o2.getValue());
    }
});
for (Map.Entry<Integer, Integer> entry : list) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}
System.out.println(map);