関小君刷题记

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

用当前数字与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常用小知识点总结（不断更新）/