总结：#

再提升1分钟的速度即可进前200
这种光标左右移动的题目，只划分左右两边的情况，使用双栈会比链表更合适。

第一题：简单遍历题#

重点在于能否快速理解并迅速编写，用一个递归可以快速搞定。

public int minMaxGame(int[] nums) {
    if (nums.length == 1) {
        return nums[0];
    }
    int[] newNums = new int[nums.length/2];
    for (int i = 0;i<newNums.length;i++) {
        if (i%2==0) {
            newNums[i] = Math.min(nums[2*i], nums[2*i+1]);
        } else {
            newNums[i] = Math.max(nums[2*i], nums[2*i+1]);
        }
    }
    return minMaxGame(newNums);
}

第二题：排序预处理#

题目说是子序列（即可以不连在一起），然后要求每个序列内差值尽可能满足小于k。

那很容易想到先排序，再选取即可，就是预处理的思想

可惜这里还是思考的慢了点，用了5分钟才做完

public int partitionArray(int[] nums, int k) {
    Arrays.sort(nums);
    int lastNum = 0;
    int result = 0;
    for (int i = 0;i < nums.length;i++) {
        if (i == 0) {
            lastNum = nums[i];
            continue;
        }
        
        if (nums[i]  - lastNum > k) {
            result++;
            lastNum = nums[i];
        }
    }
    
    result++;
    return result;
}

第三题#

这里如果能快速理解不需要考虑相同的整数，无论如何替换都是保证数组中互不相同的话，那就非常简单了，直接使用1个map进行处理即可。

public int[] arrayChange(int[] nums, int[][] operations) {
    Map<Integer, Integer> numToIndexMap = new HashMap<>();
    for (int i =0;i<nums.length;i++) {
        numToIndexMap.put(nums[i], i);
    }
    for (int[] op : operations) {
        int a = op[0];
        int b = op[1];
        if (numToIndexMap.containsKey(a)) {
            int index = numToIndexMap.get(a);
            numToIndexMap.remove(a);
            nums[index] = b;
            numToIndexMap.put(b, index);
        }
    }
    return nums;
}

第四题：链表模拟，最优则是栈模拟#

想了5分钟，决定模拟一个链表，很久没写了，写得很慢，每次还得画图。

链表模拟：#

class TextEditor {

static class Node {
            char c;
            Node last;
            Node next;

            public Node(char c) {
                this.c = c;
            }
        }

        Node cursorNode;

        public TextEditor() {
            cursorNode = new Node('|');
        }

        public void addText(String text) {
            Node lastNode = cursorNode.last;
            for (char c:text.toCharArray()) {
                Node node = new Node(c);
                node.last = lastNode;
                node.next = cursorNode;

                if (lastNode != null) {
                    lastNode.next = node;
                }
                cursorNode.last = node;
                lastNode = node;
            }
        }

        public int deleteText(int k) {
            int deleCount = 0;
            while (cursorNode.last != null && k-- > 0) {
                Node deleNode = cursorNode.last;
                Node lastNode = deleNode.last;

                if (lastNode != null) {
                    lastNode.next = cursorNode;
                }
                cursorNode.last = lastNode;
                deleCount++;
            }
            return deleCount;
        }

        public String cursorLeft(int k) {
            while(cursorNode.last != null && k-- > 0) {
                Node lastNode = cursorNode.last;
                Node nextNode = cursorNode.next;

                if (lastNode != null) {
                    lastNode.next = nextNode;
                    if (lastNode.last != null) {
                        lastNode.last.next = cursorNode;
                    }
                    cursorNode.last = lastNode.last;
                    cursorNode.next = lastNode;
                    lastNode.last = cursorNode;
                }

                if (nextNode != null) {
                    nextNode.last = lastNode;
                }
            }
            return getLeftStr();
        }

        public String getLeftStr() {
            Node lastNode = cursorNode.last;
            int k = 10;
            StringBuilder sb = new StringBuilder();
            while(lastNode != null && k-- > 0) {
                sb.append(lastNode.c);
                lastNode = lastNode.last;
            }
            return sb.reverse().toString();
        }

        public String cursorRight(int k) {
            while(cursorNode.next != null && k-- > 0) {
                Node lastNode = cursorNode.last;
                Node nextNode = cursorNode.next;

                if (nextNode != null) {
                    nextNode.last = lastNode;
                    if (nextNode.next != null) {
                        nextNode.next.last = cursorNode;
                    }
                    cursorNode.next = nextNode.next;
                    cursorNode.last = nextNode;
                    nextNode.next = cursorNode;
                }

                if (lastNode != null) {
                    lastNode.next = nextNode;
                }
            }
            return getLeftStr();
        }
}

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor obj = new TextEditor();
 * obj.addText(text);
 * int param_2 = obj.deleteText(k);
 * String param_3 = obj.cursorLeft(k);
 * String param_4 = obj.cursorRight(k);
 */

关于这一题，更好的做法是用2个栈，因为始终只划分左右两边，且都是相邻移动，不会直接跳转，用2个栈是更合适的一种实现。

使用栈实现，5分钟写完：#

class TextEditor {

    Deque<Character> leftStack = new LinkedList<>();
    Deque<Character> rightStack = new LinkedList<>();

    public TextEditor() {
        
    }

    public void addText(String text) {
        for (char c : text.toCharArray()) {
            leftStack.push(c);
        }
    }

    public int deleteText(int k) {
        int deleCount = Math.min(k, leftStack.size());
        while (!leftStack.isEmpty() && k-- > 0) {
            leftStack.pop();    
        }
        return deleCount;
    }

    public String cursorLeft(int k) {
        while (!leftStack.isEmpty() && k-->0) {
            rightStack.push(leftStack.pop());
        }
        return getLeftStr();
    }

    public String getLeftStr() {
        int k = 10;
        StringBuilder sb = new StringBuilder();
        while (!leftStack.isEmpty() && k-->0) {
            sb.append(leftStack.pop());                
        }
        String result = sb.reverse().toString();
        addText(result);
        return result;
    }

    public String cursorRight(int k) {
        while (!rightStack.isEmpty() && k-->0) {
            leftStack.push(rightStack.pop());
        }
        return getLeftStr();
    }
}

/**
 * Your TextEditor object will be instantiated and called as such:
 * TextEditor obj = new TextEditor();
 * obj.addText(text);
 * int param_2 = obj.deleteText(k);
 * String param_3 = obj.cursorLeft(k);
 * String param_4 = obj.cursorRight(k);
 */

破晓的知识屋

第296场周赛-209名-36分钟4题