刷题练习、Go字符串拼接、删除二叉搜索树节点

---

Go实现字符串拼接

+号拼接

s := "123"
s += "456"
fmt.Println(s) // 123456

fmt 拼接

s := fmt.Sprintf("%s world\n", "hello")
println(s) // hello world

Join 拼接

strs := []string{"hello", "world"}
println(strings.Join(strs, " ")) // hello world

buffer拼接

buffer := bytes.NewBufferString("hi")
buffer.WriteByte(' ')
buffer.WriteString("world")
buffer.WriteRune('哈')
println(buffer.String()) // hi world哈

练习

给你一个字符串 s，找到 s 中最长的回文子串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：

输入：s = "cbbd"
输出："bb"

代码：

import "bytes"

func longestPalindrome(s string) string {
    buffer := bytes.NewBufferString("#")
    for i:=0;i<len(s);i++ {
        buffer.WriteByte(s[i])
        buffer.WriteByte('#')
    }
    
    result := 0
    mid := 0
    str := buffer.String()
    for i:=0;i<len(str);i+=1 {
        gap := 1
        for i-gap>=0 && i+gap<len(str) && str[i-gap]==str[i+gap] {
            gap++
        }
        // #1#1#
        // #1#
        if gap-1 > result {
            mid = i
            result = gap-1
        }
    }

    var ret []byte
    if str[mid]!='#' {
        ret = append(ret,str[mid])
    }
    for i:=1;i<=result;i++ {
        if str[mid+i]!='#' {
            ret = append(ret,str[mid+i])
            ret = append([]byte{str[mid-i]},ret...)
        }
    }
    return string(ret)
}

297. 二叉树的序列化与反序列化

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null) return "";
        StringBuilder sb = new StringBuilder();
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        TreeNode cur;
        while(!deque.isEmpty()) {
            int sz = deque.size();
            for(int i=0;i<sz;i++) {
                cur = deque.pollFirst();
                if(cur!=null) {
                    sb.append(cur.val);
                    deque.addLast(cur.left);
                    deque.addLast(cur.right);
                } else {
                    sb.append("null");
                }
                sb.append(",");
            }
        }
        sb.deleteCharAt(sb.length()-1);
        //System.out.println(sb);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.length()==0) return null;
        String[] nodes = data.split(",");
        TreeNode root = new TreeNode(Integer.parseInt(nodes[0]));
        Deque<TreeNode> deque = new LinkedList<>();
        deque.addLast(root);
        TreeNode cur;
        int idx = 1;
        while(!deque.isEmpty()) {
            int sz = deque.size();
            for(int i=0;i<sz;i++) {
                cur = deque.pollFirst();
                if(!nodes[idx].equals("null")) {
                    cur.left = new TreeNode(Integer.parseInt(nodes[idx]));
                    deque.addLast(cur.left);
                }
                idx++;
                if(!nodes[idx].equals("null")) {
                    cur.right = new TreeNode(Integer.parseInt(nodes[idx]));
                    deque.addLast(cur.right);
                }
                idx++;
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

状态机

8. 字符串转换整数 (atoi)

class Solution {
    public int myAtoi(String s) {
        //"  -123 sfs123"
        // 1:前导空格, 空格->1,符号->2,数字->3,其它->4
        // 2:符号,数字->3,其它->4
        // 3:数字,数字->3,其它->4
        // 4:结束
        int curState = 1;
        long positeveNum = 0;
        int sig = 1;
        for(int i=0;i<s.length();i++) {
            if(s.charAt(i)==' ') {
                if(curState!=1) break;
            } else if(s.charAt(i)=='-'||s.charAt(i)=='+') {
                if(curState!=1) break;
                curState = 2;
                if(s.charAt(i)=='-') sig=-1;
            } else if(s.charAt(i)>='0'&&s.charAt(i)<='9') {
                curState = 3;
                positeveNum = positeveNum*10+s.charAt(i)-'0';
                if(sig*positeveNum>=Integer.MAX_VALUE) return Integer.MAX_VALUE;
                if(sig*positeveNum<=Integer.MIN_VALUE) return Integer.MIN_VALUE;
            } else {
                break;
            }
        }
        return sig*(int)positeveNum;
    }
}

450. 删除二叉搜索树中的节点（挺妙的，再看看）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null) return null;
        if(key>root.val) root.right = deleteNode(root.right,key);
        else if(key<root.val) root.left = deleteNode(root.left,key);
        else {
            if(root.right==null) return root.left;
            if(root.left==null) return root.right;
            TreeNode p = root.right;
            while(p.left!=null) p = p.left;
            p.left = root.left;
            return root.right;
        }
        return root;
    }
}