Category: LeetCode

Posted 2022-04-30Updated 2022-04-29LeetCode / Medium2 minutes read (About 259 words)

1249. Minimum Remove to Make Valid Parentheses

Given a string s of ‘(‘ , ‘)’ and lowercase English characters.

Your task is to remove the minimum number of parentheses ( ‘(‘ or ‘)’, in any positions ) so that the resulting parentheses string is valid and return any valid string.

Formally, a parentheses string is valid if and only if:

It is the empty string, contains only lowercase characters, or

It can be written as AB (A concatenated with B), where A and B are valid strings, or

It can be written as (A), where A is a valid string.

用栈储存括号，按顺序将括号压入栈。
如果和上一个括号配对，则挤出上一个括号。

当栈不为空时，如果栈顶的符号为“)”，则优先去掉字符串左侧的括号。
如果栈顶的符号为“(”，则优先去掉字符串右侧的括号。
最后返回字符串。

class Solution {
    public String minRemoveToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        StringBuffer sb = new StringBuffer(s);
        
        for(int i = 0; i < s.length(); i++){
            if(s.charAt(i) == '(') stack.push('(');
            else if(s.charAt(i) == ')'){
                if(!stack.isEmpty() && stack.peek() == '(') stack.pop();
                else stack.push(')');
            }
        }
        
        while(!stack.isEmpty()){
            if(stack.pop() == ')'){
                int index = sb.indexOf(")");
                sb.delete(index, index+1);
            }
            else{
                int index = sb.lastIndexOf("(");
                sb.delete(index, index+1);
            }
        }        
        return sb.toString();
    }
}

Posted 2022-04-30Updated 2022-04-29LeetCode / Easy / 复习a minute read (About 203 words)

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Implement the MinStack class:

MinStack() initializes the stack object.

void push(int val) pushes the element val onto the stack.

void pop() removes the element on the top of the stack.

int top() gets the top element of the stack.

int getMin() retrieves the minimum element in the stack.

分别将数据保存在一个Priority Queue和一个栈中。
pop方法pop掉stack的内容，然后将其从优先队列中移除。
top方法返回stack的栈顶。
getMin方法返回优先队列的顶。

class MinStack {
    Queue<Integer> pq;
    Stack<Integer> stack;
    public MinStack() {
        pq = new PriorityQueue<>();
        stack = new Stack<>();
    }
    
    public void push(int val) {
        pq.add(val);
        stack.add(val);
    }
    
    public void pop() {
        int i = stack.pop();
        pq.remove(i);
        
    }
    
    public int top() {
        return stack.peek();
    }
    
    public int getMin() {
        return pq.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Posted 2022-04-29Updated 2022-04-29LeetCode / Mediuma minute read (About 189 words)

413. Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
Given an integer array nums, return the number of arithmetic subarrays of nums.

A subarray is a contiguous subsequence of the array.

动态规划，遍历一次记录所有数字的差。
然后遍历并计算连续相同的数字数量temp。
当不相同时，则计算temp长度可以选择的组合数，将其添加到count。

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {

        if(nums.length == 1) return 0;
        int[] difference = new int[nums.length-1];
        for(int i = 0; i < nums.length-1; i++){
            difference[i] = nums[i+1] - nums[i];
        }
        
        int count = 0;
        int temp = 1;
        int prev = difference[0];
        for(int j = 1; j < nums.length-1; j++){
            if(difference[j] == prev){
                temp++;
            }
            else{
                count += combinations(temp);
                temp = 1;
            }
            prev = difference[j];
        }
        count += combinations(temp);
        return count;
    }
    
    private int combinations(int n){
        return (n * (n-1)) / 2;
    }
}

Posted 2022-04-29Updated 2022-04-29LeetCode / Mediuma minute read (About 208 words)

62. Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time.

Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

The test cases are generated so that the answer will be less than or equal to 2 * 109.

动态规划，每一个位置的线路都等于其左侧和上侧的两条线路的加和。
将初始的两个边值设置为1，然后计算直至终点位置即可。

class Solution {
    int count;
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0; i < m; i++){
            dp[i][0] = 1;
        }
        for(int j = 0; j < n; j++){
            dp[0][j] = 1;
        }
        
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

Posted 2022-04-29Updated 2022-04-29LeetCode / Medium3 minutes read (About 385 words)

785. Is Graph Bipartite?

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:

There are no self-edges (graph[u] does not contain u).

There are no parallel edges (graph[u] does not contain duplicate values).

If v is in graph[u], then u is in graph[v] (the graph is undirected).

The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.
A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Return true if and only if it is bipartite.

原题等于问：每个节点与其相连接的节点是否可以颜色不同？
通过BFS搜索，将每一层通过开关flag分组。
创建一个visited数组，记录分组和遍历情况。
当节点被放入错误的分组时，返回false。

注意因为图里的各个节点可能不连接，因此需要遍历对所有节点进行BFS搜索，通过visited的情况进行剪枝。

class Solution {
    public boolean isBipartite(int[][] graph) {
        Queue<int[]> q = new LinkedList<>();
        int[] visited = new int[graph.length];
        
        for(int i = 0; i < graph.length; i++){
            boolean flag = false;
            if(graph[i].length == 0 || visited[i] != 0) continue;
            q.add(graph[i]);
            visited[i] = 1;
            int size = 1;
        
            while(!q.isEmpty()){
                for(int j = 0; j < size; j++){
                    int[] node = q.poll();
                    for(int next : node){
                        if(visited[next] == 0){
                            q.add(graph[next]);
                        }
                        if(flag){
                            if(visited[next] == 2) return false;
                            visited[next] = 1;
                        }
                        else{
                            if(visited[next] == 1) return false;
                            visited[next] = 2;
                        }
                    }
                }
                flag = !flag;
                size = q.size();
            }
        }
        return true;
    }
}

Posted 2022-04-28Updated 2022-04-28LeetCode / Medium / 复习3 minutes read (About 409 words)

1631. Path With Minimum Effort

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, or right, and you wish to find a route that requires the minimum effort.

A route’s effort is the maximum absolute difference in heights between two consecutive cells of the route.

Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

A*算法，启发式搜索。BFS搜索结合Priority Queue。
采用一个数组储存当前访问点的位置，以及其effort。
采用优先队列，优先搜索effort最小的方向。
每次循环倾倒出队列中所有的元素。
计算上一个节点和当前节点的差值作为nextEffort，并和上一个节点的effort作比较，较大的作为当前节点的effort，
将effort作为权重，优先搜索一个层级内effort较小的路径。
将所有操作加入队列，并排除越界的位置。
当当前节点为最后一个节点时，返回其effort。

class Solution {
    int min;
    public int minimumEffortPath(int[][] heights) {
        int[][] operations = {{1,0},{-1,0},{0,1},{0,-1}};
        int m = heights.length, n = heights[0].length;
        
        Queue<int[]> q = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        int[] point = {0, 0, 0};
        int size = 1;
        int[][] visited = new int[m][n];
        
        q.add(point);
        while(!q.isEmpty()){
            
            for(int k = 0; k < size; k++){
                int[] curr = q.poll();
                int i = curr[0], j = curr[1], currEffort = curr[2];
                if(visited[i][j] == 1) continue;
                visited[i][j] = 1;
                if(i == m-1 && j == n-1) return currEffort;
                for(int[] operation : operations){
                    int nextX = i + operation[0];
                    int nextY = j + operation[1];
                    if(nextX < 0 || nextY < 0 || nextX >= m || nextY >= n) continue;
                    int nextEffort = Math.max(currEffort, Math.abs(heights[i][j] - heights[nextX][nextY]));
                    int[] next = {nextX, nextY, nextEffort};
                    
                    q.add(next);
                }
            }
            size = q.size();
        }
        return -1;
    }
}

Posted 2022-04-28Updated 2022-04-27LeetCode / Medium / 复习a minute read (About 209 words)

45. Jump Game II

Given an array of non-negative integers nums, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

You can assume that you can always reach the last index.

设置一个当前可以访问的最大范围limit，在遍历中对其进行更新。
和当前可访问位置中的最远距离end，每次访问到达end时，计算步数。

遍历数组，比较limit和当前i能访问的最远距离i+nums[i]，保留较大值。
当i达到end时，更新end为之前记录的可访问最远距离limit。步数+1。

class Solution {
    public int jump(int[] nums) {
        int count = 0;
        int limit = 0;
        int end = 0;
        
        for(int i = 0; i < nums.length-1; i++){
            limit = Math.max(limit, i + nums[i]);
            if(i == end){
                end = limit;
                count++;
            }
        }
        
        return count;
    }
}

Posted 2022-04-28Updated 2022-04-28LeetCode / Hard / 复习3 minutes read (About 474 words)

25. Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes, in the end, should remain as it is.

You may not alter the values in the list’s nodes, only nodes themselves may be changed.

采用直接更改节点的方法可以使用O(1)的空间完成操作。

递归，DFS搜索，首先初始化一个哨兵节点。
将哨兵节点记录为first，下一个节点记录为second。

将first与second传入递归方法。
向下递归下一个节点，并将长度k-1。
当长度k等于1时，则递归到当前所需的栈底。将当前节点指向上一个节点，并将当前节点记录为last，下一个节点记录为next，返回true。
当curr为null时，返回false。

当递归返回为true时（即剩余的链表有k个节点以供翻转），上级的节点们都指向其前一个节点。当返回到的栈顶（即k等于最开始的值）时，将first指向last，将second指向next。

继续向下递归first与second。

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    int K;
    ListNode next;
    ListNode prev;
    ListNode last;
    ListNode first;
    ListNode second;
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k == 1) return head;
        
        K = k;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        prev = dummy;
        next = null;
        last = null;
        first = prev;
        second = prev.next;
        
        reverse(prev, dummy.next, k);
        
        return dummy.next;
    }
    
    private boolean reverse(ListNode prev, ListNode curr, int k){
        if(curr == null) return false;
        if(k == 1){
            last = curr;
            next = curr.next;
            curr.next = prev;
            return true;
        }
        
        if( reverse(curr, curr.next, k-1) ){
            curr.next = prev;
            if(k == K){
                first.next = last;
                second.next = next;
                first = curr;
                second = curr.next;
            
                reverse(first, second, k);
            }
            return true;
        }
        return false;
    }
    
    private void print(ListNode root){
        while(root != null){
            root = root.next;
        }
    }
}

Posted 2022-04-27Updated 2022-04-27LeetCode / Medium / 复习3 minutes read (About 484 words)

707. Design Linked List

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.
A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.
If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class:

MyLinkedList() Initializes the MyLinkedList object.

int get(int index) Get the value of the indexth node in the linked list. If the index is invalid, return -1.

void addAtHead(int val) Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list.

void addAtTail(int val) Append a node of value val as the last element of the linked list.

void addAtIndex(int index, int val) Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted.

void deleteAtIndex(int index) Delete the indexth node in the linked list, if the index is valid.

单链表，设置一个哨兵节点在头部。
设置辅助方法，取得index的前一个节点。
addAtHead和addAtTail都可以采用addAtIndex实现。

采用双链表速度可以更快。

class MyLinkedList {
    ListNode head;
    int size;
    public MyLinkedList() {
        ListNode dummy = new ListNode(0);
        head = dummy;
        size = 0;
    }
    
    public ListNode getPrev(int index){
        ListNode prev = head;
        for(int i = 0; i < index; i++){
            prev = prev.next;
        }
        return prev;
    }
    
    public int get(int index) {
        if(index >= size) return -1;
        return getPrev(index).next.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0, val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size, val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index > size) return;
        ListNode prev = getPrev(index);
        ListNode temp = prev.next;
        prev.next = new ListNode(val);
        prev.next.next = temp;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index >= size) return;
        if(index == size-1){
            ListNode prev = getPrev(index);
            prev.next = null;
            size--;
            return;
        }
        ListNode prev = getPrev(index);
        prev.next = prev.next.next;
        size--;
    }
    
    private void print(){
        ListNode root = head.next;
        while(root != null){
            System.out.print(root.val+" ->   ");
            root = root.next;
        }
        System.out.println("Size:   "+size);
    }
    
    class ListNode{     
        int val;
        ListNode next;
        public ListNode(int v){
            val = v;
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

Posted 2022-04-27Updated 2022-06-25LeetCode / Medium / 复习2 minutes read (About 353 words)

1202. Smallest String With Swaps

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string.

You can swap the characters at any pair of indices in the given pairs any number of times.

Return the lexicographically smallest string that s can be changed to after using the swaps.

并查集，注意要使用路径压缩否则会超时。
先将所有配对联通。然后创建一个数组group记录每个字符串位置的分组情况。
根据分组，借助优先队列保存字符串。
通过哈希表创建group和PriorityQueue的映射。
按当前位置的分组情况和优先队列的顺序来添加字符串。
最后返回字符串。

class Solution {
    public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
        StringBuffer sb = new StringBuffer();
        UnionFind uf = new UnionFind(s.length());
        
        for(List<Integer> pair : pairs){
            uf.union(pair.get(0), pair.get(1));    
        }
        
        int[] group = new int[s.length()];
        for(int i = 0; i < s.length(); i++){
            group[i] = uf.find(i);
        }
        
        HashMap<Integer, PriorityQueue<Character>> map = new HashMap<>();
        
        for(int i = 0; i < s.length(); i++){
            PriorityQueue<Character> bin = map.getOrDefault(group[i], new PriorityQueue<Character>());
            bin.add(s.charAt(i));
            map.put(group[i], bin);
        }
        for(int i = 0; i < s.length(); i++){
            sb.append(map.get(group[i]).poll());
        }
        return sb.toString();
    }
    
    class UnionFind {
        int[] parent;
        int[] count;
        public UnionFind(int n){
            parent = new int[n];
            count = new int[n];
            for(int i = 0; i < n; i++){
                parent[i] = i;
                count[i] = 1;
            }
        } 
        
        private int find(int id){
            if(parent[id] == id) return id;
            parent[id] = find(parent[id]);
            return parent[id];
        }
        
        private boolean union(int id1, int id2){
            int p1 = find(id1);
            int p2 = find(id2);
            if(p1 == p2) return false;
            if(count[p1] > count[p2]) parent[p2] = p1;
            else parent[p1] = p2;
            return true;
        }
    }
}

Posted 2022-04-27Updated 2022-04-26LeetCode / Medium / 复习3 minutes read (About 440 words)

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

反向查找，动态规划。
到达目标点前必须到达上一个节点，且上一个节点能前进的步数必须大于目标点。
设置目标点goal，反向遍历goal以外的点。
如果该点能前进的步数加上自身的位置i大于目标点，则可以从上一个点到达goal。
更新goal的位置到上一个点。
如果遍历结束后，能返回到起始点0，则可以到达终点。

class Solution {
    public boolean canJump(int[] nums) {
        int goal = nums.length-1;
        for(int i = nums.length-2; i >=0; i--){
            if(nums[i] >= goal - i) goal = i;
        }
        return goal == 0;
    }
}

贪心算法，储存一个到i时可以到达的最远值maxJump。
遍历数组，如果i大于maxJump，则无法到达下一个点，返回false。
在当前点可以到达的最大范围为nums[i]+i，如果大于maxJump则更新该值。
遍历完毕返回true。

class Solution {
    public boolean canJump(int[] nums) {
        int maxJump = 0;
        for(int i = 0; i < nums.length; i++){
            if(i > maxJump) return false;
            maxJump = Math.max(maxJump, nums[i] + i);
        }
        return maxJump >= nums.length-1;
    }
}

设置一个数组记录可访问的范围。
当遍历时，如果可以访问，则将当前位置可以进一步访问的位置变为1。
如果访问范围大于等于数组末尾，则返回真。

class Solution {
    public boolean canJump(int[] nums) {
        int[] reach = new int[nums.length];
        reach[0] = 1;
        
        for(int i = 0; i < nums.length; i++){
            if(reach[i] == 1){
                if(i == nums.length-1) return true;
                for(int j = 0; j < nums[i]; j++){
                    if(i+j+1 >= nums.length) return true;
                    reach[i+j+1] = 1;
                }
            }
        }
        return false;
    }
}

Posted 2022-04-26Updated 2022-04-26LeetCode / Medium / 复习2 minutes read (About 291 words)

213. House Robber II

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

动态规划，和普通的动态规划不同的是这道题是首尾相连的。
因此分两种情况讨论——如果选择了头，就不选择尾。反之亦然。
建立两个动态规划表，分别选择第一个和第二个数字作为第一次抢劫的目标。
前一个最多抢劫到倒数第一个房子，后一个最多抢劫到最后一个房子。

class Solution {
    public int rob(int[] nums) {
        if(nums.length == 1) return nums[0];
        
        int max = 0;
        int[] dp = new int[nums.length+1];
        int[] dp2 = new int[nums.length+1];
        dp[1] = nums[0];

        for(int i = 2; i < nums.length; i++){
            dp[i] = Math.max(dp[i-2] + nums[i-1], dp[i-1]);
        }

        dp2[2] = nums[1];
        
        for(int i = 3; i <= nums.length; i++){
            dp2[i] = Math.max(dp2[i-2] + nums[i-1], dp2[i-1]);
        }
        
        return Math.max(dp[dp.length-2], dp2[dp2.length-1]);
    }
}

Posted 2022-04-26Updated 2022-04-26LeetCode / Medium / 复习2 minutes read (About 267 words)

24. Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

先建立一个哨兵节点，next指向head。
交换时同时传入前一个节点pre和当前节点root。
当当前节点非null且下一个节点非null，则可以交换两个节点。
首先保存当前节点的下一个节点next和下一个节点的下一个节点last。

1.将pre指向next。
2.将next指向root。
3.将root指向last。
4.处理下一组节点，root作为pre，root.next作为root递归。
最后返回哨兵节点的next。

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        swap(dummy, head);
        return dummy.next;
    }
    
    private void swap(ListNode pre, ListNode root){
        if(root == null || root.next == null){
            return;
        }
        else if(root != null && root.next != null){
            
            ListNode last = root.next.next;
            ListNode next = root.next;
            pre.next = next;
            next.next = root;
            root.next = last;
        }
        swap(root, root.next);
    }
}

Posted 2022-04-26Updated 2022-04-26LeetCode / Easy2 minutes read (About 353 words)

160. Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

计算两个链表的长度。将长的链表向下移动两者长度的差，对齐两个链表的长度。
同时向下移动两个链表，如果两个节点的内存地址相同，则返回节点。否则返回null。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int sizeA = 0, sizeB = 0;
        ListNode l1 = headA, l2 = headB;
            
        while(l1 != null){
            l1 = l1.next;
            sizeA++;
        }
        while(l2 != null){
            l2 = l2.next;
            sizeB++;
        }
        if(sizeA > sizeB){
            int size = sizeA - sizeB;
            while(size != 0){
                headA = headA.next;
                size--;
            }
        }
        else{
            int size = sizeB - sizeA;
            while(size != 0){
                headB = headB.next;
                size--;
            }
        }
        while(headA != null){
            if(headA == headB) return headA;
                headA = headA.next;
                headB = headB.next;
        }
        return null;
    }
}

遍历移动一个链表，将其加入哈希集合。
然后移动另一个链表，如果哈希集合中有重复节点，则返回该节点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        while(headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while(headB != null){
            if(set.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}

Posted 2022-04-26Updated 2022-04-26LeetCode / Medium2 minutes read (About 301 words)

79. Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.

回溯，遍历所有初始元素。
当寻找的字符与当前matrix里的字符相同时，将当前位置记录在visited里，并向下递归搜索四个方向，回溯visited。
当越界或者字符已经visited时返回false。
当寻找到单词的最后一位时，如果当前matrix里的字符与搜索的字符相等，则返回true。反之返回false。

class Solution {
    char[][] bd;
    String wd;
    int[][] visited;
    public boolean exist(char[][] board, String word) {
        boolean ans = false;
        visited = new int[board.length][board[0].length];
        bd = board;
        wd = word;
        for(int i = 0; i < board.length; i++){
            for(int j = 0; j < board[0].length; j++){
                ans = ans || backtracking(i, j, 0);
            }
        }
        return ans;
    }
    
    private boolean backtracking(int i, int j, int n){
        
        if(i < 0 || j < 0 || i >= bd.length || j >= bd[0].length || n >= wd.length()) return false;
        if(visited[i][j] == 1) return false;
        if(n == wd.length()-1) return bd[i][j] == wd.charAt(n); 
        if( bd[i][j] == wd.charAt(n) ){
            n++;
            visited[i][j] = 1;
            boolean a = backtracking(i+1, j, n);
            boolean b = backtracking(i-1, j, n);
            boolean c = backtracking(i, j+1, n);
            boolean d = backtracking(i, j-1, n);
            visited[i][j] = 0;
            return a || b || c || d;
        }
        return false;
    }
}

Recents

Archives

Links