date: 2020/01/22

050Pow(x,n)(中等)

https://leetcode-cn.com/problems/powx-n

double myPow(double x, int n) {
    double result = 1.f;
    if(n < 0){
        n = -n;
        x = 1.f / x;
    }
    for(int i = 0; i < n; i++)
        result *= x;
    return result;
}

函数栈中包含的中间结果

double helper(double x, long n){
    if(n == 1)
        return x;
    else if(n % 2 == 0)
        return myPow(x*x, n/2);
    else
        return myPow(x*x, n/2) * x;
}

double myPow(double x, long n) {
    if(n == 0)
        return 1.f;
    if(n < 0){
        n = -n;
        x = 1.f / x;
    }
    return helper(x, n);
}

每次直接累计起来就行,不需要保存的中间结果

double myPow(double x, long n) {
    if(n == 0) return 1.f;
    if(n < 0){
        n = -n;
        x = 1.f / x;
    }
    double ans = 1.f;
    while(n != 0){
        if((n & 1) == 1)
            ans = ans * x;
        x = x * x;
        n >>= 1;
    }
    return ans;
}
long myPow(long x, long n, long m) {
    if(n == 0) return 1;
    long ans = 1;
    while(n != 0){
        if((n & 1) == 1)
            ans = ((ans % m) * (x % m)) % m;
        x = ((x % m) * (x % m)) % m;
        n >>= 1;
    }
    return ans;
}


169多数元素(简单)

https://leetcode-cn.com/problems/majority-element

注意:这里的“多数”并不是众数,“多数”在数组中的数量大于(n为数组长度),正是这一限制,才使得分治法和投票法能生效。


int majorityElement(vector<int>& nums) {
    unordered_map<int, int> counter;
    for(int i = 0; i < nums.size(); i++)
        counter[nums[i]]++;

    int max_num, max_counter = INT_MIN;
    for(unordered_map<int, int>::iterator it = counter.begin(); it != counter.end(); it++){
        if(it->second > max_counter){
            max_counter = it->second;
            max_num = it->first;
        }
    }
    return max_num;
}
int helper(vector<int>& nums, int left, int right){
    // 终止条件
    if(left == right)
        return nums[left];
    // 递归判断
    int middle = (left + right) / 2;
    int left_majority = helper(nums, left, middle);  // 左子数组的“多数”
    int right_majority = helper(nums, middle + 1, right);   // 右子数组的“多数”
    // 同一个“多数”,直接返回
    if(left_majority == right_majority)
        return left_majority;
    // “多数”不同,则分别计数确定真正的“多数”
    int count1 = 0, count2 = 0;
    for(int i = left; i <= right; i++){
        if(nums[i] == left_majority)
            count1++;
        else if(nums[i] == right_majority)
            count2++;
    }
    return (count1 > count2) ? left_majority : right_majority;
}

int majorityElement(vector<int>& nums) {
    return helper(nums, 0, nums.size() - 1);
}
int majorityElement(vector<int>& nums) {
    int counter = 1;
    int cand = nums[0];

    for(int i = 1; i < nums.size(); i++){
        if(counter == 0){
            cand = nums[i];
            counter = 1;
        }else if(nums[i] == cand){
            counter++;
        }else{
            counter--;
        }
    }

    return cand;
}


053最大子序列和(简单)

https://leetcode-cn.com/problems/maximum-subarray

// 计算横跨左右子数组(nums[a:b], 其中a<=p, b>p)的最大序列
int middle_sum(vector<int>& nums, int left, int right, int mid){
    if(left == right)
        return nums[left];
    // 计算左子数组的最大后缀序列和
    int cur_sum = 0;
    int left_sum = INT_MIN;
    for(int i = mid; i >= left; i--){
        cur_sum += nums[i];
        if(cur_sum > left_sum)
            left_sum = cur_sum;
    }
    // 计算右子数组的最大前缀序列和
    cur_sum = 0;
    int right_sum = INT_MIN;
    for(int i = mid + 1; i <= right; i++){
        cur_sum += nums[i];
        if(cur_sum > right_sum)
            right_sum = cur_sum;
    }
    // 返回合并后的最大和
    return left_sum + right_sum;
}

int helper(vector<int>& nums, int left, int right){
    if(left == right)
        return nums[left];

    int mid = (left + right) / 2;
    int left_max = helper(nums, left, mid);   // 左子数组的最大和
    int right_max = helper(nums, mid + 1, right);   // 右子数组的最大和
    int middle_max = middle_sum(nums, left, right, mid);    // 横跨左右子数组的最大和

    return max(max(left_max, right_max), middle_max);
}

int maxSubArray(vector<int>& nums) {
    return helper(nums, 0, nums.size() - 1);
}

思路很简单,一次遍历,如果前序序列和是负数会对后续带来减益效果,不如丢弃

// 考虑特殊情况:整个数组的元素均为负数
// 事实上这段代码依旧能正常工作,sum值按数组的元素依次变化,恰好退化成寻找数组最大值问题
int maxSubArray(vector<int>& nums) {
    int sum = nums[0], max = nums[0];
    for(int i = 1; i < nums.size(); i++){
        sum = nums[i] + max(sum, 0);
        if(sum > max)
            max = sum;
    }
    return max;
}


"022括号生成(中等)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#T80ua


"051N皇后(困难)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#ocRrB


"052N皇后II(困难)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#fzGDl


"036有效数独(中等)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#M73u3


"037解数独(困难)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-dfs_bfs#BeiRC


"079单词搜索(中等)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/trie#U4Ro8


"212单词搜索II(困难)

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/trie#HCuOD


"面试题07重建二叉树

此处为语雀文档,点击链接查看:https://www.yuque.com/yahei/hey-yahei/leetcode-tree#TVDLs


面试题51数组中的逆序对(困难)

https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof

分治排序,时间O(nlogn)空间O(n)

int reversePairs(vector<int>& nums, int left, int right) {
    if(left >= right)
        return 0;

    int mid = (left + right) / 2;
    int res = reversePairs(nums, left, mid) + reversePairs(nums, mid + 1, right);
    
    // 归并
    int tmp[right - left + 1];
    int idx_tmp = 0, idx_left = left, idx_right = mid + 1;
    while(idx_left <= mid && idx_right <= right){
        if(nums[idx_left] <= nums[idx_right]){
            tmp[idx_tmp++] = nums[idx_left++];
        }else{
            tmp[idx_tmp++] = nums[idx_right++];
            res += mid - idx_left + 1;      // 逆序对增量
        }
    }
    // 处理左子集、右子集的剩余元素
    for(int j = idx_left; j <= mid; j++)
        tmp[idx_tmp++] = nums[j];
    for(int j = idx_right; j <= right; j++)
        tmp[idx_tmp++] = nums[j];
    // 拷贝回原始数组中
    for(int i = 0; i < right - left + 1; i++)
        nums[left + i] = tmp[i];
    return res;
}

int reversePairs(vector<int>& nums) {
    return reversePairs(nums, 0, nums.size() - 1);
}


面试题62 约瑟夫环-圆圈最后剩下的数字(简单)

https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof

int lastRemaining(int n, int m) {
    if(n == 1)
        return 0;
    return (lastRemaining(n-1, m) + m) % n;
}
int lastRemaining(int n, int m) {
    int res = 0;
    for(int i = 1; i <= n; i++)
        res = (res + m) % i;
    return res;
}