5. 最長(zhǎng)回文子串

給你一個(gè)字符串 s，找到 s 中最長(zhǎng)的回文子串。

示例 1：

輸入：s = "babad"
輸出："bab"
解釋："aba" 同樣是符合題意的答案。
示例 2：

輸入：s = "cbbd"
輸出："bb"
示例 3：

輸入：s = "a"
輸出："a"
示例 4：

輸入：s = "ac"
輸出："a"

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路及方法

這道題使用中心擴(kuò)展算法，先寫一個(gè)函數(shù)，用雙指針的方法從中心擴(kuò)展找到回文串。然后調(diào)用該方法，從字符串的開頭尋找回文串，并對(duì)比長(zhǎng)度。

注意，因?yàn)榛匚拇拈L(zhǎng)度有奇有偶，所以用中心算法的時(shí)候，奇數(shù)就以單個(gè)字符為中心，偶數(shù)就用兩個(gè)字符為中心。

class Solution {
    public String longestPalindrome(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            // 尋找以s[i]為中心的奇數(shù)長(zhǎng)度回文串
            String s1 = findPalindrome(s, i, i);
            // 尋找以s[i]、s[i + 1]為中心的偶數(shù)長(zhǎng)度回文串
            String s2 = findPalindrome(s, i, i + 1);

            res = res.length() > s1.length() ? res : s1;
            res = res.length() > s2.length() ? res : s2;
        }

        return res;
    }

    public String findPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            // 向兩邊擴(kuò)張
            left--;
            right++;
        }

        return s.substring(left + 1, right);
    }
}

結(jié)果如下：

劍指 Offer 32 - III. 從上到下打印二叉樹 III

請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。

例如:
給定二叉樹: [3,9,20,null,null,15,7],

   3
  / \
 9  20
   /  \
  15   7

返回其層次遍歷結(jié)果：

  [
    [3],
    [20,9],
    [15,7]
  ]

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-iii-lcof
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

解題思路及方法

很簡(jiǎn)單的層次遍歷算法，只不過(guò)題目要求的是Z字型，所以我們用層數(shù)來(lái)區(qū)分。當(dāng)層數(shù)為偶數(shù)層的時(shí)候?qū)?dāng)前出隊(duì)序列翻轉(zhuǎn)即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int step = 1;

        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> row = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode cur = queue.poll();
                row.add(cur.val);
                // 子結(jié)點(diǎn)入隊(duì)
                if (cur.left != null) queue.offer(cur.left);
                if (cur.right != null) queue.offer(cur.right);
            }
            if (step % 2 == 0) Collections.reverse(row);
            res.add(row);
            step++;
        }

        return res;
    }
}

結(jié)果如下：