【Leetcode Sheet】Weekly Practice 2

这篇具有很好参考价值的文章主要介绍了【Leetcode Sheet】Weekly Practice 2。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

Leetcode Test

1281 整数的各位积和之差(8.9)

给你一个整数 n,请你帮忙计算并返回该整数「各位数字之积」与「各位数字之和」的差。

提示:

  • 1 <= n <= 10^5

【原始代码】:

int subtractProductAndSum(int n){
    //1 <= n <= 10^5
    //except 100000, there're 5 bits
    if(n==100000){
        return -1;
    }
    int bits[5]={0,0,0,0,0,0};
    int cnt=0;
    while(n>0){
        bits[cnt++]=n%10;
        n/=10;
    }
    int multi=1,sum=0;
    for(int i=0;i<cnt;i++){
        multi*=bits[i];
        sum+=bits[i];
    }
    return (multi-sum);
}

【优化代码】

int subtractProductAndSum(int n) {
    int m = 1, s = 0;	//m是乘积,sum是求和
    while (n) {	//当n!=0时
        int x = n % 10;		//x是n的余数
        n /= 10;	//n缩小
        m *= x;		//m进行乘积
        s += x;		//s进行求和
    }
    return m - s;	//返回 乘积-求和
}
//减少位数的存储,空间复杂度为O(1)
//时间复杂度仍然为O(m),m为n的位数

【其他思路】

将n转为字符串,例如n是1234,则char temp=‘1234’

后续直接遍历strlen(temp),计算temp[i]-'0’的值即可

1289 下降路径最小和 II(8.10)

给你一个 n x n 整数矩阵 grid ,请你返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为:从 grid 数组中的每一行选择一个数字,且按顺序选出来的数字中,相邻数字不在原数组的同一列。

提示:

  • n == grid.length == grid[i].length
  • 1 <= n <= 200
  • -99 <= grid[i][j] <= 99
int minFallingPathSum(int** grid, int gridSize, int* gridColSize) {
    int first_min_sum = 0;
    int second_min_sum = 0;
    int first_min_index = -1;
    
    for (int i = 0; i < gridSize; i++) {    //遍历外层
        int cur_first_min_sum = INT_MAX;    //记录最小值
        int cur_second_min_sum = INT_MAX;   //记录次小值
        int cur_first_min_index = -1;   //记录最小值列编号
        for (int j = 0; j < gridSize; j++) {    //遍历内层
            int cur_sum = (j != first_min_index ? first_min_sum : second_min_sum) + grid[i][j];
            //当前求和计算,如果j和最小值列编号不一样,则添加最小值,否则添加次小值
            if (cur_sum < cur_first_min_sum) {  //如果当前求和,小于最小
                cur_second_min_sum = cur_first_min_sum;     //更新次小为之前的最小
                cur_first_min_sum = cur_sum;    //更新最小为当前的求和
                cur_first_min_index = j;    //更新比列编号
            } else if (cur_sum < cur_second_min_sum) {  //如果当前求和,小于次小
                cur_second_min_sum = cur_sum;   //更新次小为当前的求和
            }
        }
        first_min_sum = cur_first_min_sum;  //更新最小
        second_min_sum = cur_second_min_sum;    //更新次小
        first_min_index = cur_first_min_index;  ///更新列编号
    }
    return first_min_sum;
}

1572 矩阵对角线元素的和(8.11)

给你一个正方形矩阵 mat,请你返回矩阵对角线元素的和。

请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

提示:

  • n == mat.length == mat[i].length
  • 1 <= n <= 100
  • 1 <= mat[i][j] <= 100
int diagonalSum(int** mat, int matSize, int* matColSize){
    //n x n matrix
    int n=matSize,sum=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if((i==j)||(i+j==n-1)){    
                //i==j 主对角线;i+j==n-1 次对角线
                sum+=mat[i][j];
            }
        }
    }
    return sum;
}

2681 英雄的力量(8.1补)

给你一个下标从 0 开始的整数数组 nums ,它表示英雄的能力值。如果我们选出一部分英雄,这组英雄的 力量 定义为:

  • i0i1 ,… ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 max(nums[i0],nums[i1] ... nums[ik])2 * min(nums[i0],nums[i1] ... nums[ik])

请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大,请你将结果对 109 + 7 取余。

提示:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
int cmp(void *a,void *b){
    return *(int*)a-*(int*)b;
}

int sumOfPower(int* nums, int numsSize){
    qsort(nums,numsSize,sizeof(int),cmp);   
    //元素的顺序不影响答案,先排序
    //power = max*max*min
    int dp = 0, preSum = 0;
    int res = 0, mod = 1e9 + 7;
    for (int i = 0; i < numsSize; i++) {
        dp = (nums[i] + preSum) % mod;
        preSum = (preSum + dp) % mod;
        res = (int) ((res + (long long) nums[i] * nums[i] % mod * dp) % mod);
        if (res < 0) {
            res += mod;
        }
    }
    return res;
}

23 合并K个升序链表(8.12)

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

提示:

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i]升序 排列
  • lists[i].length 的总和不超过 10^4
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

int cmp(const void * a, const void * b)//升序子函数
{
    return *(int *)a - *(int *)b;
}
struct ListNode* mergeKLists(struct ListNode** lists, int listsSize){
    if(listsSize == 0 )
    {
        return NULL;
    }
    int ans[10000];//临时保存链表值
    int node = 0;
    for(int i = 0; i <listsSize; i++)//保存所有链表值
    {
        while(lists[i])
        {
            ans[node++] = lists[i]->val;
            lists[i] = lists[i]->next;
        }
    }
    qsort(ans, node, sizeof(int), cmp);//排序
    struct ListNode * h = NULL;
    struct ListNode * root = NULL;
    for(int i = 0; i < node; i++)//转换为链表存储
    {
        struct ListNode * r = malloc(sizeof(struct ListNode));
        r->val = ans[i];
        r->next = NULL;
        if(root == NULL)
        {
            h = r;
            root = r;
        }
        else
        {
            h->next = r;
            h = r;
        }  
    }
    return root;
}

88 合并两个有序数组(8.13)

给你两个按 非递减顺序 排列的整数数组 nums1nums2,另有两个整数 mn ,分别表示 nums1nums2 中的元素数目。

请你 合并 nums2nums1 中,使合并后的数组同样按 非递减顺序 排列。

**注意:**最终,合并后数组不应由函数返回,而是存储在数组 nums1 中。为了应对这种情况,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n

提示:

  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109
int cmp(void *a,void *b){
    return *(int*)a-*(int*)b;
}

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int cnt=0,i=m;
    while(cnt<n){
        nums1[i++]=nums2[cnt++];
    }
    qsort(nums1,(n+m),sizeof(int),cmp);
}

a former method

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    for(int i=0;i!=n;i++){
        nums1[m+i]=nums2[i];
    }
    int minno;
    for(int i=0;i<m+n-1;i++){
        minno=i;
        for(int j=i+1;j<m+n;j++){
            if(nums1[j]<nums1[minno]){
                minno=j;
            }
        }
        //找到i后面的最小数,交换i位置和minno位置
        int temp=nums1[i];
        nums1[i]=nums1[minno];
        nums1[minno]=temp;
    }
}

a new-spaced method: O(n+m) of both time and space

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int p1 = 0, p2 = 0;
    int sorted[m + n];	//new-spaced
    int cur;
    while (p1 < m || p2 < n) {
        if (p1 == m) {
            cur = nums2[p2++];
        } else if (p2 == n) {
            cur = nums1[p1++];
        } else if (nums1[p1] < nums2[p2]) {
            cur = nums1[p1++];
        } else {
            cur = nums2[p2++];
        }
        sorted[p1 + p2 - 1] = cur;
    }
    for (int i = 0; i != m + n; ++i) {
        nums1[i] = sorted[i];
    }
}

617 合并二叉树(8.14)

给你两棵二叉树: root1root2

想象一下,当你将其中一棵覆盖到另一棵之上时,两棵树上的一些节点将会重叠(而另一些不会)。你需要将这两棵树合并成一棵新二叉树。合并的规则是:如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;否则,不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

提示:

  • 两棵树中的节点数目在范围 [0, 2000]
  • -104 <= Node.val <= 104
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

//深度优先搜索 dfs
struct TreeNode* mergeTrees(struct TreeNode* root1, struct TreeNode* root2){
    //如果两个节点重叠,那么将这两个节点的值相加作为合并后节点的新值;
    //否则,不为 null 的节点将直接作为新二叉树的节点。
    if(root1 == NULL) return root2;
    else if(root2 == NULL) return root1;
    struct TreeNode* result=malloc(sizeof(struct TreeNode));
    result->val=root1->val + root2->val;
    result->left=mergeTrees(root1->left,root2->left); 	//左子树递归
    result->right=mergeTrees(root1->right,root2->right);	//右子树递归
    return result;
}

C++:

递归,直接在原root1进行修改

class Solution {
public:
    TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if (root1 && root2) {
            root1->val += root2->val;
            root1->left = mergeTrees(root1->left, root2->left);
            root1->right = mergeTrees(root1->right, root2->right);
        }
        return root1 ? root1 : root2;
    }
};

另可进行广度优先(较为复杂)文章来源地址https://www.toymoban.com/news/detail-653415.html

到了这里,关于【Leetcode Sheet】Weekly Practice 2的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 代码随想录Leetcode70. 爬楼梯

            空间复杂度为O(N),如果想要优化空间复杂度,则只用三个变量进行状态转移也可以,参考 代码随想录 Leetcode509. 斐波那契数-CSDN博客

    2024年02月19日
    浏览(82)
  • 代码随想录Leetcode 343. 整数拆分

            dp[i]表示i所能拆分的最大乘积,则dp[i] 与dp[i - 1]的递推公式是:                 max( 1~n * dp[n ~ 1])

    2024年02月21日
    浏览(85)
  • 代码随想录 Leetcode763. 划分字母区间

    2024年02月21日
    浏览(121)
  • 代码随想录 LeetCode数组篇 二分查找

    # (简单)704. 二分查找 题目链接 代码随想录 - 二分查找思路 二分查找,思路很简单,但是在while循环left和right的比较是写=还是,还有right=mid还是right=mid-1容易混淆 需要想清楚对区间的定义,是[left,right],还是[left,right) (版本一,左闭右闭版本) (版本二,左闭右开) 题目

    2024年02月02日
    浏览(57)
  • 代码随想录 Leetcode18. 四数之和

            不行了,今天做了太多n数之和要吐了,太恶心了,一堆剪枝,去重太恶心人了。最后还是照着卡哥的改

    2024年01月17日
    浏览(94)
  • 代码随想录刷题第4天|LeetCode24、LeetCode19、LeetCode160、LeetCode142

    1、LeetCode24 两两交换链表中的节点 题目链接:24、两两交换链表中的节点 要想清楚终止条件,cur每次指向要交换的两个节点的前一个节点,cur = cur-next-next; 若链表元素个数为偶数 , 则最后时刻 cur-next = NULL; 若链表元素个数为奇数,则最后时刻 cur-next-next = NULL; 最后要返回

    2024年02月05日
    浏览(47)
  • 【代码随想录 | Leetcode | 第四天】数组 | 螺旋矩阵 | 59

    欢迎来到小K的Leetcode|代码随想录|专题化专栏,今天将为大家带来螺旋矩阵的分享 ✨ 给你一个正整数 n ,生成一个包含 1 到 n 2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。 示例 1: 示例 2: 提示: 思路: 本类型题目其实都不涉及什么算法,就是模拟

    2024年02月16日
    浏览(49)
  • 代码随想录 Leetcode142. 环形链表 II

            双指针解决百分之99的链表题

    2024年01月19日
    浏览(46)
  • 【代码随想录-Leetcode第二题:27.移除元素】

    给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的 样例:示例 1: 解释:函数

    2024年02月14日
    浏览(51)
  • 代码随想录第一天 | LeetCode704.二分查找,LeetCode 27.移除元素

    数组理论基础要点: 数组也是数据结构的一种, 是存放在连续内存空间上的相同类型数据的集合。 数组注意点: 数组下标都是从0开始的。 数组内存空间的地址是连续的。 因为上述两点, 数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要

    2024年02月08日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包