// 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); }
相关推荐
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 ...
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 英文高清书签
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 as his name
图形编程人员手头必备的书,是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公司设计和生产规格齐全的流量传感器和开关,用于导电流体、非导电流体以及气体的可靠和高效测量。它们非常稳固,可预设为从cc/min到100 GPM的流量范围,能够激活报警或系统自动关机,是...
Gems 压力传感器样本pdf,Gems 压力传感器样本
gems使用手册ruby on rails,真的很好很好很好用啊
Fast Line–Edge Intersections on a Uniform Grid (651) 29GRAPHICS GEMS I Edited by ANDREW S. GLASSNER viii CONTENTS Anti-Aliasing Summary 37 Area of Intersection: Circle and a Half-Plane 38 Area of ...
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 ...
图形编程人员手头必备的书,是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 by Mark DeLoura (Editor) 游戏编程精粹2英文版
introduction to gems simulator.
Game.Programming.Gems.2 英文版 Game.Programming.Gems.2 英文版
GPU Gems 1-3 htm格式 高清 文字版
Gems行业应用白皮书 船舶应用 – Gems传感器如何为造船业提供解决方案zip,在船舶运营中效率越高,维护成本就越低,机器寿命越长,这需要应用当今某些超凡的创新压力、液位和流量传感装置来实现。
GPU Gems 1.pdf 电子书, 英文原版,GPU开发必备书籍。 包含:英文CHM版、中文pdf版、英文扫描版
Gems 流量仪表样本pdf,Gems 流量仪表样本
GPU Gems2 pdf 清晰版本 英文版本