leetcode解题思路分析（三十八）318 - 327题

今天药忘吃喽~ 2022-11-29 03:19 99阅读 0赞

1.  最大单词长度乘积  
    给定一个字符串数组 words，找到 length(word\[i\]) \* length(word\[j\]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

**为了方便比较，可以采取位操作存储每个单词的bitfield，通过位运算进行互相比较。**

class Solution { 
    public:
        int str2int(const string& s) { 
            int res = 0;
            for (auto c : s)
                res |= 1 << (c - 'a');
            return res;
        }
        int maxProduct(vector<string>& words) { 
            int N = words.size();
            vector<int> m(N, 0);
            for (int i = 0; i < N; ++i)
                m[i] = str2int(words[i]);
            int res = 0;
            for (int i = 0; i < N; ++i) { 
                for (int j = 0; j < i; ++j) { 
                    if ((m[i] & m[j]) == 0 && words[i].size() * words[j].size() > res)
                        res = words[i].size() * words[j].size();
                }
            }
            return res;
        }
    };

1.  灯泡开关  
    初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。

**只有完全平方数能够满足被操作奇数次，问题演变为求 1~n 完全平方数的个数，1 \* 1、2 \* 2、…、\\sqrt\{n\} \* \\sqrt\{n\} ，有 \\sqrt\{n\} n个**

class Solution { 
    public:
        int bulbSwitch(int n) { 
            return sqrt(n);        
        }
    };

1.  拼接最大数

**很经典的贪心算法题**

class Solution { 
    public:
    // 返回数组nums中，从idx，到nums.size()-len-1中最大数的索引。
    int findMaxIndex(vector<int> &nums, int idx, int len){ 	
        int maxIdx = idx;
        for (int i=idx; i<nums.size()-len; i++){ 
            if (nums[i] > nums[maxIdx]) maxIdx = i;
        }
        return maxIdx;
    }
    typedef pair<int,int> P;
    vector<int> maxNumber(vector<int>& nums1, vector<int>& nums2, int k) { 
        int n = nums1.size();
        int m = nums2.size();
        set<P> start;	// 存储所有可能的起点索引
        start.insert(pair<int,int>{ 0,0});	// 数组1初始起点为0，数组2初始起点为0。
        vector<int> ans;	//存储答案
        while(k){ 
            int maxNum = -1;// 第i位数初始值
            set<P> temp;	// 存储第i位数可以导致的所有可能的起点索引
            for(auto p:start){ 	// 考虑能够到达第i位的所有可能的起点索引
                int s1 = p.first;
                int s2 = p.second;
                int len1 = max(0, k-(m-s2+1));
                int maxIdx1 = findMaxIndex(nums1, s1, len1);	// 数组1此时能够取的最大数的索引
                int maxNum1 = maxIdx1 >= n ? -1 : nums1[maxIdx1];// 该索引对应的最大数
                if(maxNum1>=maxNum){ 
                    if(maxNum1>maxNum) temp.clear();	// 如果当前起点索引获得的最大数比之前起点索引获得的最大值还要大，那么之前起点索引得到后续可能索引（temp）可以不用考虑。
                    maxNum = maxNum1;
                    temp.insert({ maxIdx1+1, s2});	// 更新temp
                }
                int len2 = max(0, k-(n-s1+1));
                int maxIdx2 = findMaxIndex(nums2, s2, len2);
                int maxNum2 = maxIdx2 >= m ? -1 : nums2[maxIdx2];
                if(maxNum2>=maxNum){ 
                    if(maxNum2>maxNum) temp.clear();
                    maxNum = maxNum2;
                    temp.insert({ s1, maxIdx2+1});
                }
            }
            ans.push_back(maxNum);	// 确定第i位数
            start.swap(temp);	    // 下一位所有可能的起点索引
            k--;
        }
        return ans;
    }
    };

1.  零钱兑换  
    给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

**典型的贪心算法题，每次选取最大面额的最大上限，不行再回退**

class Solution { 
    public:
        void coinChange(vector<int>& coins, int amount, int c_index, int count, int& ans)
        { 
            if (amount == 0)
            { 
                ans = min(ans, count);
                return;
            }
            if (c_index == coins.size()) return;
    
            for (int k = amount / coins[c_index]; k >= 0 && k + count < ans; k--)
            { 
                coinChange(coins, amount - k * coins[c_index], c_index + 1, count + k, ans);
            }
        }
    
        int coinChange(vector<int>& coins, int amount)
        { 
            if (amount == 0) return 0;
            sort(coins.rbegin(), coins.rend());
            int ans = INT_MAX;
            coinChange(coins, amount, 0, 0, ans);
            return ans == INT_MAX ? -1 : ans;
        }
    };

1.  摆动排序2  
    给定一个无序的数组 nums，将它重新排列成 nums\[0\] < nums\[1\] > nums\[2\] < nums\[3\]… 的顺序。

**采用中位数的方式来拆分成两个数组，再交替拼接。为了实现O(1)空间复杂度采取虚拟地址的方式直接映射到原数组而不是新建数组**

class Solution { 
    public:
        void wiggleSort(vector<int>& nums) { 
            int n = nums.size();
    
            // Find a median.
            auto midptr = nums.begin() + n / 2;
            nth_element(nums.begin(), midptr, nums.end());
            int mid = *midptr;
    
            // Index-rewiring.
            #define A(i) nums[(1+2*(i)) % (n|1)]
    
            // 3-way-partition-to-wiggly in O(n) time with O(1) space.
            int i = 0, j = 0, k = n - 1;
            while (j <= k) { 
                if (A(j) > mid)
                    swap(A(i++), A(j++));
                else if (A(j) < mid)
                    swap(A(j), A(k--));
                else
                    j++;
            }
        }
    };

1.  3的幂  
    给定一个整数，写一个函数来判断它是否是 3 的幂次方。

**数学题，考换底公式**

class Solution { 
    public:
        bool isPowerOfThree(int n) { 
        if(n <= 0) return false;
        double a = log10(n) / log10(3) ;        //换底
        return  a == floor(a);         //判断换底后的log3n是否为整数，即n是否为3的倍数
        }
    };

1.  区间和的个数  
    给定一个整数数组 nums，返回区间和在 \[lower, upper\] 之间的个数，包含 lower 和 upper。  
    区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

**区间和的做法在前面已经出现过几次了，就是保存每一个位置到0位的和，相减即可。**

typedef long long LL;
    class Solution { 
    public:
        
        vector<LL> data;
        vector<int> tr;
        
        // 查找小于等于x的第一个数的下标，找不到返回0
        int binary_search1(LL x) { 
            
            int l = 0, r = data.size() - 1;
            while (l < r) { 
                int mid = l + r + 1 >> 1;
                if (data[mid] <= x) l = mid;
                else r = mid - 1;
            }
            if (l == 0 && data[0] > x) return 0;
            else return l + 1;
        }
        
        // 查找小于x的第一个数的下标，找不到返回0
        int binary_search2(LL x) { 
            int l = 0, r = data.size() - 1;
            while (l < r) { 
                int mid = l + r + 1 >> 1;
                if (data[mid] < x) l = mid;
                else r = mid - 1;
            }
            if (l == 0 && data[0] >= x) return 0;
            else return l + 1;
        }
        
        int lowbit(int x) { 
            return x & -x;
        }
        
        int find(int x) { 
            int ans = 0;
            for (int i = x; i; i -= lowbit(i)) ans += tr[i];
            return ans;
        }
        
        void add(int x, int c) { 
            int n = tr.size() - 1;
            for (int i = x; i <= n; i += lowbit(i)) tr[i] += c;
        }
        
        int countRangeSum(vector<int>& nums, int lower, int upper) { 
            int n = nums.size();
            LL sum = 0;
            vector<LL> s(n);
            for (int i = 0; i < n; i ++) { 
                sum += nums[i];
                s[i] = sum;
            }
            data = s;
            data.push_back(0);
            sort(data.begin(), data.end());
            data.erase(unique(data.begin(), data.end()), data.end());
            tr = vector<int>(data.size() + 1);
            
    // for (int i = 0; i < data.size(); i ++) cout << data[i] << " ";
    // cout << endl;
            int ans = 0;
            int idx_zero = binary_search1(0);
            add(idx_zero, 1);
            for (auto x : s) { 
                LL a = x - upper, b = x - lower;
                int idxa = binary_search2(a), idxb = binary_search1(b);
                int idxx = binary_search1(x);
                // cout << idxa << " " << idxb << " " << idxx << endl;
                if (idxb != 0) { 
                    if (idxa == 0) ans += find(idxb);
                    else ans += find(idxb) - find(idxa);
                }
                add(idxx, 1);   
                // cout << ans << endl;
            }
            return ans;
        }
    };