X

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;
}

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

异或运算符经典使用场景之一。

a^=b;
b^=a;
a^=b;

// 普通写法:
int temp = a;
a = b;
b = temp;

四,求最大公约数

递归方法,用两数相除的余数与两数较小的数继续递归,直到较小的数字变为0,较大数即是结果。

// 求a和b的最大公约数
// 递归方法,用两数相除的余数与两数较小的数继续递归,
// 直到较小的数字变为0,较大数即是结果。
long gcd(long a, long b) {
    if(a > b) return gcd(b, a);
    if (a == 0) return b;
    return gcd(b % a, a);
}

五,求最小公倍数

最小公倍数 = 两数乘积 / 最大公约数;

long lcm(long a, long b) {
    return a * b / gcd(a, b);
}

六,求字符串的Hash值

求字符串的Hash值公式为:

int hash=s[0]∗31^(n−1)+s[1]∗31^(n−2) +...+s[n−2]∗31^1+s[n−1]∗31^0

如果给字符串s的首位添加一个字符,那么Hash值将变为:

hash = hash*31 + 新添头字符ch

如果给字符串s的末位添加一个字符,那么Hash值将变为:

hash = hash + 新添尾字符*31^t   (t为字符串长度减1)

七,求一个数因子的个数

理论上最笨的方式是从1遍历至num,看num与哪些数字的余数为0即可,但这种做法明显效率不高。其实,当i是num的一个因子时,那么num/i也一定是num的另一个因子,比如3是27的一个因子,那么27/3=9也是27的一个因子,我们实际上同时找到了2个因子。不过唯一的例外是当因子是数字的平方根时,比如3是9的一个因子,这时 9/3 同样还是3,这时我们实际上只找到了一个因子而已。因此循环时,我们只需要从1循环至num的平方根即可,比如数字9,我们只要从1循环至3,就能遍历出9的所有因子。

int countDivisors(int num){
    int sqrt=(int)Math.sqrt(num);
    int count=0;
    for(int i=1;i<=sqrt;i++){
        if(num%i==0) {
            if(num/i==i) count+=1;
            else count+=2;
        }
    }
    return count;
}

八,位运算:将二进制数某一位变为0

//将二进制的第n位变为0.
int res = num & ~(1 << n);


九,位运算:将二进制数某一位变为1

//将二进制的第n位变为1.
int ret = num | (1 << n);

未完待续,不断更新中。欢迎补充!

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode常用小知识点总结(不断更新)/
Categories: leetcode
kwantong:

View Comments (6)