Rotate Function

Given an array of integers A and let n to be its length.

Assume Bk to be an array obtained by rotating the array A k positions clock-wise, we define a “rotation function” F on A as follow:

F(k) = 0 * Bk[0] + 1 * Bk[1] + ... + (n-1) * Bk[n-1].

Calculate the maximum value of F(0), F(1), ..., F(n-1).
观察一下规律不难发现f(n) = f(n-1) + arraySum – arrayLength*A[i-1]

public class Solution {
    public int maxRotateFunction(int[] A) {
        int oneRoundSum = 0;
        int max = 0;
        for (int i = 0; i <A> 0; i--) {
            int cur = prev + oneRoundSum - A.length * A[i];
            max = Math.max(max, cur);
            prev = cur;
        }
        return max;
    }
}

Coin Change

    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        if amount == 0: return 0
        if not coins: return -1
        dp = [0] + [-1] * amount
        for x in coins:
            for v in range(x, amount+1):
                if dp[v-x] >= 0:
                    dp[v] = min(dp[v], dp[v-x] + 1) if dp[v] > 0 else dp[v-x] + 1
        return dp[amount]

Odd Even Linked List

class Solution(object):
    def oddEvenList(self, head):
        dummy = ListNode(0)
        dummy.next = head
        odd = dummy.next
        if not odd or not odd.next:
            return head
        even = odd.next
        dummy_even = ListNode(0)
        dummy_even.next = even
        while even and odd:
            odd.next = even.next
            odd = odd.next
            if odd:
                even.next = odd.next
                even = even.next
        cur = head
        while cur.next:
            cur = cur.next
        cur.next = dummy_even.next
        return dummy.next

Longest Increasing Path in a Matrix

class Solution(object):
    def longestIncreasingPath(self, M):
        R = len(M)
        if not R: return 0
        C = len(M[0])
        if not C: return 0
        mem = [[0 for _ in range(C)] for _ in range(R)]
        def dfs(i, j):
            tmp = 0
            for (x, y) in [(i, j+1), (i+1, j), (i, j-1), (i-1, j)]:
                if 0 <= x < R and 0 <= y < C:
                    if mem[x][y] == 0 and M[x][y] > M[i][j]:
                        dfs(x, y)
                    if M[x][y] > M[i][j]:
                        tmp = max(tmp, mem[x][y])
            mem[i][j] = tmp + 1
        for i in range(R):
            for j in range(C):
                if mem[i][j] == 0:
                    dfs(i, j)
        result = max([max(row) for row in mem])
        return result

Effective Java 学习笔记 — Chapter 3. Methods common to all objects

Item 8. Obey the general contract when overriding equals
高质量的equals函数应该包括以下几步:
a. check if they are the same object using: this == obj
b. check if obj is an instance of the correct class using: obj.instanceof(TheClass)
大多数情况下这个TheClass是当前类,但是有时候也可能是某个接口
c. cast obj to correct class using: TheClass cc = (TheClass)obj;
d. For each “significant” field in the class, check if that field of the argument matches the corresponding field of this object
需要注意的点有:
(1)一定要重写hashCode
(2)参数的类型是Object,而不是任何其他类型,这样才会override,否则会overload,成为另一个函数, 用@override是一个非常好的习惯。

Item 9. Always override hashCode when you override equals
如果一个类是immutable,并且产生hashcode的函数过于复杂或者影响性能,可以考虑cache这个值,并且lazy initialization

Item 10. Always override toString
When practical, the toString method should return all of the interesting information contained in the object。

Item 11. Override clone judiciously
Cloneable 接口存在flaw,因为它并没有一个clone()函数,(实际上这个接口没有任何函数).Clone() 是Object类的 native protected函数。
“all classes that implement Cloneable should override clone with a public method whose return type is the class itself. This method should first call super.clone and then fix any fields that need to be fixed. ”
具体override clone函数的步骤是
(1) implements Cloneable
(2) public Object clone() throws CloneNotSupportedException
(3) 调用super.clone(), 接下来调用持有对象的clone()方法, i.e. deep copy
为什么要实现Cloneable 接口呢,第一,作为一个标示,第二,如果一个类没有implement Cloneable接口并且调用了super.clone(), Object的clone()方法就会抛出 CloneNotSupportedException异常。

Item 12. Consider implementing Comparable
compareTo函数是Comparable 接口提供的唯一函数签名。

public final class CaseInsensitiveString implements Comparable<CaseInsensitiveString> {
   public int compareTo(CaseInsensitiveString cis) {
       return String.CASE_INSENSITIVE_ORDER.compare(s, cis.s);
   }
}

Effective Java 学习笔记 — Chapter 7. Methods

Item 38. check parameters for validity

Item 39. make defensive copy of parameters
(1)因为java多数是传引用,如果不对参数进行deep copy,会出问题。例如:

public Period(Date start, Date end) {
    if (start.compareTo(end) > 0)
       throw new IllegalArgumentException(
             start + " after " + end); // 应该在defensive copy之后进行!!!
       this.start = start;
       this.end   = end;
    }
}
Date start = new Date();
Date end = new Date();
Period p = new Period(start, end); 
end.setYear(78);    //会修改p.end!!!

(2) check parameters for validity 应该在defensive copy之后进行。上例中是错误示范。

(3) 另外,不要使用Date的clone函数来make copy。
“Because Date is nonfinal, the clone method is not guaranteed to return an object whose class is java.util.Date: it could return an instance of an untrusted subclass”。
do not use the clone method to make a defensive copy of a parameter whose type is subclassable by untrusted parties.

(4) 返回一个defensive copies of mutable internal fields,而不是直接返回这个对象:

public Date getEnd() {
  return new Date(end.getTime());
}

(5) 资深程序员会尽量保存immutable object,例如上面的例子中,会用long 保存date.getTime()而不是保存mutable的Date

Item 40: Design method signatures carefully
(1)参数不要过多,
(2)函数不要过多(只提供有意义的函数作为接口)
(3)For parameter types, 尽量用 interfaces over classes(例如用map而不用hash map,这样可以take不同的实现作为parameter)
(4)Prefer two-element enum types to boolean parameters

Item 41: Use overloading judiciously
(1)很重要的一点,overloaded函数是在compile时决定的,overridden函数是在runtime决定的
A safe, conservative policy is never to export two overloadings with the same number of parameters
(2)autoboxing 也会出现一些问题,例如

Set<Integer> set = new HashSet<Integer>();
set.add(1);
set.add(2);
set.remove(1);//set只有一个参数为Object的remove函数,因此remove之后为[2]
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.remove(1);//list overload了remove,一个take int, 一个take Integer,因此会remove index为1的值,成为[1]

Item 42:Use varargs judiciously
因为varargs可以是0个参数,因此如果需要这个参数至少有一个的时候,应该强制pass 两个参数, e.g. int min(int firstArg, int… remainingArgs) 以防需要在函数内进行参数个数判断甚至抛出异常

Item 43:Return empty arrays or collections, not nulls
“there is no reason ever to return null from an array- or collection-valued method instead of returning an empty array or collection.”
一个很实用的tip,当array为空时,不要返回一个新建的array,这样太浪费空间,用

private static final Cheese[] EMPTY_CHEESE_ARRAY = new Cheese[0];
   /**
    * @return an array containing all of the cheeses in the shop.
    */
   public Cheese[] getCheeses() {
       return cheesesInStock.toArray(EMPTY_CHEESE_ARRAY);
}

如果参数为空array,toArray函数会返回一个immutable的object,which may be shared freely[item 15]
当collection为空时,也不要新建一个对象,用Collections.emptyList()也会返回immutable object

Item 44: Write doc comments for all exposed API elements
tip: the Javadoc {@code} tag is preferable because it eliminates the need to escape HTML metacharacters

Word Break II

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences.

For example, given
s = “catsanddog”,
dict = [“cat”, “cats”, “and”, “sand”, “dog”].

A solution is [“cats and dog”, “cat sand dog”]


word break I 差不多的思路,第一遍TLE, 原因是对于任何一个i,如果i+1到s.length()这一段是not solvable,那么0-i这一段不需要进行。因此在解决问题之前,做一遍word break I, 用于判断有没有必要对当前i找出list of strings.

public class Solution {
    public List<String> wordBreak(String s, Set<String> dict) {
        List<String> result = new ArrayList<String>();
        if (s == null || dict == null || s.length() == 0 || dict.size() == 0) {
            return result;
        }
        boolean[] solvable = new boolean[s.length() + 1];
        solvable[s.length()] = true;
        for (int i = s.length()-1; i >= 0; i--) {//
            for (int j = s.length() - 1; j >= i; j--) {
                if (solvable[j+1] == true && dict.contains(s.substring(i, j+1))) {
                    solvable[i] = true;
                    break;
                }
            }
        }
        
        Map<Integer, List<String>> map = new HashMap<Integer, List<String>>();
        for (int i = 0; i < s.length(); i++) {
            if(i == s.length()-1 || solvable[i+1]) {
                for (int j = 0; j <= i; j++) {
                    if ((j == 0 || map.containsKey(j-1)) && dict.contains(s.substring(j, i+1))) {
                        if (j == 0) {
                            List<String> newList = new ArrayList<String>();
                            newList.add(s.substring(0, i+1));
                            map.put(i, newList);
                        } else {
                            List<String> curList = map.containsKey(i) ? map.get(i) : new ArrayList<String>();
                            List<String> jList = map.get(j-1);
                            for (String str : jList) {
                                curList.add(str + " " + s.substring(j, i+1));
                            }
                            map.put(i, curList);
                        }
                    }
                }
            }
        }
        return map.get(s.length()-1) == null ? result : map.get(s.length()-1);
    }
}

Evaluate Reverse Polish Notationpo

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Easy one

public class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        int result = 0;
        for (String s : tokens) {
            if (s.equals("+")) {
            	result = stack.pop() + stack.pop();
            	stack.push(result);
            } else if (s.equals("-")) {
            	result = -stack.pop() + stack.pop();
            	stack.push(result);
            } else if (s.equals("*")) {
            	result = stack.pop() * stack.pop();
            	stack.push(result);
            } else if (s.equals("/")) {
            	int a = stack.pop(); result = stack.pop()/a;
            	stack.push(result);
            } else {
                stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }
}

Min Stack

第一遍:

Memory limit exceeded. 因为如果当前元素大于当前最小值,不需要更新mins。因此pop的时候如果当前元素等于mins顶元素, mins才需要pop

Try 1:

class MinStack {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> mins = new Stack<Integer>();

    public void push(int x) {
        stack.push(x);
        mins.push((mins.isEmpty() || mins.peek() > x) ? x : mins.peek());
    }

    public void pop() {
        if (!stack.isEmpty()) {
            stack.pop();
            mins.pop();
        }
    }

    public int top() {
        return stack.isEmpty() ? -1 : stack.peek();
    }

    public int getMin() {
        return mins.isEmpty()? -1 : mins.peek();
    }
}

第二遍:

class MinStack {
    Stack<Integer> stack = new Stack<Integer>();
    Stack<Integer> mins = new Stack<Integer>();

    public void push(int x) {
        stack.push(x);
        if(mins.isEmpty() || mins.peek() >= x) {
            mins.push(x);
        }
    }

    public void pop() {
        if (!stack.isEmpty()) {
            int curVal = stack.pop();
            if (curVal == mins.peek()) {
                mins.pop();
            }
        }
    }

    public int top() {
        return stack.isEmpty() ? -1 : stack.peek();
    }

    public int getMin() {
        return mins.isEmpty()? -1 : mins.peek();
    }
}

Find Minimum in Rotated Sorted Array

比较简单。

一个序列被rotate后只有两种可能:递增序列,或左大右小序列。

对一个rotated后的数组取mid 有三种情况:

1)左小右大,说明是递增序列,取左边, mid-1

2)左大右大, 说明是左大右小序列的右边,取左边,mid不减,因为mid有可能是最小

3)左小右小, 说明是左大右小序列的左边, 取右边, mid+1

注:只剩两个数的时候单独判断,因为mid==left

public class Solution {
    public int findMin(int[] num) {
        int start = 0, end = num.length - 1;
		while (start + 1 < end) {
			int mid = (start + end)/2;
			if (num[start] > num[mid] && num[end] > num[mid]) {
				end = mid;
			} else if (num[start] < num[mid] && num[end] < num[mid]) {
				start = mid + 1;
			} else {//case of left < mid && mid < end
				end = mid  -1;
			}
		}
		return start < end ? Math.min(num[start], num[end]) : num[start];
    }
}