leetcode解题思路分析（四十三）372 - 378 题

叁歲伎倆 2022-12-09 15:54 177阅读 0赞

1.  超级次方  
    你的任务是计算 ab 对 1337 取模，a 是一个正整数，b 是一个非常大的正整数且会以数组形式给出。

**1. 对指数数组的处理，可以每次去尾部元素，然后取10出来，递归处理。 2. 关于mod运算，实际可以写成(a % k)(b % k) % k = BD % k 的形式。 3. 关于指数幂，奇数可以拆成1和偶数，偶数可以拆成二分之一乘以二**

class Solution { 
    public:
        int base = 1337;
        // 计算 a 的 k 次方然后与 base 求模的结果
        int mypow(int a, int k) { 
            if (k == 0) return 1;
            a %= base;
    
            if (k % 2 == 1) { 
                // k 是奇数
                return (a * mypow(a, k - 1)) % base;
            } else { 
                // k 是偶数
                int sub = mypow(a, k / 2);
                return (sub * sub) % base;
            }
        }
    
        int superPow(int a, vector<int>& b) { 
            if (b.empty()) return 1;
            int last = b.back();
            b.pop_back();
            
            int part1 = mypow(a, last);
            int part2 = mypow(superPow(a, b), 10);
            // 每次乘法都要求模
            return (part1 * part2) % base;
        }
    };

1.  查找和最小的K对数字  
    给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。  
    定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。  
    找到和最小的 k 对数字 (u1,v1), (u2,v2) … (uk,vk)。

**看到最小的K个就很明显是堆排序的问题了**

class Solution { 
    public:
    
    	struct cmp { 
    		bool operator() (const pair<int, pair<int, int> >& a, const pair<int, pair<int, int> >& b) { 
    			return a.first + a.second.first > b.first + b.second.first;
    		}
    	};
    	
    	vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { 
    
    		int len1 = nums1.size();
    		int len2 = nums2.size();
    		if (len1 == 0 || len2 == 0) { 
    			return vector<vector<int>>();
    		}
    		int flag = 0;
            //如果nums1的长度大于nums2 则调换，保证nums1较短
    		if (len1 > len2) { 
    			flag = 1;
    			swap(nums1, nums2);
    			swap(len1, len2);
    		}
    
            //pair<int,pair<int,int> >，外层pair第一个类型int是nums1 中的数， 第二个类型pair<int,int> 表示的是nums2中的数和对应的下标
    		priority_queue <pair<int,pair<int,int> >,vector<pair<int, pair<int, int> > >, cmp > q;
    		vector<vector<int>> ans;
    		
            //队列的初始化，将nums1中的所有数都入栈，每个数的初始指针设置为1
    		for (int i = 0; i < len1; i++) { 
    			pair<int, pair<int, int> > t(nums1[i], pair<int, int>(nums2[0] , 0));
    			q.push(t);
    		}
    
            //取前k个最小的数，每次弹出最小的一个值，同时将其指针后移一位并入栈（如果指针没有到尾的话）
    		for (int i = 0; i < k && !q.empty(); i++) { 
    			pair<int, pair<int, int> > t  = q.top();
    			q.pop();
    			vector<int> s();
    			if (flag == 0) { 
    				ans.push_back({  t.first,t.second.first });
    			}
    			else { 
    				ans.push_back({  t.second.first,t.first });
    			}
    			
    			if (t.second.second < len2 - 1) { 
    				t.second.second++;
    				t.second.first = nums2[t.second.second];
    				q.push(t);
    			}
    		}
    		return ans;
    	}
    };

1.  猜数字大小

**二分法的基础题，核心点是防止溢出**

/** * Forward declaration of guess API. * @param num your guess * @return -1 if num is lower than the guess number * 1 if num is higher than the guess number * otherwise return 0 * int guess(int num); */
    
    class Solution { 
    public:
        int guessNumber(int n) { 
            int left = 1, right = n, mid = left + (right - left) / 2;
    
            while (left <= right)
            { 
                if (guess(mid) == 0)
                    return mid;
                else if (guess(mid) < 0)
                { 
                    right = mid - 1;
                    mid = left + (right - left) / 2;
                }
                else 
                { 
                    left = mid + 1;
                    mid = left + (right - left) / 2;
                }
    
            }
            return left;
        }
    };

1.  猜数字大小2

**本题主要有以下几个要点：1. 采取动态规划的思想, dp\[i\]\[j\]表示从i到j的区域，dp\[i\]\[j\] 中选择一个猜测位置piv，则可写成**

class Solution { 
    public:
        int getMoneyAmount(int n) 
        { 
            if (n == 1) return 0;
    
            int dp[n + 1][n + 1];
    
            for(int i = 0; i <= n; i++)
            { 
                dp[i][i]=0;
            }    
    
    		// 从第二列开始
            for (int len = 2; len <= n; len++) 
            { 
            	// 从上往下或从下往上都行
                for (int start = 1; start <= n - len + 1; start++) 
                { 
                    int minres = INT_MAX;
                    for (int piv = start + (len - 1) / 2; piv < start + len - 1; piv++) 
                    { 
                        int res = piv + max(dp[start][piv - 1], dp[piv + 1][start + len - 1]);
                        minres = min(res, minres);
                    }
                    dp[start][start + len - 1] = minres;
                }
    
            }
            return dp[1][n];  
        }
    };

1.  摆动序列  
    给定一个整数序列，返回作为摆动序列的最长子序列的长度。 通过从原始序列中删除一些（也可以不删除）元素来获得子序列，剩下的元素保持其原始顺序。

**本题可采用动态规划求解，其实就是在最长上升子序列的基础上加了一个下降子序列，最后求两个的最大值即可。因此本题亦可采用贪心算法。**

class Solution { 
    public:
        int wiggleMaxLength(vector<int>& nums) 
        { 
            int n = nums.size();
            if (n < 2) return n;
            int up = 1, down = 1;
            for (int i = 1; i < n; i++) 
            { 
                if (nums[i] > nums[i - 1]) 
                { 
                    up = down + 1;
                } else if (nums[i] < nums[i - 1]) 
                { 
                    down = up + 1;
                }
            }
            return max(down, up);
        }
    };

1.  组合总和  
    给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

**简单的动态规划题**

class Solution { 
    public:
        int combinationSum4(vector<int>& nums, int target) { 
            int N = nums.size();
            if(N==0)
                return 0;
            vector<unsigned long long> dp(target+1,0);
            dp[0] = 1;
            for(int i = 1;i<=target;i++){ 
                for(int j = 0;j<N;j++){ 
                    dp[i] += ( (i-nums[j]>=0) ? dp[i-nums[j]] : 0);
                }
            }
            return dp[target];
        }
    };

1.  有序矩阵中第K小的元素  
    给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。  
    请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

**任取一个数 mid在最小数和最大数之间，那么矩阵中不大于 midmid 的数，肯定全部分布在矩阵的左上角，由此可采用二分法求解**

class Solution { 
       public:
        bool check(vector<vector<int>>& matrix, int mid, int k, int n) { 
            int i = n - 1;
            int j = 0;
            int num = 0;
            while (i >= 0 && j < n) { 
                if (matrix[i][j] <= mid) { 
                    num += i + 1;
                    j++;
                } else { 
                    i--;
                }
            }
            return num >= k;
        }
    
        int kthSmallest(vector<vector<int>>& matrix, int k) { 
            int n = matrix.size();
            int left = matrix[0][0];
            int right = matrix[n - 1][n - 1];
            while (left < right) { 
                int mid = left + ((right - left) >> 1);
                if (check(matrix, mid, k, n)) { 
                    right = mid;
                } else { 
                    left = mid + 1;
                }
            }
            return left;
        }
    };