[数据结构与算法]剑指offer 2021/8/1

58 - I. 翻转单词顺序

法一：

class Solution {
    public String reverseWords(String s) {
        if(s.equals(""))
            return "";
        int m = 0;
        //去掉字符串前的空格
        while(s.charAt(m)==' '){
            s = s.substring(m+1);
            if(s.equals(""))
                return "";
        }
        //去掉字符串后的空格
        int n = s.length() - 1;
        while(s.charAt(n)==' '){
            s=s.substring(0,n);
            n--;
        }
        //将字符串以空格划分
        String[] split = s.split(" ");
        String res = "";
        for(int i = split.length - 1; i >= 0; --i){
            if(split[i].equals("")){
                continue;
            }
            if(i == 0){
                res += split[0];
            }else{
                res += split[i];
                res += ' ';
            }
            System.out.println(i+split[i]);
        }
        return res;
    }
}

法二：

和方法一思路一样，但是使用了trim方法来删除首尾空格。

class Solution {
    public String reverseWords(String s) {
        String[] split = s.split(" ");
        StringBuilder str = new StringBuilder();
        for(int i = split.length - 1; i >= 0; --i){
            if(split[i].equals("")){
                continue;
            }
            str.append(split[i] + " ");
        }
        return str.toString().trim();
    }
}

法三：

双指针法

class Solution {
    public String reverseWords(String s) {
        StringBuffer str = new StringBuffer();
        //i,j两个指针分别指向单词的首尾
        int i = s.length()-1, j = s.length()-1;
        while(i >= 0){
            //寻找单词的左边界
            while(i >= 0 && s.charAt(i) != ' ')   i--;
            str.append(s.substring(i+1, j+1) + " ");
            //寻找单词的有边界
            while(i >= 0 && s.charAt(i) == ' ')   i--;
            j = i;
        }
        //去掉首尾空格
        return str.toString().trim();
    }
}

注意：

每次对 String 类型进行改变的时候其实都等同于生成了一个新的 String 对象，然后将指针指向新的 String 对象。
所以当程序中需要大量的对某个字符串进行操作时，应该考虑应用StringBuilder类处理该字符串，其设计目的就是针对大量string操作的一种改进办法，避免产生太多的临时对象；而当程序中只是对某个字符串进行一次或几次操作时，采用string类即可。

32 - III. 从上到下打印二叉树 III

法一：

双端队列。
设置一个flag标记，通过判断flag的值决定从左到右or从右到左输出。要注意插入和删除元素的位置。(可以不设置flag，因为在奇数层遍历完之后队列中已经有了偶数层的节点，只需判断队列是否为空，继续操作即可。）

/**
 * 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) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<List<Integer>> res = new LinkedList<>();
        if(root == null)
            return res;
        queue.push(root);
        int flag = 0;
        while(!queue.isEmpty()){
            //保存每层的遍历结果
            LinkedList<Integer> temp = new LinkedList<>();
            int n = queue.size();
            if(flag == 0){
                for(int i = 0; i < n; ++i){
                    TreeNode node = queue.removeLast();
                    temp.add(node.val);
                    if(node.left!=null){
                        queue.push(node.left);
                    }
                    if(node.right!=null){
                        queue.push(node.right);
                    }
                }
            }else{
               for(int i = 0; i < n; ++i){
                    TreeNode node = queue.pop();
                    temp.add(node.val);
                    if(node.right!=null){
                        queue.add(node.right);
                    }
                    if(node.left!=null){
                        queue.add(node.left);
                    }
                } 
            }
            flag = 1-flag;
            res.add(temp);
        }
        return res;
    }
}

法二：

和方法一的思想类似，但是不用在插入删除节点的时候改变顺序，而是在将节点的val值插入temp列表时改变顺序。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<List<Integer>> res = new LinkedList<>();
        if(root != null)
            queue.add(root);
        while(!queue.isEmpty()){
            //保存每层的遍历结果
            LinkedList<Integer> temp = new LinkedList<>();
            for(int i = queue.size(); i > 0; --i){
                TreeNode node = queue.pop();
                //奇数层,从尾部插入
                if(res.size() % 2 == 0) temp.add(node.val);
                //偶数层，从前端插入
                else    temp.push(node.val);
                if(node.left != null)
                    queue.add(node.left);
                if(node.right != null)
                    queue.add(node.right);
            }
            res.add(temp);
        }
        return res;
    }
}

法三：

按普通层次遍历的方法进行遍历，最后判断若为奇数层，则将tmp数组中的元素反转。

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<>();
        LinkedList<List<Integer>> res = new LinkedList<>();
        if(root != null)
            queue.add(root);
        while(!queue.isEmpty()){
            List<Integer> tmp = new LinkedList<>();
            for(int i = queue.size(); i > 0; --i){
                TreeNode node = queue.pop();
                tmp.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            //如果是偶数层，则将tmp反转
            if(res.size()%2 != 0)
                Collections.reverse(tmp);
            res.add(tmp);
        }
        return res;
    }
}

35. 复杂链表的复制

法一：哈希表

首次遍历将旧节点和新节点对应存在哈希表中，再次遍历给next和random赋值。

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        Node cur = head;
        HashMap<Node, Node> map = new HashMap<>();
        while(cur != null){
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }
        cur = head;
        while(cur != null){
            //get(cur)是旧链表中cur节点在新链表中对应的节点
            //get(cur.next)是旧链表中cur节点的next节点在新链表中对应的节点
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

法二：

首先拼接新旧链表，接着循环给random赋值，最后拆分新旧链表，返回新链表头节点。

class Solution {
    public Node copyRandomList(Node head) {
        if(head==null){
            return null;
        }
        //将新旧链表合并为同一个
        Node cur = head;
        while(cur != null){
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        //给random赋值
        cur = head;
        while(cur != null){
            if(cur.random != null)
                cur.next.random = cur.random.next;
            cur = cur.next.next;
        }
        cur = head.next;
        Node res = head.next, pre = head;
        //拆分新旧链表
        while(cur.next != null){
            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;
        return res;
    }
}