题目编号： 26、27、28、35、38、53、58、66、67、69、70、83 26.删除排序数组中的重复项： 我的解法： 设置一个偏移量变量Offset用来记录重复的元素个数，length记录不重复的元素。遍历一次数组，若当前元素与下一个元素相同，则偏移量Offset加一；若当前元素与下一个元素不同，则Offset不变，length加一；循环每执行一次当前元素向前移动Offset位，即可实现覆盖重复元素。
class Solution(object): def removeDuplicates(self, nums): """ :type nums: List[int] :rtype: int """ Offset = 0 length = 0 for i in range(len(nums)): if i == 0: max = nums[i] length += 1 if i != 0: if nums[i] <= max: Offset += 1 if nums[i] > max: max = nums[i] nums[i-Offset] = nums[i] length += 1 return length题解思路： 双指针法： 数组完成排序后，我们可以放置两个指针 i 和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i]=nums[j]，我们就增加 j 以跳过重复项。当我们遇到 nums[j]≠nums[i]时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i+1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。 27.移除元素： 我的解法：思路同26题
class Solution(object): def removeElement(self, nums, val): """ :type nums: List[int] :type val: int :rtype: int """ Offset = 0 length = 0 for i in range(len(nums)): if nums[i] == val: Offset += 1 else: length += 1 nums[i-Offset] = nums[i] return length题解思路：同26题双指针法
28.实现strStr()： 我的解法： 一开始的解法为暴力法，双重循环，但结果超时，后使用python内置函数 暴力法：
class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ len_H = len(haystack) len_N = len(needle) if len_N == 0: return 0 if len_H < len_N: return -1 for i in range(0,len_H): length = 0 if haystack[i] == needle[0]: for j in range(0,len_N): if i+len_N-1 >= len_H: break if haystack[i+j] == needle[j]: length += 1 if length == len_N: return i return -1find()函数寻找子串：
class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ return haystack.find(needle)题解思路：KMP算法 一个比较有趣的KMP算法讲解
35. 搜索插入位置 我的解法： 采用二分查找，若找到对应元素，则返回其位置，若未找到对应元素，则返回查找最后的left指向位置，即为插入元素应该插入有序序列的位置
class Solution(object): def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ length = len(nums) left = 0 right = length - 1 if target < nums[0]: return 0 if target > nums[right]: return length while(left <= right): mid = (left + right)/2 if nums[mid] > target: right = mid - 1 if nums[mid] < target: left = mid + 1 if nums[mid] == target: return mid return left题解思路：二分查找 38. 报数 我的解法： 所求结果为外观数列，初始时设置一个计数变量count为1，用来记录当前数值的个数，定义一个buffer缓冲变量，用来记录当前数值生成的外观数列的对应项，每当外观数列进入下一项时，buffer重新置为空，count置为初始值1，并将旧的buffer值添加到结果串中，符合人的直观思想
class Solution(object): def countAndSay(self, n): """ :type n: int :rtype: str """ res = '1' buf = '' while(n-1): count = 1 for i in range(len(res)): if i+1 == len(res): buf = buf + str(count) + str(res[i]) break if res[i] == res[i+1]: count += 1 continue elif res[i] != res[i+1]: buf = buf + str(count) + str(res[i]) count = 1 continue res = buf buf = '' n -= 1 return res题解思路： 先设置上一人为’1’ 开始外循环 每次外循环先置下一人为空字符串，置待处理的字符num为上一人的第一位，置记录出现的次数为1 开始内循环，遍历上一人的数，如果数是和num一致，则count增加。 若不一致，则将count和num一同添加到next_person报的数中，同时更新num和count 别忘了更新next_person的最后两个数为上一个人最后一个字符以及其出现次数
class Solution: def countAndSay(self, n: int) -> str: prev_person = '1' for i in range(1,n): next_person, num, count = '', prev_person[0], 1 for j in range(1,len(prev_person)): if prev_person[j] == num:count += 1 else: next_person += str(count) + num num = prev_person[j] count = 1 next_person += str(count) + num prev_person = next_person return prev_person53. 最大子序和 我的解法： tmp记录当前子串，若是tmp+nums[i]>tmp，说明继续向下寻找有可能是最大字串，则当前Max记录为当前串的值；反之，则从当前Max，tmp，nums[i]，tmp+nums[i]中选出最大值赋给Max，并把当前最大子串赋值为nums[i]，继续向下寻找
class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ tmp = nums[0] Max = nums[0] for i in range(1,len(nums)): if tmp + nums[i] > nums[i]: Max = max(tmp+nums[i],Max) tmp = tmp + nums[i] else: Max = max(Max,tmp,nums[i],tmp+nums[i]) tmp = nums[i] return Max题解思路： 动态规划： 动态规划题解
58. 最后一个单词的长度 我的解法： 先把字符串最后的空格去掉，然后从后往前遍历，不是空格长度加一，遇到第一个空格退出循环，并返回长度
class Solution(object): def lengthOfLastWord(self, s): """ :type s: str :rtype: int """ if len(s) == 0: return 0 length = 0 s = s.rstrip() for i in range(len(s)-1,-1,-1): if s[i].isspace(): break length += 1 return length66. 加一 我的解法： 先将数字转成字符串，拼接起来，将拼接的结果转成int并加一，再将所得到的int值转成结果所需要的形式即可
class Solution(object): def plusOne(self, digits): """ :type digits: List[int] :rtype: List[int] """ Str = '' res = [] for i in range(0,len(digits)): Str += str(digits[i]) val = int(Str) + 1 Str = str(val) for i in range(0,len(Str)): res.append(Str[i]) return res67. 二进制求和 我的解法： 手写实现函数str转十进制和十进制转二进制
def str2ten(Str): res = 0 for i in range(0,len(Str)): res += int(Str[i])*pow(2,len(Str)-1-i) return res def ten2binary(value): print("value:",value) if value == 0: return '0' Str = '' while(1): if value == 0: break mod = value%2 Str += str(mod) value /= 2 string = '' for i in range(0,len(Str)): string += Str[len(Str)-1-i] return string class Solution(object): def addBinary(self, a, b): """ :type a: str :type b: str :rtype: str """ A = str2ten(a) B = str2ten(b) Res = ten2binary(A+B) print("Res:",Res) return Res69. x 的平方根 我的解法： 采用折半查找法，在0~x的整数范围内寻找，若查找到合适的整数，则返回该值，若折半查找未找到该值，则返回结束时的位置向左一位，即为平方根的向下取整
class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """ left = 0 right = x while(left<=right): mid = (left + right)/2 if pow(mid,2) == x: return mid elif pow(mid,2) < x: left = mid + 1 elif pow(mid,2) > x: right = mid - 1 return left - 1题解思路： 二分查找+牛顿法 牛顿法： 使用牛顿法可以得到一个正实数的算术平方根，因为题目中说“结果只保留整数部分”，因此，我们把使用牛顿法得到的浮点数转换为整数即可。 在迭代过程中，以直线代替曲线，用一阶泰勒展式（即在当前点的切线）代替原曲线，求直线与 xxx 轴的交点，重复这个过程直到收敛。
70. 爬楼梯 我的解法： 斐波那契数列，递归解决超时，使用动态规划解决
class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ if n == 1: return 1 if n == 2: return 2 dp = [] dp.append(1) dp.append(2) for i in range(2,n): dp.append(dp[i-1] + dp[i-2]) return dp[n-1]题解思路： 斐波那契数 Fib(n)=Fib(n−1)+Fib(n−2)
public class Solution { public int climbStairs(int n) { if (n == 1) { return 1; } int first = 1; int second = 2; for (int i = 3; i <= n; i++) { int third = first + second; first = second; second = third; } return second; } }83. 删除排序链表中的重复元素 我的解法： 定义一个指针，从head开始往后遍历，若指针的值与next的值相同，则删除该节点即可，需要注意的是避免出现越界问题，对next为空的情况单独判断
# Definition for singly-linked list. # class ListNode(object): # def __init__(self, x): # self.val = x # self.next = None class Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ NewHead = head temp = head while temp and temp.next: if temp.val == temp.next.val: temp.next = temp.next.next else: temp = temp.next return NewHead