3.栈与队列
3.4 经典汉诺塔问题，递归实现
public class Num3_4 { public static void main(String[] args) { } /* * 汉诺塔问题 * 当盘子只有一个时，则直接从柱子A移动到柱子C * 当盘子多余一个时，将盘子分为两部分，前n-1个和第n个，分三步进行 * 第一步将前n-1个盘子从柱子A移动到柱子B * 第二步将第n个盘子从柱子A移动到柱子C * 第三步将前n-1个盘子从柱子B移动到柱子C */ public static void TowerOfHanoi(int n, char A, char B,char C) { if (n < 1) return; TowerOfHanoi(n-1, A, C, B); System.out.println(A + "->" + C); TowerOfHanoi(n-1, B, A, C); } }
3.5 两个栈实现一个队列的两种解法
import java.util.Stack; /* * 两个栈实现一个队列 */ public class Num3_5 { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); /* public void push(int node) { int size = stack1.size(); for (int i = 0; i < size; i++) { stack2.push(stack1.pop()); } stack1.push(node); for (int i = 0; i < size; i++) { stack1.push(stack2.pop()); } } public int pop() { return stack1.pop(); } */ /* * 更好的方法，不用每次pop()操作都要移动元素 * stack1最顶元素为最新，stack2最顶元素为最旧元素 * 如果stack2不为空，则直接从stack2执行pop()，反之，将stack1的元素按序压入stack2，并pop()栈底元素 * push()则直接在stack1上操作 */ public void push(int node) { stack1.push(node); } public int pop() { if (!stack2.isEmpty()) { return stack2.pop(); } else { int size = stack1.size(); for (int i = 0; i < size - 1; i++) { stack2.push(stack1.pop()); } return stack1.pop(); } } public int peek() { if (!stack2.isEmpty()) { return stack2.peek(); } else { int size = stack1.size(); for (int i = 0; i < size - 1; i++) { stack2.push(stack1.pop()); } return stack1.peek(); } } }
4.树与图
4.1
实现一个函数，检查二叉树是否平衡，平衡的定义如下，对于树中的任意一个结点，其两颗子树的高度差不超过1。
给定指向树根结点的指针TreeNode* root，请返回一个bool，代表这棵树是否平衡。
public class Num4_1 { /* * 时间复杂度为N*logN，N为树的节点数 public boolean isBalance(TreeNode root) { // write code here if (root == null || (root.left == null && root.right == null)) return true; if (Math.abs((getDepth(root.left) - getDepth(root.right))) > 1) return false; else return isBalance(root.left) && isBalance(root.right); } //计算当前节点的高度 public int getDepth(TreeNode node) { if (node == null) return 0; else return Math.max(getDepth(node.left),getDepth(node.right)) + 1; } */ /* * 减少getDepth的调用次数，在计算高度的同时判断是否为平衡二叉树 * 时间复杂度为O(N)，还不是最优 */ /* boolean balance = true; public boolean isBalance(TreeNode root) { // write code here if (root == null || (root.left == null && root.right == null)) return true; getDepth(root); return balance; } public int getDepth(TreeNode node) { if (node == null) return 0; else { int leftDepth = getDepth(node.left); int rightDepth = getDepth(node.right); if (Math.abs(leftDepth - rightDepth) > 1) balance = false; return Math.max(leftDepth, rightDepth) + 1; } } */ /* * 最优解法，当发现子树不是平衡二叉树时，立即中断getDepth递归 * 时间复杂度是O(N),但是平均时间复杂度要比上一种解法更优 */ public boolean isBalance(TreeNode root) { // write code here if (getDepth(root) == -1) { return false; } else return true; } public int getDepth(TreeNode node) { if (node == null) return 0; else { int leftDepth = getDepth(node.left); if (leftDepth == -1) return -1; int rightDepth = getDepth(node.right); if (rightDepth == -1) return -1; if (Math.abs(leftDepth - rightDepth) > 1) { return -1; } else { return Math.max(leftDepth, rightDepth) + 1; } } } }
4.2
对于一个有向图，请实现一个算法，找出两点之间是否存在一条路径。
给定图中的两个结点的指针UndirectedGraphNode*a,UndirectedGraphNode* b(请不要在意数据类型，图是有向图),请返回一个bool，代表两点之间是否存在一条路径(a到b或b到a)。
import java.util.HashSet; import java.util.LinkedList; import java.util.Queue; import java.util.Set; /* import java.util.ArrayList; public class UndirectedGraphNode { int label = 0; UndirectedGraphNode left = null; UndirectedGraphNode right = null; ArrayList<UndirectedGraphNode> neighbors = new ArrayList<UndirectedGraphNode>(); public UndirectedGraphNode(int label) { this.label = label; } } */ /* * 结果显示DFS比BFS稍微快一点 * 注意两个方向都要遍历 */ public class Num4_2 { Set<UndirectedGraphNode> set = new HashSet<UndirectedGraphNode>(); public boolean checkPath(UndirectedGraphNode a, UndirectedGraphNode b) { // write code here //BFS //return check3(a, b) || check3(b, a); //DFS if (check(a, b)) return true; else { set.clear(); return check(b, a); } } //DFS public boolean check(UndirectedGraphNode a, UndirectedGraphNode b){ if (a == b) return true; set.add(a); for (UndirectedGraphNode u : a.neighbors) { if (!set.contains(u)) { if (check(u, b)) return true; } } return false; } //广度优先遍历BFS public boolean check3(UndirectedGraphNode a, UndirectedGraphNode b){ Set<UndirectedGraphNode> set3 = new HashSet<UndirectedGraphNode>(); Queue<UndirectedGraphNode> qu = new LinkedList<UndirectedGraphNode>(); qu.add(a); while (!qu.isEmpty()) { UndirectedGraphNode u = qu.poll(); if (u == b) return true; set3.add(u); for (UndirectedGraphNode uu : u.neighbors) { if (!set3.contains(uu)) { qu.add(uu); } } } return false; } }
4.3
对于一个元素各不相同且按升序排列的有序序列，请编写一个算法，创建一棵高度最小的二叉查找树。
给定一个有序序列int[] vals,请返回创建的二叉查找树的高度。
注：题意描述与书本原题是有出入的。原题是重在创建这颗二叉树，而本题只要返回高度即可，并不用创建二叉树。在代码中也给出创建二叉树的部分。
/* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Num4_3 { /* * 对于一个元素各不相同且按升序排列的有序序列，请编写一个算法，创建一棵高度最小的二叉查找树。 * 并返回树高度 */ public int buildMinimalBST(int[] vals) { // write code here build(vals, 0, vals.length - 1); //树高度等于log2(n+1)取上整 ，用到换底公式 log2(n+1) = loge(n+1)/loge(2) return (int)Math.ceil(Math.log(vals.length + 1) / Math.log(2)); } public TreeNode build(int[] vals, int a, int b) { if (a > b) { return null; } TreeNode t = new TreeNode(vals[(a + b)/2]); t.left = build(vals, a, (a + b) / 2 - 1); t.right = build(vals, (a + b) / 2 + 1, b); return t; } }
4.4
对于一棵二叉树，请设计一个算法，创建含有某一深度上所有结点的链表。
给定二叉树的根结点指针TreeNode* root，以及链表上结点的深度，请返回一个链表ListNode，代表该深度上所有结点的值，请按树上从左往右的顺序链接，保证深度不超过树的高度，树上结点的值为非负整数且不超过100000。
注：书中的返回是前dep层的所有节点构成的链表集合，每一层一个链表，这里返回的是第dep层的节点构成的链表
public class Num4_4 { ListNode ans = null; ListNode last = null; public ListNode getTreeLevel(TreeNode root, int dep) { // write code here //前两种方法都是广度优先遍历，第一种判断每层结束的方法比较复杂，是根据上一层空节点的个数，来pandaun下一层总结点数 //在遍历的时候再计数，如果每一层节点计数大于了该层节点数，则层数增一 /* Queue<TreeNode> qt = new LinkedList<TreeNode>(); ListNode start = null; ListNode last = null; qt.add(root); int count = 0; int depth = 1; int nCount = 0; while (!qt.isEmpty()) { count++; if (count > (Math.pow(2, depth - 1) - 2 * nCount)) { depth++; if (depth > dep) return start; count = 1; nCount = 0; } TreeNode temp = qt.poll(); if (temp != null) { if (depth == dep) { ListNode l = new ListNode(temp.val); if (start == null) start = l; else last.next = l; last = l; } qt.add(temp.left); qt.add(temp.right); } else { nCount++; } } return start; */ /* 对每一层都新建一个队列，把该层所有节点添加进去 直到到达指定层 */ /* Queue<TreeNode> current = new LinkedList<TreeNode>(); ListNode ans = null; ListNode last = null; current.add(root); int depth = 1; while (!current.isEmpty()) { if (depth == dep) break; Queue<TreeNode> parents = current; current = new LinkedList<TreeNode>(); for (TreeNode parent : parents) { if (parent.left != null) current.add(parent.left); if (parent.right != null) current.add(parent.right); } depth++; } for (TreeNode cur : current) { ListNode l = new ListNode(cur.val); if (ans == null) ans = l; else last.next = l; last = l; } return ans; */ get(root, dep, 1); return ans; } //深度优先遍历 public void get(TreeNode root, int dep, int currentDepth) { if (root == null) return ; if (currentDepth == dep) { ListNode l = new ListNode(root.val); if (ans == null) ans = l; else last.next = l; last = l; return ; } get(root.left, dep, currentDepth + 1); get(root.right, dep, currentDepth + 1); } }
4.5
请实现一个函数，检查一棵二叉树是否为二叉查找树。
给定树的根结点指针TreeNode* root，请返回一个bool，代表该树是否为二叉查找树。
public class Num4_5 { /* //结果显示第一种解法较好，但是其实复杂度是相当的 int pre = Integer.MIN_VALUE; public boolean checkBST(TreeNode root) { // wurite code here //中序遍历 if (root == null) return true; if (!checkBST(root.left)) return false; if (root.val < pre) return false; pre = root.val; return checkBST(root.right); } */ //最小最大值法（我称为夹逼法） public boolean checkBST(TreeNode root) { return check(root, Integer.MIN_VALUE, Integer.MAX_VALUE); } public boolean check(TreeNode root, int min, int max) { if (root == null) return true; if (root.val < min || root.val > max) { return false; } if (!check(root.left, min, root.val)) return false; return check(root.right, root.val, max); } }
4.6
请设计一个算法，寻找二叉树中指定结点的下一个结点（即中序遍历的后继）。
给定树的根结点指针TreeNode* root和结点的值int p，请返回值为p的结点的后继结点的值。保证结点的值大于等于零小于等于100000且没有重复值，若不存在后继返回-1。
import java.util.ArrayList; import java.util.List; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; TreeNode parent = null; public TreeNode(int val) { this.val = val; } } */ public class Num4_6 { /* * 不使用父节点的办法，给出根节点，返回下一节点的值,没有后继结点则返回-1 * 利用中序遍历递归找到该节点，并在递归时几下当前节点的递归次数，则下一次就是后继节点 List<Integer> vals = new ArrayList<Integer>(); static int count = 0; static int pos = -2; public static int findSucc(TreeNode root, int p) { // write code here if (root == null) return -1; int temp = findSucc(root.left, p); if (temp == -1) { count++; if (count == pos + 1) return root.val; if (root.val == p) pos = count; return findSucc(root.right, p); } return temp; } */ public static void main(String[] args) { TreeNode root = new TreeNode(1); TreeNode r1 = new TreeNode(2); TreeNode r2 = new TreeNode(3); TreeNode r3 = new TreeNode(4); TreeNode r4 = new TreeNode(5); TreeNode r5 = new TreeNode(6); TreeNode r6 = new TreeNode(7); root.left = r1; root.right = r2; r1.left = r3; r1.right = r4; r4.right = r5; r2.right = r6; // System.out.println(findSucc(root, 3)); } /* 可以连接到父节点的做法，给出当前节点,返回下一节点(书上给出的做法) * 若当前节点有右子树，则返回右子树的最左节点 * 若当前节点没有右子树，则回溯到父节点，直到当前节点不再是右子节点，返回当前节点的父节点 * 如果一直找不到一个父节点使当前节点为左子节点，说明已到最右节点，没有后继结点，返回null */ public static TreeNode findSucc(TreeNode node) { if(node == null) return null; if(node.right != null) { TreeNode temp = node.right; while (temp.left != null) { temp = temp.left; } return temp; } TreeNode parent = node.parent; while (parent != null && node == parent.right) { node = parent; parent = node.parent; } return parent; } }
4.7
有一棵无穷大的满二叉树，其结点按根结点一层一层地从左往右依次编号，根结点编号为1。现在有两个结点a，b。请设计一个算法，求出a和b点的最近公共祖先的编号。
给定两个int a,b。为给定结点的编号。请返回a和b的最近公共祖先的编号。注意这里结点本身也可认为是其祖先。
测试样例：
2，3
返回：1
import java.util.*; public class LCA { public int getLCA(int a, int b) { // write code here while (a != b) { if (a > b) a = a / 2; else b = b / 2; } return a; } }
当一般情况时，任意二叉树的任意节点，返回最近公共祖先
//二叉树中两个节点的最近共同祖先 public class Num4_7 { /* * 第一种情况满二叉树，并且每个节点的值是按照层序遍历1，2，3，4。。。依次排列，给出两个节点值，求共同祖先的节点值 */ public int findCommonAncestor(int a, int b) { while (a != b) { if (a > b) a /= 2; if (b > a) b /= 2; } return a; } /* * 第二种一般情况下的二叉树，给出根节点和任意两个节点，返回祖先节点 */ public TreeNode find(TreeNode root, TreeNode a, TreeNode b) { //节点不在树中 if (!isCoverNode(root, a) || !isCoverNode(root, b)) return null; return findCommonAncestor(root, a, b); } public TreeNode findCommonAncestor(TreeNode root, TreeNode a, TreeNode b) { if (root == null) return null; if (root == a || root == b) return root; boolean aCoverLeft = isCoverNode(root.left, a); boolean bCoverleft = isCoverNode(root.left, b); //不在同一子树 if (aCoverLeft != bCoverleft) { return root; } //在同一子树，则继续遍历那棵子树 return findCommonAncestor(aCoverLeft == false ? root.right : root.left, a, b); } //判断节点是否在以root为根节点所在的子树 public boolean isCoverNode(TreeNode root, TreeNode node) { if (root == null) return false; if (root == node) return true; return isCoverNode(root.left, node) || isCoverNode(root.right, node); } public static void main(String[] args) { Num4_7 num4_7 = new Num4_7(); TreeNode root = new TreeNode(1); TreeNode r1 = new TreeNode(2); TreeNode r2 = new TreeNode(3); TreeNode r3 = new TreeNode(4); TreeNode r4 = new TreeNode(5); TreeNode r5 = new TreeNode(6); TreeNode r6 = new TreeNode(7); TreeNode r7 = new TreeNode(7); root.left = r1; root.right = r2; r1.left = r3; r1.right = r4; r4.right = r5; r2.right = r6; TreeNode t = num4_7.find(root, root, r5); if (t != null) System.out.println(t.val); else System.out.println("null"); } }
一般情况的算法的时间复杂度为O(n)，因为在检查节点是否在树中的时候isCoverNode()执行了2n次，左边n次，右边n次。然后在判断节点在哪一边时，第一次是2*n/2，第二次2*n/4，以此类推，相加后求和渐进于O(4n),也就是O(n);
4.8
判断一棵二叉树是否为另一棵二叉树的子树
解法一：用两个字符串分别来表示树的前序遍历和中序遍历，如果树A的中序遍历是树B的中序遍历的字串，树A的前序遍历是树B的前序遍历的字串，则树A是树B的子树，注意要用特殊字符来表示空节点。此时空间复杂度为O(n+m),时间复杂度为O(n+m)(忽略常数系数，n和m分别为两棵树的节点数)，如果树的节点数较多时，这个方法就不太适用，所占用内存会过大。
解法二：遍历搜索较大的那棵树，如果找到某个节点与另棵树相同，则从此节点开始对比余下节点是否都相同，每遇到与另一棵树根据诶点相同的节点都要搜索一次，直到判断出是否为子树。使用递归来遍历，所以空间复杂度为O(log(n)+log(m)),最坏时间复杂度为O(nm)。但是假设相同的节点只会出现k次，时间复杂度就变为O(n+km),所以这个解法总体来说比较好。
public class Num4_8 { public static boolean isSubTree(TreeNode rootA, TreeNode rootB) { if (rootB == null) return true; if (rootA == null) return false; if (rootA.val == rootB.val) { if (isMatch(rootA, rootB)) return true; } return isSubTree(rootA.left, rootB) || isSubTree(rootA.right, rootB); } public static boolean isMatch(TreeNode nodeA, TreeNode nodeB) { if (nodeA == null && nodeB == null) return true; if (nodeA == null || nodeB == null || nodeA.val != nodeB.val) { return false; } return isMatch(nodeA.left, nodeB.left) && isMatch(nodeA.right, nodeB.right); } }
4.9
给定一棵二叉树和一个定值，找出二叉树中节点和等于这个定值的所有路径。
import java.util.ArrayList; /* * 起始节点和结束节点为树种的任意节点，只要构成路径即可 * 如果没有规定节点值都为正整数，则在找到满足的路径之后还要继续往下遍历，直到叶子节点 * 如果值都为正整数，则找到之后就可以结束当前路径的遍历 * 如果规定路径必须从根节点到叶子节点，更加简化了题目，把findhelper的递归注释即可，见注释部分 */ public class Num4_9 { ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { findHelper(root, target); return ans; } public void findHelper(TreeNode root, int target) { if (root == null) return ; //值都为正整数 // find(root, target, 0, new ArrayList<Integer>()); //值为正负零三种 find2(root, target, 0, new ArrayList<Integer>()); findHelper(root.left, target); findHelper(root.right, target); } //如果规定为正整数值 public void find(TreeNode node, int target, int sum, ArrayList<Integer> path) { if (node == null) return ; int curSum = sum + node.val; if (curSum <= target) { path.add(node.val); if (curSum == target) { ans.add(path); } else { find(node.left, target, curSum, new ArrayList<Integer>(path)); find(node.right, target, curSum, path); } } } //如果节点值可能为零或负数 public void find2(TreeNode node, int target, int sum, ArrayList<Integer> path) { if (node == null) return ; int curSum = sum + node.val; path.add(node.val); if (curSum == target) { ans.add(path); //注意new的使用，两边都要new find2(node.left, target, curSum, new ArrayList<Integer>(path)); find2(node.right, target, curSum, new ArrayList<Integer>(path)); } else { //有一边用new就行，而且这两句不能调换顺序 find2(node.left, target, curSum, new ArrayList<Integer>(path)); find2(node.right, target, curSum, path); } } /* * 规定路径必须从根节点到叶子节点，更加简化了题目 ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) { findHelper(root, target); return ans; } public void findHelper(TreeNode root, int target) { if (root == null) return ; find(root, target, 0, new ArrayList<Integer>()); // findHelper(root.left, target); // findHelper(root.right, target); } public void find(TreeNode node, int target, int sum, ArrayList<Integer> path) { if (node == null) return ; int curSum = sum + node.val; if (curSum <= target) { path.add(node.val); if (curSum == target && node.left == null && node.right == null) { ans.add(path); } else { find(node.left, target, curSum, new ArrayList<Integer>(path)); find(node.right, target, curSum, path); } } } */ public static void main(String[] args) { Num4_9 num4_9 = new Num4_9(); TreeNode root = new TreeNode(1); TreeNode r1 = new TreeNode(2); TreeNode r2 = new TreeNode(3); TreeNode r3 = new TreeNode(4); TreeNode r4 = new TreeNode(-1); TreeNode r5 = new TreeNode(0); TreeNode r6 = new TreeNode(7); TreeNode r7 = new TreeNode(7); root.left = r1; root.right = r2; r1.left = r3; r1.right = r4; r4.right = r5; r2.right = r6; ArrayList<ArrayList<Integer>> ret = num4_9.FindPath(root, 2); } }
9.8硬币面值组合问题
分析转自 http://www.cnblogs.com/python27/p/3303721.html
给定一个数值sum，假设我们有m种不同类型的硬币{V1, V2, ..., Vm}，如果要组合成sum，那么我们有
sum = x1 * V1 + x2 * V2 + ... + xm * Vm
求所有可能的组合数，就是求满足前面等值的系数{x1, x2, ..., xm}的所有可能个数。
[思路1] 当然我们可以采用暴力枚举，各个系数可能的取值无非是x1 = {0, 1, ..., sum / V1}, x2 = {0, 1, ..., sum/ V2}等等。这对于硬币种类数较小的题目还是可以应付的，比如华为和创新工厂的题目，但是复杂度也很高O（sum/V1 * sum/V2 * sum/V3 * ...）
[思路2] 从上面的分析中我们也可以这么考虑，我们希望用m种硬币构成sum，根据最后一个硬币Vm的系数的取值为无非有这么几种情况，xm分别取｛0, 1, 2, ..., sum/Vm｝，换句话说，上面分析中的等式和下面的几个等式的联合是等价的。
sum = x1 * V1 + x2 * V2 + ... + 0 * Vm
sum = x1 * V1 + x2 * V2 + ... + 1 * Vm
sum = x1 * V1 + x2 * V2 + ... + 2 * Vm
...
sum = x1 * V1 + x2 * V2 + ... + K * Vm
其中K是该xm能取的最大数值K = sum / Vm。可是这又有什么用呢？不要急，我们先进行如下变量的定义：
dp[i][sum] = 用前i种硬币构成sum 的所有组合数。
那么题目的问题实际上就是求dp[m][sum]，即用前m种硬币（所有硬币）构成sum的所有组合数。在上面的联合等式中：当xn=0时，有多少种组合呢？ 实际上就是前i-1种硬币组合sum，有dp[i-1][sum]种！ xn = 1 时呢，有多少种组合？ 实际上是用前i-1种硬币组合成(sum - Vm)的组合数，有dp[i-1][sum -Vm]种; xn =2呢， dp[i-1][sum - 2 * Vm]种，等等。所有的这些情况加起来就是我们的dp[i][sum]。所以：
dp[i][sum] = dp[i-1][sum - 0*Vm] + dp[i-1][sum - 1*Vm]
+ dp[i-1][sum - 2*Vm] + ... + dp[i-1][sum - K*Vm]; 其中K = sum / Vm
换一种更抽象的数学描述就是：
通过此公式，我们可以看到问题被一步步缩小，那么初始情况是什么呢？如果sum=0，那么无论有前多少种来组合0，只有一种可能，就是各个系数都等于0；
dp[i][0] = 1 // i = 0, 1, 2, ... , m
如果我们用二位数组表示dp[i][sum], 我们发现第i行的值全部依赖与i-1行的值，所以我们可以逐行求解该数组。如果前0种硬币要组成sum，我们规定为dp[0][sum] = 0.
将二维数组转变成一维数组
public int makeChange(int n) { int coins[] = {1,5,10,25}; int dp[] = new int[n + 1]; dp[0] = 1; for (int i = 0 ;i < 4; ++i) { for (int j = coins[i]; j <= n; ++j) { dp[j] = (dp[j] + dp[j - coins[i]]) % 1000000007; } } return dp[n]; }
9.9 n皇后问题
public class Num9_9 { //递归算法，效率比较差 /* * 从第一行开始，判断在每一列拜访皇后是否合法，若合法则摆放，并到下一行摆放，不合法则到下一列 * 判断是否合法主要是与前面已经摆放过的皇后进行比较，看是否同一列或者同对角线 * 判断对角线相同的原则是行数差和列数差的绝对值相等，不用判断是否在同一行，因为在摆放的时候是逐行摆放的 */ public int nQueens(int n) { // write code here int[] way = new int[n]; return placeQueens(n, 0, way); } public int placeQueens(int size, int row, int[] way) { if (row == size) return 1; int count = 0; for (int i = 0; i < size ; i++) { if (checkValid(row, i, way)) { way[row] = i; count += placeQueens(size, row + 1, way); } } return count; } public boolean checkValid(int row, int column, int[] way) { for (int i = 0; i < row; i++) { if (column == way[i] || Math.abs(column - way[i]) == row - i) return false; } return true; } }
9.10 堆箱子
import java.util.HashMap; import java.util.Map; public class Num9_10 { public int getHeight(int[] w, int[] l, int[] h, int n) { // write code here //这里一定要循环调用 int maxHeight = 0; for (int i = 0; i < n; i++) { int newHeight = getDp(w, l, h, i, n); if (newHeight > maxHeight) maxHeight = newHeight; } return maxHeight; } /* * 递归算法 */ public int get(int[] w, int[] l, int[] h, int bottom, int n) { int maxHeight = 0; for (int j = 0; j < n; j++) { if (canBeAbove(w, l, bottom, j)) { int newHeight = get(w, l, h, j, n); if (newHeight > maxHeight) { maxHeight = newHeight; } } } if (bottom < n) { maxHeight += h[bottom]; } return maxHeight; } /* * 动态规划 */ //保存以编号bottom为底时的最高堆高度 Map<Integer, Integer> bottoms = new HashMap<Integer, Integer>(); public int getDp(int[] w, int[] l, int[] h, int bottom, int n) { if (bottoms.containsKey(bottom)) { return bottoms.get(bottom); } int maxHeight = 0; for (int j = 0; j < n; j++) { if (canBeAbove(w, l, bottom, j)) { int newHeight = getDp(w, l, h, j, n); if (newHeight > maxHeight) { maxHeight = newHeight; } } } if (bottom < n) { maxHeight += h[bottom]; bottoms.put(bottom, maxHeight); } return maxHeight; } public boolean canBeAbove(int[] w, int[] l, int bottom, int j) { if (w[j] < w[bottom] && l[j] < l[bottom]) return true; return false; } }
11.2
一开始没有看清题意，在线解题和书本的题意不同
import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; import java.util.HashMap; import java.util.Map; public class Num11_2 { public ArrayList<String> sortStrings(String[] str, int n) { // write code here Arrays.sort(str); ArrayList<String> ans = new ArrayList<String>(); for (int i = 0; i < n; i++) { boolean insertOk = true; // //变位词只保留字典序最前的一个 // for (int j = 0; j < ans.size(); j++) { // if (str[i].length() == ans.get(j).length()) { // char[] a = ans.get(j).toCharArray(); // char[] b = str[i].toCharArray(); // Arrays.sort(a); // Arrays.sort(b); // String aa = String.valueOf(a); // String bb = String.valueOf(b); // if (aa.equals(bb)) { // insertOk = false; // break; // } // } // } // if (insertOk) // ans.add(str[i]); //变位词排在相邻位置 for (int j = ans.size() - 1; j >= 0; j--) { if (str[i].length() == ans.get(j).length()) { char[] a = ans.get(j).toCharArray(); char[] b = str[i].toCharArray(); Arrays.sort(a); Arrays.sort(b); String aa = String.valueOf(a); String bb = String.valueOf(b); if (aa.equals(bb)) { ans.add(j + 1, str[i]); insertOk = false; break; } } } if (insertOk) ans.add(str[i]); } return ans; } //只考虑变位词拍在相邻位置而不考虑其他顺序 /* * 方法一：重写排序函数 */ class MyComparator implements Comparator<String> { public String sortStr(String str) { char[] array = str.toCharArray(); Arrays.sort(array); return new String(array); } @Override public int compare(String o1, String o2) { // TODO Auto-generated method stub return sortStr(o1).compareTo(sortStr(o2)); } } public String[] simpleSort(String[] str) { Arrays.sort(str, new MyComparator()); return str; } /* * 方法二：利用散列表将变位词分组 */ public ArrayList<String> hashSort(String[] str) { Map<String, ArrayList<String>> hm = new HashMap<String, ArrayList<String>>(); //将变位词分组 for (String s : str) { char[] arr = s.toCharArray(); Arrays.sort(arr); String ss = new String(arr); if (!hm.containsKey(ss)) hm.put(ss, new ArrayList<String>()); ArrayList<String> al = hm.get(ss); al.add(s); } //将hashmap转为数组/ArrayList ArrayList<String> ans = new ArrayList<String>(); int index = 0; for(String key : hm.keySet()) { ArrayList<String> al = hm.get(key); for (String s : al) { ans.add(s); } } return ans; } public static void main(String[] args) { Num11_2 n112 = new Num11_2(); String[] str = {"dad","add","abc","ab","cba","ba"}; n112.simpleSort(str); } }
11.3
public class Num11_3 { /* * 二分法的变形 * 具体解释看书P257吧，懒得码了 * 需要注意的是第三中情况也就是中间的数等于左右两头的数的时候，两边都要搜索了 * 如果左边搜索得不到结果就要搜索右边，如果得到结果就直接返回 * 所有元素不同的话时间复杂度为O(log(n)),很多元素重复的话,会有很多第三种情况出现，就会接近于O(n) */ public int findElement(int[] A, int n, int x) { // write code here return find(A, 0, n - 1,x); } public int find(int[] arr, int left, int right, int x) { if (left <= right) { int mid = (left + right) / 2; if (x == arr[mid]) return mid; if (arr[left] < arr[mid]) { if (x >= arr[left] && x <= arr[mid]) { return find(arr, left, mid, x); } return find(arr, mid + 1, right, x); } if (arr[mid + 1] < arr[right]) { if (x >= arr[mid + 1] && x <= arr[right]) { return find(arr, mid + 1, right, x); } return find(arr, left, mid, x); } //前面两个条件都不满足时 int ans = find(arr, left, mid, x); if (ans == -1) return find(arr, mid + 1, right, x); return ans; } return -1; } }
11.6
public class Num11_6 { public int[] findElement(int[][] mat, int n, int m, int x) { // write code here return find(mat, 0, 0, mat[0].length - 1, x); } /* * 方法一：对每一行进行二分查找 */ public int[] find(int[][] mat, int row, int left, int right, int x) { if (row < mat.length) { if (left <= right) { int mid = (left + right) / 2; if (mat[row][mid] == x) { int[] ans = {row, mid}; return ans; } if (mat[row][mid] > x) { if (mid == 0) return null; return find(mat, row, left, mid - 1, x); } return find(mat, row, mid + 1, right, x); } return find(mat, row + 1, 0, mat[0].length - 1, x); } return null; } /* * 方法二：利用以下四个原则进行查找 * 1.列首元素如果大于X，则往该列的左一列查找 * 2.列尾元素如果小于X，则往该列的右一列查找 * 3.行首元素如果大于X，则往该行的上一行查找 * 4.行尾元素如果小于X，则往该行的下一行查找 * 我们可以从矩阵的任意位置开始查找，这里从最右上方的元素开始 */ public int[] find(int[][] mat, int x) { int row = 0; int col = mat[0].length - 1; while (row <= mat.length && col >= 0) { if (mat[row][col] == x) { int[] ans = {row, col}; return ans; } if (mat[row][col] > x) { col--; } else row++; } return null; } /* * 方法三：对对角线上的元素进行二分查找，把矩阵分为四个区域,进行递归查找 * 具体解释参照书本P262 */ public int[] findDiv(int[][] mat, int topRow, int topCol, int botRow, int botCol, int x) { if (topRow >= 0 && topCol >= 0 && botRow <= mat.length && botCol <= mat[0].length && topRow <= botRow && topCol <= botCol) { //某个子矩阵只有一个元素时 if (topRow == botRow && topCol == botCol) { if (mat[topRow][topCol] == x) { int[] ans = {topRow, topCol}; return ans; } return null; } //矩阵不是正方形，所以得求出其中的最大正方形的对角线 int min = Math.min(botRow - topRow, botCol - topCol); int mid = min / 2; if (mat[topRow + mid][topCol + mid] == x) { int[] ans = {topRow + mid, topCol + mid}; return ans; } else if (mat[topRow + mid][topCol + mid] < x) { int[] ans = findDiv(mat, topRow + mid + 1, topCol + mid + 1, botRow, botCol, x ); //右下区域 if (ans == null) { ans = findDiv(mat, topRow + mid + 1, topCol, botRow, topCol + mid, x ); // 左下区域 if (ans == null) return findDiv(mat, topRow, topCol + mid + 1, topRow + mid, botCol, x ); //右上区域 return ans; } else { return ans; } } else { int[] ans = findDiv(mat, topRow, topCol, topRow + mid, topCol + mid, x); //左上区域 if (ans == null) { ans = findDiv(mat, topRow + mid + 1, topCol, botRow, topCol + mid, x ); // 左下区域 if (ans == null) return findDiv(mat, topRow, topCol + mid + 1, topRow + mid, botCol, x ); //右上区域 return ans; } else { return ans; } } } return null; } public static void main(String[] args) { Num11_6 n116 = new Num11_6(); int[][] mat = {{0,2,3,4},{1,5,6,7}}; n116.find(mat, 0, 0, 3, 7); } }
11.8
public class Num11_8 { //实现一个二叉查找树来插入元素，并且在结点中存储每个结点的左子树结点数量 RankNode root = null; public int[] getRankOfNumber(int[] A, int n) { // write code here int[] rank = new int[n]; for (int i = 0; i < n; i++) { track(A[i]);//插入数据 rank[i] = root.getRank(A[i]);//获得该数据的秩 } return rank; } public void track(int val) { if (root == null) root = new RankNode(val); else root.insert(val); } } //实现的数据结构 class RankNode { RankNode left = null, right = null; int val = 0; int leftSize = 0; public RankNode(int val) { this.val = val; } //往树中插入数据 时间复杂度为O(log(n)) public void insert(int val) { if (val <= this.val) { if (this.left != null) this.left.insert(val); else this.left = new RankNode(val); this.leftSize++; } else { if (this.right != null) this.right.insert(val); else this.right = new RankNode(val); } } //获得秩 时间复杂度为O(log(n)) public int getRank(int val) { if (val == this.val) return this.leftSize; if (val > this.val) { if(this.right == null) return -1; return this.leftSize + 1 + this.right.getRank(val); } if (this.left == null) return -1; return this.left.getRank(val); } }
17.3
计算n!尾部零的个数
/* * 计算n!尾部零的个数 * 零的个数也就是10的个数 ，10的个数可以看成是5的倍数或2的倍数，因为是2的倍数的数比是5的倍数多 * 所以只用求5的倍数 * 需要注意的是5的次方 25 = 5*5，所以相当于有两个5,125有三个5，所以次方増一，5的倍数也増一 */ public class Num17_3 { public int countZero(int n) { if (n < 0) { return -1; } int count = 0; for (int i = 5; n / i > 0; i *= 5) { count += n / i; } return count; } }
18.1
不用加号以及其他算术运算符的加法
public int addAB(int A, int B) { // write code here /*非递归解法 int c = 0; int j = 0; for (int i = 0; i < 32; i++) { if (((A & (1 << i)) | (B & (1 << i))) == 0) { if (j == 1) { c |= 1 << i; j = 0; } } else if (((A & (1 << i)) & (B & (1 << i))) == 0) { if (j == 0) c |= 1 << i; else j = 1; } else { if (j == 1) c |= 1 << i; else j = 1; } } return c;*/ //递归解法 if (B == 0) return A; int sum = A ^ B; //相加不进位 int carry = (A & B) <<1; //进位不想加 return addAB(sum,carry); }
18.2
完美洗牌--完美打乱一个数组
public class Num18_2 { /* * 随机打乱一个数组 * 采用递归的方式 * 先打乱数组的前n-1个元素，再将第n个元素与前n个元素中的元素随机交换 */ //产生[lower,higher]之间的随机数 public int rand(int lower,int higher) { return lower + (int) (Math.random() * (higher - lower + 1)); } //参数i为数组最后一个元素的索引 public int[] shuffleArrayRecursiveLy(int[] arr, int i) { if (i == 0) return arr; shuffleArrayRecursiveLy(arr, i - 1); int k = rand(0,i); //前i+1个元素中的随机一个 //将第i+1个元素与其交换 int temp = arr[k]; arr[k] = arr[i]; arr[i] = temp; return arr; } /* * 迭代的方式 */ public int[] shuffleArray(int[] arr) { for (int i = 1; i < arr.length; i++) { int k = rand(0,i); int temp = arr[k]; arr[k] = arr[i]; arr[i] = temp; } return arr; } }
18.4
输出0~n中的数字含有2的个数
public int countNumberOf2s(int n) { // write code here int count = 0; int length = Integer.toString(n).length(); for (int i = 0; i < length; i ++) { count += countAtDigit(n,i); } return count; } public int countAtDigit(int n, int d) { int powerOf10 = (int)Math.pow(10,d); int nextPow = powerOf10 * 10; int downRound = n - n % nextPow; int upRound = downRound + nextPow; int right = n % powerOf10; int digit = (n / powerOf10) % 10; if (digit == 2) { return downRound / 10 + right + 1; } else if (digit > 2) { return upRound / 10; } else return downRound / 10; }
18.7
public class Num17_7 { /* * 书本中给出的使用了hashmap来缓存的前提是字符串数组已经排序了 * 这样可以从长到短来遍历 * 这里没有使用缓存 */ public int getLongest(String[] str, int n) { // write code here int ans = 0, lastLen = 0; for (int i = 0; i < n; i++) { if (lastLen < str[i].length() && divideAndFind(str, str[i], i)) lastLen = str[i].length(); } return lastLen; } public boolean hasSub(String[] strs, String str, int index) { if (str == null) return true; for (int i = 0; i < strs.length; i++) { if (i != index) { if (strs[i].equals(str)) return true; } } return false; } public boolean divideAndFind(String[] strs, String str, int strIndex) { if (str == null || str.length() == 0) return true; for (int i = 1; i <= str.length(); i++) { if (hasSub(strs, str.substring(0, i), strIndex) && divideAndFind(strs, str.substring(i),strIndex)) return true; } return false; } }
18.8
利用后缀树实现的判断短字符串是否是某个字符串的子串，也附上kmp实现的代码
package 高难度题; import java.util.ArrayList; import java.util.HashMap; public class Num18_8 { /* * 利用后缀树实现 */ public boolean[] chkSubStr(String[] p, int n, String s) { // write code here SuffixTreeNode root = new SuffixTreeNode(); for (int i = 0;i < s.length(); i++) { root.insert(s.substring(i), i); } boolean[] ans = new boolean[n]; for (int i = 0;i < n; i++) { if (p[i] == null || p[i].length() == 0) ans[i] = false; else ans[i] = root.search(p[i]); } return ans; } /* * 利用kmp算法实现 */ public boolean[] chkSubStrKmp(String[] p, int n, String s) { // write code here boolean[] ans = new boolean[n]; for (int i = 0; i < n; i++) { if (isSubStr(p[i], s)) ans[i] = true; } return ans; } public boolean isSubStr(String par, String ori) { int next[] = new int[par.length()+1]; //求next数组每个元素值 next[0] = -1; int k = -1, j = 0; while ( j < par.length()) { //k == -1就表示比较到了第一位还不相等，所以next[j] = 0 //k其实就是next[j-1](k == -1时其实也是),par.charAt(j) == par.charAt(k)满足的话，也就是说next[j] = next[j-1]+1 //如果不满足那就要从前k个字符的前缀不相等的那一位开始 if (k == -1 || par.charAt(j) == par.charAt(k)) { next[++j] = ++k;//也就是说next[j] = next[j-1]+1 } else { k = next[k];//从前k个字符的前缀不相等的那一位开始从新比较 } } int p = 0,q = 0; while (p < ori.length()) { if (par.charAt(q) == ori.charAt(p)) { if (q == par.length()-1) { q = next[q]; return true;//出现模式串则返回 } else { //相等则继续往后比较 p++; q++; } } else { //不相等则移动 q = next[q]; } if (q == -1) { //比较了模式串的第一个字符且不相等 p++; q++; } } return false; } } /* * 后缀树的实现 */ class SuffixTreeNode { public SuffixTreeNode() {} HashMap<Character, SuffixTreeNode> children = new HashMap<Character, SuffixTreeNode>(); ArrayList<Integer> indexes = new ArrayList<Integer>(); public void insert(String str, int index) { if (str != null && str.length() != 0) { indexes.add(index); char value = str.charAt(0); SuffixTreeNode child; if (children.containsKey(value)) { child = children.get(value); } else { child = new SuffixTreeNode(); children.put(value, child); } String subStr = str.substring(1); child.insert(subStr, index); } } /* * 可以返回子串在原字符串中的索引，由于原字符串中的子串可能不止一个，所以返回的是ArrayList public ArrayList search(String t) { if (t == null || s.length() == 0) return indexes; else { char value = t.charAt(0); if (children.containsKey(value)) { String subStr = str.substring(1); return children.get(value).search(subStr); } } return null; }*/ public boolean search(String t) { if (t == null || t.length() == 0) return true; else { char value = t.charAt(0); if (children.containsKey(value)) { String subStr = t.substring(1); return children.get(value).search(subStr); } } return false; } }
18.10
/* * solution ： * 算法基础是广度优先遍历，在此基础上加上回溯 * 对于每一个遍历过的单词，利用hashmap backTrack将其与相差一个字母的单词映射 backTrack[v] = temp,表示v可以由temp更改得到 * backTrack 记录的是首次出现的键值对，因为以后如果再出现v，v已经visited，所以不会沿着这次出现的查询下去，因此没必要再加入backTrack * 当找到了目标单词后，在backTrack中往回回溯，即可得到路径 */ public class Num18_10 { public int countChanges(String[] dic, int n, String s, String t) { // write code here if (s.equals(t)) return 0; Set<String> dict = new HashSet<String>(); for (String ss : dic) { dict.add(ss); } Queue<String> q = new LinkedList<String>(); Map<String, String> backTrack = new HashMap<String, String>(); Set<String> visited = new HashSet<String>(); q.add(s); visited.add(s); while(!q.isEmpty()) { String temp = q.poll(); for (String v : change(temp)) { if (v.equals(t)) { int ret = 0; //注释部分可以用于返回整个路径 /* List<String> ans = new ArrayList<String>(); ans.add(v); */ while (temp != null) { ret++; /* ans.add(0, temp); */ temp = backTrack.get(temp); } //返回步数 return ret; } if (dict.contains(v) && !visited.contains(v)) { q.add(v); visited.add(v); backTrack.put(v,temp); } } } //没找到路径 return -1; } public Set<String> change(String str) { Set<String> changes = new HashSet<String>(); for (int i = 0; i < str.length(); i++) { char[] arr = str.toCharArray(); for (char c = 'a'; c <= 'z'; c++) { if (str.charAt(i) != c) { arr[i] = c; changes.add(new String(arr)); } } } return changes; } }
18.11
/* * solution 时间复杂度 是O(n^4),最简单的做法 * 按边长从大到小的顺序遍历矩阵中每个位置是否可以构成同值方阵，检查四条边的值是否全部相同 * 需要注意的是方阵的中心不一定是在原始矩阵的中心 */ public class Num18_11 { public int maxSubMatrix(int[][] mat, int n) { // write code here for (int len = n; len > 0; len--) { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++ ) { if (i + len <= n && j + len <= n) { if (checkTop(mat, i, j, len) && checkRight(mat, i, j, len) && checkBottom(mat, i, j, len) && checkLeft(mat, i, j, len)) { return len; } } } } } return 0; } public boolean checkTop(int[][] mat, int row, int column, int len) { for (int i = column + 1; i < column + len; i++) { if (mat[row][i] != mat[row][i - 1]) { return false; } } return true; } public boolean checkRight(int[][] mat, int row, int column, int len) { for (int i = row + 1; i < row + len; i++) { if (mat[i][column + len - 1] != mat[i - 1][column + len - 1]) { return false; } } return true; } public boolean checkBottom(int[][] mat, int row, int column, int len) { for (int i = column + 1; i < column + len; i++) { if (mat[row + len - 1][i] != mat[row + len - 1][i - 1]) { return false; } } return true; } public boolean checkLeft(int[][] mat, int row, int column, int len) { for (int i = row + 1; i < row + len; i++) { if (mat[i][column] != mat[i - 1][column]) { return false; } } return true; } }
18.12
/* * 题意：求矩阵的元素总和最大的子矩阵 ，返回 和 * solution : 若矩阵是R行C列 时间复杂度是O(R^2*C) * 子矩阵是由连续的行和连续的列组成的 * 迭代所有连续的行的组合，在每种行的组合中找使得和最大的连续的列的组合， 再得出每种行的组合的最大值即可 * 在每种行的组合中，我们可以把问题简化为求和最大子数组问题 * 在每种行的组合中，把每一列的和看成一维数组的一个元素，所以我们要求一维数组的和最大子数组，这个算法比较简单，已经实现 */ public class Num18_12 { public int sumOfSubMatrix(int[][] mat, int n) { // write code here if (mat == null) return -1; int maxSum = Integer.MIN_VALUE; int[] rowSum = new int[mat[0].length]; for (int i = 0; i < mat.length; i++) { //数组清零 for ( int k = 0; k < mat[0].length; k++) { rowSum[k] = 0; } for (int j = i; j < mat.length; j++) { for ( int k = 0; k < mat[0].length; k++) { rowSum[k] += mat[j][k]; } int curMax = maxSubArray(rowSum); if (curMax > maxSum) maxSum = curMax; } } return maxSum; } public int maxSubArray(int[] arr) { if (arr == null) return -1; int max = Integer.MIN_VALUE; int curSum = 0; for (int i = 0; i < arr.length; i++) { curSum += arr[i]; if (curSum > max) max = curSum; if (curSum < 0) curSum = 0; } return max; } }