徒手挖地球二四周目

NO.225 用队列实现栈 简单

思路一：使用队列API 其实没有太搞明白这个题目的意思。。。leetcode打卡活动第一天题目。

主要是push()方法每次将新加入元素x之前的元素都按序出队并重新入队，这样新元素x就在队头。

然后pop()、top()、empty()直接调用队列API就好。。。

public class MyStack {

    Queue<Integer> queue;
    /** Initialize your data structure here. */
    public MyStack() {
        this.queue=new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        queue.add(x);
        for (int i = 1; i < queue.size(); i++) {
            queue.add(queue.remove());
        }
    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }

    /** Get the top element. */
    public int top() {
        return queue.peek();
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

时间复杂度：push()是O(n)，其余三个方法时O(1)

NO.53 最大子序和 简单

思路一：动态规划法 分析dp那就要先分析dp[i]的含义：以第i元素结尾的最大序列和。

初始化：dp[0]以第0号元素结尾的序列只有nums[0]本身，所以dp[0]=nums[0]。

转移方程：dp[i]=Max(dp[i-1]+nums[i],nums[i])，因为dp[i-1]是以i-1为结尾的序列和中的最大值，所以我们想找nums[i]结尾的最大序列和只需要比较"前一个最大序列和+nums[i]“和"nums[i]”。举个例子：

public int maxSubArray(int[] nums) {
    if (nums==null||nums.length==0)return 0;
    int[] dp=new int[nums.length];
    //初始化
    dp[0]=nums[0];
    //填写dp数组同时用max记录当前最大的序列和
    int max=dp[0];
    for (int i = 1; i < nums.length; i++) {
        dp[i]=Math.max(nums[i],dp[i-1]+nums[i]);
        max=Math.max(max,dp[i]);
    }
    return max;
}

经过思考不难发现，并不需要开辟一个数组来保存每一个子序和。每次填写只需要关心上一次状态值即可，且每个状态值只需要使用一次。所以我们可以用一个int变量代替dp数组即可：

public int maxSubArray(int[] nums) {
    if (nums==null||nums.length==0)return 0;
    //初始化
    int dp=nums[0];
    //更新当前i结尾的最大序列和同时用max记录最大的序列和
    int max=dp;
    for (int i = 1; i < nums.length; i++) {
        dp=Math.max(nums[i],dp+nums[i]);
        max=Math.max(max,dp);
    }
    return max;
}

时间复杂度：O(n)

NO.206 翻转链表 简单

本题是K个一组翻转链表这道题的其中一步，学习完本题可以趁热打铁学习NO.25，题解参考徒手挖地球十八周目。

思路一：迭代实现 翻转链表需要三个"指针"：pre指向前驱、curr指向当前节点、next指向后继。

过程比较简单，自己模拟一遍就好了：

public ListNode reverseList(ListNode head) {
    if (head==null||head.next==null)return head;
    ListNode pre=null,curr=head;
    while (curr!= null) {
        ListNode next=curr.next;
        curr.next=pre;
        pre=curr;
        curr=next;
    }
    return pre;
}

时间复杂度：O(n)

思路二：递归实现 每层递归返回已经翻转好的部分。

public ListNode reverseList(ListNode head) {
    if (head==null||head.next==null)return head;
    ListNode pre=reverseList(head.next);
    head.next.next=head;
    head.next=null;
    return pre;
}

时间复杂度：O(n)

NO.54 螺旋矩阵 中等

思路一：按层模拟法 从[0][0]开始模拟顺时针一层一层的遍历所有元素。

计算层数count：(Min(row，col)+1)/2，因为每次最多有两行两列组成，最少由一行或一列组成。

遍历每一层curr即[0,count)，每层有四次"转弯"：

1. 每一层先从左到右遍历一行，即for(i=curr;i<col-curr;i++)matrix[curr][i]。
2. 再从上到下遍历一列，即for(i=curr+1;i<row-curr;i++)matrix[i][col-1-curr]。
3. 再从右到左遍历一行，即for(i=col-1-curr-1;i>=curr;i--)matrix[row-1-i][i]。
4. 最后从下到上遍历一列，即for(i=row-1-curr-1;i>=curr+1;i--)matrix[i][curr]。

ps：每一层除了第一行是遍历一整行元素，其余三部分都需要注意不要重复遍历"拐点"元素。

上述是常规层(两行两列)的遍历；如果只有一行，从右向左遍历时会重复遍历；如果只有一列，从下向上遍历时会重复遍历，如何解决这个问题？

答：只有一行或只有一列时，不进行右向左或下向上的遍历即可。如何判断？row-1-curr==curr说明当前层只有一行；col-1-curr==curr说明当前层只有一列。

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res=new ArrayList<>();
    if (matrix==null||matrix.length==0)return res;
    int row = matrix.length,col=matrix[0].length;
    //计算有多少层
    int count=(Math.min(row,col)+1)/2;
    //当前层
    int curr=0;
    //遍历每一层
    for (;curr<count;curr++){
        //从左向右
        for (int i = curr; i < col - curr; i++) {
            res.add(matrix[curr][i]);
        }
        //从上到下
        for (int i = curr+1; i < row-curr; i++) {
            res.add(matrix[i][col-1-curr]);
        }
        //从右到左
        for (int i = col-1-curr-1; i >= curr&&(row-1-curr!=curr); i--) {
            res.add(matrix[row-1-curr][i]);
        }
        //从下到上
        for (int i = row-1-curr-1; i >= curr+1&&(col-1-curr!=curr); i--) {
            res.add(matrix[i][curr]);
        }
    }
    return res;
}

时间复杂度：O(n)

---

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github