Tags » Iterator

[LeetCode]Closest Binary Search Tree Value II

题目:
给定一个BST,一个target value,请找出k个closest value
https://leetcode.com/problems/closest-binary-search-tree-value-ii/

解法:
凡是BST的题目,先当成有序数组做。
实质就是实现BST的正向,反向iterator
没什么特殊的

Java代码:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    // accepted
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        Stack<TreeNode> forward = initForwardStack(root, target);
        Stack<TreeNode> backward = initBackwardStack(root, target);
        
        if (!forward.isEmpty() && !backward.isEmpty() && forward.peek() == backward.peek()) {
            getNext(forward);
        }
        
        List<Integer> res = new ArrayList<>();
        while(k> 0) {
            if (forward.isEmpty()) {
                res.add(getPrev(backward));
            } else if (backward.isEmpty()) {
                res.add(getNext(forward));
            } else {
                double diff_prev = Math.abs(backward.peek().val - target);
                double diff_next = Math.abs(forward.peek().val - target);
                if (diff_prev < diff_next) {
                    res.add(getPrev(backward));
                } else {
                    res.add(getNext(forward));
                }
            }
            k--;
        }
        
        return res;
    }
    
    private Stack<TreeNode> initForwardStack(TreeNode root, double target) {
        Stack<TreeNode> forward = new Stack<>();
        TreeNode cur = root;
        while(cur != null) {
            if (cur.val == target) {
                forward.push(cur);
                break;
            } else if (cur.val > target) {
                forward.push(cur);
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return forward;
    }
    
    private Stack<TreeNode> initBackwardStack(TreeNode root, double target) {
        Stack<TreeNode> backward = new Stack<>();
        TreeNode cur = root;
        while(cur != null) {
            if (cur.val == target) {
                backward.push(cur);
                break;
            } else if (cur.val < target) {
                backward.push(cur);
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return backward;
    }
    
    private int getNext(Stack<TreeNode> forward) {
        TreeNode cur = forward.pop();
        int res = cur.val;
        cur = cur.right;
        while(cur != null) {
            forward.push(cur);
            cur = cur.left;
        }
        return res;
    }
    
    private int getPrev(Stack<TreeNode> backward) {
        TreeNode cur = backward.pop();
        int res = cur.val;
        cur = cur.left;
        while(cur != null) {
            backward.push(cur);
            cur = cur.right;
        }
        return res;
    }
}

[LeetCode] Flatten Nested List Iterator

题目:
一个list,元素可能是integer,也可能是list
请实现它的iterator

解法:
iterator的实现方法有很多,看你怎么选择状态变量,怎么维护next,hasNext函数。只要结果对,逻辑清晰就可以了。

Java代码:

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * public interface NestedInteger {
 *
 *     // @return true if this NestedInteger holds a single integer, rather than a nested list. 165 more words

Leetcode 284. Peeking Iterator

https://leetcode.com/problems/peeking-iterator/

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation — it essentially peek() at the element that will be returned by the next call to next(). 303 more words

Algorithms

[LeetCode] Zigzag Iterator

题目:
按照zigzag路线来回打印两个list
https://leetcode.com/problems/zigzag-iterator/

解法:
1)naive,用两个坐标,来回alternate
2)用internal data structure自带的iterator

Java代码(naive):

public class ZigzagIterator {
    private int x;
    private int y;
    private List<Integer> v1;
    private List<Integer> v2;
    private int cur;
    
    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.v1 = v1;
        this.v2 = v2;
        x = 0;
        y = 0;
        cur = 0;
    }

    public int next() {
        int res;
        if (cur == 0) {
            if (x < v1.size()) {
                res = v1.get(x++);
            } else {
                res = v2.get(y++);
            }
        } else {
            if (y < v2.size()) {
                res = v2.get(y++);
            } else {
                res = v1.get(x++);
            }
        }
        
        cur = 1 - cur;
        
        return res;
    }

    public boolean hasNext() {
        if (v1 == null && v2 == null) {
            return false;
        } else if (v1 == null) {
            return y < v2.size();
        } else if (v2 == null) {
            return x < v1.size();
        } else {
            return x < v1.size() || y < v2.size();
        }
    }
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i = new ZigzagIterator(v1, v2);
 * while (i.hasNext()) v = i.next();
 */
… 96 more words

Iterator Pattern

What is Iterator Design Pattern ?

  • is a behavioural design pattern
  • defines a way to move through a collection of data in a particular class…
  • 62 more words
Design Patterns

ZigZag Iterator

Problem: Given two 1d vectors, implement an iterator to return their elements alternately.

For example, given two 1d vectors:

v1 = 
v2 = 

By calling next repeatedly until hasNext returns… 101 more words

IN ENGLISH

Spelunking Linux - what is this auxv thing anyway

While spelunking Linux, trying to find an easier way to do this or that, I ran across this vDSO thing (virtual ELF Dynamic Shared Object). What? 2,062 more words

LuaJIT