Gausst松鼠会

这个屌丝很懒，什么也没留下！

热门标签

Leetcode每日一题_10的9次方字典序排数

作者：Gausst松鼠会 | 2024-03-26 07:32:10

踩

10的9次方字典序排数

Leetcode每日一题

2021.9.10

1894. 找到需要补充粉笔的学生编号

一开始打算直接打暴力,就一直遍历,当到末尾的时候,就再返回到最前面.直到当前的粉笔数小于当前学生需要的粉笔数量.

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        int i = 0;
        while(true){
            for(;i < chalk.size();i++){
                if(chalk[i] > k) return i;
                k -= chalk[i];
            }
            // 返回到开头
            i = 0;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

但是这样有个样例过不了,看了一下数据,好家伙k最大到10的9次方.

再想了想，先遍历一遍数组，求一下一轮所消耗的粉笔数量，然后直接k去模用一轮的总数量，这样就能使下一次遍历一轮即可

class Solution {
public:
    int chalkReplacer(vector<int>& chalk, int k) {
        // 要开long long,
        long long sum = 0;
        for(int  i = 0;i < chalk.size();i++) sum += chalk[i];
        // 直接返回
        if(k % sum == 0) return 0;
        else k %= sum;
        for(int i = 0;i < chalk.size();i++){
            if(chalk[i] > k) return i;
            k -= chalk[i];
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2021.9.11（数位DP）

600. 不含连续1的非负整数

暴力

class Solution {
public:
    int findIntegers(int n) {
        int ans = 0;
        for(int i = 0;i <= n;i++){
            int temp = i;   
            bool flag = false,isans = true;
            while(temp){    
                int k = temp % 2;   
                if(k == 1){         
                    if(!flag) flag = true;
                    else {
                        isans = false;
                        break;
                    }
                }else flag = false;
                temp /= 2;
            }
            if(isans) ans++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

过不了，mark一下，学完数位DP再来

2021.9.12

678. 有效的括号字符串

一开始模拟,样例都能过,但是卡着一个点过不去,再思考一下,发现这样模拟不对

class Solution {
public:
    bool checkValidString(string s) {
        int cnt1 = 0,cnt2 = 0;
        if(s.size() == 0) return true;
        for(int i = 0;s[i];i++){
            if(s[i] == '(') cnt1++;
            else if(s[i] ==')'){
                if(cnt1 <= 0){
                    if(cnt2 < 0) return false;
                    else cnt2--;
                }else cnt1--;
            }else if(s[i] =='*'){
                cnt2++;
            }
        }
        printf("%d\n",cnt1);
        printf("%d\n",cnt2);
        if(cnt1 == 0 || cnt2 >= cnt1) return true;
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

使用双栈,栈内保存下标

其实第一次遍历和上面模拟思路是一样的,区别点在于

第二次遍历的时候,将*视为右括号,每个左括号必须在右括号之前

class Solution {
public:
    bool checkValidString(string s) {
        stack<int> s1,s2;
        for(int i = 0;s[i];i++){
            if(s[i] == '(') s1.push(i);
            else if(s[i] == ')'){
                if(!s1.empty()) s1.pop();
                else {
                    if(!s2.empty()) s2.pop();
                    else return false;
                }
            }else s2.push(i);
        }
        while(!s1.empty() && !s2.empty()){
            int idx1 = s1.top(),idx2 = s2.top();
            s1.pop(),s2.pop();
            if(idx1 > idx2) return false;
        }
        if(s1.empty()) return true;
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

贪心

维护最大值和最小值

当遇到左括号,最大值和最小值都加一
遇到右括号,最小值和最小值都减一
遇到星号,最大值加一,最小值减一

维护时应该

保证最小值非负
判断最大值是否为负,如果为负,则返回
最后判断最小值是否为0,为0则表示左右括号能匹配成功

class Solution {
public:
    bool checkValidString(string s) {
        int minn = 0,maxn = 0;
        for(int i = 0;s[i];i++){
            if(s[i] == '(') minn++,maxn++;
            else if(s[i] == ')'){
                maxn--;
                minn = max(0,minn-1);
                if(maxn < 0) return false;
            }else{
                maxn++;
                minn = max(0,minn-1);
            }
        }
        return minn == 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2021.9.13

447. 回旋镖的数量

距离使用平方，避免开方
使用哈希表查找
从m 个元素中选出 2 个不同元素的排列数

class Solution {
public:
    int numberOfBoomerangs(vector<vector<int>>& points) {
        if(points.size() <= 2) return 0;
        int ans = 0;
        for(int i = 0;i < points.size();i++){
            unordered_map<int,int> m;
            int x1 = points[i][0],y1 = points[i][1];
            for(int j = 0;j < points.size();j++){
                int x2 = points[j][0],y2 = points[j][1];
                if(i == j) continue;
                int dis = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
                m[dis]++;
            }
            for(auto dis:m) ans += (dis.second-1) * dis.second;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

2021.9.14

524. 通过删除字母匹配到字典里最长单词

先对字典排序，排序后字典序是由大到小
双指针，判断字典里面的字符串的指针能否走完，能走完就是s字符串的子串
如果长度长那就替换，因为越到后面字典序越小

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        string ans = "";
        sort(dictionary.rbegin(),dictionary.rend());
        for(int i = 0;i < dictionary.size();i++){
            string sub = dictionary[i];
            int k = 0;
            for(int j = 0;j < s.size();j++){
                while(k < sub.size() && sub[k] == s[j]) k++,j++;
            }
            if(k == sub.size() && sub.size() >= ans.size()) ans = sub;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2021.9.15

162. 寻找峰值

遍历，处理好边界即可

法一：遍历

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size() == 1) return 0;
        for(int i = 0;i < nums.size();i++){
            if(i == 0) {
                if(nums[0] > nums[1]) return 0;
            }
            else if(i == nums.size()-1) {
                if(nums[nums.size()-1] > nums[nums.size()-2]) return nums.size()-1;
            }
            else {
                if(nums[i] > nums[i-1] && nums[i] > nums[i+1]) return i;
            }
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

法二：二分

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int l = 0,r = nums.size()-1;
        while(l < r){
            int mid = (l+r) >> 1;
            if(nums[mid] > nums[mid+1]) r = mid;
            else l = mid + 1;
        }
        return l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

思考一下：

因为num[i] != num[i+1]，并且num[-1] = num[N] = 负无穷
这就代表着只要数组中存在一个元素比相邻元素大，那么沿着它一定可以找到一个峰值
根据上述结论，我们就可以使用二分查找找到峰值
查找时，左指针 l，右指针 r，以其保持左右顺序为循环条件
根据左右指针计算中间位置 m，并比较 m 与 m+1 的值，如果 m 较大，则左侧存在峰值，r = m，如果 m + 1 较大，则右侧存在峰值，l = m + 1
Base on ： https://leetcode-cn.com/problems/find-peak-element/solution/hua-jie-suan-fa-162-xun-zhao-feng-zhi-by-guanpengc/ 作者：guanpengchn

2021.9.17

36. 有效的数独

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        // 遍历每一行每一列
        for(int i = 0;i < 9;i++){
            int x[9],y[9];
            for(int i = 0;i < 9;i++) x[i] = 0,y[i] = 0;
            for(int j = 0;j < 9;j++){
                int idxx = board[i][j] - '0',idxy = board[j][i] - '0';
                if(idxx >=0 && idxx <= 9){
                    if(!x[idxx-1]) x[idxx-1] = 1;
                    else return false;
                }
                if(idxy >= 0 && idxy <= 9){
                    if(!y[idxy-1]) y[idxy-1] = 1;
                    else return false;
                }
            }
        }

        // 遍历九个方格
        int count  = 9;
        int countx=-3,county=0;
        while(count--){
            countx+=3;
            if(countx == 9) countx = 0,county+=3;
            int st[9];
            for(int i = 0;i < 9;i++) st[i] = 0;
            for(int i = 0+county;i < 3+county;i++){
                // 输出三行
                for(int j = 0+countx;j < 3+countx;j++){
                    int idx = (int)(board[i][j] - '0');
                    if(idx >= 1 && idx <= 9) {
                        if(!st[idx-1]) st[idx-1] = 1;
                        else return false;
                    }
                }
            }
        }
        return true;
    }
};
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

2021.9.19

650. 只有两个键的键盘

class Solution {
    // 判断是否为指数
    public boolean isPrime(int x){
        if(x <= 2) return false;
        for(int i = 2;i <= x/i;i++){
            if(x%i==0) return false;
        }
        return true;
    }

    public int minSteps(int n) {
        // dp[i],i这个数,最小的操作数
        int[] dp = new int[n+1];
        for(int i = 0;i <=n;i++){
            // 质数
            if(isPrime(i)) dp[i] = i;
            // 偶数
            else if(i%2 == 0) dp[i] = dp[i/2] + 2;
            // 奇数
            else {
                for(int j = i-1;j > 0;j--){
                    if(i % j == 0){
                        dp[i] = dp[j] + i/j;
                        break;
                    }
                }
            }
        }
        return dp[n];
    }
}
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

我觉得这个思路其实就相当DP了

2021.9.20

300. 最长递增子序列

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length,maxL = 0;
        int[] dp = new int[n];
        for(int i = 0;i < n;i++){
            dp[i] = 1;
            for(int j = 0;j < i;j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]) dp[i] = dp[j]+1;
                }
            }
            if(dp[i] > maxL) maxL = dp[i];
        }
        return maxL;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

DP分析：

dp数组以及下表含义：
- 以nums[i]结尾的元素的最长递增子序列的长度
dp的边界考虑
- 每次遍历之前dp[i]初始化为1，当作一个数字作为上升子序列
dp的状态转移方程
- dp[i] = max(dp[j]) + 1
- 因为dp[j]表示第i个元素之前的最长递增子序列的长度，那么直接将num[i]插入最后面还能构成递增子序列的话就能求出dp[i]
遍历顺序
- j在i之前，dp[i]需要dp[j]，从左往右
打印dp表

673. 最长递增子序列的个数

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length,maxL = 0,ans = 0;
        // 以nums[i]结尾的最长上升子序列的长度
        int[] dp = new int[n];
        // 以nums[i]结尾的最长上升子序列的个数
        int[] cnt = new int[n];
        // 遍历
        for(int i = 0;i < n;i++){
            dp[i] = 1;
            cnt[i] = 1;
            for(int j = 0;j < i;j++){
                // 可以直接加在dp[j]之后
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        // 能构成一个比之前长的递增子序列
                        dp[i] = dp[j]+1;
                        cnt[i] = cnt[j];
                        // 构成的上升子序列和之前的上升子序列一样长
                    }else if(dp[j] + 1 == dp[i]) cnt[i] += cnt[j];
                }
            }
            // 刷新最大长度
            if(dp[i] > maxL){
                maxL = dp[i];
                ans = cnt[i];
            }else if(dp[i] == maxL) ans += cnt[i];
        }
        return ans;
    }
}
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

DP分析的方法和上面一题一样，这里多了个cnt[]数组

cnt[i]表示以nums[i]结尾的最长上升子序列的个数

2021.9.21

58. 最后一个单词的长度

class Solution {
    public int lengthOfLastWord(String s) {
        int ans = 0;
        boolean flag = true;
        for(int i = s.length()-1;i >=0;i--){
            if(s.charAt(i) == ' ' && flag) continue;
            else {
                flag = false;
                if(s.charAt(i) == ' ') break;
                ans++;
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

从后面往前面遍历，从第一个不是空格的字母到第一个空格

2021.9.22

2021.9.23

326. 3的幂

class Solution {
    public boolean isPowerOfThree(int n) {
        long x = 1;
        while(x <= n){
            if(x == n) return true;
            x *= 3;
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CPNXY67D-1634459055741)(https://i.loli.net/2021/09/23/hFNZm4jPOUqs9MT.png)]

2021.9.26

371. 两整数之和

class Solution {
    public int getSum(int a, int b) {
        int count = 1;
        while(b != 0){
            // a & b 可以得出所有需要进位的位
            // << 1 将进位的位置移到需要进位的地方
            int carry = (a&b) << 1;
            // ^ 异或运算,无进位加法
            a = a ^ b;
            b = carry;
            
        }
        return a;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

https://leetcode-cn.com/problems/sum-of-two-integers/solution/liang-zheng-shu-zhi-he-by-leetcode-solut-c1s3/

2021.10.1

1436. 旅行终点站

双重遍历:如果cityB没有在cityA出现过

class Solution {
    public String destCity(List<List<String>> paths) {
        int n = paths.size();
        for(int i = 0;i < n;i ++ ){
            List<String> list1 = paths.get(i);
            String second = list1.get(1);
            boolean flag = true;
            for(int j = 0;j < n;j++){
                List<String> list2 = paths.get(j);
                String first = list2.get(0);
                if(first.equals(second)){
                    flag = false;
                    break;
                }
            }
            if(flag) return second;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

哈希表:

class Solution {
    public String destCity(List<List<String>> paths) {
        Set<String> hashSet = new HashSet<>();
        // 遍历cityA
        for(List<String> list : paths){
            String cityA = list.get(0);
            hashSet.add(cityA);
        }
        // 遍历cityB,如果cityB没有在cityA出现过,那就是终点
        for(List<String> list : paths){
            String cityB = list.get(1);
            if(!hashSet.contains(cityB)) return  cityB;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2021.10.2

405. 数字转换为十六进制数

进制转换-> 辗转相除法

class Solution {
    public String toHex(int _num) {
        if(_num == 0) return "0";
        Stack<Character> stack = new Stack<>();
        String str = "0123456789abcdef";
        long num = _num;
        if(num < 0) num = (long)(Math.pow(2, 32) + num);
        int size = 0;
        while(num > 0){
            long k = num % 16;
            stack.push(str.charAt((int)k));
            num /= 16;
            size++;
        }
        char[] ans = new char[size];
        int idx = 0;
        for(int i = 0;i < size;i++) ans[idx++] = stack.pop();
        return new String(ans);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

调用函数：

class Solution {
    public String toHex(int num) {
        return Integer.toHexString(num);
    }
}
1
2
3
4
5

2021.10.3

166. 分数到小数

class Solution {
    public String fractionToDecimal(int numerator, int denominator) {
        // 转成long，防止溢出
        long a = numerator,b = denominator;
        // 如果自身能被整除，直接返回
        if(a % b == 0) return String.valueOf(a / b);
        StringBuilder sb = new StringBuilder();
        // 如果有一个是负数，先追加负号
        if(a * b < 0) sb.append('-');
        // 都先变为正数
        a = Math.abs(a);b = Math.abs(b);
        // 计算小数点前的数,并将余数赋值给a
        sb.append(String.valueOf(a/b) + ".");
        a %= b;
        Map<Long,Integer> map = new HashMap<>();
        while(a != 0){
            // 记录当前的余数所在位置，并且继续模拟除法
            map.put(a,sb.length());
            // 后面加0
            a*=10;
            sb.append(a/b);
            // 余数
            a %= b;
            // 如果当前余数之前出现过，则将 [出现位置 到 当前位置] 的部分抠出来（循环小数部分）
            if(map.containsKey(a)){
                int u = map.get(a);
                return String.format("%s(%s)",sb.substring(0,u),sb.substring(u));
            }
        }
        // 有限小数
        return sb.toString();
    }
}
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

思路来源：https://leetcode-cn.com/problems/fraction-to-recurring-decimal/solution/gong-shui-san-xie-mo-ni-shu-shi-ji-suan-kq8c4/

2021.10.4

482. 密钥格式化

两个char数组

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        int n = s.length();
        char[] ch = new char[n];
        int len = 0;
        for(int i = 0;i < n;i++){
            if(s.charAt(i) != '-') ch[len++] = Character.toUpperCase(s.charAt(i));
        }
        int cout = 0;
        if(len%k == 0)cout = len/k-1;
        else  cout = len/k;
        if(len + cout == -1) cout = 0;
        char[] ans = new char[len+cout];
        int idx = len+cout-1,k2 = k;
        for(int i = len-1;i >= 0;i--){
            if(idx >= 0)ans[idx--] = ch[i];
            k2--;
            if(k2 == 0 && idx >= 0) {
                ans[idx--] = '-';
                k2 = k;
            }
        }
        return new String(ans);
    }
}
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

StringBuilder

class Solution {
    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        // 从后往前
        for(int i = s.length()-1,cnt = 0;i >=0 ;i--){
            if(s.charAt(i) == '-') continue;
            // 计数器
            if(cnt == k){
                sb.append('-');
                cnt = 0;
            }
            sb.append(s.charAt(i));
            cnt++;
        }
        return sb.reverse().toString().toUpperCase();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2021.10.5

284. 顶端迭代器

// Java Iterator interface reference:
// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

class PeekingIterator implements Iterator<Integer> {
    // 迭代器
    private Iterator<Integer> iterator;
    private Integer nextElement;
	public PeekingIterator(Iterator<Integer> iterator) {
	    // initialize any member here.
	    this.iterator = iterator;
        nextElement = iterator.next();
	}
	
    // Returns the next element in the iteration without advancing the iterator.
	public Integer peek() {
        return nextElement;
	}
	
	// hasNext() and next() should behave the same as in the Iterator interface.
	// Override them if needed.
	@Override
	public Integer next() {
	    Integer ret = nextElement;
        nextElement = iterator.hasNext() ? iterator.next() : null;
        return ret;
	}
	
	@Override
	public boolean hasNext() {
	    return nextElement != null;
	}
}
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

2021.10.6

414. 第三大的数

有序序列:

TreeSet里面就放最大的三个元素
每次都把当前元素加进来,有重复的TreeSet自动去重
当大于三个的时候,把最小的,就是第一个清除即可

class Solution {
    public int thirdMax(int[] nums) {
        TreeSet<Integer> treeSet = new TreeSet<>();
        for(int i = 0;i < nums.length;i++){
            treeSet.add(nums[i]);
            // 弹出最小的
            if(treeSet.size() > 3) treeSet.remove(treeSet.first());
        }
        return treeSet.size() == 3 ? treeSet.first():treeSet.last();
    }
}
1
2
3
4
5
6
7
8
9
10
11

三个变量

class Solution {
    public int thirdMax(int[] nums) {
        Integer a = null,b = null,c = null;
        for(Integer num : nums){
            // 最大的
            if(a == null || num > a){
                c = b;
                b = a;
                a = num;
                // 第二大的,要保证此时的num小于a,不能等于a
            }else if((b == null || num > b) && a >  num){
                c = b;
                b = num;
                // 保证b以及复制了,并且当前的null小于b
            }else if(b != null &&(c == null || num > c) && b > num){
                c = num;
            }
        }
        return c == null ? a : c;
    }
}
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 thirdMax(int[] nums) {
        // 排序
        Arrays.sort(nums);
        // 从大到小
        revers(nums);
        int differ = 1;
        // 最大的
        int ans = nums[0];
        for(int i = 1;i < nums.length;i++){
            if(nums[i] != nums[i-1]) differ++;
            if(differ == 3){
                ans = nums[i];
                break;
            }
        }
        return ans;

    }
    public void revers(int[] nums){
        int l = 0,r = nums.length-1;
        while(l < r){
            int temp = nums[l];
            nums[l] = nums[r];
            nums[r] = temp;
            l++;r--;
        }
    }
}
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

2021.10.7

434. 字符串中的单词数

class Solution {
    public int countSegments(String s) {
        int ans = 0;
        if(s.equals("")) return 0;
        for(int i = 0;i < s.length()-1;i++){
            if(s.charAt(i) != ' ' && s.charAt(i+1) == ' ') ans++;
        }
        if(s.charAt(s.length()-1 ) != ' ')return ans+1;
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2021.10.8

187. 重复的DNA序列

class Solution {
    public List<String> findRepeatedDnaSequences(String s) {
        int n = s.length();
        List<String> ans = new ArrayList<>();
        Map<String,Integer> hashMap = new HashMap<>();
        if(n < 10) return ans;
        for(int i = 0;i <= n - 10;i++){
            // 截取子串
            String sub = s.substring(i,i+10);
            hashMap.put(sub,hashMap.getOrDefault(sub,0)+1);
            if(hashMap.get(sub) == 2) ans.add(sub);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2021.10.10

441. 排列硬币

class Solution {
    public int arrangeCoins(int n) {
        int i = 1,count = 0;
        while(n > 0){
            if(n >= i) count++;
            n-=i;
            i++;
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2021.10.13

class Solution {
    public List<String> fizzBuzz(int n) {
        List<String> ans = new ArrayList<>();
        for(int i = 1;i <= n;i++){
            if(i % 3 == 0 && i % 5 == 0) ans.add("FizzBuzz");
            else if(i % 3 == 0) ans.add("Fizz");
            else if(i % 5 == 0) ans.add("Buzz");
            else ans.add(String.valueOf(i));
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

2021.10.14

剑指 Offer II 069. 山峰数组的顶部

遍历：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int ans = 0,max = arr[0];
        for(int i = 0;i < arr.length;i++){
            if(max < arr[i]) {
                ans = i;
                max = arr[i];
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

二分：

class Solution {
    public int peakIndexInMountainArray(int[] arr) {
        int l = 0,r = arr.length-1;
        while(l < r){
            int mid = (l+r)/2;
            if(arr[mid] > arr[mid+1]) r = mid;
            else l = mid+1;
        }
        return l;
    }
}
1
2
3
4
5
6
7
8
9
10
11

2021.10.17

230. 二叉搜索树中第K小的元素

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private List<Integer> arrayList = new ArrayList<>();
    public int kthSmallest(TreeNode root, int k) {
        visit(root);
        return arrayList.get(k-1);
    }
    // 中序遍历
    private void visit(TreeNode root){
        if(root == null) return;
        visit(root.left);
        arrayList.add(root.val);
        visit(root.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
25
26
27
28
29

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/315502