LeetCode(31) -- 707, 717, 720, 724

P707. Design Linked List (Easy)

自己实现Linked List

我的代码

public class E_707_DesignLinkedList {

    class LinkedListNode{
        int value;
        LinkedListNode next;

        public LinkedListNode(int value, LinkedListNode next) {
            this.value = value;
            this.next = next;
        }
    }

    LinkedListNode head;
    private int size;

    /** Initialize your data structure here. */
    public E_707_DesignLinkedList() {

    }

    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    public int get(int index) {
        if (index >= size || index < 0) {
            return -1;
        }
        int current = 0;
        LinkedListNode position = head;
        while (current != index) {
            position = position.next;
            current++;
        }
        return position.value;
    }

    /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    public void addAtHead(int val) {
        head = new LinkedListNode(val, head);
        size++;
    }

    /** Append a node of value val to the last element of the linked list. */
    public void addAtTail(int val) {
        if (head == null) {
            head = new LinkedListNode(val, null);
            size++;
            return;
        }
        LinkedListNode position = head;
        while (position.next != null) {
            position = position.next;
        }
        position.next = new LinkedListNode(val, null);
        size++;
    }

    /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index <= 0) {
            addAtHead(val);
        } else {
            int currentIndex = 1;
            LinkedListNode position = head;
            while (currentIndex != index) {
                currentIndex++;
                position = position.next;
            }
            position.next = new LinkedListNode(val, position.next);
            size++;
        }
    }

    /** Delete the index-th node in the linked list, if the index is valid. */
    public void deleteAtIndex(int index) {
        if (index >= size || index < 0) {
            return;
        }
        if (index == 0) {
            head = head.next;
            size--;
            return;
        }
        LinkedListNode position = head;
        for (int i = 0; i < index - 1; i++) {
            position = position.next;
        }
        position.next = position.next.next;
        size--;
    }

    public static void main(String[] args) {
        E_707_DesignLinkedList obj = new E_707_DesignLinkedList();
        obj.addAtIndex(-1,0);
        obj.get(0);
        obj.deleteAtIndex(-1);
    }
}

答案

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
}

class MyLinkedList {
  int size;
  ListNode head;  // sentinel node as pseudo-head
  public MyLinkedList() {
    size = 0;
    head = new ListNode(0);
  }

  /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
  public int get(int index) {
    // if index is invalid
    if (index < 0 || index >= size) return -1;

    ListNode curr = head;
    // index steps needed
    // to move from sentinel node to wanted index
    for(int i = 0; i < index + 1; ++i) curr = curr.next;
    return curr.val;
  }

  /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
  public void addAtHead(int val) {
    addAtIndex(0, val);
  }

  /** Append a node of value val to the last element of the linked list. */
  public void addAtTail(int val) {
    addAtIndex(size, val);
  }

  /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
  public void addAtIndex(int index, int val) {
    // If index is greater than the length,
    // the node will not be inserted.
    if (index > size) return;

    // [so weird] If index is negative,
    // the node will be inserted at the head of the list.
    if (index < 0) index = 0;

    ++size;
    // find predecessor of the node to be added
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;

    // node to be added
    ListNode toAdd = new ListNode(val);
    // insertion itself
    toAdd.next = pred.next;
    pred.next = toAdd;
  }

  /** Delete the index-th node in the linked list, if the index is valid. */
  public void deleteAtIndex(int index) {
    // if the index is invalid, do nothing
    if (index < 0 || index >= size) return;

    size--;
    // find predecessor of the node to be deleted
    ListNode pred = head;
    for(int i = 0; i < index; ++i) pred = pred.next;

    // delete pred.next
    pred.next = pred.next.next;
  }
}

P717. 1-bit and 2-bit Characters (Easy)

有两个特殊字符，第一个字符可以用0来表示，第二个字符可以用两个bits，10或11来表示。 给一个字符串，判断最后一个字符一定是一个1bit的字符吗。给的字符串一定以0结尾。

我的思路

从倒数第二位开始往前推，只要是0，就能确定了，但true,false 是交替的。

我的代码

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        boolean flag = true;
        for (int i = bits.length - 2; i >= 0; i--) {
            if (bits[i] == 0) {
                return flag;
            }
            flag = !flag;
        }
        return flag;
    }
}

100%

答案

解法1：

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = 0;
        while (i < bits.length - 1) {
            i += bits[i] + 1;
        }
        return i == bits.length - 1;
    }
}

解法2：

class Solution {
    public boolean isOneBitCharacter(int[] bits) {
        int i = bits.length - 2;
        while (i >= 0 && bits[i] > 0) i--;
        return (bits.length - i) % 2 == 0;
    }
}

P720. Longest Word in Dictionary (Easy)

给一个字符串数组， 找到可以一个一个字母拼接起来的最长的词，如果有多于一个答案，则返回字母表排序的第一个

Input:
words = ["w","wo","wor","worl", "world"]
Output: "world"
Explanation:
The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".

我的思路

用HashMap，但实现时有bug，放弃了。

答案

解法一：

class Solution {
    public String longestWord(String[] words) {
        String ans = "";
        Set<String> wordset = new HashSet();
        for (String word: words) wordset.add(word);
        for (String word: words) {
            if (word.length() > ans.length() ||
                    word.length() == ans.length() && word.compareTo(ans) < 0) {
                boolean good = true;
                for (int k = 1; k < word.length(); ++k) {
                    if (!wordset.contains(word.substring(0, k))) {
                        good = false;
                        break;
                    }
                }
                if (good) ans = word;
            }
        }
        return ans;
    }
}

解法二：

public class E_720_LongestWordinDictionary {
    public String longestWord(String[] words) {
        Trie trie = new Trie();
        int index = 0;
        for (String word : words) {
            trie.insert(word, ++index);
        }
        trie.words = words;
        return trie.dfs();
    }
    class Node {
        char c;
        HashMap<Character, Node> children = new HashMap<>();
        int end;
        public Node(char c) {
            this.c = c;
        }
    }

    class Trie {
        Node root;
        String[] words;
        public Trie() {
            root = new Node('0');
        }

        public void insert(String word, int index) {
            Node cur = root;
            for (char c: word.toCharArray()) {
                cur.children.putIfAbsent(c, new Node(c));
                cur = cur.children.get(c);
            }
            cur.end = index;
        }

        public String dfs() {
            String ans = "";
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while (!stack.empty()) {
                Node node = stack.pop();
                if (node.end > 0 || node == root) {
                    if (node != root) {
                        String word = words[node.end - 1];
                        if (word.length() > ans.length() ||
                            word.length() == ans.length() && word.compareTo(ans) < 0) {
                            ans = word;
                        }
                    }
                    for (Node nei : node.children.values()) {
                        stack.push(nei);
                    }
                }
            }
            return ans;
        }

    }
}

最优解

class Solution {
    class Trie {
        Trie[] next;
        String word;

        public Trie() {
            next = new Trie[26];
            word = "";
        }
    }

    private void insert(String s, Trie root) {
        for(char c: s.toCharArray()) {
            if (root.next[c - 'a'] == null) root.next[c - 'a'] = new Trie();
            root = root.next[c - 'a'];
        }
        root.word = s;
    }

    private String res = "";

    private void dfs(Trie root) {
        if (res.length() < root.word.length()) res = root.word;
        for (Trie node : root.next) {
            if (node != null && !node.word.isEmpty()) dfs(node);
        }
    }

    public String longestWord(String[] words) {
        Trie root = new Trie();
        for (String s : words) insert(s, root);
        dfs(root);
        return res;
    }
}

P724. Find Pivot Index (Easy)

找到一个数组的pivot，它左边所有数的和等于右边所有数的和。

我的思路

先跑一趟把所有数的和求出来，然后一个一个地加，直到找到跟右边相等为止。

我的代码

public class E_724_FindPivotIndex {
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }

        int leftSum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum - leftSum - nums[i] == leftSum) {
                return i;
            }
            leftSum += nums[i];
        }
        return -1;
    }
}

100%

最优解

class Solution {
    public int pivotIndex(int[] nums) {
        int left = 0;
        int right = 0;
        for (int i : nums) {
            right += i;
        }
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                right -= nums[i];
                if (right == 0) {
                    return i;
                }
            } else {
                right -= nums[i];
                left += nums[i - 1];
                if (left == right) {
                    return i;
                }
            }
        }
        return -1;
    }
}