Leetcode: Ransom Note

Given
 an 
arbitrary
 ransom
 note
 string 
and 
another 
string 
containing 
letters from
 all 
the 
magazines,
 write 
a 
function 
that 
will 
return 
true 
if 
the 
ransom 
 note 
can 
be 
constructed 
from 
the 
magazines ; 
otherwise, 
it 
will 
return 
false. 



Each 
letter
 in
 the
 magazine 
string 
can
 only 
be
 used 
once
 in
 your 
ransom
 note.

简单题，只需判断magazine里是否包含ransom note。对于26个字母不需要使用hash map，直接用一个数组即可。

public class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] magazineCount = new int[26];
        for (int i = 0; i < magazine.length(); i++) {
            magazineCount[magazine.charAt(i) - 'a']++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            if (--magazineCount[ransomNote.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }
}

Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

简单题

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> numToCount1 = new HashMap<Integer, Integer>();
        for (int num : nums1) {
            numToCount1.put(num, numToCount1.getOrDefault(num, 0) + 1);
        }
        Map<Integer, Integer> resultMap = new HashMap<Integer, Integer>();
        List<Integer> resultList = new ArrayList<Integer>();
        for (int num : nums2) {
            if (resultMap.getOrDefault(num, 0) < numToCount1.getOrDefault(num, 0)) {
                resultMap.put(num, resultMap.getOrDefault(num, 0) + 1);
                resultList.add(num);
            }
        }
        int[] result = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            result[i] = resultList.get(i);
        }
        return result;
    }
}

Palindrome Pairs

Given a list of unique words. Find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
解法：
对于每一个word， 拆分成前后两部分， 如果其中任意一部分本身是palindrome， 查看另一部分的reverse是否存在。 存在即可连接成为palindrome。
需要注意的是如果有word为空，因为会跳过最内层for循环，因此要单独处理。

public class Solution {
  public List<List<Integer>> palindromePairs(String[] words) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    Map<String, Integer> wordToIndex = new HashMap<String, Integer>();;
    for (int i = 0; i < words.length; i++) {
      wordToIndex.put(words[i], i);
    }
    for (int i = 0; i < words.length; i++) {
      String word = words[i];
      if (word.length() == 0) {
        for (int j = 0; j < words.length; j++) {
          if (isPalindrome(words[j]) && j != i) {
            List<Integer> pair = new ArrayList<Integer>();
            pair.add(i);
            pair.add(j);
            result.add(pair);      
          }
        }
      }
      for (int index = 0; index < word.length(); index++) {
        String firstHalf = word.substring(0, index);
        String secondHalf = word.substring(index, word.length());
        String reversedSecond = new StringBuilder(secondHalf).reverse().toString();
        String reversedFirst = new StringBuilder(firstHalf).reverse().toString();
        if (isPalindrome(firstHalf) && wordToIndex.containsKey(reversedSecond) && wordToIndex.get(reversedSecond) != i) {
          List<Integer> pair = new ArrayList<Integer>();
          pair.add(wordToIndex.get(reversedSecond));
          pair.add(i);
          result.add(pair);
        }
        if (isPalindrome(secondHalf) && wordToIndex.containsKey(reversedFirst) && wordToIndex.get(reversedFirst) != i) {
          List<Integer> pair = new ArrayList<Integer>();
          pair.add(i);
          pair.add(wordToIndex.get(reversedFirst));
          result.add(pair);
        }
      }
    }
    return result;
  }
    
  private boolean isPalindrome(String a) {
    for (int i = 0, j = a.length() - 1; i <= j; i++, j--) {
      if (a.charAt(i) != a.charAt(j)) {
        return false;
      }
    }
    return true;
  }
}

Leetcode: Contains Duplicate II

public class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums == null || nums.length <= 1) {
            return false;
        }
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && i - map.get(nums[i]) <= k) {
                return true;
            }
            map.put(nums[i], i);
        }
        return false;
    }
}

Leetcode: LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

---

public class LRUCache {
    Map<Integer, Node> map = new HashMap<Integer, Node>();
    int capacity;
    int size;
    Node head;
    Node tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        populateNode(node);
        return node.val;
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            populateNode(node);
            node.val = value;
        } else {
            Node newNode = new Node(key, value);
            newNode.next = head;
            if (head != null)
            	head.pre = newNode;
            head = newNode;
            if (tail == null) {
            	tail = newNode;
            }
            map.put(key, newNode);
            if (size == capacity) {
            	map.remove(tail.key);
            	tail = tail.pre;
            	tail.next = null;
            } else {
                size++;
            }
        }
    }
    
    private void populateNode(Node node) {
    	if (node != head) {
        	if (node == tail) { //update tail
            	tail = node.pre;
            	tail.next = null;
            } else {
            	node.next.pre = node.pre;
            }
        	//populate node
        	node.pre.next = node.next;
        	node.next = head;
        	head.pre = node;
        	head = node;
        }
	}

	class Node {
        int val;
        int key;
        Node next;
        Node pre;
        public Node (int key, int val) {
        	this.key = key;
            this.val = val;
        }
    }
}

Leetcode: Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given “egg”, “add”, return true.
Given “foo”, “bar”, return false.
Given “paper”, “title”, return true.

---

很容易写错的一道题。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }
        Map<Character, Character> map = new HashMap<Character, Character>();
        Set<Character> used = new HashSet<Character>();
        for (int i = 0; i < s.length(); i++) {
            if (!map.containsKey(s.charAt(i)) && !used.contains(t.charAt(i))) {
                map.put(s.charAt(i), t.charAt(i));
                used.add(t.charAt(i));
            } else if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i)).equals(t.charAt(i))) {
                continue;
            } else {
                return false;
            }
        }
        return true;
    }
}

HackerRank: Missing Number

简单题

public static void main(String[] args) {
        Map<Integer, Integer> map = new TreeMap<Integer, Integer>();
        Scanner sc = new Scanner(System.in);
        int size1 = sc.nextInt();
        for (int i = 0; i < size1; i++) {
            int cur = sc.nextInt();
            map.put(cur, map.containsKey(cur) ? map.get(cur) + 1 : 1);
        }
        int size2 = sc.nextInt();
        for (int i = 0;i < size2; i++) {
            int cur = sc.nextInt();
            map.put(cur, map.containsKey(cur) ? map.get(cur) - 1 : -1);
        }
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() != 0) {
                System.out.print(entry.getKey() + " ");
            }
        }
}