LEETCODE常用小知识点总结(不断更新)

一,取得十进制数字上的每一位

用当前数字与10求余数,该余数即是当前数字最低位上的数字,接下来我们将当前数字除以10,继续求它与10的余数,该数字即是次低位上的数字,重复上述过程直到当前数字为0为止。

List<Integer> list = new ArrayList<>();
// 取得x上的每一位
while(x>0){
    list.add(x%10);
    x/=10;
}

二, 判断回文

判断一个字符串是否是回文我们通常采用剥洋葱的方式,从最外层向内比较,解题时可以定义左右两个指针,初始时左指针指向下标0,右指针指向字符串末尾位,如果当前俩指针指向的值不一致,直接返回false。反之,左指针加一,右指针减一,向内移动一层继续比较,重复此过程直到左指针不再小于右指针为止。

public boolean isPalindrome(String s) {
    // 定义左右指针
    int left=0,right=list.size()-1;
    while(left<right){
        // 左右指针指向的数字不同时,返回false
        if(s.charAt(left) != s.charAt(right)){
            return false;
        }
        left++;
        right--;
    }
    return true;
}

三,不使用额外变量交换两个数字或字符的值

继续阅读
发表在 leetcode | 标签为 , , , , , , | 2条评论

LEETCODE刷题心得-你必须掌握的4类必考题型

前(fei)言(hua):

大约在一年前左右,我第一次打开leetcode的网站。在那之前,我从未想过要进行算法编程方面的学习。作为一名骨灰级AndroidApp程序猿,平时的工作与底层算法毫无干系。我们关心的内容大多是,AndroidOS推出哪些新鲜的功能?Animation又增加了什么绚丽的效果?最近又在流行什么框架?。。。什么?你问我是否关心代码执行效率?对不起,那不是硬件该去解决的问题吗?将你的内存,CPU,GPU,显卡,屏幕再加上手机壳,手机链统统升级一圈,你会发现我的程序速度将得到大幅改善。

算法的重要性

继续阅读
发表在 leetcode | 标签为 , , | 一条评论

LEETCODE 1533. Find the Index of the Large Integer 解题思路分析

题目大意:

找出大数的下标

给你一个整数数组arr,其中只有一个数字大于其他所有数字,另外的数字都相同。你不能直接访问该数组,只能使用ArrayReader 类的API,它具有以下方法:

  1. int compareSub(int l, int r, int x, int y): 其中0 <= l, r, x, y < ArrayReader.length()l <= r 并且 x <= y. 这个函数用来比较子区间 arr[l..r]内数字和 与子区间 arr[x..y]内数字和的大小关系,返回结果为:
    • 1 当arr[l]+arr[l+1]+...+arr[r] > arr[x]+arr[x+1]+...+arr[y]时.
    • 0 当arr[l]+arr[l+1]+...+arr[r] == arr[x]+arr[x+1]+...+arr[y]时.
    • -1 当if arr[l]+arr[l+1]+...+arr[r] < arr[x]+arr[x+1]+...+arr[y]时.
  2. int length(): 返回数组长度

你最多只能调用compareSub方法20次,另外上述两个方法的时间复杂度均为O(1)。

请找出数组中最大数的下标。

继续阅读
发表在 leetcode | 标签为 , , | 留下评论

LEETCODE 1521. Find a Value of a Mysterious Function Closest to Target 解题思路分析

题目大意:

找到最接近目标值的函数值

Winston 构造了一个如上所示的函数 func 。他有一个整数数组 arr 和一个整数 target ,他想找到让 |func(arr, l, r) – target| 最小的 l 和 r 。

请你返回 |func(arr, l, r) – target| 的最小值。

请注意, func 的输入参数 l 和 r 需要满足 0 <= l, r < arr.length 。

继续阅读
发表在 leetcode | 留下评论

LEETCODE 1526. Minimum Number of Increments on Subarrays to Form a Target Array 解题思路分析

题目大意:

形成目标数组的子数组最少增加次数

给你一个整数数组 target 和一个数组 initial ,initial 数组与 target  数组有同样的维度,且一开始全部为 0 。

请你返回从 initial 得到  target 的最少操作次数,每次操作需遵循以下规则:

  • 在 initial 中选择 任意 子数组,并将子数组中每个元素增加 1 。

答案保证在 32 位有符号整数以内。

继续阅读
发表在 leetcode | 标签为 , , , , | 留下评论

LEETCODE 1531. String Compression II 解题思路分析

题目大意:

压缩字符串 II

行程长度编码 是一种常用的字符串压缩方法,它将连续的相同字符(重复 2 次或更多次)替换为字符和表示字符计数的数字(行程长度)。例如,用此方法压缩字符串 “aabccc” ,将 “aa” 替换为 “a2″ ,”ccc” 替换为` “c3” 。因此压缩后的字符串变为 “a2bc3” 。

注意,本问题中,压缩时没有在单个字符后附加计数 ‘1’ 。

给你一个字符串 s 和一个整数 k 。你需要从字符串 s 中删除最多 k 个字符,以使 s 的行程长度编码长度最小。

请你返回删除最多 k 个字符后,s 行程长度编码的最小长度 。

继续阅读
发表在 leetcode | 标签为 , , , , , | 留下评论

LEETCODE 1529. Bulb Switcher IV 解题思路分析

题目大意:

灯泡开关 IV

房间中有 n 个灯泡,编号从 0 到 n-1 ,自左向右排成一行。最开始的时候,所有的灯泡都是  着的。

请你设法使得灯泡的开关状态和 target 描述的状态一致,其中 target[i] 等于 1 第 i 个灯泡是开着的,等于 0 意味着第 i 个灯是关着的。

有一个开关可以用于翻转灯泡的状态,翻转操作定义如下:

  • 选择当前配置下的任意一个灯泡(下标为 i )
  • 翻转下标从 i 到 n-1 的每个灯泡

翻转时,如果灯泡的状态为 0 就变为 1,为 1 就变为 0 。

返回达成 target 描述的状态所需的 最少 翻转次数。

继续阅读
发表在 leetcode | 标签为 , , | 留下评论

LEETCODE 1530. Number of Good Leaf Nodes Pairs 解题思路分析

好叶子节点对的数量

给你二叉树的根节点 root 和一个整数 distance 。

如果二叉树中两个  节点之间的 最短路径长度 小于或者等于 distance ,那它们就可以构成一组 好叶子节点对 。

返回树中 好叶子节点对的数量 。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 676. Implement Magic Dictionary 解题思路分析

题目大意:

实现一个魔法字典

实现一个带有buildDict, 以及 search方法的魔法字典。

对于buildDict方法,你将被给定一串不重复的单词来构建一个字典。

对于search方法,你将被给定一个单词,并且判定能否只将这个单词中一个字母换成另一个字母,使得所形成的新单词存在于你构建的字典中。

继续阅读
发表在 leetcode | 标签为 , , , , | 留下评论

LEETCODE 1513. Number of Substrings With Only 1s 解题思路分析

题目大意:

仅含 1 的子串数

给你一个二进制字符串 s(仅由 ‘0’ 和 ‘1’ 组成的字符串)。

返回所有字符都为 1 的子字符串的数目。

由于答案可能很大,请你将它对 10^9 + 7 取模后返回。

继续阅读
发表在 leetcode | 标签为 , , , | 留下评论

LEETCODE 1514. Path with Maximum Probability 解题思路分析

题目大意:

概率最大的路径

给你一个由 n 个节点(下标从 0 开始)组成的无向加权图,该图由一个描述边的列表组成,其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边,且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ,请你找出从起点到终点成功概率最大的路径,并返回其成功概率。

如果不存在从 start 到 end 的路径,请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ,就会被视作正确答案。

继续阅读
发表在 leetcode | 标签为 , , , | 2条评论

LEETCODE 1510. Stone Game IV 解题思路分析

题目大意:

石子游戏 IV

Alice 和 Bob 两个人轮流玩一个游戏,Alice 先手。

一开始,有 n 个石子堆在一起。每个人轮流操作,正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了,则无法操作的玩家输掉游戏。

给你正整数 n ,且已知两个人都采取最优策略。如果 Alice 会赢得比赛,那么返回 True ,否则返回 False 。

继续阅读
发表在 leetcode | 标签为 , , , , , | 留下评论