新的一天，刷题继续！今天小目标：五道题。shiro权限框架的一篇笔记写完。有额外时间就再写个定时器的笔记。好的，就这样！
寻找峰值
题目：峰值元素是指其值大于左右相邻值的元素。给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。你可以假设 nums[-1] = nums[n] = -∞。
示例 1:
输入: nums = [1,2,3,1]
输出: 2
解释: 3 是峰值元素，你的函数应该返回其索引 2。
示例 2:
输入: nums = [1,2,1,3,5,6,4]
输出: 1 或 5
解释: 你的函数可以返回索引 1，其峰值元素为 2；
或者返回索引 5， 其峰值元素为 6。
说明:
你的解法应该是 O(logN) 时间复杂度的。
思路：这个题感觉才是正确的打开方式，这个进阶要求是主要的，不然这个题就是送分题，昨天也是有一个旋转数组找最小值的，就差了这么一句话。好了，闲话不说，logN的时间复杂度，二分法是最容易想到的一个了，我去实现下看看。
好了，面向测试案例编程，我直接贴代码：
class Solution {
public int findPeakElement(int[] nums) {
if(nums.length == 1) return 0;
if(nums[0]>nums[1]) return 0;
if(nums[nums.length-1]>nums[nums.length-2]) return nums.length-1;
return dfs(nums,0,nums.length-1);
}
public int dfs(int[] nums,int start,int end){
if(start+1<end){
int mid = (end-start)/2+start;
if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1])return mid;
return Math.max(dfs(nums,start,mid),dfs(nums,mid,end));
}else{
return 0;
}
}
}
先判断边值，边值不行再往里判断，虽然我现在也不确定这个二分法是不是有用，是不是logN了。。。反正这个代码执行是0ms，超过百分百。我去看下别人的代码吧。
看到了一个更好的思路，差不多想法，都是二分，但是思路就是优秀，我先贴代码：
class Solution {
public int findPeakElement(int[] nums) {
if(nums.length == 1) return 0;
if(nums[0]>nums[1]) return 0;
if(nums[nums.length-1]>nums[nums.length-2]) return nums.length-1;
return dfs(nums,0,nums.length-1);
}
public int dfs(int[] nums,int start,int end){
if(start+1<end){
int mid = (end-start)/2+start;
if(nums[mid]>nums[mid-1] && nums[mid]>nums[mid+1])return mid;
//后面一定有峰值。
if(nums[mid]<nums[mid+1]) return dfs(nums,mid,end);
//前面有峰值
if(nums[mid]<nums[mid-1]) return dfs(nums,start,mid);
}
return -1;
}
}
一开始我没太明白怎么判断前后一定 有峰值的，后来仔细想了想才明白。其实画个图就能理解了。
好了，这道题比较简单，所以就这样了，下一题了。
比较版本号
题目：比较两个版本号 version1 和 version2。如果 version1 > version2 返回 1，如果 version1 < version2 返回 -1， 除此之外返回 0。你可以假设版本字符串非空，并且只包含数字和 . 字符。
. 字符不代表小数点，而是用于分隔数字序列。例如，2.5 不是“两个半”，也不是“差一半到三”，而是第二版中的第五个小版本。你可以假设版本号的每一级的默认修订版号为 0。例如，版本号 3.4 的第一级（大版本）和第二级（小版本）修订号分别为 3 和 4。其第三级和第四级修订号均为 0。
示例 1:
输入: version1 = "0.1", version2 = "1.1"
输出: -1
示例 2:
输入: version1 = "1.0.1", version2 = "1"
输出: 1
示例 3:
输入: version1 = "7.5.2.4", version2 = "7.5.3"
输出: -1
示例 4：
输入：version1 = "1.01", version2 = "1.001"
输出：0
解释：忽略前导零，“01” 和 “001” 表示相同的数字 “1”。
示例 5：
输入：version1 = "1.0", version2 = "1.0.0"
输出：0
解释：version1 没有第三级修订号，这意味着它的第三级修订号默认为 “0”。
提示：
版本字符串由以点 （.） 分隔的数字字符串组成。这个数字字符串可能有前导零。
版本字符串不以点开始或结束，并且其中不会有两个连续的点。
思路：我差点笑出了声，我真的发现最近这几道题都简单的离谱，，，差点以为我刷回简单的了呢。这道题的思路就是从前往后逐个比较，然后没有任何额外要求，比如空间，时间复杂度，有点奇怪啊。偷懒点的做法通过点分割数组，然后从第一个开始逐个比较。稍微好一点的拆成char数组，然后比较，至于前导0.应该就是多加判断的事，我去写代码了
回来了，标准的面向测试案例编程，性能超过百分之九十四。我直接贴代码：
class Solution {
public int compareVersion(String version1, String version2) {
char[] c1 = version1.toCharArray();
char[] c2 = version2.toCharArray();
int sum1 = 0;
int sum2 = 0;
int l1 = 0;
int l2 = 0;
while(l1<c1.length && l2<c2.length){
while(l1<c1.length && c1[l1]!='.'){
sum1 = sum1*10 + (c1[l1]-'0');
l1++;
}
while(l2<c2.length && c2[l2]!='.'){
sum2 = sum2*10 + (c2[l2]-'0');
l2++;
}
if(sum2!=sum1) return sum1>sum2?1:-1;
sum1 = 0;
sum2 = 0;
if(l1<c1.length) l1++;
if(l2<c2.length) l2++;
}
if(l1 == c1.length && l2 == c2.length){
return 0;
}else if(l1 < c1.length){
for(int i = l1;i<c1.length;i++){
if(c1[i] != '0' && c1[i] != '.') return 1;
}
return 0;
}else{
for(int i = l2;i<c2.length;i++){
if(c2[i] != '0' && c2[i] != '.') return -1;
}
return 0;
}
}
}
这个题好麻烦啊，我后悔了，应该直接用字符串分割的方式，我去用那种方式写一遍。
class Solution {
public int compareVersion(String version1, String version2) {
String[] c1 = version1.split("\\.");
String[] c2 = version2.split("\\.");
for(int i = 0;i<c1.length;i++){
if(i<c2.length){
if(Integer.valueOf(c1[i])==Integer.valueOf(c2[i])) continue;
if(Integer.valueOf(c1[i])>Integer.valueOf(c2[i])){
return 1;
}else{
return -1;
}
}else{
if(Integer.valueOf(c1[i])>0) return 1;
}
}
if(c2.length>c1.length){
for(int i = c1.length;i<c2.length;i++){
if(Integer.valueOf(c2[i])>0) return -1;
}
}
return 0;
}
}
第二种写法， 代码简洁，性能是一样的。这道题因为性能比较好了我就不看题解了，直接下一题了。
分数到小数
题目：给定两个整数，分别表示分数的分子 numerator 和分母 denominator，以字符串形式返回小数。如果小数部分为循环小数，则将循环的部分括在括号内。
示例 1:
输入: numerator = 1, denominator = 2
输出: "0.5"
示例 2:
输入: numerator = 2, denominator = 1
输出: "2"
示例 3:
输入: numerator = 2, denominator = 3
输出: "0.(6)"
思路：这个题，难点暂时不知道，可能是循环小数括号？我先写代码试试吧，没有太好的思路，就是硬算被？
我直接贴代码吧，写的有点闹心：
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if(numerator==0) return "0";
if(denominator==1) return numerator+"";
//转成long是因为溢出问题，-最大值除-1.结果溢出,倍数
long b = (long)numerator/(long)denominator;
StringBuffer sb = new StringBuffer();
if(numerator>0 && denominator<0) sb.append("-");
sb.append(b+"");
long x = numerator%denominator;//余数
if(x!=0){//不是整除
sb.append(".");
StringBuffer sb2 = new StringBuffer();
Map<Long,Integer> map = new HashMap<Long,Integer>();
while(x != 0){
x *= 10;
if(map.containsKey(x)){
sb2.append(")");
sb2.insert(map.get(x),"(");
break;
}else{
map.put(x,sb2.length());
sb2.append(Math.abs(x/denominator));
}
x = x%denominator;
}
sb.append(sb2);
}
return sb.toString();
}
}
居然写烦躁了，这个题不难，但是很墨迹，而且很弱智。测试案例更是奇葩，居然还特么溢出了，简直日狗了。这个题重点就是找出循环，然后一开始我甚至想用链表的，但是没写明白。改用map了，因为除数已经确定，所以当被除数x重复说明进入循环了，然后第一的出现的位置填左括号，当前位置添加有括号，跳出循环。
反正就这样吧，我这个代码性能贼差，我去看看排行第一的代码，差不多就行了。
class Solution {
public String fractionToDecimal(int numerator, int denominator) {
if (numerator == 0) {
return "0";
}
StringBuilder fraction = new StringBuilder();
// If either one is negative (not both)
if (numerator < 0 ^ denominator < 0) {
fraction.append("-");
}
// Convert to Long or else abs(-2147483648) overflows
long dividend = Math.abs(Long.valueOf(numerator));
long divisor = Math.abs(Long.valueOf(denominator));
fraction.append(String.valueOf(dividend / divisor));
long remainder = dividend % divisor;
if (remainder == 0) {
return fraction.toString();
}
fraction.append(".");
Map<Long, Integer> map = new HashMap<>();
while (remainder != 0) {
if (map.containsKey(remainder)) {
fraction.insert(map.get(remainder), "(");
fraction.append(")");
break;
}
map.put(remainder, fraction.length());
remainder *= 10;
fraction.append(String.valueOf(remainder / divisor));
remainder %= divisor;
}
return fraction.toString();
}
}
这是性能排行第一的代码，思路差不多，细节处理有区别，然后过了，我继续往下做了。
二叉搜索树迭代器
题目：实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。调用 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
提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。
思路：首先，我看了下这个迭代是中序迭代（因为是二叉搜索树，从小到大肯定是中序）。然后主要难度应该是时间复杂度O（1），也就是常量级别的，还有O(h)内存。首先这个O(h)内存就决定了不能直接遍历整个树来实现这两个方法。其次，因为只能遍历一部分，我觉得应该是先遍历左节点，因为首先第一个next肯定是要获取最左边的节点，保证时间复杂度是常量的情况下一定是先找到这个节点的，有了个模糊的想法，我去实现下。
这个题挺有意思，我也错了几次，但是大概思路是对的，先入后出用栈保存效果好，其实别的数据结构也是可以实现的。我直接贴代码了：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class BSTIterator {
Stack<TreeNode> stack ;
public BSTIterator(TreeNode root) {
//从头遍历，应该是最左边的最后遍历到。适合先入后出
stack = new Stack<TreeNode>();
while(root!= null){
stack.push(root);
root = root.left;
}
//初始化保证栈中最上面的元素的最小值
}
/** @return the next smallest number */
public int next() {
TreeNode n = stack.pop();
int res = n.val;
//这个n的左节点要么没有，要么已经用过了， 只要判断右节点就行
if(n.right!=null){
n = n.right;
while(n != null){
stack.push(n);
n = n.left;
}
}
return res;
}
/** @return whether we have a next smallest number */
public boolean hasNext() {
return !stack.isEmpty();
}
}
/**
* Your BSTIterator object will be instantiated and called as such:
* BSTIterator obj = new BSTIterator(root);
* int param_1 = obj.next();
* boolean param_2 = obj.hasNext();
*/
之前在next中有点错误，一开始我是想着用if，如果有左节点添加进去，后来提交报错我检查了好几遍因为树又不好调试，怎么也找不到问题。最后去看了题解，才发现这个问题。因为树高有限，一层存一个节点空间复杂度满足O（h）。
我这个性能只超过百分之七十多，我去看看性能排行第一的代码。
额，他用的全遍历，O（n）空间复杂度，，没啥好看的了。
这个题就这样吧。最后一道题。
接下来几道题是sql题，本来我打算自己写写就好了，但是看到一个不错的题目，所以分享下。
分数排名
这个题其实做法很多，反正我是不会。因为我是sql渣，工作中只学会了crud。稍微难点的就是靠着百度一点点尝试了，哈哈，不过基本的连表查询还是知道一些的。然后这个题我是直接看的题解，有的写得复杂有的写得简单，我把我看了觉得很容易懂的分享下：
SELECT a.score as Score,count(DISTINCT b.score) as Rank
from scores a join scores b where b.score>=a.score
group by a.id
order by a.score Desc
这个几乎是最简洁的做法了，关联条件大于等于，然后distinct b.score使得从1开始排名。group by a.id使得每一个同学都有排名，最后的升序排列不用说了。我不是说这个sql性能会多好，但是真的很容易理解，顺便贴上我看了就眼花的sql：
-- select Scores.Score ,
-- if(@agerank=Scores.Score ,@curRank, @curRank := @curRank + 1) as Rank,
-- @agerank := Scores.Score
-- from Scores , (select @curRank :=0,@agerank = NULL) r
-- order by Score desc;
SELECT Score, Rank FROM
(SELECT Score,
@curRank := IF(@prevRank = Score, @curRank+0,@curRank:=@curRank+1) AS Rank,
@prevRank := Score
FROM Scores, (
SELECT @curRank :=0, @prevRank := NULL
) r
ORDER BY Score DESC) s
说真的，我都开始怀疑我平时用的是不是假的mysql数据库！！！看不太懂我都，这个@是什么？
哎，反正我第一次贴的那个方法我是记住了，也算是学到了，这个就这样了。
最大数
题目：给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
示例 1:
输入: [10,2]
输出: 210
示例 2:
输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
思路：这个题比较简单啊，我目前的想法是从写排序规则，然后排序，排序规则是从第一个数开始比较，大的就大，如果第一个数一样比较第二个。如果是数位少的默认按照当前首位计算。说起来有点清楚，我去写一下吧。
很好，学到一点，基本类型不能重写compare。。。拉倒吧，我自己排序吧。
这个题做出来了，我之前思路错了，没必要一个数一个数比较。直接转成字符串相加，a+b 和b+a比较就行了。我先贴代码：
class Solution {
public String largestNumber(int[] nums) {
for(int i = 0;i<nums.length-1;i++){
for(int j = i;j<nums.length;j++){
if(!compare(nums[i],nums[j])){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
}
StringBuffer sb = new StringBuffer();
for(int i : nums){
sb.append(String.valueOf(i));
}
if(sb.charAt(0)=='0') return "0";
return sb.toString();
}
//比较两个数大小，第一个大true，第二个大false
public boolean compare(int a, int b){
String sa = String.valueOf(a);
String sb = String.valueOf(b);
String suma = sa+sb;
String sumb = sb+sa;
for(int i = 0;i<suma.length();i++){
if(suma.charAt(i)>sumb.charAt(i)) return true;
if(suma.charAt(i)<sumb.charAt(i)) return false;
}
return true;
}
}
至于这个代码的性能，我觉得是浪费在冒泡排序上了啊，我去优化一下。
改成快排变成7ms了。
class Solution {
public String largestNumber(int[] nums) {
qSort(nums,0,nums.length-1);
StringBuffer sb = new StringBuffer();
for(int i : nums){
sb.append(String.valueOf(i));
}
if(sb.charAt(0)=='0') return "0";
return sb.toString();
}
public void qSort(int[] nums,int start,int end){//快排
if(start>=end) return;
int l = start;
int r = end;
int mid = nums[(start+end)/2];
while(l<=r){
while(l<end && compare(nums[l],mid)) l++;
while(r>start && compare(mid,nums[r])) r--;
if(l<=r){
int t = nums[l];
nums[l] = nums[r];
nums[r] = t;
l++;
r--;
}
}
if(start<r) qSort(nums,start,r);
if(end>l) qSort(nums,l,end);
}
//比较两个数大小，第一个大true，第二个大false
public boolean compare(int a, int b){
String sa = String.valueOf(a);
String sb = String.valueOf(b);
String suma = sa+sb;
String sumb = sb+sa;
for(int i = 0;i<suma.length();i++){
if(suma.charAt(i)>sumb.charAt(i)) return true;
if(suma.charAt(i)<sumb.charAt(i)) return false;
}
return false;
}
}
刚刚看了下性能好的代码，是直接把数字数组转化成String数组。其实这个确实是好办法，不然像我这样要来回来去转换，一个单词转换好多次。。
附上大佬的代码：
class Solution {
public String largestNumber(int[] nums) {
String[] numstr = new String[nums.length];
for(int i=0;i<nums.length;i++){
numstr[i] = String.valueOf(nums[i]);
}
quickSort(numstr,0,nums.length-1);
// System.out.println(Arrays.toString(numstr));
StringBuffer sb = new StringBuffer();
if(numstr[0].charAt(0)=='0'){
return "0";
}
for(String num:numstr){
sb.append(num);
}
return sb.toString();
}
int compare(String a,String b){
int l1 = a.length();
int l2 = b.length();
int l = l1+l2;
int i=0;
for(;i<l;i++){
char ac = a.charAt(i%l1);
char bc = b.charAt(i%l2);
if(ac==bc){
continue;
}
return ac-bc;
}
return 0;
// System.out.println("a:"+a+",b:"+b+",cp:"+cp);
// return cp;
}
void quickSort(String[] nums,int start,int end){
if(start>=end){
return;
}
int index = getIndex(nums,start,end);
quickSort(nums,start,index-1);
quickSort(nums,index+1,end);
}
int getIndex(String[]nums,int low,int high){
String tmp = nums[low];
while(low<high){
while(low<high&&compare(nums[high],tmp)<=0){
high--;
}
nums[low] = nums[high];
while(low<high&&compare(nums[low],tmp)>=0){
low++;
}
nums[high] = nums[low];
}
nums[low] = tmp;
return low;
}
}
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！~
