`

Pocket Gems专题

 
阅读更多

 

// Maximum Product Subarray 
public int maxProduct(int[] nums) {
    int result = nums[0];
    int maxHere = nums[0];
    int minHere = nums[0];
    for(int i=1; i<nums.length; i++) {
        int a = nums[i] * maxHere;
        int b = nums[i] * minHere;
        maxHere = Math.max(nums[i], Math.max(a, b));
        minHere = Math.min(nums[i], Math.min(a, b));
        result = Math.max(result, maxHere);
    }
    return result;
}

// Neighboring classroom, given a map of m * m, and n classrooms, 
//determine if every classroom belongs to one single component; 
//bounds: (1)classroom is at most 3 * 3 in area 
//(2) no overlapping classrooms
// (3) classrooms are at least 5% of m * m in total area 
//(4) isConnected returns true only when two classroom shares a common EDGE.
public static class Room {
	int x, y, h, w;
}
private static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public boolean isConnected(int m, int n, List<Room> rooms) {
	boolean[][] board = new boolean[m][n];
	int area = 0;
	for(Room room : rooms) {
		for(int i=room.y-room.h+1; i<=room.y; i++) {
			for(int j=room.x; j<=room.x+room.w-1; j++) {
				board[i][j] = true;
			}
		}
		area += room.h * room.w;
	}
	
	Queue<Integer> queue = new LinkedList<>();
	int start = rooms.get(0).y * n + rooms.get(0).x;
	queue.offer(start);
	int sum = 0;
	
	while(!queue.isEmpty()) {
		sum++;
		int point = queue.poll();
		int y = point / n;
		int x = point % n;
		board[y][x] = false;
		for(int i=0; i<dir.length; i++) {
			int row = y + dir[i][0];
			int col = x + dir[i][1];
			if(row >= 0 && row < m && col >=0 && col < n && board[row][col]) {
				queue.offer(row*n+col);
			}
		}
	}
	
	return sum == area;
}

// sliding windows max
public static int[] slidingMax(int[] A, int w) {
	int n = A.length;
	w = Math.min(n, w);
	int k = n - w + 1;
	int[] max = new int[k];
	Deque<Integer> deq = new ArrayDeque<>();
	for(int i=0; i<n; i++) {
		while(!deq.isEmpty() && A[deq.getLast()] <= A[i]) { // A[deq.getLast()] >= A[i] for slidingMin
			deq.removeLast();
		}
		deq.addLast(i);
		if(i < w-1) continue;
		while(!deq.isEmpty() && i-w>=deq.getFirst()) {
			deq.removeFirst();
		}
		max[i-w+1] = A[deq.getFirst()];
	}
	return max;
}

// given an array, return the starting and ending index of all subarrays that sums to 0;
public void getZeroSumIndex(int[] A) {
	int n = A.length;
	int[] sum = new int[n+1];
	Map<Integer, List<Integer>> map = new HashMap<>();
	Set<Integer> result = new HashSet<>();
	for(int i=0; i<n; i++) {
		sum[i+1] = A[i] + sum[i];
		if(sum[i+1] == 0) {
			result.add(0*31 +i);
		}
		if(A[i] == 0) {
			result.add(i*31 + i);
		}
		List<Integer> list = map.get(sum[i+1]);
		if(list == null) {
			list = new ArrayList<>();
			map.put(sum[i+1], list);
		} else {
			for(int index : list) {
				result.add((index+1)*31 + i);
			}
		}
		list.add(i);
	}
	
	for(int num: result) {
		System.out.println(num/31 + ", " + num%31);
	}
}

// word break 1
// 重要的是要写出时间复杂度 递归(2^n)? 和worst case(如aaac, 字典是("a", "aa", "aaa"))
// Time: O(n^2)
public boolean wordBreak(String s, Set<String> wordDict) {
    int n = s.length();
    boolean[] f = new boolean[n+1];
    f[0] = true;
    for(int i=1; i<=n; i++) {
        for(int j=0; j<i; j++) {
            String word = s.substring(j, i);
            f[i] = f[j] && wordDict.contains(word);
            if(f[i]) break;
        }
    }
    return f[n];
}

public static boolean wordBreak(String s, Set<String> dict){
	//Base case
	if(dict.contains(s)) return true;
	for(int i = 0; i < s.length(); i++){
		String sstr = s.substring(0, i);
		if(dict.contains(sstr) && wordBreak(s.substring(i), dict))
			return true;
	}
	return false;
}

// word break 1的另外一种写法 O(M*N), 
// Time: O(string length * dict size)
public boolean wordBreak(String s, Set<String> dict) {
        boolean[] t = new boolean[s.length()+1];
        t[0] = true; //set first to be true, why?
        //Because we need initial state
        for(int i=0; i<s.length(); i++){
            //should continue from match position
            if(!t[i]) continue;
            for(String a: dict){
                int len = a.length();
                int end = i + len;
                if(end > s.length()) continue;
                if(t[end]) continue;
                if(s.substring(i, end).equals(a)){
                    t[end] = true;
                }
            }
        }
        return t[s.length()];
    }
}

// word break II recursive method, Time is O(n^2) 
public List<String> wordBreak(String s, Set<String> dict) {
    List<String> list = new ArrayList<>();
    boolean[] f = new boolean[s.length()+1];
    Arrays.fill(f, true);
    breakWord(list, dict, f, s, 0, "");
    return list;
}

public void breakWord(List<String> list, Set<String> dict, boolean[] f, String s, int start, String t) {
    if(start == s.length()) {
        list.add(t.substring(1));
        return;
    }
    for(int i=start+1; i<=s.length(); i++) {
        String word = s.substring(start, i);
        if(dict.contains(word) && f[i]) {
            int size = list.size();
            breakWord(list, dict, f, s, i, t+" "+word);
            if(list.size() == size) f[i] = false;
        }
    }
}

// longest palindrome substring
public String longestPalindrome(String s) {
    String res = "";
    for(int i=0; i<s.length(); i++) {
        String str = palindromeAtCenter(s, i, i);
        if(str.length() > res.length()) {
            res = str;
        }
        
        str = palindromeAtCenter(s, i, i+1);
        if(str.length() > res.length()) {
            res = str;
        }
    }
    return res;
}

private String palindromeAtCenter(String s, int c1, int c2) {
    while(c1>=0 && c2<s.length() && s.charAt(c1) == s.charAt(c2)) {
        c1--;
        c2++;
    }
    return s.substring(c1+1, c2);
}

// reservior sampling
public int[] samplingK(Scanner s, int k) {
	int[] res = new int[k];
	int i = 0;
	while (i < k) {
		res[i++] = s.nextInt();
	}
	Random r = new Random();
	while(s.hasNext()) {
		int num = s.nextInt();
		int rand = r.nextInt(i+1); // important: inclusive range 
		if(rand < k) {
			res[rand] = num;
		}
	}
	return res;
}

// topological sorting
public String getOrderedString(String[] strs, int charSize) {
	DirectedGraph g = new DirectedGraph(charSize);
	boolean[] visited = new boolean[charSize];
	Arrays.fill(visited, true); //~~
	for(String s:strs) {
		if(s.isEmpty()) continue;
		visited[s.charAt(0)-'a'] = false; //~~
		for(int i=1; i<s.length(); i++) {
			visited[s.charAt(i)-'a'] = false; //~~
			g.addEdge(s.charAt(i-1)-'a', s.charAt(i)-'a');
		}
	}
	Stack<Integer> stack = new Stack<>();
	for(int i=0; i<charSize; i++) {
		if(!visited[i])
			toposort(g, i, visited, stack);
	}
	
	StringBuilder sb = new StringBuilder();
	while(!stack.isEmpty()) {
		sb.append((char)(stack.pop()+ 'a'));
	}
	System.out.println(sb.toString());
	return sb.toString();
}

public void toposort(DirectedGraph g, int v, boolean[] visited, Stack<Integer> stack) {
	visited[v] = true;
	for(int u : g.adj[v]) {
		if(!visited[u]) {
			toposort(g, u, visited, stack);
		}
	}
	stack.push(v);
}

// room isConnected
// 第四轮的题还问到了时间复杂度
// 对于访问到的每个点判断是否满足小于k需要O(k),
// 所有访问到的点形成的图形最长半径为n的话则有O(n2)个点,所以总共是O(n2*k)。
public class MonkeyProblem {
	static class Point {
		int x, y;
		Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
		@Override
		public boolean equals(Object o) {
			if (this == o) return true;
			if (!(o instanceof Point)) return false;
			Point pair = (Point) o;
			return x == pair.x && y == pair.y;
		}
		@Override
		public int hashCode() {
			return 31 * x + y;
		}
	}
	
	public static int digitSum(int n) {
		if(n < 0) n = -n;
		int sum = 0;
		while(n != 0) {
			sum += n % 10;
			n /= 10;
		}
		return sum;
	}

	private static int[][] dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
	public static int countSteps(int k) {
		Set<Point> set = new HashSet<>();
		Queue<Point> queue = new LinkedList<>();
		queue.offer(new Point(0, 0));
		while(!queue.isEmpty()) {
			Point p = queue.poll();
			if(set.contains(p) || (digitSum(p.x) + digitSum(p.y)) > k) continue;
			set.add(p);
			for(int i=0; i<4; i++) {
				queue.offer(new Point(p.x+dir[i][0], p.y+dir[i][1]));
			}
		}
		return set.size();
	}

	public static void main(String[] args) {
		System.out.println(countSteps(19));
	}
}

// serialize binary tree
public String serialize(TreeNode root){  
    StringBuilder sb = new StringBuilder();  
    serialize(root, sb);  
    return sb.toString();  
}  
   
private void serialize(TreeNode x, StringBuilder sb){  
    if (x == null) {  
        sb.append("# ");  
    } else {  
        sb.append(x.val + " ");  
        serialzie(x.left, sb);  
        serialzie(x.right, sb);  
    }  
}  
   
public TreeNode deserialize(String s){  
    if (s == null || s.length() == 0) return null;  
    StringTokenizer st = new StringTokenizer(s, " ");  
    return deserialize(st);  
}  
   
private TreeNode deserialize(StringTokenizer st){  
    if (!st.hasMoreTokens())  
        return null;  
    String val = st.nextToken();  
    if (val.equals("#"))  
        return null;  
    TreeNode root = new TreeNode(Integer.parseInt(val));  
    root.left = deserialize(st);  
    root.right = deserialize(st);  
    return root;  
}  

// a?b:c  tenary tree
public TreeNode convertToTree (char[] values) {
    TreeNode root = new TreeNode(values[0]);
    TreeNode n = root;
    Stack<TreeNode> stack =  new Stack<TreeNode>();
    for (int i = 1; i < values.length; i += 2) {
        if (values[i] == '?') {
            n.left = new TreeNode (values[i + 1]);
            stack.push(n);
            n = n.left;

        }
        else if (values[i] == ':') {
            n = stack.pop();
            while (n.right != null) {
                n = stack.pop();
            }             
            n.right = new TreeNode (values[i + 1]);
            stack.push(n);
            n = n.right;
        }
    }
    return root;
}	

// mutable string
public char charAt(int index) {
    if ((index < 0) || (index >= count)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index + offset];
}

public String substring(int beginIndex, int endIndex) {
	if (beginIndex < 0) {
	    throw new StringIndexOutOfBoundsException(beginIndex);
	}
	if (endIndex > count) {
	    throw new StringIndexOutOfBoundsException(endIndex);
	}
	if (beginIndex > endIndex) {
	    throw new StringIndexOutOfBoundsException(endIndex - beginIndex);
	}
	return ((beginIndex == 0) && (endIndex == count)) ? this :
	    new String(offset + beginIndex, endIndex - beginIndex, value);
}

 

 

分享到:
评论
2 楼 yuanhsh 2015-06-02  
popu_12 写道
Can you please explain neighboring classroom question with example I cannot understand solution because the question is not understood? An example will help

就是房子连通问题,看所有房子能否连接成一个连通区域。
假设1代表房子所占用的区域,0代表没被房子占用的区域,那么下图的两个房子不是连通的。
00110
00110
11000
11000
但是如果下图的两个房子是连通的(每个房子都是正规的矩形)。
00110
00110
11110
11000
1 楼 popu_12 2015-06-01  
Can you please explain neighboring classroom question with example I cannot understand solution because the question is not understood? An example will help

相关推荐

    Graphics Gems 4 part2

    Graphics Gems IV is the newest volume in the Graphics Gems series. All of the books in the series contain practical solutions for graphics problems using the latest techniques in the field. The books ...

    Game Programming Gems 5 中文 part1

    With the wisdom of many industry experts, Gems 5 includes 62 newly unearthed gems that were polished up for your reading pleasure. These gems are filled with practical insights and techniques that ...

    Lua Programming Gems 高清书签

    Lua Programming Gems 英文高清书签 Lua Programming Gems 英文高清书签

    Game Programming Gems 5 中文 part2

    With the wisdom of many industry experts, Gems 5 includes 62 newly unearthed gems that were polished up for your reading pleasure. These gems are filled with practical insights and techniques that ...

    Graphics Gems 1.pdf

    Graphics Gems 1 as his name

    GPU Gems3 part3

    图形编程人员手头必备的书,是Nvidia公司编著的GPU Gems系列的第三版,官方的介绍为: GPU Gems 3 is a collection of state-of-the-art GPU programming examples. It is about putting data-parallel ...

    丹纳赫Gems流量产品.zip

    丹纳赫Gems流量产品zip,Gems公司设计和生产规格齐全的流量传感器和开关,用于导电流体、非导电流体以及气体的可靠和高效测量。它们非常稳固,可预设为从cc/min到100 GPM的流量范围,能够激活报警或系统自动关机,是...

    Gems 压力传感器样本.pdf

    Gems 压力传感器样本pdf,Gems 压力传感器样本

    gems使用手册ruby on rails

    gems使用手册ruby on rails,真的很好很好很好用啊

    Game Programming Gems 7 中文 part1

    accurate, and useful.There are gems that contribute directly to a player's experience of the game, including audio production gems and human-game interactions. Does your development team include a ...

    GPU Gems3 part1

    图形编程人员手头必备的书,是Nvidia公司编著的GPU Gems系列的第三版,官方的介绍为: GPU Gems 3 is a collection of state-of-the-art GPU programming examples. It is about putting data-parallel ...

    Game Programming Gems 2

    Game Programming Gems 2 by Mark DeLoura (Editor) 游戏编程精粹2英文版

    gems tutorial

    introduction to gems simulator.

    Game.Programming.Gems.2

    Game.Programming.Gems.2 英文版 Game.Programming.Gems.2 英文版

    GPU Gems 1-3

    GPU Gems 1-3 htm格式 高清 文字版

    Gems行业应用白皮书 船舶应用 – Gems传感器如何为造船业提供解决方案.zip

    Gems行业应用白皮书 船舶应用 – Gems传感器如何为造船业提供解决方案zip,在船舶运营中效率越高,维护成本就越低,机器寿命越长,这需要应用当今某些超凡的创新压力、液位和流量传感装置来实现。

    GPU Gems 1 pdf 电子书

    GPU Gems 1.pdf 电子书, 英文原版,GPU开发必备书籍。 包含:英文CHM版、中文pdf版、英文扫描版

    Gems 流量仪表样本.pdf

    Gems 流量仪表样本pdf,Gems 流量仪表样本

    GPU Gems 2 pdf 清晰版本

    GPU Gems2 pdf 清晰版本 英文版本

    Simics with Gems 安装笔记

    Simics with Gems 安装笔记

Global site tag (gtag.js) - Google Analytics