LeetCode 题目

尽量一天更新一道题。

PS:代码是自己做完后经过查看优代码修改后的代码。

1. 题目 :Two Sum

题意：给你一个n个数的数组A[ ] 和一个数值target，在数组中找到两个加起来等于target的元素的位置。注意：位置下标从1开始的。

解题思路：

1. vector + map/hash_map（hash_map可能更好点，但是有的编译器不支持），复杂度： O(nlogn)；
2. 先对数组排序，然后用两个指针，一个指针 st 指向开始，一个指针 end 指向结尾，计算两个指针指向的值的和，如果大于目标值 target ，则end--，如果小于st++，等于则记录返回。复杂度：O(n)；

（1）代码

2.题目：Add Two Numbers

解题思路：属于胡搞一类的吧，so easy！

代码

3.题目：Longest Substring Without Repeating Characters

解题思路：这题主要保持两类记录值就可以，一个是以字符下标为索引的最新下标（这里的下标是字符串中的下标，有点绕，），另一个是所有字符下标的最大值，不断更新这两类坐标最可以了，同时不断计算保存答案。说白了还是一道想法题。

代码

4.题目：Median of Two Sorted Arrays

解题思路：挺好的一道题，解题思路在代码中。

代码

6.题目：ZigZag Conversion

解题思路：第5题先放一下，本题是一道找规律的题目，具体的解析在代码中。

代码

14.题目：Longest Common Prefix

题意：写一个函数来寻找一个字符串数组中的最长公共前缀。

解题思路：以第一个字符串为标准，依次判断与每个字符串的第i个字符是否相等，如果当前字符串的长度为i（i的取值从0开始）或者当前字符串的字符不和第一个字符串的字符相等，则返回先前记录的长度，否则继续比较第i+1个字符是否相等。

代码

15.题目：3Sum

题意：给定一组数，找出3个数a，b，c，使得a + b + c = 0，找出的三元组不能重复。

解题思路：先对数组排序，然后依次设定每一个数为target = - 当前数，然后就想2Sum一样处理，去找另外的两个数，时间复杂度为O(n^2)；

代码

20.题目：Valid Parentheses

题意：验证括号是否能正常闭合，如“()[]{}”是可以正常闭合的，但“(]”就是不正常的。

解题思路：顺手A掉这题，老掉牙的题目，具体题目解析在代码中。

代码

21.题目： Merge Two Sorted Lists

解题思路：主要考归并思想，具体题目解析在代码中。

代码

70.题目：Climbing Stairs

题意：有n级楼梯，你一次可以爬一级或两级，问爬上n级楼梯有多少种爬法。

解题思路：典型的斐波那契数列。 当然用DP的思想来的话：dp[ i ] = dp[i - 1] + dp[i - 2];

代码 

98.题目：Validate Binary Search Tree

题意：判断一颗二叉树是否是二叉排序树。

解题思路：二叉排序树中序遍历后是有序的，采用中序遍历，访问当前节点的时候，当前节点的值是否大于前一个节点的值（如果有的话），如果小于则不是二叉排序树。

代码

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/76710644