ARTS打卡：第一周

发表于 | 分类于 | 本文总阅读量 次

ARTS 第一周分享

ARTS 是耗子叔发起的一次活动，感兴趣的小伙伴们可以到知乎上查看极客时间《左耳听风》发起的ARTS挑战怎么参加？

每周完成一个ARTS：

  1. Algorithm：每周至少做一个 leetcode 的算法题
  2. Review：阅读并点评至少一篇英文技术文章
  3. Tip：学习至少一个技术技巧
  4. Share：分享一篇有观点和思考的技术文章

Algorithm

LeetCode 的萌新用户，这周做的几道题是 Recursion 1 里面的题目，记录如下：

#344. Reverse String（Easy）

Write a function that reverses a string. The input string is given as an array of characters char[].
Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.
You may assume all the characters consist of printable ascii characters.
Example 1 ：
Input: [“h”,”e”,”l”,”l”,”o”]
Output: [“o”,”l”,”l”,”e”,”h”]
Example 2 ：
Input: [“H”,”a”,”n”,”n”,”a”,”h”]
Output: [“h”,”a”,”n”,”n”,”a”,”H”]

这道题的大致意思是写一个方法，用于反转输入的字符数组，不允许额外分配多一个数组，要求只能使用O(1)的额外内存来实现。
解法简单，就直接上代码了:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public void reverseString(char[] s) {
        char temp;
        int midIndex = s.length / 2;
        for (int i = 0; i < midIndex; i++) {
            temp = s[i];
            s[i] = s[s.length - 1 -i];
            s[s.length - 1 - i] = temp;
        }
    }
}

贴一个在 Discuss 里看到的答案，利用 ascii 来实现的，是我想不到的思路(:з」∠)：[Java] two pointer solution without temp var ：

1
2
3
4
5
6
7
8
9
class Solution {
    public void reverseString(char[] s) {
        for (int i=0,j=s.length-1;i<j;i++,j--){
            s[i]=(char)(s[j]-s[i]);
            s[j]=(char)(s[j]-s[i]);
            s[i]=(char)(s[j]+s[i]);
        }
    }
}

#24. Swap Nodes in Pairs（Medium）

Given a linked list, swap every two adjacent nodes and return its head.
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example:
Given 1->2->3->4, you should return the list as 2->1->4->3.

题目的大致意思：给定一个链表，交换每两个相邻节点并返回其头部。 只能更改节点本身。

解题思路：这道题可以当做是递归问题，解决递归问题两大关键点：

  • recurrence relation：the relationship between the result of a problem and the result of its subproblems.（即大问题分解为小问题的规律，基于这个规律写出递推公式）
  • base case：the case where one can compute the answer directly without any further recursion calls. （即递归的终止条件）

所以我们第一步，就是先找出递归关系，将大问题分解为小问题。

以 Example 提供的数据为例，将两个节点划分为一组来看，会发现（1->2），交换位置后为（2->1），即将 2 作为头部节点，并指向 1，且 1 节点要指向下一组的头部节点，然后返回头部2；下一组（3->4），通过同样的操作，变为（4->3），3 指向了下一组的头部节点，然后返回头部节点 4。

你看，递归关系就出来了，都是把原头结点的下一个节点当做当前头结点，把原头结点指向下一组的头结点，然后把当前头节点的下一个节点指向原头结点，最后返回当前头结点。（表述能力有点渣，请见谅(:з」∠) ）。

把递归关系写成方法，如下：

1
2
3
4
5
6
7
8
9
10
11
12
public ListNode swapPairs(ListNode head) {
    // 临时变量保存原先的头结点
    ListNode tmp = head;
    // 把原先头结点的下一个节点当做当前头结点
    head = head.next;
    // 把原头结点指向下一组的头结点
    tmp.next = swapPairs(head.next);
    // 把当前节点的下一个节点指向原先头结点
    head.next = tmp;
    // 返回当前头结点
    return head;
}

当然，还没完，我们还需要找到递归的终止条件，即当：

  • 假设传入的是一个空节点时，直接返回空节点。
  • 假设传入的节点没有下一个节点时，直接返回当前节点。

这时答案就出来了：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
        public ListNode swapPairs(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode tmp = head;
            head = head.next;
            tmp.next = swapPairs(head.next);
            head.next = tmp;
            return head;
        }
    }

Review

本周阅读了一篇在《左耳听风》第71讲中推荐阅读的文章：《The Key To Accelerating Your Coding Skills》。

作者在这篇文章中讲述了如何有效地快速提高自己的编程能力，认为在学习编程的过程中，存在着编码拐点，一旦通过这个拐点，作为一个开发人员的操作方式，将会有很大的不同。通过拐点之前，将可能是一段令人沮丧的经历，但一旦它过去了，它就会让你变得无比强大。

Tip

分享一个关于 Intellij IDEA Debug的小技巧：
有时候我们进入方法体之后，还想退回到方法体外时，如果手速过快，点多了几下F8/F9，这时，只需点击 Drop Frame，即可退回方法体外，如下图所示：
arts

这里附上在Github上找到的IntelliJ IDEA 简体中文专题教程

Share

分享一个在阿里技术公众号上看到的一篇文章《工程师男友如何反窃听？趣聊密码学入门科普》，文章生动有趣，非常值得一看，妈妈再也不担心如何向别人介绍我所处的行业了(:з」∠) 。