ARTS打卡—第2周

清明放假出去旅游，没有打卡，这次时补上周的打卡。本周主要对Leetcode 网站上做了一道算法题及一道数据结构题，算法涉及到了动态规划，数据结构涉及到了Limit的用法。

• Algorithm
  • 描述
  • 分析
  • 动态规划方法代码
    • Java
    • Python
• DataBase
• Review
• Tips
• Share

Algorithm

描述

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: “bb”

大致意思就是给定一个字符串，求其最大的回文字符串，所谓回文字符串，简单来讲就是一个字符串正着读和倒着读诗一样的，也就是以中心点对称的。

分析

题目解决方法有好几种，比如

• 暴力解法：循环字符串中每个字符，以该字符起点分别向左右两侧字符进行比较，直到遇到两侧有不相同的字符为止。这种方法需要注意偶数对称和奇数对称的差异化处理。

• 最长公共子串：把给定的字符传反转得到新的字符传，求两个字符串最大的公共字符串，但是这种情况下有些解是错误的。

• 动态规划：

  定义

  $P(i,\ j)=true, \ 下标从 i 到 j 的子串是回文子串$

  $P(i,\ j)=false,\ 其它情况$

  因此

  $P(i, j) = P(i + 1, j - 1) \ \ and \ \ S~i~ == S~j~$

  所以递推公式为：

  $P(i, \ i) = true$

  $P(i, i + 1) = (S~i~ == S~i+1~)$

动态规划方法代码

Java

String longestPalindrome(String s) {
  if (s == null || s.length() == 0) {
    return "";
  }
  int len = s.length();
  boolean[][] temp = new boolean[len][len];
  int maxLen = 1;
  int start = 0;
  for (int i = 0; i < len - 1; i++) {
    temp[i][i] = true;
    if (s.charAt(i) == s.charAt(i + 1)) {
      maxLen = 2;
      temp[i][i + 1] = true;
      start = i;
    }
  }
  temp[len - 1][len - 1] = true;
  for (int tmpLen = 3; tmpLen <= len; tmpLen++) {
    for (int i = 0; i < len - tmpLen + 1; i++) {
      int j = i + tmpLen - 1;
      if (temp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
        maxLen = tmpLen;
        start = i;
        temp[i][j] = true;
      }
    }
  }
  return s.substring(start, start + maxLen);
}

Python

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s or len(s) == 0:
            return ''
        res = [[False for i in range(len(s))] for j in range(len(s))]
        max_len = 1
        start = 0
        str_len = len(s)
        for i in range(str_len - 1):
            res[i][i] = True
            if s[i] == s[i + 1]:
                res[i][i + 1] = True
                start = i
                max_len = 2
        res[str_len - 1][str_len - 1] = True
        for tmp_len in range(3, str_len + 1):
            for i in range(str_len - tmp_len + 1):
                j = i + tmp_len - 1
                if res[i+1][j-1] and s[i] == s[j]:
                    max_len = tmp_len;
                    start = i
                    res[i][j]=True
        return s[start: start + max_len]

运行数据如下：

貌似可以优化？不过这样相对比较好理解啊

DataBase

Write a SQL query to get the second highest salary from the Employee table.

Write a SQL query to get the n^th highest salary from the Employee table.

# 第二高
SELECT
    IFNULL(
        (SELECT DISTINCT Salary
        FROM Employee
        ORDER BY Salary DESC
        LIMIT 1,1),
    NULL) AS SecondHighestSalary
# 第N高
CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  set N = N - 1;
  RETURN (
      # Write your MySQL query statement below.
      SELECT DISTINCT Salary
      FROM Employee
      ORDER BY Salary DESC
      LIMIT 1 OFFSET N
  );
END

Review

Understanding Clean Code in Android

主要讲了Android中的代码规范：S.O.L.I.D规范:

• Single Responsibility Principle — SRP： 每个类必须只有单一的功能
• Open-Closed Principle — OCP：对继承开放，但是要对修改关闭
• Liskov Substitutions Principle — LSP：子类可以继承并重写自己的功能，但是不能改变父类的功能
• Interface Segregation Principle — ISP：实现接口时不应该实现所有接口方法，应只实现使用到的方法
• Dependency Inversion Principle — DIP：高级模块不应依赖低级模块，抽象不应依赖于细节，细节应依赖抽象

Tips

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

  • sudo gedit /etc/default/grub修改# GRUB_DEFAULT=0一行
  • sudo update-grub

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

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

• git status 不显示文件权限修改

  git config fileMode false

Share

https://blog.csdn.net/Luoshengyang/article/details/6564592

老罗的 Android 课中的下载 android 内核代码的方法。