构建乘积数组： 构建左右乘积表： 左乘积表表示A中位置i以前的所有元素乘积。对于i=0，由于左侧无元素，设为1 右乘积表表示A中位置i以后的所有元素乘积。对于i=n-1，由于左侧无元素，设为1 最终结果为左右乘积表对应位置相乘即可 public int[] multiply(int[] A) { if (A == null || A.length <= 1) { return null; } int n = A.length; int[] B1 = new int[n]; ...

解题思路：借助集合 设一个集合，用于存放已经遍历过且没有重复的元素，便于之后遍历时判断是否有重复。做法如下： 遍历数组，若集合不包含该元素，加入集合 若集合包含该元素，表示该元素之前有被访问过，且是第一个重复的元素，直接返回 最后若都没有重复的，表示数组中无重复元素 public boolean duplicate(int numbers[],int length,int [] duplication) { if (numbers == null || numbers.length == 0) { return false; ...

题目描述题目抽象：给定一个由[0...n-1]构成的数组，第一次从0开始数m个数，然后删除，以后每次都从删除的数下一个位置开始数m个数，然后删除，直到剩余一个数字，找出那个数字。比如：arr = [0 1 2 3 4]， m = 3第一次：删除2 ，变成 arr = [0 1 3 4]第二次，删除0，变成 arr = [1 3 4]第三次，删除4，变成 arr = [1 3]第四次，删除1，变成 arr = [3]解题方法借助队列一般涉及到这种循环移位，都可以借助队列来实现。移除队首可加入队尾 import java.util.LinkedList; import java.util.Queu...

题目抽象：给定一个首尾可能带空格的字符串，请让你翻转该字符串。首尾不能有多余空格。如果全部是空格，请返回原字符串。 实现拆分单词的操作。一个单词为：从不是空格的字符开始到是空格的前一个字符结束，即为一个单词。 借助栈来存放分离出来的单词 public static String ReverseSentence(String str) { if (str == null || str.length() < 2) { return str; } StringBuilder tem = new StringBuilder(); Deque&l...

题目描述：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！###求解方法：借助队列，1、队列队尾进，队首出。刚好与循环左移对应上，即：将队首移除的元素从队尾添加进去，即可实现循环左移 public static String LeftRotateString(String str,int n) { if (str == null || str.le...

题目描述输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。返回值描述:对应每个测试案例，输出两个数，小的先输出。###求解方法：双指针 1.初始化：指针l指向数组头， 指针r指向数组尾2. 如果array[l] + array[r]== sum , 说明是可能解3. 否则如果array[l] + array[r] > sum, 说明和太大，所以--r4. 否则如果array[l] + array[r] < sum, 说明和太小，所以++l 注意：升序数组中，当最外层两个数和里层两个数和相等时，外层两个数乘...

暴力求解 注意到连续和最大的情况是sum/2+sum/2+1.且这是针对sum为奇数。 public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer>> result = new ArrayList<>(); ArrayList<Integer> tem = new ArrayList<>(); if (su...

递归做法： 这道题最好结合树的深度那道题做。二叉树深度在树的深度中，我们已经得到了一个求解树的深度的递归函数。在本题中，我们可以设一个boolean值，在递归求解深度的函数中，顺便加上一个判断：即若左子树和右子树的高度相差大于1，则不平衡，布尔值变为false boolean flag = true; public boolean IsBalanced_Solution(TreeNode root) { if (root == null) { return true; } dfs(root); return flag; } private i...

递归求解： 递归结束条件：节点为空，则其深度为0否则以root为根节点的子树的深度等于1加上左右子树的深度大的那一个 public int TreeDepth(TreeNode root) { if (root == null) { return 0; } return 1 + Math.max(TreeDepth(root.left), TreeDepth(root.right)); }迭代求解：层序遍历 每当遍历完一层，深度加一 import java.util.LinkedList; import j...

题目描述在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,如果没有则返回 -1（需要区分大小写）.（从0开始计数） /** * 求解思路：借助哈希表 * 首先遍历字符串，得出每个字符出现的次数 * 然后遍历哈希表，比较出现次数为1的字符出现的索引，得到最小索引 * @param str * @return */ public int FirstNotRepeatingChar(String str) { if (str == null...

题目描述输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。 最简单直白的做法是排列出所有可能的数字，然后选出其中最小的那一个数作为返回结果。涉及到穷举出所有可能的排列结果，当然就采用回溯法求解。 public String PrintMinNumber(int [] numbers) { if (numbers == null || numbers.length == 0) { return null; ...

题目描述输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。方法：搜索回溯 思路：本题目是一个全排列问题。且给出的字符串中有重复元素，重复元素之间的顺序只当作一种顺序处理。为了穷举出所有的可能排列顺序，使用回溯法求解： 1、首先假设有n个空格，我们str中取出一个字符依次填入空格，待空格填充完毕，可得到一个字符排列。 2、设回溯函数 backing(vistied, pa...

方法：递归求解根据题意可知，需要一个函数判断树A和树B是否有相同的结构。显然是个递归程序。可考察递归程序3部曲。 递归函数的功能：判断2个数是否有相同的结构，如果相同，返回true，否则返回false 递归终止条件：如果树B为空，返回true，此时，不管树A是否为空，都为true否则，如果树B不为空，但是树A为空，返回false，此时B还没空但A空了，显然false 下一步递归参数：如果A的根节点和B的根节点不相等，则只需要用递归函数判断该节点的左子树和右子树是否与树B同结构否则，相等，就继续判断A的左子树和B的左子树以及A的右子树和B的右子树是否相同。还需要用递归函数判断该节点的左子树和右...