leetcode-1

[21] 合并两个有序链表

利用一个pre指针，来不断遍历迭代。利用prehead指针来返回头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode *preHead = new ListNode(-1);
    ListNode *pre ;
    pre = preHead;
    while (list1!=nullptr && list2!=nullptr)
    {
        if(list1->val < list2->val){
            pre->next=list1;
            list1=list1->next;
        }else{
            pre->next=list2;
            list2=list2->next;
        }
        pre=pre->next;
    }
    
    pre->next = (list1 ==nullptr ? list2:list1);  
    return preHead->next; 
}

[191] 位1的个数

循环遍历累加

1
2
3
4
5
6
7
8
9
10

int hammingWeight(int n) {
    int ret=0;
    for(int i=0;i<32;i++){
        if(n&(1<<i)){
            ret++;
        }
    }
    return ret;
}

最优：n&（n-1），做一次这样的运算，即可把最低位的1翻转，做了多少次就有多少1的个数

1
2
3
4
5
6
7
8
9
10

int hammingWeight(int n) {
    int ret=0;
    while (n)
    {   
        n=n&(n-1);
        ret++;
    }
    return ret;
}

[9] 回文数

通过除以10来判断余数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

bool isPalindrome(int x) {
    if(x<10||(x%10==0 && x!=0)){
        return false;
    }
    int reverNum=0;
    while(x>reverNum){
        reverNum = x%10 + reverNum*10;
        x = x/10;
    }
    if(x==reverNum || x ==reverNum/10){
        return true;
    }
    return false;   
}

[36]有效的数独

新建三个数组，一个是行数组，计算每行每个数字出现的次数，同理，列数组和小3*3数组，没加入一次，则判断一次时候重复，如果重复则返回false。
原理：利用数组来作为hash表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

bool isValidSudoku(vector<vector<char>>& board) {
    int row[9][9];
    int column[9][9];
    int box[3][3][9];
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            char tmp=board[i][j];
            if(tmp!='.')
            {
                int index = tmp-'0'-1;
                row[i][index]++;
                column[j][index]++;
                box[i/3][j/3][index]++;
                if(row[i][index]>1 ||column[j][index]>1||box[i/3][j/3][index]>1){
                    return false;
                }
            }
        }
    }
    return true;
}

在某些特定情况下，可以用数组来代替哈希表。以下是适合使用数组而不是哈希表的情境：

  1. 数据索引是连续整数：如果数据的键值是连续的整数（例如0到n），数组可以直接用索引来存取数据，不需要哈希函数的计算。比如在统计字符频率时，字符的ASCII值可以作为数组的索引，直接访问数组元素来存储频率。
  2. 键的范围已知且较小：当键的范围较小且已知时，可以使用数组代替哈希表。例如，如果键是0到100之间的整数，那么可以创建一个大小为101的数组，以避免哈希冲突，提高存取效率。
  3. 需要更高的访问速度：数组的直接访问（O(1)时间复杂度）比哈希表的平均访问速度要快，并且没有哈希冲突的风险。如果对访问速度有更高要求且数据范围适合，数组会是更高效的选择。
  4. 没有删除操作：在某些应用中，如果不涉及数据的删除操作，数组可以更加直接。哈希表需要处理删除的复杂性（例如标记删除），而数组不涉及这种操作。
  5. 空间复杂度要求低：哈希表在一定的负载因子下可能会占用更多空间，尤其是当数据量少但键范围大时。数组在这种情况下可能更加节省空间，因为可以根据需要创建大小合适的数组。
    总结来说，当键是整数、范围较小且已知，并且没有大量动态插入和删除操作的情况下，数组可以作为更高效的替代选择。

[80] 删除有序数组中的重复项 II

双指针查找即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int removeDuplicates(vector<int>& nums) {
    int fast =2;
    int slow =2;
    int len = nums.size();
    if(len<2){s
        return slow;
    }

    while(fast < len){
        if(nums[slow-2]!=nums[fast]){
            nums[slow] =nums[fast];
            ++slow;
        }
        ++fast;
    }
    return slow;
}

一个快指针，一个慢指针