leetcode解题思路分析（七十九）693 - 699 题

缺乏、安全感 2022-10-06 13:57 142阅读 0赞

1.  交替位二进制数  
    给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

**按位取数并异或即可**

class Solution { 
    public:
        bool hasAlternatingBits(int n) 
        { 
            int a = n & 1;
            n = n >> 1;
            while (n)
            { 
                int b = n & 1;
                n = n >> 1;
                if (b ^ a == 0)
                { 
                    return false;
                }
                a = b;
            }
            return true;
        }
    };

1.  岛屿的最大面积  
    给定一个包含了一些 0 和 1 的非空二维数组 grid 。  
    一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。  
    找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

**遍历一遍，搜过的赋值为0，没搜过的继续检测**

class Solution { 
        int dfs(vector<vector<int>>& grid, int cur_i, int cur_j) { 
            if (cur_i < 0 || cur_j < 0 || cur_i == grid.size() || cur_j == grid[0].size() || grid[cur_i][cur_j] != 1) { 
                return 0;
            }
            grid[cur_i][cur_j] = 0;
            int di[4] = { 0, 0, 1, -1};
            int dj[4] = { 1, -1, 0, 0};
            int ans = 1;
            for (int index = 0; index != 4; ++index) { 
                int next_i = cur_i + di[index], next_j = cur_j + dj[index];
                ans += dfs(grid, next_i, next_j);
            }
            return ans;
        }
    public:
        int maxAreaOfIsland(vector<vector<int>>& grid) { 
            int ans = 0;
            for (int i = 0; i != grid.size(); ++i) { 
                for (int j = 0; j != grid[0].size(); ++j) { 
                    ans = max(ans, dfs(grid, i, j));
                }
            }
            return ans;
        }
    };

1.  计数二进制子串  
    给定一个字符串 s，计算具有相同数量 0 和 1 的非空（连续）子字符串的数量，并且这些子字符串中的所有 0 和所有 1 都是连续的。重复出现的子串要计算它们出现的次数。

**遍历一遍记录重复子串的计数，然后和上一次的重复数求最小值则为重复子串数，累加即可。**

class Solution { 
    public:
        int countBinarySubstrings(string s) 
        { 
            int before = 0, cnt = 1, ret = 0, size = s.size();
            char c;
    
            if (size == 0) 
                return ret;
    
            c = s[0];
            for (int i = 1; i < size;)
            { 
                while (i < size && c == s[i])
                { 
                    cnt++;
                    i++;
                }
                ret += min(cnt, before);
                before = cnt;
                cnt = 0;
                c = s[i];
            }
    
            return ret;
        }
    };

1.  数组的度  
    给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。  
    你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

**哈希表的使用，其中用一个长度为3的数组标识这个数出现的次数、这个数在原数组中第一次出现的位置和这个数在原数组中最后一次出现的位置**

class Solution { 
    public:
        int findShortestSubArray(vector<int>& nums) 
        { 
            unordered_map<int, int[3]> mp;
            int n = nums.size();
            for (int i = 0; i < n; i++) 
            { 
                if (mp.count(nums[i])) 
                { 
                    mp[nums[i]][0]++;
                    mp[nums[i]][2] = i;
                } 
                else 
                { 
                    mp[nums[i]][0] = 1;
                    mp[nums[i]][1] = i;
                    mp[nums[i]][2] = i;                                
                }
            }
            int maxNum = 0, minLen = 0;
            for (auto& [_, vec] : mp) 
            { 
                if (maxNum < vec[0]) 
                { 
                    maxNum = vec[0];
                    minLen = vec[2] - vec[1] + 1;
                } 
                else if (maxNum == vec[0]) 
                { 
                    if (minLen > vec[2] - vec[1] + 1) 
                    { 
                        minLen = vec[2] - vec[1] + 1;
                    }
                }
            }
            return minLen;
        }
    };

1.  划分为k个相等的子集  
    给定一个整数数组 nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。

**回溯剪枝或者用哈希记录均可**

class Solution { 
    public:
        bool canPartitionKSubsets(vector<int>& nums, int k) { 
            sort(nums.rbegin(), nums.rend());
            int sum = accumulate(nums.begin(), nums.end(), 0);
            if (sum % k != 0) return false;
            int avg = sum / k;
    
            vector<int> vi(nums.size(), 0);
            return dfs(nums, vi, avg, 0, k);
        }
    
        bool dfs(vector<int>& nums, vector<int>& vi, int target, int sum, int k) { 
            if (k == 0) return true;
    
            int firstIdx = -1;
            for (int i = 0; i < nums.size(); i++) { 
                if (vi[i] == 1) continue;
                firstIdx = (firstIdx == -1) ? i : firstIdx;
                if (sum == 0 && i != firstIdx) return false;
    
                int temp = sum + nums[i];
                if (temp > target) continue;
    
                int nextK = (temp == target) ? k - 1 : k;
                int nextSum = (temp == target) ? 0 : temp;
    
                vi[i] = 1;
                if (dfs(nums, vi, target, nextSum, nextK)) return true;
                vi[i] = 0;
            }
            return false;
        }
    };

class Solution { 
    public:
        bool canPartitionKSubsets(vector<int>& nums, int k) 
        { 
            int maxNum = 0, cnt = 0, goal = 0, dif = 0, left = 0;
            bool bFind = false;
            unordered_map<int, stack<int>> m_map;
    
            for (int i = 0; i < nums.size(); i++)
            { 
                cnt += nums[i];
                maxNum = max(maxNum, nums[i]);
                m_map[nums[i]].push(i);
            }
    
            if (cnt % k) return false;
    
            goal = cnt / k;
            if (maxNum > goal) return false;
    
            cnt = 0;
            left = goal;
            for (int i = 0; i < nums.size(); ++i)
            { 
                if (nums[i] == - 1) continue;
    
                dif = left - nums[i];
    
                if (dif == 0)
                { 
                    cnt++;
                    left = goal;
                    nums[i] = -1;
                    continue;
                }   
    
                auto tempStack = m_map[dif];
                if (tempStack.size() > 0)
                { 
                    bFind = false;
                    while (tempStack.size() > 0)
                    { 
                        int index = tempStack.top();
                        if (nums[index] == -1)
                        { 
                            tempStack.pop();
                            continue;
                        }
                        else
                        { 
                            cnt++;
                            left = goal;
                            nums[index] = -1;
                            tempStack.pop();
                            bFind = true;                       
                            break;
                        }
                    }
                }
    
                if (!bFind)
                { 
                    goal -= nums[i];
                }
            }
    
            if (cnt == k) 
                return true;
            else
                return false;
        }
    };

1.  掉落的方块  
    返回一个堆叠高度列表 ans 。每一个堆叠高度 ans\[i\] 表示在通过 positions\[0\], positions\[1\], …, positions\[i\] 表示的方块掉落结束后，目前所有已经落稳的方块堆叠的最高高度。

**线段树求解**

class Solution { 
    public:
        int a[10005], mark[10005];
    
        void build(int p, int l, int r) { 
            if (l == r) { 
                a[p] = 0;
                mark[p] = 0;
                return;
            }
            int mid = l + (r - l) / 2;
            build(p << 1, l, mid);
            build(p << 1 | 1, mid + 1, r);
            a[p] = max(a[p << 1], a[p << 1 | 1]);
        }
    
        void push_down(int p) { 
            mark[p << 1] = max(mark[p], mark[p << 1]);
            mark[p << 1 | 1] = max(mark[p], mark[p << 1 | 1]);
            a[p << 1] = max(a[p << 1], mark[p << 1]);
            a[p << 1 | 1] = max(a[p << 1 | 1], mark[p << 1 | 1]);
            mark[p] = 0;
        }
    
        int query(int p, int l, int r, int ql, int qr) { 
            if (qr < l || ql > r) return 0;
            else if (ql <= l && qr >= r) return a[p];
            else { 
                if (mark[p]) { 
                    push_down(p);
                }
                int mid = l + (r - l) / 2;
                if (qr <= mid) return query(p << 1, l, mid, ql, qr);
                else if (ql > mid) return query(p << 1 | 1, mid + 1, r, ql, qr);
                else return max(query(p << 1, l, mid, ql, qr),query(p << 1 | 1, mid + 1, r, ql, qr));
            }
        }
    
        void update(int p, int l, int r, int ul, int ur, int val) { 
            if (ur < l || ul > r) return;
            else if (ul <= l && ur >= r) { 
                a[p] = max(a[p], val);
                mark[p] = max(mark[p], val);
            } else { 
                if (mark[p]) push_down(p);
                int mid = l + (r - l) / 2;
                update(p << 1, l, mid, ul, ur, val);
                update(p << 1 | 1, mid + 1, r, ul, ur, val);
                a[p] = max(a[p << 1], a[p << 1 | 1]);
            }
        }
    
    
        vector<int> fallingSquares(vector<vector<int>>& positions) { 
            vector<int> arr;
            for (auto &p : positions) { 
                arr.push_back(p[0]);
                arr.push_back(p[0] + p[1] - 1);
            }
            sort(arr.begin(), arr.end());
            arr.erase(unique(arr.begin(), arr.end()), arr.end());
            int n = arr.size();
            unordered_map<int, int> mp;
            for (int i = 0; i < n; ++i) mp[arr[i]] = i;
            build(1, 0, n - 1);
            vector<int> ans;
            int maxh = 0;
            for (auto &p : positions) { 
                int ql = mp[p[0]], qr = mp[p[0] + p[1] - 1];
                int h = query(1, 0, n - 1, ql, qr);
                maxh = max(maxh, h + p[1]);
                ans.push_back(maxh);
                update(1, 0, n - 1, ql, qr, h + p[1]);
            }
            return ans;
        }
    };