leetcode java刷题笔记
Leetcode Java刷题笔记
Leetcode是一个在线的算法题库，拥有近千道算法题，因其对算法、数据结构、面试题等领域有着深入浸透的探究，备受程序员们的热爱。本人日常以Java作为主力语言，刷题些许之后，总结了一些切中要害、易于理解的笔记。
java笔记总结
1. 数组、链表
数组、链表是非常基础、重要的数据结构，Leetcode也是重点考察这两类基础数据结构的算法题。
Java中数组的初始化可以采用以下方式：
int[] arr = new int[]{1,2,3}; // 显示赋值
int[] arr2 = {1,2,3}; // 简化赋值
而链表的节点定义一般如下：
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
需要掌握“哑节点”技巧，即在头节点前添加一个节点，使初始情况下链表头的操作也能同样适用于中间、尾巴等节点的操作。链表题目中涉及多个指针时，往往需要“快慢指针”，即一个指针每次走两步，另一个每次走一步，实现特定目的。
2. 栈、队列
栈（Stack）和队列（Queue）同样是高频考点。在Java中，可以采用以下方式实现：
Stack<Integer> stack = new Stack<>(); // 栈的定义，其中可以存储整数类型
stack.push(1); // 入栈
stack.pop(); // 出栈
Queue<Integer> queue = new LinkedList<>(); // 队列的定义，其中可以存储整数类型
queue.offer(1); // 入队
queue.poll(); // 出队
很多栈和队列的题目都是具有括号匹配、中缀后缀表达式等特点的问题，需要掌握转化思路。
3. 回溯法
回溯法（backtracking）主要用于在搜索问题的解空间树中查问题的解，其算法思路是“回溯”不断地试探与撤销。Java中可以采用以下模板实现：
private void backtrack(int[] nums, List<Integer> track) {
    // 终止条件
    if (track.size() == nums.length) {
        res.add(new ArrayList<>(track));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        // 做选择，若不合法则跳过
        if (ains(nums[i])) {
            continue;
        }
        track.add(nums[i]);
        // 递归
        backtrack(nums, track);
        // 撤销选择
        ve(track.size()-1);
    }
}
4. 动态规划
动态规划（Dynamic Programming）常常用于求解最优解问题，在LeetCode中也是重点考察的算法问题。其中最典型的问题便是“背包问题”，即在体积/重量有限的情况下如何在含有价值物品集合中装载最值得花费的物品。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。