一般般帅
上一篇:31~36题
37~42题
2402 2018-11-21 2020-06-25
前言：牛客网剑指Offer编程题37~42题。
一、数字在排序数组中出现的次数
1、题目描述
考点知识迁移能力，统计一个数字在排序数组中出现的次数。
2、我的代码
public int GetNumberOfK(int [] array , int k) {
int t = 0;
for (int i = 0; i < array.length; i++) {
if (array[i] == k) {
++t;
if (i + 1 != array.length && array[i + 1] != k) {
return t;
}
}
}
return t;
}
3、我的代码2
int times = 0;
public int getNumberOfK(int[] array, int k) {
binarySearch(array, k, 0, array.length - 1);
return times;
}
public int binarySearch(int[] array, int k, int start, int end) {
if (start > end || start < 0 || end >= array.length) {
return 0;
}
int mid = (start + end) / 2;
if (array[mid] < k) {
return binarySearch(array, k, mid + 1, end);
}
if (array[mid] > k) {
return binarySearch(array, k, start, mid - 1);
}
times++;
return binarySearch(array, k, start, mid - 1) + binarySearch(array, k, mid + 1, end);
}
二、二叉树的深度
1、题目描述
考点知识迁移能力，输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
2、我的代码
static class ThirtyEight {
static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
int max = 0;
int depth = 0;
public int TreeDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.right == null && root.left == null) {
if (depth > max) {
max = depth;
}
return max + 1;
}
if (root.left != null) {
depth++;
TreeDepth(root.left);
depth--;
}
if (root.right != null) {
depth++;
TreeDepth(root.right);
depth--;
}
return max + 1;
}
private static void test() {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(4);
TreeNode node4 = new TreeNode(5);
node1.left = node2;
node2.left = node3;
node2.right = node4;
System.out.println(new ThirtyEight().TreeDepth(node1));
}
}
3、别人的代码
public int TreeDepth1(TreeNode root) {
if (root == null) {
return 0;
}
int nLelt = TreeDepth1(root.left);
int nRight = TreeDepth1(root.right);
return nLelt > nRight ? (nLelt + 1) : (nRight + 1);
}
还是递归的办法比较简单啊。
三、平衡二叉树
1、题目描述
考点知识迁移能力，输入一棵二叉树，判断该二叉树是否是平衡二叉树。
2、我的代码
感觉这题出的有问题，分两个答案吧。
static class ThirtyNine {
static class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public boolean IsBalanced_Solution(TreeNode root) {
if (root == null) {
return false;
}
int left = 0, right = 0, depthLeft = 0, depthRight = 0;
if (root.left != null) {
left = root.left.val;
depthLeft = TreeDepth1(root.left);
if (left >= root.val) {
return false;
}
}
if (root.right != null) {
right = root.right.val;
depthRight = TreeDepth1(root.right);
if (right <= root.val) {
return false;
}
}
if (depthLeft - depthRight > 1 || depthRight - depthLeft > 1) {
return false;
}
boolean result = true;
if (root.left != null) {
result = IsBalanced_Solution(root.left);
}
if (root.right != null && result) {
result = IsBalanced_Solution(root.right);
}
return result;
}
public boolean IsBalanced_Solution1(TreeNode root) {
if (root == null) {
return true;
}
int depthLeft = TreeDepth1(root.left);
int depthRight = TreeDepth1(root.right);
if (depthLeft - depthRight > 1 || depthRight - depthLeft > 1) {
return false;
}
boolean result = true;
if (root.left != null) {
result = IsBalanced_Solution1(root.left);
}
if (root.right != null && result) {
result = IsBalanced_Solution1(root.right);
}
return result;
}
public int TreeDepth1(TreeNode root) {
if (root == null) {
return 0;
}
int nLelt = TreeDepth1(root.left);
int nRight = TreeDepth1(root.right);
return nLelt > nRight ? (nLelt + 1) : (nRight + 1);
}
private static void test() {
TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
node4.left = node2;
node4.right = node6;
node2.left = node1;
node2.right = node3;
node6.left = node5;
node6.right = node7;
System.out.println(new ThirtyNine().IsBalanced_Solution(node1));
}
}
四、数组中只出现一次的数字
1、题目描述
考点知识迁移能力，一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。
2、我的代码
static class Forty {
public void FindNumsAppearOnce(int[] array,int num1[] , int num2[]) {
HashMap<Integer, Integer> map = new HashMap(array.length);
for (int i = 0; i < array.length; i++) {
if (map.containsKey(array[i])) {
map.put(array[i], 0);
} else {
map.put(array[i], 1);
}
}
boolean findOne = false;
Set<Map.Entry<Integer, Integer>> entry = map.entrySet();
for (Map.Entry<Integer, Integer> t : entry) {
if (t.getValue() == 1 && !findOne) {
num1[0] = t.getKey();
findOne = true;
} else if (t.getValue() == 1) {
num2[0] = t.getKey();
}
}
}
}
不好意思，偷了个懒。
3、别人的代码
/*考虑过程：
首先我们考虑这个问题的一个简单版本：一个数组里除了一个数字之外，其他的数字都出现了两次。请写程序找出这个只出现一次的数字。
这个题目的突破口在哪里？题目为什么要强调有一个数字出现一次，其他的出现两次？我们想到了异或运算的性质：任何一个数字异或它自己都等于0 。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字，因为那些出现两次的数字全部在异或中抵消掉了。
有了上面简单问题的解决方案之后，我们回到原始的问题。如果能够把原数组分为两个子数组。在每个子数组中，包含一个只出现一次的数字，而其它数字都出现两次。如果能够这样拆分原数组，按照前面的办法就是分别求出这两个只出现一次的数字了。
我们还是从头到尾依次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其它数字都出现了两次，在异或中全部抵消掉了。由于这两个数字肯定不一样，那么这个异或结果肯定不为0 ，也就是说在这个结果数字的二进制表示中至少就有一位为1 。我们在结果数字中找到第一个为1 的位的位置，记为第N 位。现在我们以第N 位是不是1 为标准把原数组中的数字分成两个子数组，第一个子数组中每个数字的第N 位都为1 ，而第二个子数组的每个数字的第N 位都为0 。
现在我们已经把原数组分成了两个子数组，每个子数组都包含一个只出现一次的数字，而其它数字都出现了两次。因此到此为止，所有的问题我们都已经解决。*/
public class 数组中只出现一次的数字 {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array==null ||array.length<2)
return ;
int temp = 0;
for(int i=0;i<array.length;i++)
temp ^= array[i];
int indexOf1 = findFirstBitIs(temp);
for(int i=0;i<array.length;i++){
if(isBit(array[i], indexOf1))
num1[0]^=array[i];
else
num2[0]^=array[i];
}
}
public int findFirstBitIs(int num){
int indexBit = 0;
while(((num & 1)==0) && (indexBit)<8*4){
num = num >> 1;
++indexBit;
}
return indexBit;
}
public boolean isBit(int num,int indexBit){
num = num >> indexBit;
return (num & 1) == 1;
}
}
感觉那个只出现一次的数字很有启发性，异或运算符（^）。
五、和为S的连续正数序列
1、题目描述
考点知识迁移能力，输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。
2、我的代码
static class FortyOne {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<>();
int end = sum % 2 == 0 ? sum / 2 : sum / 2 + 1;
for (int i = 1; i < end; i++) {
int cur = 0;
ArrayList<Integer> list = new ArrayList<>();
for (int j = i; j <= end; j++) {
cur += j;
if (cur < sum) {
list.add(j);
} else if (cur == sum) {
list.add(j);
lists.add(list);
} else {
break;
}
}
}
return lists;
}
}
3、别人的代码
1）由于我们要找的是和为S的连续正数序列，因此这个序列是个公差为1的等差数列，而这个序列的中间值代表了平均值的大小。假设序列长度为n，那么这个序列的中间值可以通过（S / n）得到，知道序列的中间值和长度，也就不难求出这段序列了。
2）满足条件的n分两种情况：
n 为奇数时，序列中间的数正好是序列的平均值，所以条件为：(n & 1) == 1 && sum % n == 0；
n为偶数时，序列中间两个数的平均值是序列的平均值，而这个平均值的小数部分为0.5，所以条件为：(sum % n) * 2 == n.
3）由题可知n >= 2，那么n的最大值是多少呢？我们完全可以将n从2到S全部遍历一次，但是大部分遍历是不必要的。为了让n尽可能大，我们让序列从1开始，
根据等差数列的求和公式：S = (1 + n) * n / 2，得到n < 根号下2S
最后举一个例子，假设输入sum = 100，我们只需遍历n = 13~2的情况（按题意应从大到小遍历），n = 8时，得到序列[9, 10, 11, 12, 13, 14, 15, 16]；n = 5时，得到序列[18, 19, 20, 21, 22]。
完整代码：时间复杂度为为根号n
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
for (int n = (int) Math.sqrt(2 * sum); n >= 2; n--) {
if ((n & 1) == 1 && sum % n == 0 || (sum % n) * 2 == n) {
ArrayList<Integer> list = new ArrayList<>();
for (int j = 0, k = (sum / n) - (n - 1) / 2; j < n; j++, k++) {
list.add(k);
}
ans.add(list);
}
}
return ans;
}
}
4、别人的代码2
// 双指针或窗口滑动技术
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
//存放结果
ArrayList<ArrayList<Integer> > result = new ArrayList<>();
//两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
int plow = 1,phigh = 2;
while(phigh > plow){
//由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
int cur = (phigh + plow) * (phigh - plow + 1) / 2;
//相等，那么就将窗口范围的所有数添加进结果集
if(cur == sum){
ArrayList<Integer> list = new ArrayList<>();
for(int i=plow;i<=phigh;i++){
list.add(i);
}
result.add(list);
plow++;
//如果当前窗口内的值之和小于sum，那么右边窗口右移一下
}else if(cur < sum){
phigh++;
}else{
//如果当前窗口内的值之和大于sum，那么左边窗口右移一下
plow++;
}
}
return result;
}
}
六、和为S的两个数字
1、题目描述
考点知识迁移能力，输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的（小的先输出）。
2、我的代码
static class FortyTwo {
public ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
ArrayList<Integer> list = new ArrayList<>();
if (array.length == 0) {
return list;
}
int a = 0, b = array.length - 1;
while (a != b) {
if (array[a] + array[b] > sum) {
b--;
} else if (array[a] + array[b] < sum) {
a++;
} else if (array[a] + array[b] == sum) {
list.add(array[a]);
list.add(array[b]);
break;
}
}
return list;
}
}
已经刷了十分之七了，加油，坚持就是胜利。
总访问次数: 251次, 一般般帅 创建于 2018-11-21, 最后更新于 2020-06-25
欢迎关注微信公众号，第一时间掌握最新动态！