Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

public class Solution {
    public void moveZeroes(int[] nums) {
        int valid = -1;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0 && i != valid + 1) {
                nums[++valid] = nums[i];
            } else if (nums[i] != 0) {
                valid++;
            }
        }
        for (int i = valid + 1; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

Leetcode: Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return [“0->2″,”4->5″,”7”].

---

public class Solution {
    public List<String> summaryRanges(int[] nums) {
    	List<String> res = new ArrayList<String>();
    	if (nums.length == 0) {
    		return res;
    	}
        int start = 0;
        for (int i = 1; i < nums.length; i++) {
        	if (nums[i] == nums[i-1] + 1) {
        		continue;
        	}
        	if (i - 1 == start) {
        		res.add(String.valueOf(nums[start]));
        	} else {
        		res.add(nums[start] + "->" + nums[i-1]);
        	}
        	start = i;
        }
        if (nums.length - 1 == start) {
    		res.add(String.valueOf(nums[start]));
    	} else {
    		res.add(nums[start] + "->" + nums[nums.length - 1]);
    	}
        return res;
    }
}

HackerRank: Snakes and Ladders

public class Solution {
    private static final int N = 100;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int total = sc.nextInt();
        while (total > 0) {
            total--;
            int[] store = new int[N + 1];
            int ladders = sc.nextInt();
            for (int i = 0; i < ladders; i++) {
                int from = sc.nextInt();
                store[from] = sc.nextInt() - from;
            }
            int snakes = sc.nextInt();
            for (int i = 0; i < snakes; i++) {
                int from = sc.nextInt();
                store[from] = sc.nextInt() - from;
            }
            QueueEntry entry = new QueueEntry(1, 0);
            Queue<QueueEntry> queue = new LinkedList<QueueEntry>();
            queue.add(entry);
            boolean[] visited = new boolean[N + 1];
            boolean hasRes = false;
            while (!queue.isEmpty()) {
                entry = queue.poll();
                if (entry.pos == N) {
                    System.out.println(entry.step);
                    hasRes = true;
                    break;
                }
                if (visited[entry.pos] == true) {
                    continue;
                }
                visited[entry.pos] = true;
                for (int i = 1; i <= 6 && entry.pos + i <= N; i++) {
                    int nextPos = entry.pos + i;
                    if (store[nextPos] != 0) {
                        QueueEntry nextEntry = new QueueEntry(nextPos + store[nextPos], entry.step + 1);
                        queue.offer(nextEntry);
                    } else {
                        QueueEntry nextEntry = new QueueEntry(nextPos, entry.step + 1);
                        queue.offer(nextEntry);
                    }
                }
            }
            if (hasRes == false) {
                System.out.println(-1);
            }
        }
    }
    static class QueueEntry {
        int pos;
        int step;
        public QueueEntry (int pos, int step) {
            this.pos = pos;
            this.step = step;
        }
    }
}

Lintcode：Subarray Sum Closest/ subarray sum closest to k

这个解法比较复杂，用到了treemap。
是通用与找closest to target k 的解法。简单解法参考subarray sum。排序即可。

import java.util.Map.Entry;
public class Solution {
    public ArrayList<Integer> subarraySumClosest(int[] nums) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
    	if (nums == null || nums.length == 0) {
    		return res;
    	}
    	TreeMap<Long, Integer> map = new TreeMap<Long, Integer>();
    	long sum = 0;
    	long minDiff = (long)Integer.MAX_VALUE + 1;
    	res.add(0);
    	res.add(0);
    	for (int i = 0; i < nums.length; i++) {
    		sum += nums[i];
    		Entry floorEntry = map.floorEntry(sum);
    		Entry ceilingEntry = map.ceilingEntry(sum);
    		int curDiff = 0;
    		if (floorEntry != null || ceilingEntry != null) {
	    		if (floorEntry == null || (ceilingEntry != null && Math.abs((long)floorEntry.getKey() - sum) > Math.abs((long)ceilingEntry.getKey() - sum))) {
	    			if (Math.abs((long)ceilingEntry.getKey() - sum) < minDiff) {
	    				res.set(0, (int)ceilingEntry.getValue() + 1);
	    				res.set(1, i);
	    			}
	    		} else {
	    			if (Math.abs((long)floorEntry.getKey() - sum) < minDiff) {
	    				res.set(0, (int)floorEntry.getValue() + 1);
	    				res.set(1, i);
	    				minDiff = Math.abs((long)floorEntry.getKey() - sum);
	    			}
	    		}
    		}
    		map.put(sum, i);
    	}	    	
    	return res;
    }
}

Lintcode: product of subarray exclude itself

左右分别scan法。

public class Solution {
    public ArrayList<Long> productExcludeItself(ArrayList<Integer> A) {
        ArrayList<Long> res = new ArrayList<Long>();
        if (A == null || A.size() == 0) {
          return res;
        }
        if (A.size() == 1) {
            res.add(1L);
            return res;
        }
        Long[] left = new Long[A.size()];
        Long[] right = new Long[A.size()];
        long product = 1;
        for (int i = 0; i < A.size(); i++) {
          product*= A.get(i);
          left[i] = product;
        }
        product = 1;
        for (int i = A.size()-1; i >= 0; i--) {
          product *= A.get(i);
          right[i] = product;
        }
        for (int i = 0; i < A.size(); i++) {
          if (i == 0) {
            res.add(right[i+1]);
          } else if (i == A.size() - 1) {
            res.add(left[i-1]);
          } else {
            res.add(left[i-1] * right[i+1]);
          }
        }
        return res;
    }
}

Lintcode: subarray sum

Given an integer array, find a subarray where the sum of numbers is zero. Your code should return the index of the first number and the index of the last number.
考点是前缀和。
Solution 1: faster, uses more space.

public class Solution {
    public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
            return res;
        }
        Map<Long, Integer> prefixSumMap = new HashMap<Long, Integer>();
        long sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (sum == 0) {
                res.add(0);
                res.add(i);
                break;
            }
            if (prefixSumMap.containsKey(sum)) {
                res.add(prefixSumMap.get(sum)+1);
                res.add(i);
                break;
            } else {
                prefixSumMap.put(sum, i);
            }
        }
        return res;
    }
}

Solution 2: slower, uses less space

public class Solution {
    class Element implements Comparable<Element>{
      private int index;
      private int val;

      Element (int index, int val) {
        this.index = index;
        this.val = val;
      }

      public int getVal() {
        return val;
      }

      public int getIndex() {
        return index;
      }

      public int compareTo(Element e) {
        return val - e.getVal();
      }
    }

    public ArrayList<Integer> subarraySum(int[] nums) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (nums == null || nums.length == 0) {
          return res;
        }
        int sum = 0;
        Element[] eles = new Element[nums.length];
        for (int i = 0; i < nums.length; i++) {
          sum += nums[i];
          eles[i] = new Element(i, sum);
        }
        Arrays.sort(eles);
        for (int i = 0; i < eles.length; i++) {
          if (eles[i].getVal() == 0) {
            res.add(0);
            res.add(eles[i].getIndex());
            break;
          }
          if (i > 0 && eles[i].getVal() == eles[i-1].getVal()) {
            res.add(eles[i].getIndex());
            res.add(eles[i-1].getIndex());
            break;
          }
        }
        return res;
    }
}

Codility 2.4：MaxCounters

Some content on this page was disabled on November 21, 2022 as a result of a DMCA takedown notice from Alicja Zielińska. You can learn more about the DMCA here:

https://wordpress.com/support/copyright-and-the-dmca/

Codility 13.4 : Triangles

Some content on this page was disabled on November 21, 2022 as a result of a DMCA takedown notice from Alicja Zielińska. You can learn more about the DMCA here:

https://wordpress.com/support/copyright-and-the-dmca/

Codility 13.2: CountDistinctSlices

Some content on this page was disabled on November 21, 2022 as a result of a DMCA takedown notice from Alicja Zielińska. You can learn more about the DMCA here:

https://wordpress.com/support/copyright-and-the-dmca/

Longest Increasing Subsequence

Given a sequence of integers, find the longest increasing subsequence (LIS).
You code should return the length of the LIS.

Example
For [5, 4, 1, 2, 3], the LIS is [1, 2, 3], return 3
For [4, 2, 4, 5, 3, 7], the LIS is [4, 4, 5, 7], return 4

---

虽然思路不难，但是store[i]的更新很容易写错

public class Solution {
    public int longestIncreasingSubsequence(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int[] store = new int[nums.length];
        store[0] = 1;
        int res = 1;
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i]){
                    store[i] = Math.max(store[j], store[i]);
                }
            }
            store[i]++;
            res = Math.max(res, store[i]);
        }
        return res;
    }
}