LeetCodeHot100_0x03

LeetCodeHot100_0x03

17. 缺失的第一个正数

求解思路： 这题一眼，这么简单？？？做出了还过了，第二眼，不接助O(N)空间，什么鬼？好吧，起码能想到用哈希解决，也算是解决了时间复杂度,接下来就是要想如何优化哈希表算法。其实马上就想到了，不给额外空间，直接利用原数组不就行了（高，实在是高！）
【哈希表】不符合题目中的常数级空间复杂的度

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 哈希
        Set<Integer> hs = new HashSet<>();
        for(int i=0;i<nums.length;i++) {
            hs.add(nums[i]);
        }
        int i;
        for(i=1;;i++) {
            if(!hs.contains(i))break;
        }
        return i;
    }
}

【原地哈希】
原地哈希就相当于，让每个数字n都回到下标为n-1的家里。而那些没有回到家里的就成了孤魂野鬼流浪在外，他们要么是根本就没有自己的家（数字小于等于0或者大于nums.size()），要么是自己的家被别人占领了（出现了重复）。这些流浪汉被临时安置在下标为i的空房子里，之所以有空房子是因为房子i的主人i+1失踪了（数字i+1缺失）。
因此通过原地构建哈希让各个数字回家，我们就可以找到原始数组中重复的数字还有消失的数字。(来自力扣 xph123 的形象解释)

class Solution {
    public int firstMissingPositive(int[] nums) {
        // 直接遍历数组
        for(int i=0;i<nums.length;i++) {
            //while 是为了防止交换后仍然不符合，即这个萝卜还不是这个坑的，就继续进行交换
            while(nums[i] >= 0 && nums[i] < nums.length && nums[i] != nums[nums[i]]) {
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }

        for(int i=1;i<nums.length;i++) {
            if(nums[i] != i)return i;
        }
        return nums[0] == nums.length ? nums.length + 1 : nums.length;
    }
}

18. 矩阵置零

求解思路： 第一遍遍历用于标记0，这些0对应的（i,j）都是需要置零的，所以我们可以提前用两个数组去记录那些行、列需要置零。然后第二、三遍遍历分别对行、列进行置零就行了

【模拟法】
没啥算法，就是读懂题目，这个空间复杂度是O(M + N)的，距离题目描述的O(1) 还有差距，但我第一遍刷不想细究太多，至少我觉得我写出来的方案比O(MN)的强。

class Solution {
    public void setZeroes(int[][] matrix) {
        // 思路：第一遍遍历标记出现0的位置，第二、三遍遍历将对应行置零
        int m = matrix.length;
        int n = matrix[0].length;
        int[] x = new int[m];   // 横坐标情况
        int[] y = new int[n];   // 纵坐标情况

        // 第一遍遍历
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(matrix[i][j] == 0) {
                    x[i] = 1;
                    y[j] = 1;
                }
            }
        }
        // 第二遍遍历
        for(int i=0;i<m;i++) {
            if(x[i] == 1) {
                for(int j=0;j<n;j++) matrix[i][j] = 0;
            }
        }
        // 第三遍遍历
        for(int j=0;j<n;j++) {
            if(y[j] == 1) {
                for(int i=0;i<m;i++) matrix[i][j] = 0;
            }
        }

    }
}

19. 螺旋矩阵（不熟）

求解思路： 利用模拟法模拟螺旋矩阵的转向情况，结合边界条件判断。

【模拟法】
顺时针旋转，按照 右–下–左–上 重复循环，这个过程中定义四个方向边界指针up、down、left、right。每次结束一个方向的一轮遍历后，上一个方向的边界指针就会缩小范围。在结合 （up <= down）、(left <= right) 条件判断是否出现越界，代表遍历是否完成。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 按照 右 -- 下 -- 左 -- 上 -- 右 走一圈就可以遍历完
        // 向右走 j++ 向下走 i++ 向左走j-- 向上走i-- 
        // 向右走完，则上边界会缩小
        // 向下走完，则右边界会缩小
        // 向左走完，则下边界会缩小
        // 向上走完，则左边界会缩小
        // 不断循环，判断何时出现越界情况就是结束了螺旋遍历

        List<Integer> res = new ArrayList<>();
        if(matrix ==null || matrix.length==0 || matrix[0].length == 0) return res;

        int up = 0, down=matrix.length-1;
        int left=0, right=matrix[0].length-1;

        while(true) {
            // 向右走，横向变化看（left,right）
            for(int i=left;i<=right;i++) {
                res.add(matrix[up][i]); // 维持x不变，y变
            }
            // 缩小上边界范围
            if(++up > down) break;

            // 向下走，纵向变化看(up,down)
            for(int i=up;i<=down;i++) {
                res.add(matrix[i][right]); // 维持x变，y不变
            }
            // 缩小右边界范围
            if(--right < left)break;

            // 向左走，横向变化
            for(int i=right;i>=left;i--) {
                res.add(matrix[down][i]);
            }
            // 缩小下边界范围
            if(--down<up)break;

            // 向上走，纵向变化
            for(int i=down;i>=up;i--) {
                res.add(matrix[i][left]);
            }
            // 缩小左边界范围
            if(++left > right) break; 
        }
        return res;
    }
}

【DFS搜索法】对4个方向进行深搜，利用标记数组标记过程中被访问的位置。

class Solution {

    private static final int[] dx = {0,1,0,-1};
    private static final int[] dy = {1,0,-1,0};
    private  List<Integer> res;
    private  boolean[][] visited;

    public List<Integer> spiralOrder(int[][] matrix) {

        res = new ArrayList<>();
        if(matrix==null || matrix.length==0 || matrix[0].length==0) return res;

        int rows = matrix.length;
        int cols = matrix[0].length;
        visited = new boolean[rows][cols];
        dfs(0,0,0,matrix);

        return res;
    }

    // DFS ，当前点坐标，当前方向数组下标，原数组
    private void dfs(int x,int y,int direction,int[][] matrix) {
        int rows = matrix.length;
        int cols = matrix[0].length;
        //1. 标记访问
        visited[x][y] = true;
        res.add(matrix[x][y]);

        //2. 尝试遍历当前方向的下一个位置
        int u = x + dx[direction];
        int v = y + dy[direction];
        if(u >=0 && u<rows && v>=0 && v<cols && !visited[u][v]) {
            // 未越界、没访问就可以下一层dfs
            dfs(u,v,direction,matrix);
        }

        //3. 尝试其他四个方向
        for(int i=0;i<4;i++) {
            int U = x + dx[i];
            int V = y + dy[i];
            if(U >=0 && U<rows && V>=0 && V<cols && !visited[U][V]) {
                // 未越界、没访问就可以下一层dfs
                dfs(U,V,i,matrix);
            }
        }
    }
}

20. 旋转图像

求解思路： 先上下翻转图像，再对焦翻转图像就可以达到旋转的效果
【模拟法】

class Solution {
    public void rotate(int[][] matrix) {
        // 上下翻转后对角翻转
        int n = matrix.length;
        // 上下翻转(i,j) -- (n-i-1,j)
        for(int i=0;i<n/2;i++) {
            for(int j=0;j<n;j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n-i-1][j];
                matrix[n-i-1][j] = temp;
            }
        }
        // 对角翻转(i,j) -- (j,i)
        for(int i=0;i<n;i++) {
            for(int j=i;j<n;j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}

21. 搜索二维矩阵

求解思路： 看到单调性搜索元素，优先考虑使用二分算法

【二分搜索法】
首先纵向进行二分，找到最后一个起始元素满足 <= target 的行
接着遍历所有满足的行，再横向进行二分判断该行是否存在target元素即可

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // 这题用两遍二分搜索，都没结果就是找不到(行列具有单调性)
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;

        // 纵向二分查找：找到最后一个起始元素 <= target 的行
        int u = 0, d = m - 1;
        int row = -1;
        while (u <= d) {
            int mid = u + (d - u) / 2;
            if (matrix[mid][0] <= target) {
                row = mid;
                u = mid + 1;
            } else {
                d = mid - 1;
            }
        }

        // 若所有行首元素都大于target，直接返回false
        if (row == -1) {
            return false;
        }

        // 横向遍历0到row行，每行进行二分查找
        for (int i = 0; i <= row; i++) {
            int l = 0, r = n - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (matrix[i][mid] == target) {
                    return true;
                } else if (matrix[i][mid] < target) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            }
        }
        return false;
    }
}

【二维指针遍历】

这个做法更是绝了！我原本以为使用二分法已经够快了，但是实际上还是没有充分利用矩阵的特性。行内：从左到右递增，列内：从上到下递增。

那么我们用i维护行，初始值为0，j维护行内，初始值为n-1。这样一来,开始的值就是第一行的最大值。

• 如果这个值大于target，就行内指针j–；
• 直到第一行找遍所有大于target且没有发现target时，证明第一行肯定没有。
• 接着就会碰到小于target，行指针i++；接着重复找，直到找到最后如果都没能发现target，证明不存在。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n =matrix[0].length;
        int i=0,j=n-1;
        while(i>=0 && i<m && j>=0 && j<n) {
            if(matrix[i][j] > target) j--;
            else if(matrix[i][j] < target) i++;
            else return true;
        }
        return false;
    }
}

22. 相交链表

求解思路： 这题要求求两个链表有没有相交，其实我们可以思考一下，相交的条件无非是链表之间有相同的元素。那么问题就转换成了如何判断链表有没有相同元素？借助哈希表很快就能解决这个问题

【哈希表法】先遍历headA，将元素存入，再遍历headB，判断是否存在相同元素

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 只要具有相同元素，那就相交了
        // 可以采用哈希的思想，先遍历headA，将元素存入，再遍历headB，看看有无相同元素
        Set<ListNode> hs = new HashSet<>();
        ListNode node = headA;
        while(node != null) {
            hs.add(node);
            node = node.next;
        }
        node = headB;
        while(node != null) {
            if(hs.contains(node)) return node;
            node = node.next;
        }
        return null;
    }
}

【双指针法】
看完题解发现还要一种更牛的方法，不需要额外空间，而是利用双指针无限循环匹配，直到匹配到相同元素或相同空指针跳出，然后返回指针的结果。具体的，就是指针pA维护headA，pB维护headB，同步移动，遇到链表尾重置，循环往复，直到得出结果。

这种方法看似很不合理，无限循环那么程序的出口在哪里？其实仔细想想，当多进行几轮匹配，必然能有一次匹配恰好pA指针和pB指针都指向同一元素或者null (长度最小公倍数) ，所有是可行的。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        if(headA == null || headB == null) return null;

        ListNode pA = headA;
        ListNode pB = headB;
        while(pA != pB) {
            pA = pA == null ? headA : pA.next;
            pB = pB == null ? headB : pB.next;
        }
        return pA;
    }
}

23. 反转链表(不熟)

求解思路：
　　看到这题，对指针操作不熟悉的我立马想到把值倒过来不就好了？虽然也成功了，但是没有起到锻炼的目的。除此之外，这题更多的是考察指针的用法。第二种方法，借助中间节点，将原链表的指针方向进行反向。
【反值不反向】将链表的值反转更新

class Solution {
    public ListNode reverseList(ListNode head) {
        // 方法一：只改值 不改指针
        LinkedList<Integer> value = new LinkedList<>();
        ListNode node = head;
        while(node != null) {
            value.add(node.val);
            node = node.next;
        }

        node = head;
        while(node != null) {
            node.val = value.getLast();
            value.removeLast();
            node = node.next;
        }
        return head;
    }
}

【迭代法】利用curr、next、node指针完成链表转向

class Solution {
    public ListNode reverseList(ListNode head) {
        // 迭代法

        ListNode node = null; // 新节点
        ListNode curr = head; // 当前节点
        ListNode next = null; // 当前系欸但的下一节点
        while(curr != null) {
            next = curr.next; // 保存当前节点的下一节点
            curr.next = node; // 改变当前节点的指向
            node = curr;      // 奖新节点的头节点移动
            curr = next;      // 遍历下一节点
        }
        return node;
    }
}

【递归法】这个太狠了，根本想不到，看题解也理解了半天

class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归法
        // 递归终止条件
        if(head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

24. 回文链表

求解思路： 取出来再判断是否回文
【双指针法】

class Solution {
    public boolean isPalindrome(ListNode head) {
        // 朴素做法，取出来再判断
        if(head == null) return false;
        List<Integer> value = new ArrayList<>();
        ListNode curr = head;
        while(curr != null) {
            value.add(curr.val);
            curr = curr.next;
        }
        int i=0,j=value.size()-1;
        while(i<=j) {
            if(value.get(i) != value.get(j)) return false;
            i++;
            j--;
        }
        return true;
    }
}

25. 总结

今天做链表有点做到吐了，不想刷了，总结一下今天的题型吧。

1. 缺失的第一个正数 哈希
   • 这题哈希秒杀，原地哈希苦哈哈
2. 矩阵置零 数组、思维
   • 预先标记好需要置零的行和列，分别置零就行了
3. 螺旋矩阵 数组、dfs、思维
   • 模拟思维，注意边界值判断。
   • dfs去四个方向搜索，利用边界条件和visited数组做好越界、去重判断
4. 旋转图像 数组、思维
   • 纯思维题，朴素做法是复杂一份，高级一点的是利用两次翻转，先上下，后对角
5. 搜索二维矩阵 数组、二分、思维
   • 看到单调性，直接考虑二分，但是要注意二分的写法，避免死循环
   • 高级：考虑矩阵特性，用一次遍历，两个指针就可以实现
6. 相交链表 链表、哈希
   • 直接哈希判断有无相同元素得了
7. 翻转链表 链表、迭代、递归
   • 朴素做法，把值反过来更新进去就行了，不用动指针
   • 迭代做法，利用node、curr、next指针巧妙变向（3，4步不能调换顺序）
   • 递归做法：难呐呐呐，大概是一直递归到尾结点，将指针转向，然后利用递归返回的特性，完美的规避了因为链表方向改变而造成的节点信息丢失的问题。
8. 回文链表 链表、双指针、递归（没写）
   • 朴素做法：取出来，双指针遍历得了

总的来说，多数是数组和链表两大类型题目，做题做多了发现哈希算法的运用很广。其次还开始接触了dfs深度搜索算法、二分算法、递归算法等等。链表的题目整体难度不大，但是一旦涉及到了递归优化的时候，就会变得无比抽象。还是多练吧孩子！