leetcode解题思路分析（二十八）200—206题

曾经终败给现在 2023-02-14 05:58 10阅读 0赞

1.  岛屿数量  
    给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。  
    岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。

**本题可用BFS或DFS求解**

class Solution { 
    private:
        void dfs(vector<vector<char>>& grid, int r, int c) { 
            int nr = grid.size();
            int nc = grid[0].size();
    
            grid[r][c] = '0';
            if (r - 1 >= 0 && grid[r-1][c] == '1') dfs(grid, r - 1, c);
            if (r + 1 < nr && grid[r+1][c] == '1') dfs(grid, r + 1, c);
            if (c - 1 >= 0 && grid[r][c-1] == '1') dfs(grid, r, c - 1);
            if (c + 1 < nc && grid[r][c+1] == '1') dfs(grid, r, c + 1);
        }
    
    public:
        int numIslands(vector<vector<char>>& grid) { 
            int nr = grid.size();
            if (!nr) return 0;
            int nc = grid[0].size();
    
            int num_islands = 0;
            for (int r = 0; r < nr; ++r) { 
                for (int c = 0; c < nc; ++c) { 
                    if (grid[r][c] == '1') { 
                        ++num_islands;
                        dfs(grid, r, c);
                    }
                }
            }
    
            return num_islands;
        }
    };

class Solution { 
    public:
        int numIslands(vector<vector<char>>& grid) { 
            int nr = grid.size();
            if (!nr) return 0;
            int nc = grid[0].size();
    
            int num_islands = 0;
            for (int r = 0; r < nr; ++r) { 
                for (int c = 0; c < nc; ++c) { 
                    if (grid[r][c] == '1') { 
                        ++num_islands;
                        grid[r][c] = '0';
                        queue<pair<int, int>> neighbors;
                        neighbors.push({ r, c});
                        while (!neighbors.empty()) { 
                            auto rc = neighbors.front();
                            neighbors.pop();
                            int row = rc.first, col = rc.second;
                            if (row - 1 >= 0 && grid[row-1][col] == '1') { 
                                neighbors.push({ row-1, col});
                                grid[row-1][col] = '0';
                            }
                            if (row + 1 < nr && grid[row+1][col] == '1') { 
                                neighbors.push({ row+1, col});
                                grid[row+1][col] = '0';
                            }
                            if (col - 1 >= 0 && grid[row][col-1] == '1') { 
                                neighbors.push({ row, col-1});
                                grid[row][col-1] = '0';
                            }
                            if (col + 1 < nc && grid[row][col+1] == '1') { 
                                neighbors.push({ row, col+1});
                                grid[row][col+1] = '0';
                            }
                        }
                    }
                }
            }
    
            return num_islands;
        }
    };

1.  数字范围按位与  
    给定范围 \[m, n\]，其中 0 <= m <= n <= 2147483647，返回此范围内所有数字的按位与（包含 m, n 两端点）。

**本题的精髓在于如何简化位操作的次数。首先我们应该关注较小的数，如果位数不同直接从小数开始看即可。其次，当数位相同的时候，找到不相同的位赋值为0即可**

class Solution { 
    public:
        int rangeBitwiseAnd(int m, int n) { 
            if (m == n || m == 0) { 
                return m;
            } else if (floor(log(n)/log(2)) - floor(log(m)/log(2)) >= 1) { 
                return 0;
            } else { 
                int xorResult = n ^ m;
                int bits = floor(log(xorResult)/log(2)) + 1;
                return (m >> bits) << bits;
            }
        }
    };

1.  快乐数  
    编写一个算法来判断一个数 n 是不是快乐数。  
    「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

**该题涉及到可能有循环的情况，因此用快慢指针检测循环为佳**

class Solution { 
    public:
        int bitSquareSum(int n) { 
            int sum = 0;
            while(n > 0)
            { 
                int bit = n % 10;
                sum += bit * bit;
                n = n / 10;
            }
            return sum;
        }
        
        bool isHappy(int n) { 
            int slow = n, fast = n;
            do{ 
                slow = bitSquareSum(slow);
                fast = bitSquareSum(fast);
                fast = bitSquareSum(fast);
            }while(slow != fast);
            
            return slow == 1;
        }
    };

1.  移除链表元素  
    删除链表中等于给定值 val 的所有节点。

class Solution { 
      public:
      ListNode* removeElements(ListNode* head, int val) { 
        ListNode* sentinel = new ListNode(0);
        sentinel->next = head;
    
        ListNode *prev = sentinel, *curr = head, *toDelete = nullptr;
        while (curr != nullptr) { 
          if (curr->val == val) { 
            prev->next = curr->next;
            toDelete = curr;
          } else prev = curr;
    
          curr = curr->next;
    
          if (toDelete != nullptr) { 
            delete toDelete;
            toDelete = nullptr;
          }
        }
    
        ListNode *ret = sentinel->next;
        delete sentinel;
        return ret;
      }
    };

1.  计数质数  
    统计所有小于非负整数 n 的质数的数量。

**采用厄拉多塞筛法：先把所有设为质数，然后依次排除其倍数**

class Solution { 
    public:
        int countPrimes(int n) { 
            int count = 0;
            //初始默认所有数为质数
            vector<bool> signs(n, true);
            for (int i = 2; i < n; i++) { 
                if (signs[i]) { 
                    count++;
                    for (int j = i + i; j < n; j += i) { 
                        //排除不是质数的数
                        signs[j] = false;
                    }
                }
            }
            return count;
        }
    };

1.  同构字符串  
    给定两个字符串 s 和 t，判断它们是否是同构的。  
    如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。  
    所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

**本题有两种方法：采用一个map映射已有的字符，后面每个检查一遍是否映射相同。第二种方法是把字符对应转换为数字，然后比较两串数字**

class Solution { 
    public:
        bool isIsomorphic(string s, string t) 
        { 
            if (s.empty() && t.empty())
                return true;
            
            for(int i = 0; i < s.size(); i++)
            { 
                if( s.find(s[i]) != t.find(t[i])) 
                return false;
            }
            return true;       
        }
    };

1.  反转链表  
    反转一个单链表。

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* reverseList(ListNode* head) { 
            ListNode *next, *ptr, *prev;
            ptr = next = head;
            prev = NULL;
            while (ptr)
            { 
                next = ptr->next;
                ptr->next = prev;
                prev = ptr;
                ptr = next;
            }
            return prev;
        }
    };

class Solution { 
    public:
        ListNode* reverseList(ListNode* head) { 
            if (head == NULL || head->next == NULL) { 
                return head;
            }
            ListNode* ret = reverseList(head->next);
            head->next->next = head;
            head->next = NULL;
            return ret;
        }
    };