PTA刷题总结-Part 1 基础部分
PTA刷题总结-Part 2 模拟与数学问题
PTA刷题总结-Part 3 数据结构与算法

3 数据结构与算法

对于大多数OJ,一秒能承受的运算次数大概是10^7 ~ 10^8， 所以，对于1000规模的数据，可以承受O(n^2)时间复杂度的算法，因为10^3 * 10^3 = 10^6

3.1 数组和链表

数组不用多说，想来强调链表的写法。
我做题比较习惯于给链表设置哨兵（sentinel），这样可以减少边界极端情况判断，避免没有考虑周全导致出错。如下图中，深灰色部分就是哨兵结点。

image.png

关于链表章节，我单独用一章的篇幅详细写了各种操作。
详情点击：PTA刷题总结-Part3.1 数组与链表专题

注意以下几点

1. 能用哨兵结点简化尽量用哨兵结点
2. 指针指向一个不存在的地址时就会出现段错误，所以要注意指针位置
3. 注意free()掉删除结点

链表真的只有多练习，光看是不会的。

3.2 二分法

二分法听起来很简单，老生常谈了，但是事实上二分法有很多不同的拓展，极易写错，需要单独拉出来一个专题来讲。

详情点击：二分法专题

3.3 排序

排序章节涵盖了冒泡排序O(n^2) 、选择排序O(n^2) 、插入排序O(n^2)、快速排序O(nlogn)和归并排序O(nlogn)的内容。

详情点击：排序专题

3.4 二叉树

树结构有很多内容，具体可以分为

• 数组、链表的存储和基本操作
• 二叉搜索树
• 平衡二叉树
• 堆和哈夫曼树
• 并查集

详情可见：树结构专题

3.5 动态规划

7-17 最长对称子串(最长回文子串) (25分)
https://leetcode-cn.com/problems/longest-palindromic-substring/

public class Solution {
    /**
     * @param s: input string
     * @return: the longest palindromic substring
     */
    public String longestPalindrome(String s) {
       if (s == null || "".equals(s)){
           return "";
       }
       
       int n = s.length();
       int start = 0, end = 0, maxlen = 0;
       for (int i = 0; i < n; i++){
           int len = findLongestPalindromeFrom(s, i, i);
           if (len > maxlen){
               maxlen = len;
               start = i - len / 2;
               end = start + len;
           }
           
           len = findLongestPalindromeFrom(s, i, i+1);
           if (len > maxlen){
               maxlen = len;
               start = i - len / 2 + 1;
               end = start + len;
           }
       }
       
       return s.substring(start, end);
    }
    
    private int findLongestPalindromeFrom(String s, int left, int right) {
        int len = 0;
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
            len = right - left + 1;
            left--;
            right++;
        }
        return len;
    }
}

区间型动态规划
小区间依赖于大区间的结果

• for循环区间的长度 1~n
• for循环区间的起点 0~n-1
• 计算出区间的终点

#include <stdio.h>
#include <string.h>

char str[1001];
int pal[1000][1000];
int main(){
    gets(str);
    int n = strlen(str);
    int maxLen = 0;
    for (int len = 1; len <= n; len++){
        for (int i=0; i<n;i++){
            int j = i + len - 1;
            if (j >= n){
                break;
            }
            if (len == 1){
                pal[i][j] = 1;
            }
            else if (len == 2){
                if (str[i] == str[j]){
                    pal[i][j] = 1;
                }
            }
            else if (str[i] == str[j] && pal[i+1][j-1] == 1){
                pal[i][j] = 1;
            }
            if (pal[i][j] == 1 && len > maxLen){
                maxLen = len;
            }
        }
    }
    printf("%d",maxLen);
    return(0);
}

#include <stdio.h>
#include <string.h>

char str[1001];
int pal[1000][1000];
int main(){
    gets(str);
    int n = strlen(str);
    int maxLen = 0;
    for (int i=0;i<n;i++){
        for (int j=i;j>=0;j--){
            if (str[i] == str[j] && (i-j<2 || pal[j+1][i-1]==1)){
                pal[j][i]=1;
                if (i-j+1 > maxLen){
                    maxLen = i-j+1;
                }
            }
        }
    }
    printf("%d",maxLen);
    return(0);
}

最长回文子序列
注意序列和子串概念不一样

https://www.lintcode.com/problem/longest-palindromic-subsequence/description?_from=ladder&&fromId=1

public class Solution {
    /**
     * @param s: the maximum length of s is 1000
     * @return: the longest palindromic subsequence's length
     */
    public int longestPalindromeSubseq(String s) {
        if (s == null || "".equals(s)) {
            return 0;
        }
        
        int n = s.length();
        if (n == 1) {
            return 1;
        }
        int[][] dp = new int[n + 1][n + 1];
        for (int i = n-1; i >= 0; i--) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = dp[i + 1][j] > dp[i][j - 1] ? dp[i + 1][j] : dp[i][j - 1];
                }
            }
        }
        
        return dp[0][n-1];
    }
}