从C++过渡到Java做算法题

输入

• 重定向输入

• 以及如何读入数据

FileInputStream fis=new FileInputStream("data.txt");
System.setIn(fis);

Scanner reader=new Scanner(System.in);
int N=reader.nextInt();
int M=reader.nextInt();
String str=reader.next();
System.out.println(N);
System.out.println(str);

字符串

判断是否是回文

public boolean isPalindrome(int x) {
    String reversedStr = (new StringBuilder(x + "")).reverse().toString();
    return (x + "").equals(reversedStr);
}

反转字符串

StringBuilder有reverse()
String无reverse()

如何修改一个字符

String不能修改一个字符，只能使用StringBuilder的setCharAt

StringBuilder sb=new StringBuilder("Asdf");
sb.setCharAt(0,'Z');
System.out.println(sb.toString());

Map

常用：

Map<Integer,Integer>map=new HashMap<>();
map.put(0,1);
map.containsKey(0);
map.containsValue(1);
map.get(0);
map.getOrDefault(1,3);

Sort

注意是左闭右开

Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 };    // 数组类型为Integer
Arrays.sort(a,1,4);  
for (int arr : a) {
    System.out.print(arr + " ");
}

自定义排序1 （toArray，这样可以定义排序范围）

Arrays.sort接受的第一个参数一定要是一个数组，不能是一个List类

Comparator<Integer> cmp2 = new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return o2 - o1;
    }
};
List<Integer> l2 = Arrays.asList(new Integer[]{4, 1, 2, 3});
Integer[] arr2 = new Integer[l2.size()];
Arrays.sort(l2.toArray(arr2), 0, l2.size()-1, cmp2);  //转换成Integer[]

for (int i : arr2) {
    System.out.print(i + " ");
}

自定义排序2 （List，不能确定范围，只能整个List排序）

class Stu {
    public int id, score;

    public Stu(int id, int score) {
        this.id = id;
        this.score = score;
    }

    @Override
    public String toString() {
        return "Stu{" +
            "id=" + id +
            ", score=" + score +
            '}';
    }
}

Comparator<Stu> cmp = new Comparator<Stu>() {
    @Override
    public int compare(Stu o1, Stu o2) {
        if (o1.score != o2.score) return o2.score - o1.score;
        return o1.id - o2.id;
    }
};

List<Stu> lst = new ArrayList<>();
lst.add(new Stu(2, 98));
lst.add(new Stu(3, 99));
lst.add(new Stu(1, 99));

lst.sort(cmp);
for(Stu s:lst){
    System.out.println(s);
}
System.out.println(cmp.compare(lst.get(0),lst.get(1)));

数组转换

// 注意必须是Integer[]，如果是int[]就必须手动转化为List，（there is no shortcut）
Integer[] a = { 9, 8, 7, 2, 3, 4, 1, 0, 6, 5 };
List <Integer>lst=Arrays.asList(a);
for(int i:lst){
    System.out.print(i+" ");
}
System.out.println();
Collections.reverse(lst);
for(int i:lst){
    System.out.print(i+" ");
}

队列 queue

107. 二叉树的层次遍历 II

queue必须用new LinkedList

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();

        Queue<TreeNode> q = new LinkedList<>();
        if (root != null) q.offer(root);
        while (!q.isEmpty()) {
            int n = q.size();
            List<Integer> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                TreeNode t = q.peek();
                q.poll();
                if (t.left != null) q.offer(t.left);
                if (t.right != null) q.offer(t.right);
                tmp.add(t.val);
            }
            res.add(0, tmp);
        }
        return res;
    }
}

stack

1	boolean empty() 测试堆栈是否为空。
2	Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
3	Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
4	Object push(Object element) 把项压入堆栈顶部。
5	int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。

Stack<Integer> st = new Stack<Integer>();

List

List<Integer>lst=new ArrayList<>();

添加add;
删除remove;
设置set(index,val);
获取get(index);