小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

[leetcode]题目解析(190610)

2019年6月10日 873点热度 0人点赞 0条评论

Edit distance(dynamic programing)

题目描述

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)You have the following 3 operations permitted on a word:a) Insert a character
b) Delete a character
c) Replace a character

题目解析

代码实现

int min3(int a, int b, int c)
{
    return (a < b) ? (a < c ? a : c) : (b < c ? b : c);
}
int minDistance(string word1, string word2) {
    //准备工作:获取字符串长度
    int strlen1 = word1.size();
    int strlen2 = word2.size();
    //准备工作:新建dp矩阵
    vector<vector<int> >dp(strlen1 + 1, vector<int>(strlen2 + 1, 0));
    //第一步:第一行,第一列分别置i
    for (int i = 1; i <= strlen1; i++)
        dp[i][0] = i;
    for (int i = 1; i <= strlen2; i++)
        dp[0][i] = i;
    //第二步:双层for循环进行递推
    for (int i = 1; i <= strlen1; i++)
    {
        for (int j = 1; j <= strlen2; j++)
        {
            int diff;
            if (word1[i - 1] == word2[j - 1])
                diff = 0;
            else
                diff = 1;
            dp[i][j] = min3(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + diff);

        }
    }
    return dp[strlen1][strlen2];
}

Add two numbers

题目描述

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

题目分析

链表版的两个数相加的题,题目是从个位到十位到百位……因此还是比较简单。

代码实现

ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;
    ListNode *result=new ListNode(-1);
    ListNode *p1 = l1;
    ListNode *p2 = l2;
    ListNode *p = result;
    int v = 0;
    int jin = 0;
    while (p1 != NULL || p2 != NULL||jin)
    {
        v = (p1 ? p1->val : 0) + (p2 ? p2->val : 0) + jin;
        jin = v / 10;
        v %= 10;
        ListNode *newnode = new ListNode(v);
        p->next = newnode;
        p = p->next;
        if (p1)
            p1 = p1->next;
        if (p2)
            p2 = p2->next;
    }
    return result->next;
}

partition list

题目描述

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.You should preserve the original relative order of the nodes in each of the two partitions.For example,
Given1->4->3->2->5->2and x = 3,
return1->2->2->4->3->5.

题目解析

最简单的方法,新建两个链表l1和l2,l1存放小于指定数字的链表部分,l2存放大于等于指定数字的链表部分。然后把他们拼接起来。

代码实现

ListNode *partition(ListNode *head, int x)
{
    ListNode *plist1 = new ListNode(0);
    ListNode *plist2 = new ListNode(0);
    ListNode *list1 = plist1;
    ListNode *list2 = plist2;
    while (head != NULL)
    {
        if (head->val < x)
        {
            ListNode *newnode = new ListNode(0);
            newnode->val = head->val;
            newnode->next = NULL;
            list1->next = newnode;
            list1 = list1->next;
        }
        else if (head->val >= x)
        {
            ListNode *bignode = new ListNode(0);
            bignode->val = head->val;
            bignode->next = NULL;
            list2->next = bignode;
            list2 = list2->next;
        }
        head = head->next;
    }
    list1->next = plist2->next;
    plist2->next = NULL;
    return plist1->next;
}
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年6月10日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
一雪前耻,《PES2010》世界杯巴西队12:0血洗荷兰队 第一次在手机发日志 评评95后、96后 今天距离中考还有2天 leetcode之single-number-ii、Gas station、word break S.V Beijing Travel 17:Miss the day
标签聚合
算法 Java python学习 Python linux 鸟哥的linux私房菜 生活 leetcode 高中 学习
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号