7.17号刷题

第一题 369. Plus One Linked List

题目描述

假设一个Linked List中的每一个数字代表一个整数的一个位，将这个数加1

算法

我们首先标记出本位不是9且下一位是9的数字，之后检测最后一位，如果是9.则标记的后面全部置0，本身加1。如果标记位本身为null，说明整个都需要进位，创造新的节点

public class plusOne369 {
    public ListNode plusOne(ListNode head) {
        if (head == null) return null;
        ListNode cur = head, preNoNine = null;

        while (cur.next != null) {
            if (cur.val != 9 && cur.next.val == 9)
                preNoNine = cur;
            cur = cur.next;
        }

        if (cur.val == 9) {
            if (preNoNine == null) {
                ListNode newhead = new ListNode(1);
                newhead.next = head;
                while (head != null) {
                    head.val = 0;
                    head = head.next;
                }
                return newhead;
            } else {
                preNoNine.val += 1;
                preNoNine = preNoNine.next;
                while (preNoNine != null) {
                    preNoNine.val = 0;
                    preNoNine = preNoNine.next;
                }
            }
        } else {
            cur.val += 1;
        }
        return head;
    }
}

第二题 2. Add Two Numbers

题目描述

有两个LinkedList表示两个整数(逆序排序，意味着最高位在最左半边)，求两个LinkedList相加的值

算法

public class addTwoNumbers2 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        ListNode newNode = new ListNode(0);
        ListNode cur = newNode;
        int sum = 0;
        while (l1 != null || l2 != null) {
            sum = sum / 10;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
        }

        if (sum >= 10) cur.next = new ListNode(1);
        return newNode.next;
    }
}

第三题 445. Add Two Numbers II

题目描述

给定两个表示非负整数的链表。链表头部表示高位，尾部表示低位，每一个节点只包含一位数。以链表形式返回两个链表的和。

你可以假设两个数字都不包含前导0，除非数字本身就是0。

进一步思考：

你可以不修改输入链表吗？换言之，不允许反转链表。

算法

利用list存储每个数

public class addTwoNumbers445 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        List<Integer> listL1 = new ArrayList<>();
        List<Integer> listL2 = new ArrayList<>();

        while (l1 != null) {
            listL1.add(l1.val);
            l1 = l1.next;
        }
        while (l2 != null) {
            listL2.add(l2.val);
            l2 = l2.next;
        }

        ListNode pre = new ListNode(0);
        int sum = 0;
        for (int i = listL1.size() - 1, j = listL2.size() - 1; i >= 0 || j >= 0;) {
            sum /= 10;
            int first = 0, second = 0;
            if (i >= 0)  first = listL1.get(i--);
            if (j >= 0) second = listL2.get(j--);

            sum += first + second;
            pre.val = (sum) % 10;
            ListNode cur = new ListNode(1);
            cur.next = pre;
            pre = cur;
        }
        return sum >= 10 ? pre : pre.next;
    }
}

第四题 379. Design Phone Directory

题目描述

设计一个电话铺

算法

Queue + HashSet结合

public class PhoneDirectory {

    Set<Integer> used = new HashSet<Integer>();
    Queue<Integer> available = new LinkedList<Integer>();
    int max;
    public PhoneDirectory(int maxNumbers) {
        max = maxNumbers;
        for (int i = 0; i < maxNumbers; i++) {
            available.offer(i);
        }
    }

    public int get() {
        Integer ret = available.poll();
        if (ret == null) {
            return -1;
        }
        used.add(ret);
        return ret;
    }

    public boolean check(int number) {
        if (number >= max || number < 0) {
            return false;
        }
        return !used.contains(number);
    }

    public void release(int number) {
        if (used.remove(number)) {
            available.offer(number);
        }
    }
}

第五题 127. Word Ladder

题目描述

给定两个单词（beginWord 和 endWord），以及一个字典，寻找从 beginWord 到 endWord 的最短转换序列的长度，满足约束条件：

每次只能改变一个字母

每一个得到的单词必须存在于字典中

例如，给定：

start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

最短的转换序列为：”hit” -> “hot” -> “dot” -> “dog” -> “cog”，

返回其长度5。

注意：

如果不存在这样的转换序列，返回0。

所有的单词都是等长的。

所有的单词都只包含小写字母。

算法

双向BFS，将beginword和endword分别存入两个set中。不断的替换，找到下一批临近的words, 之后如果在替换过程中发现了合适的word。返回长度，结束搜索。当所有单词都用完后，如果仍然没有发现有合适的答案，返回0.

public class ladderLength127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordListOrigin) {
        Set<String> wordList = new HashSet<>(wordListOrigin);
        if (beginWord.equals(endWord)) return 1;
        if (!wordList.contains(endWord)) return 0;

        Set<String> beginset = new HashSet<>(), endset = new HashSet<>();
        Set<String> visited = new HashSet<>();
        int count = 1;
        beginset.add(beginWord); endset.add(endWord);
        while (!beginset.isEmpty() && !endset.isEmpty()) {
            if (beginset.size() > endset.size()) {
                Set<String> change = beginset;
                beginset = endset;
                endset = change;
            }

            Set<String> temp = new HashSet<>();
            for (String word : beginset) {
                char[] chrs = word.toCharArray();

                for (int i = 0; i < chrs.length; i++) {
                    char old = chrs[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        chrs[i] = c;
                        String candidate = String.valueOf(chrs);

                        if (endset.contains(candidate))
                            return count + 1;
                        if (!visited.contains(candidate) && wordList.contains(candidate)) {
                            temp.add(candidate);
                            visited.add(candidate);
                        }
                        chrs[i] = old;
                    }
                }
            }
            beginset = temp;
            count++;
        }
        return 0;
    }
}

第六题 126. Word Ladder II

题目描述

同上题一样，只是现在需要找出所有的距离最短的路径

算法

双向BFS（获得所需要节点的所有下一变换的可能） + DFS（找出所有可能的结果）

算法略复杂，需要花时间理解

public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        Set<String> remainWords = new HashSet<>(wordList);
        if (!remainWords.contains(endWord)) 
            return new ArrayList<>();
        Map<String, List<String>> neighbors = new HashMap<>();

        Set<String> begin = new HashSet<>(), end = new HashSet<>();
        begin.add(beginWord); end.add(endWord);

        bfs(beginWord, endWord, begin, end, remainWords, true, neighbors);
        List<List<String>> res = new ArrayList<>();
        List<String> sol = new ArrayList<>(Arrays.asList(beginWord));
        dfs(beginWord, endWord, neighbors, res, sol);

        return res;
    }

    public boolean bfs(String beginWord, String endWord, Set<String> begin, Set<String> end, Set<String> remainWords, boolean forward, Map<String, List<String>> neighbors) {
        if (begin.isEmpty()) return false;

        if (end.size() > begin.size()) {
            return bfs(beginWord, endWord, end, begin, remainWords, !forward, neighbors);
        }

        remainWords.removeAll(begin);
        remainWords.removeAll(end);

        boolean done = false;
        Set<String> temp = new HashSet<>();

        for (String word : begin) {
            char[] chars = word.toCharArray();

            for (int i = 0; i < chars.length; i++) {
                char old = chars[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[i] = c;
                    String candidate = String.valueOf(chars);

                    String key = forward ? word : candidate;
                    String val = forward ? candidate : word;

                    List<String> listemp = neighbors.getOrDefault(key, new ArrayList<>());

                    if (end.contains(candidate)) {
                        done = true;
                        listemp.add(val);
                        neighbors.put(key, listemp);
                    }

                    if (!done && remainWords.contains(candidate)) {
                        temp.add(candidate);
                        listemp.add(val);
                        neighbors.put(key, listemp);
                    }
                    chars[i] = old;
                }
            }
        }
        return done || bfs(beginWord, endWord, temp, end, remainWords, forward, neighbors);
    }

    public void dfs(String cur, String endword, Map<String, List<String>> neighbors, List<List<String>> res, List<String> solution) {
        if (cur.equals(endword)) {
            res.add(new ArrayList<>(solution));
            return;
        }

        if (!neighbors.containsKey(cur)) return;

        List<String> pool = neighbors.get(cur);
        for (String word : pool) {
            solution.add(word);
            dfs(word, endword, neighbors, res, solution);
            solution.remove(solution.size() - 1);
        }
    }
}

第七题 490. The Maze

题目描述

在一个迷宫里有一个小球，小球可以朝着一个方向滚动，直到碰到墙壁。求小球在迷宫中是否可以到达指定的位置

算法

利用Queue进行存储我们所有需要访问的下一个点的位置，BFS搜索

public class hasPath490 {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        Queue<int[]> positions = new LinkedList<>();
        positions.add(start);
        boolean[][] visited = new boolean[maze.length][maze[0].length];
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        visited[start[0]][start[1]] = true;
        while (!positions.isEmpty()) {
            int[] cur = positions.poll();
            if (cur[0] == destination[0] && cur[1] == destination[1])
                return true;
            for (int[] dir : directions) {
                int x = cur[0] + dir[0];
                int y = cur[1] + dir[1];
                while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
                }
                if (!visited[x - dir[0]][y - dir[1]]) {
                    positions.add(new int[]{x - dir[0], y - dir[1]});
                    visited[x - dir[0]][y - dir[1]] = true;
                }
            }
        }
        return false;
    }
}

第八题 505. The Maze II

题目描述

与上一题相同，只是现在需要找出的是最短的路径长度

算法

依然使用Queue记录每个方向的目的地，但是现在用一个int[][]的二维矩阵记录离初始点的距离

public class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int[][] distance = new int[maze.length][maze[0].length];
        for (int[] row: distance)
            Arrays.fill(row, Integer.MAX_VALUE);
        distance[start[0]][start[1]] = 0;
        int[][] dirs={{0, 1} ,{0, -1}, {-1, 0}, {1, 0}};
        Queue < int[] > queue = new LinkedList < > ();
        queue.add(start);
        while (!queue.isEmpty()) {
            int[] s = queue.remove();
            for (int[] dir: dirs) {
                int x = s[0] + dir[0];
                int y = s[1] + dir[1];
                int count = 0;
                while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
                    x += dir[0];
                    y += dir[1];
                    count++;
                }
                if (distance[s[0]][s[1]] + count < distance[x - dir[0]][y - dir[1]]) {
                    distance[x - dir[0]][y - dir[1]] = distance[s[0]][s[1]] + count;
                    queue.add(new int[] {x - dir[0], y - dir[1]});
                }
            }
        }
        return distance[destination[0]][destination[1]] == Integer.MAX_VALUE ? -1 : distance[destination[0]][destination[1]];        
    }
}

第九题 499. The Maze III

题目描述

给定一个二维迷宫，其中包含一个小球和一个洞。小球可以向上（u）、下（d）、左（l）、右（r）四个方向移动。每当小球选择一个方向后，会持续移动直到遇到墙壁为止。小球经过洞时会落入洞中。

给定小球的初始位置ball，洞的位置hole。二维迷宫maze中1表示墙壁，0表示空地，四周被墙壁包围。求小球到洞的最短路径，如果存在距离相等的多条路径，返回字典序最短的那条。

注意：

1. 球和洞各只有1个。
2. 球和洞只存在于空地上，并且初始位置不同。
3. 给定的迷宫不包含边界，但迷宫四周都是墙壁。
4. 迷宫至少包含两个空地，并且迷宫的长度和宽度不超过30。

算法

利用新的Point记录当前点的位置及离初始点的距离等信息，然后利用Priority Queue，不断寻找最短的路径

public class findShortestWay499 {
    class Point implements Comparable<Point> {
        int x, y, l;
        String s;
        public Point(int _x,int _y) {this.x = _x; this.y = _y; this.l = Integer.MAX_VALUE; s = "";}
        public Point(int _x, int _y, int _l, String _s) {this.x = _x; this.y = _y; this.l = _l; this.s = _s;}
        public int compareTo(Point p) {return l == p.l ? s.compareTo(p.s) : l - p.l;}
    }

    public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
        int m = maze.length, n = maze[0].length;

        Point[][] points = new Point[m][n];
        for (int i = 0; i < m * n; i++)
            points[i/n][i%n] = new Point(i / n, i % n);
        int[][] dir = new int[][]{{-1,0},{0,1},{1,0},{0,-1}};
        String[] ds=new String[] {"u","r","d","l"};

        PriorityQueue<Point> list = new PriorityQueue<>();
        list.offer(new Point(ball[0], ball[1], 0, ""));

        while (!list.isEmpty()) {
            Point p = list.poll();
            if (points[p.x][p.y].compareTo(p) <= 0) continue;

            points[p.x][p.y] = p;
            for (int i = 0; i < 4; i++) {
                int xx = p.x, yy = p.y, l = p.l;
                while (xx >= 0 && xx < m && yy >= 0 && yy < n && maze[xx][yy] == 0 && (xx != hole[0] || yy != hole[1])) {
                    xx += dir[i][0];
                    yy += dir[i][1];
                    l++;
                }
                if (xx != hole[0] || yy != hole[1]) {
                    xx -= dir[i][0];
                    yy -= dir[i][1];
                    l--;
                }
                list.offer(new Point(xx, yy, l, p.s + ds[i]));
            }
        }
        return points[hole[0]][hole[1]].l == Integer.MAX_VALUE ? "impossible" : points[hole[0]][hole[1]].s;
    }
}