网站备案大概需要多久,wordpress 会员制 主题,微信开放平台开发者,网站开发实训室剑指offer -- java题解刷题地址1、数字在升序数组中出现的次数2、二叉搜索树的第k个节点3、二叉树的深度4、数组中只出现一次的两个数字5、和为S的两个数字6、左旋转字符串7、滑动窗口的最大值8、扑克牌顺子9、孩子们的游戏(圆圈中最后剩下的数)10、买卖股票的最好时机(一)刷题…
剑指offer -- java题解刷题地址1、数字在升序数组中出现的次数2、二叉搜索树的第k个节点3、二叉树的深度4、数组中只出现一次的两个数字5、和为S的两个数字6、左旋转字符串7、滑动窗口的最大值8、扑克牌顺子9、孩子们的游戏(圆圈中最后剩下的数)10、买卖股票的最好时机(一)刷题地址
https://www.nowcoder.com/exam/oj/ta?tpId13
1、数字在升序数组中出现的次数
给定一个长度为 n 的非降序数组和一个非负数整数 k 要求统计 k 在数组中出现的次数 [1,2,3,3,3,3,4,5],3 4 解析 用二分查找找到 k 0.5 的位置(k的最后一位的后一位)和 k−0.5k的第一位的位置二者相减就是k出现的次数。 代码 public class Solution {public int GetNumberOfK(int [] array , int k) {return binsearch(array, k 0.5) - binsearch(array, k - 0.5);}private int binsearch(int [] array, double k){int l 0;int r array.length - 1;while(l r){int mid l (r - l) / 2;if(array[mid] k){l mid 1;}else if(array[mid] k){r mid - 1;}}return l;}
}2、二叉搜索树的第k个节点
给定一棵结点数为n 二叉搜索树请找出其中的第 k 小的TreeNode结点值。 1.返回第k小的节点值即可 2.不能查找的情况如二叉树为空则返回-1或者k大于n等等也返回-1 3.保证n个节点的值不一样 解析 二叉搜索树中序遍历左中右序列正好是由小到大的次序因此递归中序遍历也就是从最小的一个节点开始找到k个就是我们要找的目标 代码 public class Solution {int count 0;public int KthNode (TreeNode proot, int k) {// write code hereTreeNode res midOrder(proot, k);if(res ! null) return res.val;return -1;}private TreeNode midOrder(TreeNode root, int k){if(root null || count k) return null;TreeNode left midOrder(root.left, k);if(left ! null) return left;count;if(count k) return root;return midOrder(root.right, k);}
}3、二叉树的深度
输入一棵二叉树求该树的深度。从根结点到叶结点依次经过的结点含根、叶结点形成树的一条路径最长路径的长度为树的深度根节点的深度视为 1 。 解析 dfs 代码 public class Solution {public int TreeDepth(TreeNode root) {if(root null) return 0;return Math.max(TreeDepth(root.left), TreeDepth(root.right)) 1;}
}4、数组中只出现一次的两个数字
一个整型数组里除了两个数字只出现一次其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。 解析 假设要找的两个数为a, b;数组中所有数逐个异或即x1 ^ x2 ^ y1 ^ y2 ^ …… ^ a ^ b, 最终成对的数根据归零率变成0再根据恒等率剩下的一定是a ^ b
从a ^ b中可以获得某种信息因为a ! b所以a ^ b一定不为0它其中某一位为1根据这一位可以把a和b区分开因为异或是两个输入不同时为1相同时为0
a (-a)可以找到最右侧的1 代码 public class Solution {public int[] FindNumsAppearOnce (int[] array) {int eor 0;for(int num : array){eor ^ num;}int a_b 0;//找到最右边第一个不相等的1int rightOne eor (~eor 1);for(int num : array){if((num rightOne) 0){a_b ^ num;}}int min a_b (a_b ^ eor) ? a_b : (a_b ^ eor);int max min ^ eor;return new int[]{min, max};}
}5、和为S的两个数字
输入一个升序数组 array 和一个数字S在数组中查找两个数使得他们的和正好是S如果有多对数字的和等于S返回任意一组即可如果无法找出这样的数字返回一个空数组即可。 解析 使用双指针指向数组第一个元素和最后一个元素然后双指针对撞移动如果两个指针下的和正好等于目标值sum那我们肯定找到了如果和小于sum说明我们需要找到更大的那只能增加左边的元素如果和大于sum说明我们需要找更小的只能减小右边的元素。 代码 import java.util.ArrayList;
public class Solution {public ArrayListInteger FindNumbersWithSum(int [] array,int sum) {ArrayListInteger res new ArrayList();int l 0, r array.length - 1;while(l r){int s array[l] array[r];if(s sum){l;}else if(s sum){r--;}else{res.add(array[l]);res.add(array[r]);break;}}return res;}
}6、左旋转字符串 解析 三次反转 代码 public class Solution {public String LeftRotateString(String str,int n) {if(str.isEmpty() || str.length() 0)return ;int len str.length();int m n % len;char[] s str.toCharArray();reverse(s, 0, len - 1);reverse(s, 0, len - 1 - m);reverse(s, len - m, len - 1);return new String(s);}private void reverse(char[] s, int l ,int r){while(l r){char temp s[l];s[l] s[r];s[r] temp;l;r--;}}
}
7、滑动窗口的最大值
给定一个长度为 n 的数组 num 和滑动窗口的大小 size 找出所有滑动窗口里数值的最大值。 解析 单调队列维护窗口的最大值 代码 import java.util.*;
public class Solution {public ArrayListInteger maxInWindows(int [] num, int size) {ArrayListInteger res new ArrayList();DequeInteger deque new LinkedList();if(num null || size 0 || size num.length) return res;for(int i 0; i num.length; i){//单调队列while(!deque.isEmpty() num[i] num[deque.peekLast()]){deque.pollLast();}deque.offerLast(i);//维护窗口while(!deque.isEmpty() deque.peekFirst() (i - size 1)){deque.pollFirst();}if(i - size 1 0) res.add(num[deque.peekFirst()]);}return res;}
}
8、扑克牌顺子
现在有2副扑克牌从扑克牌中随机五张扑克牌我们需要来判断一下是不是顺子。 有如下规则
A为1J为11Q为12K为13A不能视为14大、小王为 00可以看作任意牌如果给出的五张牌能组成顺子即这五张牌是连续的就输出true否则就输出false。 4.数据保证每组5个数字每组最多含有4个零数组的数取值为 [0, 13] 解析 创建一个哈希表查找重复遍历数组的同时遇到非零牌重复直接不行若没有重复则加入到哈希表中等待后续的查找。同时在遍历过程需要记录数组最大值与最小值最后检查最大值与最小值的差是否大于4小于4的话在没有非零牌重复的情况下最大值与最小值中间的牌加上0牌就可以填满这手顺子 代码 import java.util.*;
public class Solution {public boolean IsContinuous(int [] numbers) {HashMapInteger, Integer map new HashMap();int max -1;int min 14;for(int i 0; i numbers.length; i){if(numbers[i] 0) continue;if(map.containsKey(numbers[i])) return false;map.put(numbers[i], i);if(numbers[i] max) max numbers[i];if(numbers[i] min) min numbers[i];}System.out.println(max);System.out.println(min);if(max - min 4) return false;return true;}
}
9、孩子们的游戏(圆圈中最后剩下的数)
每年六一儿童节牛客都会准备一些小礼物和小游戏去看望孤儿院的孩子们。其中有个游戏是这样的首先让 n 个小朋友们围成一个大圈小朋友们的编号是0~n-1。然后随机指定一个数 m 让编号为0的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌然后可以在礼品箱中任意的挑选礼物并且不再回到圈中从他的下一个小朋友开始继续0… m-1报数…这样下去…直到剩下最后一个小朋友可以不用表演并且拿到牛客礼品请你试着想下哪个小朋友会得到这份礼品呢 解析 利用约瑟夫问题的递推公式 f(n,m) (f(n-1,m) m)%n) 公式递推 令f(n,m)表示最后一个人的下标。
假设有n个人报数m 从0 开始报数易知出圈的人下标为 m-1。m-1 出圈后我们对剩余人重新编号 即 第m个人下标为0第m1 下标为1 …以此编号。 那么重新编号之后那么最后一个人的下标为f(n-1,m) 问题1 在重新编号之后的f(n-1,m) 与 重新编号之前的f(n,m)有什么关系 重新编号之前 m, m1,m2,… 重新编号之后 0 1 2… 可知 (新编号m)%n 旧编号f(n,m) (f(n-1,m)m) %n; 代码 public class Solution {public int LastRemaining_Solution(int n, int m) {if(n 0 || m 0) return -1;return dfs(n, m);}private int dfs(int n, int m){if(n 1) return 0;int x dfs(n - 1, m);return (x m) % n;}
}
10、买卖股票的最好时机(一)
假设你有一个数组prices长度为n其中prices[i]是股票在第i天的价格请根据这个价格数组返回买卖股票能获得的最大收益 1.你可以买入一次股票和卖出一次股票并非每天都可以买入或卖出一次总共只能买入和卖出一次且买入必须在卖出的前面的某一天 2.如果不能获取到任何利润请返回0 3.假设买入卖出均无手续费 解析 贪心算法 代码 public class Solution {public int maxProfit (int[] prices) {int res 0, min prices[0];for(int i 1; i prices.length; i){if(prices[i] min){min prices[i];}res Math.max(res, prices[i] - min);}return res;}
}
