面试冲刺 - 算法题 1

59.螺旋矩阵II

对于循环的圈数 loop = (n / 2):

意思是：如果转一圈，左右都会少一条边，整个正方形的宽度减2，一共宽度是n，每次减2，就是循环n/2次。

class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;  // 控制循环次数
        int[][] res = new int[n][n];
        int start = 0;  // 每次循环的开始点(start, start)
        int count = 1;  // 定义填充数字
        int i, j;

        while (loop++ < n / 2) { // 判断边界后，loop从1开始
            // 模拟上侧从左到右
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }

            // 模拟右侧从上到下
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }

            // 模拟下侧从右到左
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }

            // 模拟左侧从下到上
            for (; i >= loop; i--) {
                res[i][j] = count++;
            }
            start++;
        }

        if (n % 2 == 1) {
            res[start][start] = count;
        }

        return res;
    }
}

206.反转链表

需要注意的是递归法：

在使用递归法的时候，每次递归传入的是下一次循环的当前结点和前一结点：

class Solution {
    public ListNode reverseList(ListNode head) {
        //ListNode dum = new ListNode(-1,head);//设置虚拟头节点  
        return reverse(head,null);
    }
    public ListNode reverse(ListNode cur,ListNode pre){
        if(cur == null){
            return pre;
        }
        ListNode temp = cur.next;
        cur.next = pre;
        return reverse(temp,cur);
    }
}

142.环形链表II

需要注意别陷入死循环，当快慢指针相遇的时候是一定有环的。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //定义一个快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){//有环
                slow = head;
                while(slow != fast){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;

    }
}

199.二叉树的右视图

注意层序遍历的有两层循环

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new LinkedList();
        if(root == null){
            return res;
        }
        Queue<TreeNode> queue = new LinkedList();
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size-- > 0){
                TreeNode cur =  queue.peek();
                queue.poll();
                if(size == 0){
                    res.add(cur.val);
                }
                if(cur.left != null){
                    queue.add(cur.left);
                }
                if(cur.right != null){
                    queue.add(cur.right);
                }
            }
        }
        return res;
    }
}