欢迎来到我的小小世界

Change is a million times less painful than regret

0%

发表于 分类于 ，
本文字数： 1.9k 阅读时长 ≈ 2 分钟

题目描述

传送门

题解

我首先想到的是判断否false而不是判断是true，毕竟有这么多条件满足才能判断true，但是只要有一个条件不满足就可以判断false，最后代码的效率也还可以：

首先定义了四个flag，对应四种字符
是否有数字：hasNum
是否有e：hasE
是否有正负符号：hasSign
是否有点：hasDot
其余还定义了字符串长度n以及字符串索引index
先处理一下开头的空格，index相应的后移
然后进入循环，遍历字符串
如果当前字符c是数字：将hasNum置为true，index往后移动一直到非数字或遍历到末尾位置；如果已遍历到末尾(index == n)，结束循环
如果当前字符c是’e’或’E’：如果e已经出现或者当前e之前没有出现过数字，返回fasle；否则令hasE = true，并且将其他3个flag全部置为false，因为要开始遍历e后面的新数字了
如果当前字符c是+或-：如果已经出现过+或-或者已经出现过数字或者已经出现过’.’，返回flase；否则令hasSign = true
如果当前字符c是’.’：如果已经出现过’.’或者已经出现过’e’或’E’，返回false；否则令hasDot = true
如果当前字符c是’ ‘：结束循环，因为可能是末尾的空格了，但也有可能是字符串中间的空格，在循环外继续处理
如果当前字符c是除了上面5种情况以外的其他字符，直接返回false处理空格，index相应的后移。
如果当前索引index与字符串长度相等，说明遍历到了末尾，但是还要满足hasNum为true才可以最终返回true，因为如果字符串里全是符号没有数字的话是不行的，而且e后面没有数字也是不行的，但是没有符号是可以的，所以4个flag里只要判断一下hasNum就行；所以最后返回的是hasNum && index == n
如果字符串中间有空格，按以上思路是无法遍历到末尾的，index不会与n相等，返回的就是false

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public boolean isNumber(String s) {
        int n = s.length();
        int index = 0;
        boolean hasNum = false, hasE = false;
        boolean hasSign = false, hasDot = false;
        while(index < n && s.charAt(index) == ' ')
            index++;
        while(index < n){
            while(index < n && s.charAt(index) >= '0' && s.charAt(index) <= '9'){
                index++;
                hasNum = true;
            }
            if(index == n){
                break;
            }
            char c = s.charAt(index);
            if(c == 'e' || c == 'E'){
                if(hasE || !hasNum){
                    return false;
                }
                hasE = true;
                hasNum = false; hasSign = false; hasDot = false;
            }else if(c == '+' || c == '-'){
                if(hasSign || hasNum || hasDot){
                    return false;
                }
                hasSign = true;
            }else if(c == '.'){
                if(hasDot || hasE){
                    return false;
                }
                hasDot = true;
            }else if(c == ' '){
                break;
            }else{
                return false;
            }
            index++;
        }
        while(index < n && s.charAt(index) == ' ')
            index++;
        return hasNum && index == n;
    }
}

阅读全文 »

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

题目描述

传送门
https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/

解题思路

这里还是不建议使用stack，使用LinkedList代替，由于Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。 但是我的意思不是像100%代码那样直接使用一个LinkedList当做队列，那确实是快，但是不符题意。加上LinkedList本身作为双链表，可以使用addFirst()、addLast()等操作在不同位置上进行添加和删除操作。这里使用两个栈，一个用来接受的，在后面去除元素的时候，将第一个栈的元素压入第二个中，然后再从顶端进行返回。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class CQueue {
    LinkedList<Integer> stack1;
     LinkedList<Integer> stack2;
    public CQueue() {
        stack1=new LinkedList<Integer>();
        stack2=new LinkedList<Integer>();
    }
    
    public void appendTail(int value) {
        stack1.addLast(value);
    }
    
    public int deleteHead() {
        if(stack2.isEmpty()){
            if(stack1.isEmpty()){
                return -1;
            }
            while(!stack1.isEmpty()){
                stack2.addLast(stack1.removeLast());
            }
            return stack2.removeLast();//注意这里要添加返回值，if-else中很容易出现这种漏掉返回值的问题
        }
        else 
             return stack2.removeLast();
    }

}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */
阅读全文 »

发表于
本文字数： 706 阅读时长 ≈ 1 分钟

题目描述

传送门
https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

解题思路

数据结构，使用LinkedList模拟栈操作，使用addFirst(),removeLast()。比较简单，尽量不要使用stack，LinkedList具有线程安全性，推荐使用。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack=new LinkedList<Integer>();
        int accout=0;
        while(head!=null){
            stack.addLast(head.val);
            head=head.next;
            accout++;
        }
        //stack.removeLast();
        int[] res=new int[accout];
        int i=0;
        while(accout>0) {
            res[i]=stack.removeLast();
            i++;
            accout--;
        }
        return res;
    }
}


阅读全文 »

发表于 分类于 ，
本文字数： 520 阅读时长 ≈ 1 分钟

题目

！传送门题目太长就不描述了

解题思路

双指针（最好理解），对向双指针，取一个数组做完全遍历，关键步骤的思路在注释中。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int breakfastNumber(int[] staple, int[] drinks, int x) {
        int ps = 0, pd = drinks.length - 1, count = 0;
        Arrays.sort(staple);
        Arrays.sort(drinks);
        while (ps < staple.length && pd >= 0) {
             if (staple[ps] + drinks[pd] <= x) {
                count += pd + 1;//这里满足条件之后，此处之前的左右元素都满足条件，因为是有序的。
                count = count % 1000000007;
                ps++;//staple左侧指针向前推进一个，直至全部遍历完staple数组。
            } else {//如果超出规定则drink数组右侧指针向前推进一个。
                pd--;
            }
        }
        return count;
    }
}

阅读全文 »

发表于 分类于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

描述

符合下列属性的数组 arr 称为 山脉数组 ：
arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给你由整数组成的山脉数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i 。

示例 1：
输入：arr = [0,1,0]
输出：1
示例 2：
输入：arr = [0,2,1,0]
输出：1
**示例 3： **
输入：arr = [0,10,5,2]
输出：1
示例 4：
输入：arr = [3,4,5,1]
输出：2
**示例 5： **
输入：arr = [24,69,100,99,79,78,67,36,26,19]
输出：2

解题思路

常规的二分，思路还是比较简单的，正常设置left、mid、right，在中间的时候判断mid两边的元素：1.当nums[mid]<nums[mid-1]时，证明还没到峰值，right移动到mid左侧；2.当nums[mid]>nums[mid-1]时再判断是否nums[mid]>nums[mid+1]，若成立证明找到峰值，直接返回mid，若不成立则证明已经过了峰值，此时将reft移动到mid右边。这里要注意越界的问题，在计算完mid后判断一下是否已经到达最低点（0），若达到直接推出循环，同时返回right（因为在你计算mid后，mid已经移动到right左边，此时mid为0已经不能比较了，所以之前保留的right一定就是峰值）。这是常规做法，后面有更高效率的写法我再研究研究。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int peakIndexInMountainArray(int[] arr) {
	int left,mid,right;
    left=0;
     mid=10;
    right=arr.length-1;
    while(right>=left){
        mid=left+(right-left)/2;
        if(mid==0) return right;
        if(arr[mid]<arr[mid-1]){
            right=mid-1;
            }
        else if(arr[mid]>arr[mid-1]){
            if(arr[mid]>arr[mid+1])
                return mid;
            else left=mid+1;
            }
        }
        return right;
    }
}
阅读全文 »

发表于 分类于
本文字数： 49 阅读时长 ≈ 1 分钟

  人总是会成为成为自己讨厌的人，并乐于成为自己讨厌的人，何为讨厌？嫉妒罢了。

阅读全文 »

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

描述

(传送门)[https://leetcode-cn.com/problems/count-negative-numbers-in-a-sorted-matrix]
给你一个 m * n 的矩阵 grid，矩阵中的元素无论是按行还是按列，都以非递增顺序排列。  
请你统计并返回 grid 中 负数 的数目。

示例 1：
输入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]] 输出：8 解释：矩阵中共有 8 个负数。
示例 2：
输入：grid = [[3,2],[1,0]] 输出：0
示例 3：
输入：grid = [[1,-1],[-1,-1]] 输出：3
示例 4：
输入：grid = [[-1]] 输出：1
提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
-100 <= grid[i][j] <= 100

解题思路

没啥好说的二分查找，对每一个二维数组中的每一行进行一个二分，一个for循环就够了，用来遍历每一行。这里注意越界的问题，因为是数组，在while中要加入一个边界的判断，内部两个if即可，大于等于0在一起。主要是最后的sum，注意减去的是left的值，因为left在最后一轮的判断中会移动到最先出现的那个负数那里，然而right判断是负数后会继续向左移动（因为此时不知道当前负数是不是最早的负数，同样left判断的是非零数，其无法识别是不是最后一个非零数，当判断是非零数向后移动一个且left大于right时此时找到了第一个负数），因此使用grid[i].length-left。全部循环完毕后得到最后的sum值。二分就是细节怪~~~~

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int countNegatives(int[][] grid) {
        		int sum=0;
        for (int i = 0; i < grid.length; i++) {

        	int left,mid,right;
        	left=0;
        	right=grid[i].length-1;
			mid=0;
			while(right>=left&&left<=grid[i].length&&right>=0) {
				mid=left+(right-left)/2;
				if(grid[i][mid]>=0) {
					left=mid+1;
				}
				else {
					right=mid-1;
				}
			}
			sum+=grid[i].length-left;
		}
        return sum;
    }
}
阅读全文 »

发表于 分类于
本文字数： 709 阅读时长 ≈ 1 分钟

题目描述

传送门
你总共有 n 枚硬币，你需要将它们摆成一个阶梯形状，第 k 行就必须正好有 k 枚硬币。
给定一个数字 n，找出可形成完整阶梯行的总行数。
n 是一个非负整数，并且在32位有符号整型的范围内。

示例 1:

1
2
3
4
5
6
7
8
n = 5

硬币可排列成以下几行:
¤  
¤ ¤  
¤ ¤  

因为第三行不完整，所以返回2.

示例 2:

1
2
3
4
5
6
7
8
9
n = 8

硬币可排列成以下几行:
¤
¤ ¤
¤ ¤ ¤
¤ ¤

因为第四行不完整，所以返回3.

解题思路

两个坑吧算是：1.注意题目给定的范围，因为涉及到前n项求和，所以在极限测试的时候会超出限制，所以采用long的形式进行定义，后期再进行强转返回。2.当right>=left的条件不满足的时候，退出while循环后返回的是right，而不是mid，因为由大向小缩进，所以right代表的是最后的结果。这两点注意之后就没啥了，常规的二分法。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {

    public int arrangeCoins(int n) {
        long left,mid,right,sum;
        left=1;
        right=n;
        mid=0;
        while(right>=left){
            mid=left+(right-left)/2;
             sum=(1+mid)*mid/2;
            if(sum>n){
                right=mid-1;
            }
            else if(sum==n){
                return (int)mid;
            }
            else {
                left=mid+1;
            }
        }
        return (int)right;
        
    }
}
阅读全文 »

发表于
本文字数： 1k 阅读时长 ≈ 1 分钟

题目描述

猜数字游戏的规则如下：

每轮游戏，我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。
如果你猜错了，我会告诉你，你猜测的数字比我选出的数字是大了还是小了。
你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果，返回值一共有 3 种可能的情况（-1，1 或 0）：

  • -1：我选出的数字比你猜的数字小 pick < num
  • 1：我选出的数字比你猜的数字大 pick > num
  • 0：我选出的数字和你猜的数字一样。恭喜！你猜对了！pick == num
    返回我选出的数字。

示例 1：
输入：n = 10, pick = 6 输出：6
示例 2 ：
输入：n = 1, pick = 1 输出：1
示例 3：
输入：n = 2, pick = 1 输出：1
示例 4：
输入：n = 2, pick = 2 输出：2

解题思路

  传统想法，初始left为0，mid值为pick的值，right为2倍的pick值；pick小于规定值left移到mid，重新计算mid值，反之一样的操作，最后返回mid值，while循环不用啥判断条件，直接while(true)就好，体内有返回语句，注意，这种情况下，while外就不需要再return了，否则会报UNreachable错误，因为压根就执行不到那一步。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left,mid,right;
        left=0;
        mid=n;
        right=2*n;
        while(true){
        if(guess(mid)==1){
            left=mid;
            mid=left+(right-left)/2;
        }
        else if(guess(mid)==-1){
            right=mid;
            mid=left+(right-left)/2;
        }
        else return mid;
        }
        //return mid;
    }   
}
阅读全文 »

发表于 分类于
本文字数： 1.1k 阅读时长 ≈ 1 分钟

问题描述

分析加代码1

  第一种想法就是传统的二分算法，解题的依据是一个数的平方根一般不超过其1/2即√x<=x/2，但要注意特殊的情况1和0，这种情况单独讨论即可。这里注意mid的求法，如果不加一的话在最后会卡住，其他的没有什么问题了，就是正常的二分，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int mySqrt(int x) {
        if(x==0)
        return 0;
        if(x==1)
        return 1;
        int left,right,mid;
        left=1;
        right=x/2;
        
        while(right>left){
            mid=left+(right-left+1)/2;
            if(mid>x/mid)
                right=mid-1;
            else 
                left=mid;
        }
        return left;
    }
}

上面的if判断中使用的是除法而不是乘法，是为了防止大整数溢出，除法可以有效避免这种情况。

分析加代码2

  这是大佬提供的题解，使用牛顿迭代法，不得不说虽然没有学过数分，但是好歹学过一点高数，这一刻被捻的稀碎啊，后面的就是借鉴大佬的分析思路。
  下面这种方法可以很有效地求出根号a的近似值：首先随便猜一个近似值x，然后不断令x等于x和a/x的平均数，迭代个六七次后x的值就已经相当精确了。例子如下：
例如，我想求根号2等于多少。假如我猜测的结果为4，虽然错的离谱，但你可以看到使用牛顿迭代法后这个值很快就趋近于根号2了：

( 4 + 2/ 4 ) / 2 = 2.25
( 2.25 + 2/ 2.25 ) / 2 = 1.56944..
( 1.56944..+ 2/1.56944..) / 2 = 1.42189..
( 1.42189..+ 2/1.42189..) / 2 = 1.41423..

牛顿迭代法
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int s;
    
 public int mySqrt(int x) {
     s=x;
     if(x==0) return 0;
    return ((int)(sqrts(x)));
  }
    
    public double sqrts(double x){
      double res = (x + s / x) / 2;
    if (res == x) {
      return x;
    } else {
      return sqrts(res);
    }
    } 
}
阅读全文 »