Leetcode Part.1
in Study on Writeup
Leetcode Part.1
前言
最近跟学弟一起写了一些leetcode 写一部分就发到博客上记录一下吧（按难度排序的 可能有点乱）。
学弟很强一直在用C++写代码, 我之前一直在用python，感觉挺蛋疼的，因为速度实在不敢恭维，有没有算法似乎影响都不大。
后来学了些golang, 改用go写算法后,写起来舒服多了。
1. Two Sum
map和unordered_map的差别和使用 enumerate() 函数用于将一个可遍历的数据对象。
#44ms
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
record = {} #搞了个字典做缓存
for i , num in enumerate(nums): #从列表里取id和value
complement = target - num #利用target找另一半的值
if complement in record:
return [record[complement],i] ##找到了直接输出
else:
record[num] = i #找不到就塞到字典里
#使用if else比两个if节省时间
补发一个go的
//64ms慢的要死 但是内存占用还是挺低的
func twoSum(nums []int, target int) []int {
ret := []int{}
for i := range nums {
for j := i + 1; j < len(nums); j++ {
if nums[j] == (target - nums[i]) {
ret = append(ret, i, j)
}
}
}
return ret
}
//0ms 空间换时间
func twoSum(nums []int, target int) []int {
hash := make(map[int]int, len(nums))
for k, v := range nums {
if j, ok := hash[target-v]; ok {
return []int{j, k}
}
hash[v] = k
}
return nil
}
cpp的解决方案同上也是要区分map以及unordered_map，在cpp中map使用红黑树（还没看）unorderd_map 使用的就是最基本的哈希表简单、快速map.count()可以查找该数值是否存在于哈希表中。
该题中数组的value做键 value对应的index做值，此处的map与java、python中的不同，一个键可以对应多个值（其实还是就是哈希表的原理）
// 12ms 很迷 就是看运气吧，能控制在10ms~20ms之间
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> m;
vector<int> res;
for(int i = 0; i < nums.size(); i++)
{
m[nums[i]] = i;
}
for(int i = 0; i < nums.size(); i++)
{
int e = target - nums[i];
if(m.count(e) && m[e] != i)
{
res.push_back(i);
res.push_back(m[e]);
break;
}
}
return res;
}
};
// cpp速度还是快的一批
7. Reverse Integer
#32ms
class Solution:
def reverse(self, x: int) -> int:
if x > 0 :
solution = int(str(x)[::-1]) #大于0直接转成字符串反转
else :
solution = -1 * int(str(x*-1)[::-1]) #小于0就处理掉-1再补回来
min = -2**31 #根据题目要求处理溢出
max = 2**31 -1
if solution in range(min,max):
return solution
else:
return 0
0ms战神
//0ms
func reverse(x int) int {
ReverseX := 0
for x != 0{
ReverseX = ReverseX * 10 + x %10
x = x/10
if ReverseX > math.MaxInt32 || ReverseX < math.MinInt32 {
return 0
}
}
return ReverseX
}
这道题c/c++一行泪，每次遇到这种有溢出可能的就会有暴毙的可能，但是在cpp中有一个INT_MAX的存在可以弥补这个错误
// 0ms 速度血妈快 超乎你的想象
class Solution {
public:
int reverse(int x) {
int res = 0;
while(x != 0)
{
if(abs(res) > INT_MAX / 10) return 0; // 在此处对res的值进行了判断！！！
res = res*10 + x%10;
x = x / 10;
}
return res;
}
};
9. Palindrome Number
python的回文果然为所欲为
#44ms
class Solution:
def isPalindrome(self, x: int) -> bool:
return str(x) == str(x)[::-1]
补充一个go的 不知道为啥时间在0-24ms之间
//0-24ms
func isPalindrome(x int) bool {
if x < 0 {
return false
}
originalX := x
reverseX := 0
for x > 0 {
reverseX = reverseX * 10 + x % 10
x /= 10
}
return reverseX == originalX
}
这道题如果加上数学上的对称等折半可以节省时间，但是还是按照最老实的方法写了
// 24ms 这是没有任何特殊思路的算法
class Solution {
public:
bool isPalindrome(int x) {
if(x < 0) return false;
return reverse(x) == x;
}
int reverse(int x){
int rev = 0;
while(x > 0)
{
if(rev > INT_MAX / 10) return 0;
rev = rev*10 + x%10;
x /= 10;
}
return rev;
}
};
13. Roman to Integer
罗马数字的精髓
class Solution:
def romanToInt(self, s: str) -> int:
dic = {"I":1,"V":5,"X":10,"L":50,"C":100,"D":500,"M":1000}
result = 0
for i in range(len(s)-1):
if(dic[s[i]]<dic[s[i+1]]):
result-=dic[s[i]]
else:
result+=dic[s[i]]
result+=dic[s[len(s)-1]]
return result
神奇的解法 还是下面的科学一点
//0ms
func s2I(ch byte) int {
var val int = 0
switch ch {
case 'I': val = 1
case 'V': val = 5
case 'X': val = 10
case 'L': val = 50
case 'C': val = 100
case 'D': val = 500
case 'M': val = 1000
}
return val
}
func romanToInt(s string) int {
var ret int = 0
var max int = 1
for i := len(s)-1; i >= 0; i-- {
cur := s2I(s[i])
if cur >= max {
max = cur
ret += cur
} else if cur < max {
ret -= cur
}
}
return ret
}
//0ms
func romanToInt(s string) int {
mapper := map[byte]int{'I': 1, 'V': 5, 'X': 10, 'L': 50, 'C': 100, 'D': 500, 'M': 1000}
var ret int = 0
var max int = 1
for i := len(s)-1; i >= 0; i-- {
cur := mapper[s[i]]
if cur >= max {
max = cur
ret += cur
} else if cur < max {
ret -= cur
}
}
return ret
}
// 24ms 有点慢其实，是不是用枚举会快一些， 没能实现枚举好像不太行
class Solution {
public:
int romanToInt(string s) {
unordered_map<char, int> m{ {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, {'C', 100}, {'D', 500}, {'M', 1000} };
int res = 0;
for(int i = 0; i < s.length(); i++)
{
if(i == s.length() - 1 || m[s[i]] >= m[s[i+1]])
res += m[s[i]];
else
res -= m[s[i]];
}
return res;
}
};
14. Longest Common Prefix（最长共同前缀）
快不快先不说 肯定最好理解
#36ms
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
prefix=""
if len(strs)==0:
return prefix
strs.sort() #为所欲为的列表排序
for x, y in zip(strs[0], strs[-1]):#最长串和最短串比较
if x == y:
prefix+=x
else:
break
return prefix
这道题我上当了，找了半天没发现问题，后来才知道可能直接传来一个空的vector我这个就直接s
// 8ms
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if (strs.empty()) return ""; // 一定要记得判空
string res = "";
for(int j = 0; j < strs[0].size(); j++)
{
for(int i = 1; i < strs.size(); i++)
{
if(j >= strs[i].size() || strs[0][j] != strs[i][j])
{
return res;
}
}
res.push_back(strs[0][j]);
}
return res;
}
};
20. Valid Parentheses
验证括号
既然都用python了 还要什么数据结构 python的效率也就这样了吧
#44ms 懒就完事了
class Solution:
def isValid(self, s: str) -> bool:
while "()" in s or "{}" in s or '[]' in s:
s = s.replace("()", "").replace('{}', "").replace('[]', "")
return s == ''
#28ms-32ms 提升不大。。。徒增大脑功耗
class Solution:
def isValid(self, s: str) -> bool:
bracket_map = {"(": ")", "[": "]", "{": "}"}
open_par = set(["(", "[", "{"])
stack = []
for i in s:
if i in open_par:
stack.append(i)
elif stack and i == bracket_map[stack[-1]]:
stack.pop()
else:
return False
return stack == []
这道题终于看到一点数据结构了，这里用到了栈，标准的判断括号的方法，但是最后一步返回是否为空非常考验题感 ```cpp // 0ms class Solution { public:
bool isValid(string s) {
stack<char> sk;
for(int i = 0; i < s.length(); i++)
{
char temp = s[i];
if(temp == '(' || temp == '{' || temp == '[') sk.push(temp);
else
{
if(sk.empty()) return false;
if(temp == ')' && sk.top() != '(') return false;
if(temp == '}' && sk.top() != '{') return false;
if(temp == ']' && sk.top() != '[') return false;
sk.pop();
}
}
return sk.empty();
} }; ``` ## 21. Merge Two Sorted Lists 我觉得 我在python里用链表好蠢 略过略过。。。 ```python ``` 混合插入有序链表
这道题我的办法有点笨，还是沿用的学数据结构的方法 ```cpp // 解法1 12ms 本意是节省一些空间，不过似乎用的空间还是挺大的 class Solution { public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
ListNode* pre,* current,* in,* res;
if(l1->val <= l2->val)
{
pre = l1;
current = l1;
in = l2;
res = l1;
}
else
{
pre = l2;
current = l2;
in = l1;
res = l2;
}
while(in != nullptr)
{
while(current != nullptr)
{
if(in->val < current->val)
{
ListNode* temp = in;
in = in->next;
temp->next = pre->next;
pre->next = temp;
pre = temp;
break;
}
else
{
if(pre != current) pre = pre->next;
current = current->next;
}
}
if(current == nullptr)
{
pre->next = in;
break;
}
}
return res;
} };
// 解法二 4ms 以空间换时间 class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if(!l1) return l2; if(!l2) return l1; ListNode* res =new ListNode(-1); ListNode* cur = res; while(l1 && l2) { if(l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 ? l1 : l2; return res->next; } };
## 26. Remove Duplicates from Sorted Array
我发现了 咱们俩 根本不在一个世界
```python
#84ms 这个据说快极限了
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
len_ = 1
if len(nums)==0:
return 0
for i in range(1,len(nums)):
if nums[i] != nums[i-1]:
nums[len_] = nums[i]
len_ +=1
return len_
这道题我觉得保持O(1)的内存是没有太大意义的，所以选择开辟一个栈来进行过滤其实用队列更好
// 20ms
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
stack<int> s;
int length;
for(int i = 0; i < nums.size(); i++)
{
int t = nums[i];
if(s.empty()) s.push(t);
if(s.top() != t) s.push(t);
}
length = s.size();
for(int i = length -1; i >= 0; i--)
{
nums[i] = s.top();
s.pop();
}
return length;
}
};
27. Remove Element
这道题和上一道题的要求一致，都要求不能使用多余的空间，但是我还是使用了一个队列进行过滤
// 4ms
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
queue<int> q;
for(int i = 0; i < nums.size(); i++)
{
if(nums[i] != val) q.push(nums[i]);
}
int length = 0;
while(!q.empty())
{
nums[length++] = q.front();
q.pop();
}
return length;
}
};
我也有了0ms的一天了
//0ms
func removeElement(nums []int, val int) int {
i :=0
for idx, _ := range nums {
if nums[idx] != val{
nums[i] = nums[idx]
i++
}
}
return i
}
28. Implement strStr()
此题我一开始想的是会不会要求我使用KMP这一类算法，后来用的bp最垃圾的匹配算法竟然也通过了= =
// 4ms
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
int h, n;
if(h < n) return -1;
h = haystack.length();
n = needle.length();
int i = 0;
for(i = 0; i <= h - n; i++)
{
int j = 0;
for(j = 0; j < n; j++)
{
if(haystack[i+j] != needle[j]) break;
}
if(j == n) return i;
}
return -1;
}
};
我怀疑leetcode的golang时间检测有问题 咋万物皆可0ms
这是刚学go的时候写的 其实就是go本身比较快
//0ms
func strStr(haystack string, needle string) int {
if needle == "" {
return 0
}
hl := len(haystack)
nl := len(needle)
for i := 0; i <= hl-nl; i++ {
for j := 0; j < nl; j++ {
if needle[j] != haystack[i+j] {
break
}
if j == nl-1 {
return i
}
}
}
return -1
}
2. Add Two Numbers
两数之和，以链表的形式相加
这道题我的代码只能用屎来形容，逻辑问题特别大，写的时候就出现了边界值混乱等问题 ```cpp // 60ms class Solution { public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(!l1) return l2;
if(!l2) return l1;
ListNode* res = new ListNode(-1);
ListNode* cur = res;
int flag = 0;
while(l1 && l2)
{
int t = l1->val + l2->val + flag;
flag = 0;
if(t >= 10)
{
flag = t/10;
t %= 10;
}
ListNode* np = new ListNode(t);
cur->next = np;
cur = cur->next;
l1 = l1->next;
l2 = l2->next;
}
if(flag == 0)
{
cur->next = l1 ? l1 : l2;
}
while(flag != 0)
{
if(l1 != nullptr && l2 == nullptr)
{
cur->next = l1;
l1 = nullptr;
cur->next->val += flag;
flag = 0;
}
else if(l1 == nullptr && l2 != nullptr)
{
cur->next = l2;
l2 = nullptr;
cur->next->val += flag;
flag = 0;
}
else if(l1 == nullptr && l2 == nullptr)
{
if(cur->next)
{
cur->next->val += flag;
}
else
{
cur->next = new ListNode(flag);
}
flag = 0;
}
cur = cur->next;
if(cur->val >= 10)
{
flag = cur->val / 10;
cur->val %= 10;
}
}
return res->next;
} };
// 解法2 64ms 代码可读性大大提高… class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* res = new ListNode(-1); ListNode* cur = res; int carry = 0; while(l1 || l2) { int val_1, val_2, temp; val_1 = l1 ? l1->val : 0; val_2 = l2 ? l2->val : 0; temp = val_1 + val_2 + carry; carry = temp / 10; temp %= 10; cur->next = new ListNode(temp); cur = cur->next; if(l1) l1 = l1->next; if(l2) l2 = l2->next; } if(carry) { cur->next = new ListNode(carry); } return res->next; } };
快
```go
//12ms
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{0, nil}
current := head
carry := 0
for l1 != nil || l2 != nil || carry > 0 {
sum := carry
if l1 != nil {
sum += l1.Val
l1 = l1.Next
}
if l2 != nil {
sum += l2.Val
l2 = l2.Next
}
carry = sum / 10
current.Next = new(ListNode)
current.Next.Val = sum % 10
current = current.Next
}
return head.Next
}
3. Longest Substring Without Repeating Characters
我建议滑着走（手动狗头
思路类似于一个滑块，从头滑到尾，每当滑块内的内容再后面右边界出现时，就把滑块的左边界移到前面该内容处
// 32ms
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
int length = s.length();
int left = -1;
unordered_map<int,int> m;
for(int i = 0; i < length; i++)
{
if(m.count(s[i]) && m[s[i]] > left)
{
left = m[s[i]];
}
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
请允许我引战 一毛一样的代码 go4ms
//4ms
func lengthOfLongestSubstring(s string) int {
m := make(map[rune]int)
left := -1
maxLength := 0
for i, v := range s {
if _, ok := m[v]; ok && m[v] > left {
left = m[v]
}
m[v] = i
if i-left > maxLength {
maxLength = i - left
}
}
return maxLength
}
5. Longest Palindromic Substring
cpp的做法是回文段分奇数长度、偶数长度，对着两种都进行同一位置的从中往左右两边展开
// 80ms 果然没有经过任何数学优化的算法都比较慢
class Solution {
public:
string longestPalindrome(string s) {
int res = 0;
int maxlen = 0;
int start = 0;
int n = s.length();
for(int i = 0; i < n; i++)
{
current_palindromic(s, i, i, start, maxlen);
current_palindromic(s, i, i+1, start, maxlen);
res = res > maxlen ? res : maxlen;
}
return s.substr(start, res);
}
void current_palindromic(string s, int left, int right, int& start, int& maxlen)
{
while(left >= 0 && right < s.length() && s[left] == s[right])
{
left--;
right++;
}
if(maxlen < right - left - 1)
{
maxlen = right - left - 1;
start = left + 1;
}
}
};
又到了我抄思路的时候了 用#把字符串统一处理成奇数 然后从中心向两边开始查 这个好拉跨。。。
//32ms
func longestPalindrome(s string) string {
slice := make([]string, 0, 4)
for _, v := range s {
slice = append(slice, "#")
slice = append(slice, string(v))
}
slice = append(slice, "#")
maxR, maxIdx, sliceLen := 0, 0, len(slice)
for idx := range slice {
r, left, right := 0, idx-1, idx+1
for {
if left < 0 || right >= sliceLen {
break
}
if slice[left] == slice[right] {
r++
left--
right++
} else {
break
}
}
if r > maxR {
maxR = r
maxIdx = idx
}
}
ret := ""
for idx, v := range slice {
if idx >= (maxIdx-maxR) && idx <= (maxIdx+maxR) && v != "#" {
ret += v
}
}
return ret
}
6. ZigZag Conversion
其实我觉得这道题不太好，有两种思路，一种硬用空间堆出来，一种是推出每一行相应位置的数学公式
// 28ms 依据数学公式
class Solution {
public:
string convert(string s, int numRows) {
if(numRows <= 1) return s;
int size = 2 * numRows - 2;
string res = "";
for(int i = 0; i < numRows; i++)
{
for(int j = i; j < s.length(); j += size)
{
res += s[j];
int pos = j + size - 2 * i;
if(i != 0 && i != numRows - 1 && pos < s.length()) res += s[pos];
}
}
return res;
}
};
go是真的快。。。
//0ms
func convert(s string, numRows int) string {
if numRows == 1 {
return s
}
ret := make([]byte, 0)
n := len(s)
cycleLen := 2*numRows - 2
for i := 0; i < numRows; i++ {
for j := 0; j+i < n; j += cycleLen {
ret = append(ret, s[j+i])
if i != 0 && i != numRows-1 && j+cycleLen-i < n {
ret = append(ret, s[j+cycleLen-i])
}
}
}
return string(ret)
}
