leetcode173: 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例： BSTIterator iterator = new BSTIterator(root); iterator.next(); // 返回 3 iterator.next(); // 返回 7 iterator.hasNext(); // 返回 true iterator.next(); // 返回 9 iterator.hasNext(); // 返回 true iterator.next(); // 返回 15 iterator.hasNext(); // 返回 true iterator.next(); // 返回 20 iterator.hasNext(); // 返回 false
class BSTIterator { TreeNode root; Stack<TreeNode> sta=new Stack<>(); public BSTIterator(TreeNode root) { this.root=root; while(root!=null){ sta.push(root); root=root.left; } } public int next() { TreeNode node=sta.pop(); int result=node.val; node=node.right; while(node!=null){ sta.push(node); node=node.left; } return result; } public boolean hasNext() { if(sta.isEmpty())return false; return true; } }leetcode:187 所有 DNA 都由一系列缩写为 A，C，G 和 T 的核苷酸组成，例如：“ACGAATTCCG”。在研究 DNA 时，识别 DNA 中的重复序列有时会对研究非常有帮助。 编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列（子串）。
示例： 输入：s = “AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT” 输出：[“AAAAACCCCC”, “CCCCCAAAAA”]
class Solution { public List<String> findRepeatedDnaSequences(String s) { Map<String,Integer> map=new HashMap<>(); List<String> list=new LinkedList<>(); for(int i=0,j=10;j<=s.length();i++,j++){ String str=s.substring(i,j); if(map.containsKey(str)&&!list.contains(str)){ list.add(str); } map.put(str,1); } return list; } }leetcode199 给定一棵二叉树，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。 示例: 输入: [1,2,3,null,5,null,4] 输出: [1, 3, 4] 解释:
1 <— / 2 3 <— \ 5 4 <—
class Solution { List<List<Integer>> levels = new ArrayList<List<Integer>>(); public void helper(TreeNode node, int level) { // start the current level if (levels.size() == level) levels.add(new ArrayList<Integer>()); // fulfil the current level levels.get(level).add(node.val); // process child nodes for the next level if (node.left != null) helper(node.left, level + 1); if (node.right != null) helper(node.right, level + 1); } public List<List<Integer>> levelOrder(TreeNode root) { if (root == null) return levels; helper(root, 0); return levels; } } class Solution { public List<Integer> rightSideView(TreeNode root) { if (root == null) { return new ArrayList<>(); } List<Integer> result = new ArrayList<>(); assembly(root, result, 1); return result; } private void assembly(TreeNode root, List<Integer> result, int n) { if (result.size() == n - 1) { result.add(root.val); } if (root.right != null) { assembly(root.right, result, n + 1); } if (root.left != null) { assembly(root.left, result, n + 1); } } }leetcode200: 给定一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。 示例 1: 输入: 11110 11010 11000 00000 输出: 1
示例 2: 输入: 11000 11000 00100 00011 输出: 3
public class Solution { private static final int[][] directions = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; private boolean[][] marked; private int rows; private int cols; private char[][] grid; public int numIslands(char[][] grid) { rows = grid.length; if (rows == 0) { return 0; } cols = grid[0].length; this.grid = grid; marked = new boolean[rows][cols]; int count = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (!marked[i][j] && grid[i][j] == '1') { count++; dfs(i, j); } } } return count; } private void dfs(int i, int j) { marked[i][j] = true; for (int k = 0; k < 4; k++) { int newX = i + directions[k][0]; int newY = j + directions[k][1]; if (inArea(newX, newY) && grid[newX][newY] == '1' && !marked[newX][newY]) { dfs(newX, newY); } } } private boolean inArea(int x, int y) { return x >= 0 && x < rows && y >= 0 && y < cols; } }