Some Trics in Coding Practice

Posted on

//TODO: 目前题目较少，先暂时这样整理，之后再整理归类

1

题目

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路

很容易想到一个会引起死循环的方法：

1
2
3
4
5
6
7
8
int NumberOf1(int n){
    int cnt = 0;
    while(n){
        if(n&1) cnt++;
        n >>= 1;
    }
    return cnt;
}

原因是负数的移位最高位总是1。
一个非常巧妙的思路是：
把一个整数 （无论正负或0）减去1，再和原整数做与运算，会把该整数最右边的一个1变为0，例如：110100减1后变为110011，二者进行与操作后，得到110000，最后边的1变为了0，而前面的位都不变。
这样，我们可以利用这这一结论来从左向右依次将整数的最右边的1变为0，当该整数的所有位为1的位均变为0之后，便统计到了该整数二进制中1的个数。

代码

1
2
3
4
5
6
7
8
9
int  NumberOf1(int n) {
    int count = 0;
    while(n)
    {
        count++;
        n = n & (n-1);
    }
    return count;
}

参考

https://blog.csdn.net/ns_code/article/details/25425577

2

题目

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

思路

暴力法复杂度为O(n^3)。利用滑动窗口，比较容易想到的是下面这种O(n^2)解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int lengthOfLongestSubstring(string s) {
    int res = 0;
    int n = s.length();
    if(n) res = 1;
    for(int i = 0; i < n; i++){
        map<char, int> mp;
        mp.insert(make_pair(s[i], 1));
        for(int j = i + 1; j < n; j++){
            if(!mp.count(s[j])){
                mp.insert(make_pair(s[j], 1));
                res = max(res, j-i+1);
            }
            else{
                break;
            }
        }
    }
    return res;
}

优化之后，可以把复杂度降为O(n)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int lengthOfLongestSubstring(string s) {
    int res = 0;
    int n = s.length();
    map<char, int> mp;
    for(int i = 0, j = 0; j < n; ){
        if(!mp.count(s[j])){
            mp.insert(make_pair(s[j], 1));
            res = max(res, j-i+1);
            j++;
        }
        else{
            mp.erase(s[i]);
            i++;
        }
    }
    return res;
}

进一步优化，建立元素到索引的映射：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int lengthOfLongestSubstring(string s) {
    int res = 0;
    int n = s.length();
    map<char, int> mp;
    for(int i = 0, j = 0; j < n;){
        if(!mp.count(s[j]) || mp[s[j]] < i){
            // std::map插入已存在的key时，key对应的内容不会被更新
            if(!mp.count(s[j])) mp.insert(make_pair(s[j], j));
            else mp[s[j]] = j;
            res = max(res, j-i+1);
            j++;
        }
        else{
            i = mp[s[j]] + 1;
        }
    }
    return res;
}

3

排序相关

快速排序

Mark一个非常清晰的快速排序代码~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int partition(vector<int>& nums, int left, int right){
    int i = left, j = right;
    int base = nums[left];
    while(i < j){
            while(i < j && nums[j] >= base) j--;
            if(i < j) nums[i++] = nums[j];
            while(i < j && nums[i] <= base) i++;
            if(i < j) nums[j--] = nums[i];
    }
    nums[i] = base;
    return i;
}
void quickSort(vector<int>& nums, int left, int right){
    if(left >= right) return;
    int par = partition(nums, left, right);
    quickSort(nums, left, par-1);
    quickSort(nums, par+1, right);
}