ARTS打卡—第1周

本周主要是做了一道LeetCode的算法题及一道DataBase的题，涉及到了快速排序以及 SQL 语句中的LEFT JOIN语句，顺便学习了一下几个表合并方式的区别，后期会做一个总结。

• Algorithm
  • Java
  • Python
• Database
• Review
• Tips
• Share

Algorithm

本周题目描述如下：

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

题目很简单，给定一个数组，求周长最大的三角形，如果没有可以组成三角形的三个数，则返回0。最简单的当然就是暴力算法了，三个 for 循环，时间复杂度是$$O(n^3)$$。另外一种解法就是利用排序，从大到小依次寻找满足三角形条件的整数，计算其周长，如不存在则返回零。Java 本身的Arrays类中带了排序的方法，但是没用，想着复习着写写快排。代码如下：

Java

public class NO976_LargestPerimeterTriangle {
    public static void main(String[] args) {
        int[] A = new int[]{1, 1, 2};
        System.out.println(largestPerimeter(A));
    }

    private static int largestPerimeter(int[] A) {
        quickSort(A, 0, A.length - 1); // increase
        int numCount = A.length;
        for (int index = numCount - 3; index >= 0; index--) {
            if (A[index] + A[index + 1] > A[index + 2]) {
                return A[index] + A[index + 1] + A[index + 2];
            }
        }
        return 0;
    }

    private static void quickSort(int[] nums, int start, int end) {
        if (start >= end) {
            return;
        }
        int pivot = partition(nums, start, end);
        quickSort(nums, start, pivot - 1);
        quickSort(nums, pivot + 1, end);
    }

    private static int partition(int[] nums, int start, int end) {
        int pivot = nums[end];
        int i = start;
        for (int j = start; j < end; j++) {
            if (nums[j] < pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, end);
        return i;
    }

    private static void swap(int[] nums, int i, int j) {
        int tmp = nums[j];
        nums[j] = nums[i];
        nums[i] = tmp;
    }
}

Python

class Solution:
    def largestPerimeter(self, A: list) -> int:
        self.quick_sort(A, 0, len(A) - 1)
        for i in range(len(A) - 3, -1, -1): # -1 
            if A[i] + A[i + 1] > A[i + 2]:
                return A[i] + A[i + 1] + A[i + 2]
        return 0

    def quick_sort(self, A: list, start: int, end: int) -> None:
        if start >= end:
            return
        pivot = self.partition(A, start, end)
        self.quick_sort(A, start, pivot - 1)
        self.quick_sort(A, pivot + 1, end)

    @staticmethod
    def partition(A: list, start: int, end: int) -> int:
        pivot = A[end]
        i = start
        for j in range(start, end, 1):
            if A[j] < pivot:
                A[i], A[j] = A[j], A[i]
                i = i + 1
        A[i], A[end] = A[end], A[i]
        return i


if __name__ == '__main__':
    print(str(Solution().largestPerimeter([2, 1, 2])))

时间复杂度为 $$O(n)$$ .

Database

Table: Person(PersonId, FirstName, LastName) and Table: Address(AddressId, PersonId, City, State). Write a SQL query for a report that provides the following information for each person in the Person table, regardless if there is an address for each of those people:

> FirstName, LastName, City, State >

SQL语句如下：

SELECT
    FirstName, LastName, City, State
FROM
    Person
LEFT JOIN
    Address
ON
    Person.personId = Address.PersonId

Review

这周开始学习了一下优美的RxJava及RxAndroid，主要看github的项目wiki，计划两周时间内阅读完该wiki：

https://github.com/ReactiveX/RxJava/wiki

Tips

• 修改Ubuntu多系统的默认启动顺序

  

  安装Ubuntu和Windows双系统之后，开机默认会进ubuntu系统，切换默认启动项的方法如下：

  1. 在 termianl 中执行一下代码：

  sudo gedit /etc/default/grub

  2. 输入密码后会打开一个问题，编辑其中GRUB_DEFAULT=0一行，将0修改为4，并保存

  4为上图启动项所在的序号，从0开始计数

  可以修改GRUB_TIMEOUT项，表示在选择界面等待时间。

  3. 在 terminal 中执行以下代码更新grub

  sudo update-grub

  这一步很重要，否则不会生效。

• python中交换 list 中 i, j 两个元素的位置：

num[i], num[j] = num[j], num[i]

Share

分享一篇很赞的文章，关于RxJava的给 Android 开发者的 RxJava 详解