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

题目解析

代码实现

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

题目分析

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

代码实现

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存放大于等于指定数字的链表部分。然后把他们拼接起来。

代码实现