LeetCode 专栏

开始有计划刷题，刷一些常见的面试题，答案都是我自己能找到并理解的最优解，监督自己，持续更新。

简单

121. 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/be…

java复制代码class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0 || prices == null)
            return 0;
        int minProfit = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (minProfit > prices[i]) {
                minProfit = prices[i];
            }
            if (prices[i] - minProfit > maxProfit) {
                maxProfit = prices[i] - minProfit;
            }
        }
        return maxProfit;
    }
}

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

来源：力扣（LeetCode）链接：leetcode-cn.com/problems/me…

java复制代码class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode cur = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        if (l1 == null) {
            cur.next = l2;
        } else {
            cur.next = l1;
        }
        return dummyHead.next;
    }
}

234. 回文链表

请判断一个链表是否为回文链表。

输入: 1->2

输出: false

输入: 1->2->2->1

输出: true

思路：如果一个链表是回文链表，那么将链表对折，对折后的两个链表上各值应该是相等的。（从今天开始，增加解题思路 20210407）

java复制代码class Solution {
    public boolean isPalindrome(ListNode head) {
        if (head == null || head.next == null)
            return true; 
        ListNode slow = head, fast = head;
        // 找中位，对折
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        // 反转后半段
        slow = revserseList(slow.next);
        // 将对折的两半链表各值做对比
        while (slow != null) {
            if (head.val != slow.val) {
                return false;
            }
            head = head.next;
            slow = slow.next;
        }
        return true;
    }
    // 反转链表（专门有一道题是反转链表，这就是答案）
    private ListNode revserseList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

哦对了，今天看到一个校招狠人在面试字节的时候，考算法时采用的是 acm 形式，即编程的一切都要自己手写，比如题中的 ListNode 也要自己定义，今天开始也要记录一下题中的一些定义类型，提前适应节奏。

java复制代码  public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }

409. 最长回文串

给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。

在构造过程中，请注意区分大小写。比如 “Aa” 不能当做一个回文字符串。

注意:
假设字符串的长度不会超过 1010。

示例1：

输入:

“abccccdd”

输出:

7

解释:

我们可以构造的最长的回文串是”dccaccd”, 它的长度是 7。
来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/lo…

思路：能组成回文字符的一组字符中，里面的字符都是偶数个，如 “abba”。但是我们可以在中间加一个字符，如“abcba”，所以我们先统计出偶数的字符再加 1 就是最长回文字符。

java复制代码class Solution {
    public int longestPalindrome(String s) {
        int cArr = new int[128];
        for (char c : s.toCharArray()) {
            cArr[c]++;
        }
        int count = 0;
        for (int i : arr) {
            count += (i % 2);
        }
        return count == 0 ? s.length() : (s.length() - count + 1);
    
    }
    
}

1. 两数之和（20210413）

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

java复制代码class Solution {
    public int[] twoSum(int[] nums, int target) {
        if (nums == null || nums.length <= 1)
            return nums;
        int[] res = new int[2];
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int val = target - num;
            if (map.containsKey(val)) {
                res[0] = i;
                res[1] = map.get(val);
                return res;
            } else {
                map.put(num, i);
            }
        }
        return res;
    }
}

来源：力扣（LeetCode）

链接：leetcode-cn.com/problems/tw…

中等

15. 三数之和

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

来源：力扣（LeetCode）链接：leetcode-cn.com/problems/3s…

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

java复制代码class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        Set<List<Integer>> res = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int l = i + 1, r = n - 1;
            while (l < r) {
                if (nums[i] + nums[l] + nums[r] == 0) {
                    res.add(Arrays.asList(nums[i], nums[l],nums[r]));
                    l++;
                    r--;
                } else if (nums[i] + nums[l] + nums[r] < 0) {
                    l++;
                } else {
                    r--;
                }
            }
        }
        List<List<Integer>> ans = new ArrayList<>();
        ans.addAll(res);
        return ans;
    }
}

103.二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

java复制代码    3
   / \
  9  20
    /  \
   15   7

返回锯齿形层序遍历如下：

java复制代码[
  [3],
  [20,9],
  [15,7]
]

java复制代码class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        boolean leftToRight = true;
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode node = queue.poll();
                if (leftToRight == true) {
                    list.add(node.val);
                } else {
                    list.add(0, node.val);
                }
                if (node.left  != null) {
                    queue.add(node.left);
                } 
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            leftToRight = !leftToRight;
            res.add(list);
        }
        return res;
    }
}

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/bi…

146. LRU 缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/lr…

java复制代码class LRUCache {
    private int capacity;
    private HashMap<Integer,Node> map;
    private Node head,tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);

        head = new Node (0,0);
        tail = new Node (0,0);

        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        // 如果找不到就返回 -1
        if (!map.containsKey(key)) {
            return -1;
        }
        // 找到了就返回 value 并将其放到第一位
        Node node = map.get(key);
        this.moveNode2First(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        // 重复替换
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            this.moveNode2First(node);
            return;
        }
        // 容量满了，就抛弃最后一个
        if (map.size() == capacity) {
            Node last = tail.prev;
            this.map.remove(last.key);
            this.removeLast(last);
        }
        Node node = new Node(key, value);
        map.put(key,node);
        this.addNode2First(node);
    }
    public void moveNode2First (Node node) {
        Node next = node.next;
        Node prev = node.prev;

        prev.next = next;
        next.prev = prev;
        addNode2First(node);
    }
    public void addNode2First (Node node) {
        Node curNode = head.next;
        curNode.prev = node;
        head.next = node;

        node.next = curNode;
        node.prev = head;
    }
    public void removeLast (Node last) {
        Node prev = last.prev;
        prev.next =tail;
        tail.prev = prev;

        last.next = null;
        last.prev = null;
    }
    public class Node {
        private Node next;
        private Node prev;
        private int key, value;
        public Node(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
}

199.二叉树的右视图(20210409)

给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例:

java复制代码public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(){}
    public TreeNode(int val){this.val = val;}
    public TreeNode(int val, TreeNode left,TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root); 
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = q.poll();
                // 添加左节点
                if (node.left != null) {
                    q.offer(node.left);
                }
                // 添加右节点
                if (node.right != null) {
                    q.offer(node.right);
                }
                // 将最后一个节点添加到结果集
                if (i == size - 1) {
                    res.add (node.val);
                }
            }
        }
        return res;

    }
}

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/bi…

209. 长度最小的子数组（20210410）

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例1：

输入：target = 7, nums = [2,3,1,2,4,3]

输出：2

解释：子数组 [4,3] 是该条件下的长度最小的子数组。

java复制代码class Solution {
    // 滑动窗口，先设置左右边界 left、right
    public int minSubArrayLen(int target, int[] nums) {
        int left = -1, right = -1;
        int sum = 0, minLen = Integer.MAX_VALUE;
        // 如果和小于 target，那么我们就移动右边界
        while (left <= right) {
            if (sum < target) {
                right++;
                if (right >= nums.length) {
                    break;
                }
                sum += nums[right];
            } else {
                // 如果大于等于 targert 我们就移动左边界
                // 同时，如果此时数组长度小于最小程度，那么我们更新最小长度。
                if (right - left < minLen) 
                    minLen = right - left;
                left++;
                if (left > right)
                    break;
                sum -= nums[left];  
            }
            
        }
        return minLen == Integer.MAX_VALUE? 0: minLen;
    }
}

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/mi…

困难

25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

来源：力扣（LeetCode）
链接：leetcode-cn.com/problems/re…

java复制代码class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || head.next == null)
            return head;
        ListNode tail = head;
        // 想象成将一个长链表分段
        for (int i = 0; i < k; i++) {
            if (tail == null) return head;
            tail = tail.next; 
        } 
        ListNode newHead = reverse(head, tail);
        head.next = reverseKGroup(tail, k);
        return newHead;
    }
    // 反转局部链表
    private ListNode reverse (ListNode head, ListNode tail) {
        ListNode pre = null, next = null;
        while (head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

简单