341. Flatten Nested List Iterator

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list — whose elements may also be integers or other lists.

Example 1:
Given the list [[1,1],2,[1,1]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:
Given the list [1,[4,[6]]],

By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6]
思路: 用一个List来盛放flatten之后的元素,同时用一个index来取当前flatten list的元素。

/**
 * // 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.
 *     public boolean isInteger();
 *
 *     // @return the single integer that this NestedInteger holds, if it holds a single integer
 *     // Return null if this NestedInteger holds a nested list
 *     public Integer getInteger();
 *
 *     // @return the nested list that this NestedInteger holds, if it holds a nested list
 *     // Return null if this NestedInteger holds a single integer
 *     public List<NestedInteger> getList();
 * }
 */
public class NestedIterator implements Iterator<Integer> {
    List<Integer> flatList;
    int index;

    public NestedIterator(List<NestedInteger> nestedList) {
        flatList = new ArrayList<Integer>();
        index = 0;
        dumpToList(nestedList, flatList);
    }

    public void dumpToList(List<NestedInteger> nestedList, List<Integer> flatList) {
        for (NestedInteger ni : nestedList) {
            if (ni.isInteger()) {
                flatList.add(ni.getInteger());
            } else {
                dumpToList(ni.getList(), flatList);
            }
        }
    }


    @Override
    public Integer next() {
        if (hasNext()) {
            Integer result = flatList.get(index);
            index++;
            return result;
        } 
        return null;
    }

    @Override
    public boolean hasNext() {
        return index < flatList.size();
    }
}

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i = new NestedIterator(nestedList);
 * while (i.hasNext()) v[f()] = i.next();
 */
Advertisements

348. Design Tic-Tac-Toe

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules:

A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
Follow up:
Could you do better than O(n2) per move() operation?

思路: 先给出最naive的解法,每下一步去查下所有的行,列,对角线跟斜对角线是否满足。 这样的话时间复杂度为O(n^2).

public class TicTacToe {
    private int[][] board;
    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        this.board = new int[n][n];
        this.n = n;
    }

    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        board[row][col] = player;
        if(isWin(board, row, col)) {
            return player;
        }
        return 0;
    }

    public boolean isWin(int[][] board,int row, int col) {
        boolean isRow = true, isCol = true, isDig = true, isAntiDig = true;
        // check row
        for (int i = 0; i < n - 1; i++) {
            if (board[row][i] != board[row][i + 1] )
                isRow = false;
        }
        // check col
        for (int j = 0; j < n - 1; j++) {
            if (board[j][col] != board[j + 1][col])
                isCol = false;
        }
        // check diagional
        if (row == col) {
            for (int i = 0; i < n - 1; i++) {
                if (board[i][i] != board[i + 1][i + 1]) 
                    isDig = false;
            }
        } else {
            isDig = false;
        }
        if (row + col == n - 1) {
            // check anti diagional
            for (int i = 0; i < n - 1; i++) {
                if (board[i][n - 1 - i] != board[i + 1][n - 2 - i]) 
                    isAntiDig = false;
            } 
        } else {
            isAntiDig = false;
        }
        return isRow || isCol || isDig || isAntiDig;
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

在followup中,问是否能把时间复杂度降到O(n^2)以下,我们只保存列,行,更对角线元素的状态。 play 1对应的值为1, play2对应的值为-1;

public class TicTacToe {
    private int[] columns; 
    private int[] rows;
    private int diagonal;
    private int antiDiagonal;
    private int n;

    /** Initialize your data structure here. */
    public TicTacToe(int n) {
        columns = new int[n];
        rows = new int[n];
        diagonal = 0;
        antiDiagonal = 0;
        this.n = n;
    }

    /** Player {player} makes a move at ({row}, {col}).
        @param row The row of the board.
        @param col The column of the board.
        @param player The player, can be either 1 or 2.
        @return The current winning condition, can be either:
                0: No one wins.
                1: Player 1 wins.
                2: Player 2 wins. */
    public int move(int row, int col, int player) {
        //Take player 1 and 2 as value of 1 and -1;
        int number = player == 1 ? 1 : -1;  // place the player, identify which player; player 1 as 1, player 2 as -1;
        rows[row] += number;   // save the value to row, col, diag, antiDiag
        columns[col] += number;
        if (row == col) {
            diagonal += number;
        }
        if (row == n - 1 - col) {
            antiDiagonal += number;
        }
        if (Math.abs(rows[row]) == n || Math.abs(columns[col]) == n ||  // winning condition
             Math.abs(diagonal) == n || Math.abs(antiDiagonal) == n)
            return player;
        return 0;    
    }
}

/**
 * Your TicTacToe object will be instantiated and called as such:
 * TicTacToe obj = new TicTacToe(n);
 * int param_1 = obj.move(row,col,player);
 */

170. Two Sum III – Data structure design

Design and implement a TwoSum class. It should support the following operations: add and find.

add – Add the number to an internal data structure.
find – Find if there exists any pair of numbers which sum is equal to the value.

For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

思路: 题目不难,用个hashmap来解,注意可能会出现重复数字. hashMap中村数字跟出现的次数,
复杂度: 插入O(n), 查找O(1)

public class TwoSum {
    HashMap<Integer, Integer> map;

    public TwoSum (){
        map = new HashMap<>();
    }

    // Add the number to an internal data structure.
    public void add(int number) {
        if (map.containsKey(number)) {
            map.put(number, map.get(number) + 1);
        } else {
            map.put(number, 1);
        }
    }

    // Find if there exists any pair of numbers which sum is equal to the value.
    public boolean find(int value) {
        for (int key: map.keySet()) {
            int target = value - key;
            if (key == target && map.get(target) > 1) {
                return true;
            } else if (key != target && map.containsKey(target)) {
                return true;
            }
        }
        return false;
    }
}

281. Zigzag Iterator

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

For example, given two 1d vectors:

v1 = [1, 2]
v2 = [3, 4, 5, 6]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1, 3, 2, 4, 5, 6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question – Update (2015-09-18):
The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example, given the following input:

[1,2,3]
[4,5,6,7]
[8,9]
It should return [1,4,8,2,5,9,3,6,7].

思路: 用一个queue来实现, 把元素按照Cyclic的顺序放到queue里面.

public class ZigzagIterator {
    private ArrayDeque<Integer> queue;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        queue = new ArrayDeque<>();
        this.addToQueue(v1, v2, queue);
    }

    public int next() {
        return queue.poll();
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }
    private void addToQueue(List<Integer> v1, List<Integer> v2, ArrayDeque<Integer> queue) {
        List<List<Integer>> list = new ArrayList<>();
        list.add(v1);
        list.add(v2);
        int size = Math.max(v1.size(), v2.size());
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < list.size(); j++) { 
                if (list.get(j).size() <= i) continue; // 排除小于size的list
                Integer value = list.get(j).get(i);
                if (value != null) {
                    queue.offer(value);
                }
            }
        }

    }
}

/**
 * Your ZigzagIterator object will be instantiated and called as such:
 * ZigzagIterator i = new ZigzagIterator(v1, v2);
 * while (i.hasNext()) v[f()] = i.next();
 */

284. 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().

Here is an example. Assume that the iterator is initialized to the beginning of the list: [1, 2, 3].

Call next() gets you 1, the first element in the list.

Now you call peek() and it returns 2, the next element. Calling next() after that still return 2.

You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.

Hint:

Think of “looking ahead”. You want to cache the next element.
Is one variable sufficient? Why or why not?
Test your design with call order of peek() before next() vs next() before peek().
For a clean implementation, check out Google’s guava library source code.
Follow up: How would you extend your design to be generic and work with all types, not just integer?

思路: 用一个全局变量next, 用来cache下一个元素。

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html
class PeekingIterator implements Iterator<Integer> {
    private Iterator<Integer> iterator;
    private Integer next;

    public PeekingIterator(Iterator<Integer> iterator) {
        // initialize any member here.
        this.iterator = iterator;
        if (iterator.hasNext()) {
            this.next = iterator.next();
        }
    }

    // Returns the next element in the iteration without advancing the iterator.
    public Integer peek() {
        return next;
    }

    // hasNext() and next() should behave the same as in the Iterator interface.
    // Override them if needed.
    @Override
    public Integer next() {
        int res = next;
        this.next = this.iterator.hasNext() ? this.iterator.next() : null;
        return res;
    }

    @Override
    public boolean hasNext() {
        return next != null;
    }
}

380/381. Insert Delete GetRandom O(1)

Design a data structure that supports all following operations in average O(1) time.

insert(val): Inserts an item val to the collection.
remove(val): Removes an item val from the collection if present.
getRandom: Returns a random element from current collection of elements. The probability of each element being returned is linearly related to the number of same value the collection contains.
思路: 设计个数据结构,用hashmap+List来做。
insert: hashmap中存(val, idx), idx为在List中的元素的下标位置。
remove: 删除的时候要求是O(1);把元素val与List中最后一个元素兑换,然后删除最后一个元素。
1. 从hashmap中拿到元素val在List中的下标 2.拿到List中最后一个元素的值last 3. List中把val下标位置的元素更新为last元素的值,map中加入(last, idx)。 4.最后List中移除最后一个元素,map中remove掉val的key。

public class RandomizedSet {
    List<Integer> list;
    HashMap<Integer, Integer> map;
    Random rand;

    /** Initialize your data structure here. */
    public RandomizedSet() {
        list = new ArrayList<>();
        map = new HashMap<>();
        rand = new Random();
    }

    /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) return false;
        list.add(val);
        map.put(val, list.size() - 1);
        return true;
    }

    /** Removes a value from the set. Returns true if the set contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int index = map.get(val);
        if (index != list.size() - 1) {
            int last = list.get(list.size() - 1);
            list.set(index, last);
            map.put(last, index);
        }
        map.remove(val);
        list.remove(list.size() - 1);
        return true;
    }

    /** Get a random element from the set. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

Follow up: 允许duplicates的存在。

public class RandomizedCollection {
    List<Integer> list;
    HashMap<Integer, Set<Integer>> map;
    Random rand = new Random();

    /** Initialize your data structure here. */
    public RandomizedCollection() {
        list = new ArrayList<>();
        map = new HashMap<>();

    }

    /** Inserts a value to the collection. Returns true if the collection did not already contain the specified element. */
    public boolean insert(int val) {
        if (map.containsKey(val)) {
            Set<Integer> set = map.get(val); // get existing set
            list.add(val); // add to list
            set.add(list.size() - 1); // add idx to set
            map.put(val, set);
            return false;
        } 
        list.add(val);
        int idx = list.size() - 1;
        map.put(val, new HashSet<Integer>(Arrays.asList(idx)));
        return true;
    }

    /** Removes a value from the collection. Returns true if the collection contained the specified element. */
    public boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        Set<Integer> set = map.get(val);
        int toRemovePos = set.iterator().next(); // the idx of to remove element 
        set.remove(toRemovePos);
        if (toRemovePos < list.size() - 1) { // list have more than 1 elements
            int last = list.get(list.size() - 1); // get the last element
            list.set(toRemovePos, last); // set the last element at toRemovePos position
            map.get(last).remove(list.size() - 1); // remove the last element from map
            map.get(last).add(toRemovePos); 
        }
        list.remove(list.size() - 1);
        if (map.get(val).isEmpty()) { // check set is empty
            map.remove(val);
        }

        return true;
    }

    /** Get a random element from the collection. */
    public int getRandom() {
        return list.get(rand.nextInt(list.size()));
    }
}

/**
 * Your RandomizedCollection object will be instantiated and called as such:
 * RandomizedCollection obj = new RandomizedCollection();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

208. Implement Trie (Prefix Tree)

Implement a trie with insert, search, and startsWith methods.

Note:
You may assume that all inputs are consist of lowercase letters a-z.

思路:Trie的实现,这里用HashMap来实现。

class TrieNode {
    // Initialize your data structure here.
    HashMap&lt;Character, TrieNode&gt; children;
    boolean hasWord;
    public TrieNode() {
        children = new HashMap&lt;Character, TrieNode&gt;();
        hasWord = false;
    }
}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        if (word.length() == 0 || word == null) return;
        TrieNode current = root;
        for (int i = 0; i &lt; word.length(); i++) {
            char c = word.charAt(i);
            if(!current.children.containsKey(c)) {
                current.children.put(c, new TrieNode());
            }
            current = current.children.get(c);
        }
        current.hasWord = true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        if (word.length() == 0 || word == null) return false;
        TrieNode current = root;
        for (int i = 0; i &lt; word.length(); i++) {
            char c = word.charAt(i);
            if (!current.children.containsKey(c)) {
                return false;
            }
            current = current.children.get(c);
        }
        return current.hasWord;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        if (prefix.length() == 0 || prefix == null) return true;
        TrieNode current = root;
        for (int i = 0; i &lt; prefix.length(); i++) {
            char c = prefix.charAt(i);
            if (!current.children.containsKey(c)) {
                return false;
            }
            current = current.children.get(c);
        }
        return true;
    }
}

// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert(&quot;somestring&quot;);
// trie.search(&quot;key&quot;);