leetcode

admin 2022年1月6日01:33:25安全博客评论6 views23629字阅读78分45秒阅读模式

大一大二的时候,老师布置的编程作业大部分都是参照别人的,看看别人的代码写法,理解就行意思就行,很少自己动手去写,导致现在编程能力特别的差,有点挺后悔的。现在确实该每天花点时间敲敲代码,刷刷编程题,提高自己的编程能力了。找个一个刷题平台,准备坚持每天刷几题,加油!

国内版:https://leetcode-cn.com/problemset/all/
国外版(要翻墙):https://leetcode.com/
辅助工具:https://github.com/jdneo/vscode-leetcode

算法

0x1 两数 之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
c语言

1
2
3
4
5
6
7
8
9
10
11
12
13
int* twoSum(int* nums, int numsSize, int target) {
static int a[2]={0};
for(int i=0;i<numsSize;i++){
for(int j=i+1;j<numsSize;j++){
if(nums[i]+nums[j]==target){
a[0]=i;
a[1]=j;
return a;
}
}
}
return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
def twoSum(self, nums, target):
d={}
size=0
while size<len(nums):
if nums[size] not in d:
d[nums[size]]=size
if (target-nums[size]) in d:
if d[target-nums[size]] <size:
return (d[target-nums[size]],size)
size += 1
sum1=Solution()
nums=[2, 7, 11, 15]
target = 9
sum=sum1.twoSum(nums,target)
print(sum)

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.HashMap;
import java.util.Map;

public class Solution {
public int[] twoSum(int[] nums, int target) {
int[] result=new int[2];
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i<nums.length;i++) {
int tmp=target-nums[i];
if(map.containsKey(tmp)) {
result[0]=map.get(tmp);
result[1]=i;
}else {
map.put(nums[i], i);
}
}
return result;

}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] nums = new int[]{2, 7, 11, 15};
int target = 9;
int[] result=new Solution().twoSum(nums,target);
System.out.println(result[0]+" "+result[1]);
}
}

0x2 两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

c语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *head,*rear = NULL,*p;
int value = 0;
while(l1 || l2)
{
if(l1)
{
value += l1->val;
l1 = l1->next;
}
if(l2)
{
value += l2->val;
l2 = l2->next;
}
p = (struct ListNode *)malloc(sizeof(struct ListNode));
p->val = value%10;
value = value / 10;
p->next = NULL;
if(rear == NULL)
{
rear = p;
head = rear;
}
else
{
rear->next = p;
rear = p;
}
}
if(value)
{
p = (struct ListNode *)malloc(sizeof(struct ListNode));
p->val = value;
p->next = NULL;
rear->next = p;
}
return head;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
ans = ListNode(0)
temp = ans
tempsum = 0
while True:
if (l1 != None):
tempsum = l1.val + tempsum
l1 = l1.next
if (l2 != None):
tempsum = tempsum + l2.val
l2 = l2.next
temp.val = tempsum % 10
tempsum = int(tempsum / 10)
if l1 == None and l2 == None and tempsum == 0:
break
temp.next = ListNode(0)
temp = temp.next
return ans





if __name__ == "__main__":
t1 = ListNode(3)
t2 = ListNode(4)
t2.next = t1
t3 = ListNode(2)
t3.next = t2
b1 = ListNode(4)
b2 = ListNode(6)
b2.next = b1
b3 = ListNode(5)
b3.next = b2

result = Solution()
add_sum = result.addTwoNumbers(t3, b3)

while (add_sum != None):
print(add_sum.val)
add_sum = add_sum.next

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

class ListNode {
int val;
ListNode next;
ListNode(int x)
{ val = x; }
}
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//定义满十进一的数
int num = 0;
//定义一个ListNode,作为链表头
ListNode proNode = new ListNode(0);
//定义一个ListNode,接受两数的和
ListNode currentNode = new ListNode(0);
//先连接两个Node
proNode.next=currentNode;

do {
//两数相加
int sum = (l1!=null?l1.val:0) + (l2!=null?l2.val:0) + num;
//是否满十
num = sum/10;
//得出个位数
int result = sum%10;
//填入结果
currentNode.val = result;
l1 = l1!=null?l1.next:l1;
l2 = l2!=null?l2.next:l2;
if(l1!=null || l2!=null || num!=0) {
currentNode.next = new ListNode(0);
currentNode = currentNode.next;
}
}while(l1!=null || l2!=null || num!=0);
return proNode.next;
}

public static void main(String[] args) {
// TODO Auto-generated method stub
ListNode a1=new ListNode(2);
ListNode a2=new ListNode(4);
ListNode a3=new ListNode(3);
a1.next=a2;
a2.next=a3;
ListNode b1=new ListNode(5);
ListNode b2=new ListNode(6);
ListNode b3=new ListNode(4);
b1.next=b2;
b2.next=b3;
ListNode c1=new Solution().addTwoNumbers(a1,b1);
while(c1!=null){
System.out.println(c1.val);
c1=c1.next;
}
}
}

0x3 无重复字符的最长子串

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”,所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”,所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”,所以其长度为 3。
请注意,你的答案必须是 子串 的长度,”pwke” 是一个子序列,不是子串。
python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
def lengthOfLongestSubstring(self, s):
"""
:type s: str
:rtype: int
"""
start = maxLength = 0
usedChar = {}
for index, char in enumerate(s):
if char in usedChar and start <= usedChar[char]:
start = usedChar[char] + 1
else:
maxLength = max(maxLength, index - start + 1)
usedChar[char] = index
return maxLength
s="asdqwes"
solution=Solution()
maxlength=solution.lengthOfLongestSubstring(s)
print(maxlength)

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
import java.util.HashMap;
import java.util.Map;


public class Solution {
public int lengthOfLongestSubstring(String s) {
int n=s.length();
int res=0;
int end=0,start=0;
Map<Character,Integer> map=new HashMap<>();
for(;start<n&&end<n;end++) {
if(map.containsKey(s.charAt(end))) {
start=Math.max(map.get(s.charAt(end)), start);
}
map.put(s.charAt(end), end+1);
res=Math.max(res, end-start+1);
}
return res;

}

public static void main(String[] args) {
String s="qweqweasd";
int maxlength=new Solution().lengthOfLongestSubstring(s);
System.out.println(maxlength);

}
}

0x4 寻找两个有序数组的中位数

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0
示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class middle {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int[] nums3=new int[nums1.length+nums2.length];
for(int i=0;i<nums1.length;i++) {
nums3[i]=nums1[i];
}
for(int j=0;j<nums2.length;j++) {
nums3[nums1.length+j]=nums2[j];
}
Arrays.sort(nums3);

return (nums3.length%2==1) ?nums3[nums3.length/2]:(nums3[nums3.length/2-1]+nums3[nums3.length/2])/2.0;


}
public static void main(String[] args) {
// TODO Auto-generated method stub
int[] num1= {1,2,3,4};
int[] num2= {5,6,7,8};
double num3;
num3=new middle().findMedianSortedArrays(num1,num2);
System.out.println(num3);

}

}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def findMedianSortedArrays(self, nums1, nums2):
"""
:type nums1: List[int]
:type nums2: List[int]
:rtype: float
"""
nums3=nums1+nums2
nums3.sort()
length=len(nums3)
if length%2:
return nums3[int(length/2)]
else:
return (nums3[int(length/2)-1]+nums3[int(length/2)])/2.0

0x5最长回文子串

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:

输入: “cbbd”
输出: “bb”

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public String findPalindrome(String s,int left,int right) {
int n=s.length();
int l=left;
int r=right;
while(l>=0&&r<=n-1&&s.charAt(l)==s.charAt(r)) {
l--;
r++;
}
return s.substring(l+1,r);

}
public String longestPalindrome(String s) {
int n=s.length();
if(n<=1) return s;
String longest="";
String str;
for(int i=0;i<n-1;i++) {
str=findPalindrome(s,i,i);
if(str.length()>longest.length()) {
longest=str;
}
str=findPalindrome(s,i,i+1);
if(str.length()>longest.length()) {
longest=str;
}

}
return longest;

}

python解法详情看
https://blog.csdn.net/asd136912/article/details/78987624

0x6. Z 字形变换

将一个给定字符串根据给定的行数,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “LEETCODEISHIRING” 行数为 3 时,排列如下:

L C I R
E T O E S I I G
E D H N
之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:”LCIRETOESIIGEDHN”。

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);
示例 1:

输入: s = “LEETCODEISHIRING”, numRows = 3
输出: “LCIRETOESIIGEDHN”
示例 2:

输入: s = “LEETCODEISHIRING”, numRows = 4
输出: “LDREOEIIECIHNTSG”
解释:

L D R
E O E I I
E C I H N
T S G
python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class solution:
def convert(self,s,numRows):
strLength=len(s)
nodeLength=2*numRows-2
result=""
if strLength==0 or numRows==0 or numRows==1:
return s
for i in range(numRows):
for j in range(i,strLength,nodeLength):
result += s[j]
if i!=0 and i!=numRows-1 and j-2*i+nodeLength<strLength:
result += s[j-2*i+nodeLength]
return result
s = "LEETCODEISHIRING"
numRows = 3
solution=solution()
ans=solution.convert(s,numRows)
print ans

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<iostream>
using namespace std;

class Solution {
public:
string convert(string s, int numRows) {
if(numRows<=1) return s;
string res="";
int size=2*numRows-2;
for(int i=0;i<numRows;i++){
for(int j=i;j<s.size();j+=size){
res+=s[j];
int tmp=j+size-2*i;
if(i!=0&&i!=numRows-1&&tmp<s.size()) res+=s[tmp];
}
}
return res;

}
};

int main(){
string s = "LEETCODEISHIRING";
int numRows = 3;
Solution sol;
string res=sol.convert(s,numRows);
cout<<res<<endl;
}

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package algorithmic;

public class ztransform {
public String convert(String s, int numRows) {
if(s==null||s.length()==0||numRows==1||numRows>=s.length()) {
return s;
}
StringBuilder sb = new StringBuilder();

for(int i=1;i<s.length()+1;i+=2*(numRows-1)) {
sb.append(s.charAt(i-1));
}
for(int i=2;i<numRows;i++) {
boolean k = true;
for(int j=i;j<s.length()+1;j+=(k)?2*(numRows-i):2*(i-1),k=!k) {
sb.append(s.charAt(j-1));
}
}
for(int i=numRows;i<s.length()+1;i+=2*(numRows-1)) {
sb.append(s.charAt(i-1));
}
return sb.toString();


}

public static void main(String[] args) {
// TODO Auto-generated method stub
String s = "LEETCODEISHIRING";
int numRows = 3;
String result=new ztransform().convert(s, numRows);
System.out.println(result);

}

}

0x7 整数反转

给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。

示例 1:

输入: 123
输出: 321
示例 2:

输入: -123
输出: -321
示例 3:

输入: 120
输出: 21

C语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<stdlib.h>
int reverse(int x) {
long tmp, result=0;
while(x){
tmp=x%10;
result=result*10+tmp;
x=x/10;
}
if(result<INT_MIN||result>INT_MAX){
return 0;
}
return result;
}

int main(){
long x=12346578;
printf("%d",reverse(x));
return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def reverse(self, x):
"""
:type x: int
:rtype: int
"""
s=str(x)
x=0
if s[0]=='-':
for i in range(len(s)-1):
x=x*10+int(s[-1-i])
if x>2**31:
return 0
return -x
else:
for i in range(len(s)):
x=x*10+int(s[-i-1])
if x>2**31-1:
return 0
return x

x=-123456789
so=Solution()
print so.reverse(x)

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package algorithmic;

public class reverse {
public int reverse1(int x) {
int result=0,tmp;
while(x!=0) {
tmp=result*10+x%10;
x=x/10;
if(result>Integer.MAX_VALUE/10||result<Integer.MIN_VALUE/10) {
return 0;
}
result=tmp;
}
return result;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int x=-123456;
int out=new reverse().reverse1(x);
System.out.println(out);
}

}

0x8 字符串转换整数 (atoi)

请你来实现一个 atoi 函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字组合起来,作为该整数的正负号;假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符,这些字符可以被忽略,它们对于函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换。

在任何情况下,若函数不能进行有效的转换时,请返回 0。

说明:

假设我们的环境只能存储 32 位大小的有符号整数,那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围,qing返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:

输入: “42”
输出: 42
示例 2:

输入: “ -42”
输出: -42
解释: 第一个非空白字符为 ‘-‘, 它是一个负号。
我们尽可能将负号与后面所有连续出现的数字组合起来,最后得到 -42 。
示例 3:

输入: “4193 with words”
输出: 4193
解释: 转换截止于数字 ‘3’ ,因为它的下一个字符不为数字。
示例 4:

输入: “words and 987”
输出: 0
解释: 第一个非空字符是 ‘w’, 但它不是数字或正、负号。
因此无法执行有效的转换。
示例 5:

输入: “-91283472332”
输出: -2147483648
解释: 数字 “-91283472332” 超过 32 位有符号整数范围。
因此返回 INT_MIN (−231) 。
java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package algorithmic;

public class stoi {
public int myAtoi(String str) {

str=str.trim();
if(str.isEmpty()) return 0;
int sign=1;
int base=0;
int i=0;
if(str.charAt(i)=='-'||str.charAt(i)=='+') {
sign=str.charAt(i++)=='-'? -1:1;
}
while(i<str.length()&&str.charAt(i)>='0'&&str.charAt(i)<='9') {
if(base>Integer.MAX_VALUE/10||(base==Integer.MAX_VALUE/10&&str.charAt(i)-'0'>7)) {
return (sign==1)?Integer.MAX_VALUE:Integer.MIN_VALUE;
}
base=10*base+(str.charAt(i++)-'0');
}

return base*sign;

}

public static void main(String[] args) {
// TODO Auto-generated method stub
String str=" 1231234sdf";
int in=new stoi().myAtoi(str);
System.out.println(in);

}

}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
def myAtoi(self, str):
"""
:type str: str
:rtype: int
"""
str=str.strip()
import re
pattern=r"[\s]*[+-]?[\d]+"
match=re.match(pattern,str)
if match:
res=int(match.group(0))
if res>2**31-1:
return 2**31-1
if res<-2**31:
return 2**31
else:
return 0
return res
s=" 12312412qweqwewq"
so=Solution()
num=so.myAtoi(s)
print num

C语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<stdio.h> 
#include<stdlib.h>
int myAtoi(char* str) {
bool flag=false;
int tMax=INT_MAX/10;
int i=0,t=0,result=0;
while(str[i]){
if(str[i]=='-'){
flag=true;
break;
}
else if(str[i]=='+'||str[i]>=48&&str[i]<=57){
break;
}
else if(str[i]!=' ')
return 0;
i++;
}
if(str[i]=='-'||str[i]=='+')
i++;
while(str[i]){
if(str[i]>=48&&str[i]<57){
t=str[i]-'0';
if(result>tMax)
return flag?INT_MIN:INT_MAX;
else if(result==tMax&&flag&&t>8)
return INT_MIN;
else if(result==tMax&&!flag&&t>7)
return INT_MAX;
else
result=result*10+t;

}else{
break;
}
i++;
}
return flag? -result:result;

}
int main(){
char st[40]=" 123456qweqwrqw";
int i;
i=myAtoi(st);
printf("%d",i);
return 0;
}

0x9.回文数

判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。

示例 1:

输入: 121
输出: true
示例 2:

输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:

输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数

c语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<stdio.h> 

bool isPalindrome(int x) {
int result=0;
if(x==0) return true;
if(x<0||x%10==0) return false;
while(x>result){
result=result*10+x%10;
x /=10;
}
return (x==result||result/10==x);
}
int main(){
int num=121;
bool flag=isPalindrome(num);
printf("%d",flag);

}

python

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(object):
def isPalindrome(self, x):
"""
:type x: int
:rtype: bool
"""
st=str(x)
st1=st[len(st)::-1]
return st1==st
x=121
so=Solution()
print so.isPalindrome(x)

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
package algorithmic;

public class ispalindrome {
public boolean isPalindrome(int x) {
String str=String.valueOf(x);
int i=0;
int len=str.length();
while(i<len/2) {
if(str.charAt(i)==str.charAt(len-i-1)) {
i++;
}else{
return false;

}
}
return true;

}
public static void main(String[] args) {
// TODO Auto-generated method stub
int x=121;
boolean flag=new ispalindrome().isPalindrome(x);
System.out.println(flag);

}

}

0x10. 正则表达式匹配

给定一个字符串 (s) 和一个字符模式 (p)。实现支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符。
‘*’ 匹配零个或多个前面的元素。
匹配应该覆盖整个字符串 (s) ,而不是部分字符串。

说明:

s 可能为空,且只包含从 a-z 的小写字母。
p 可能为空,且只包含从 a-z 的小写字母,以及字符 . 和 *。
示例 1:

输入:
s = “aa”
p = “a”
输出: false
解释: “a” 无法匹配 “aa” 整个字符串。
示例 2:

输入:
s = “aa”
p = “a*”
输出: true
解释: ‘*’ 代表可匹配零个或多个前面的元素, 即可以匹配 ‘a’ 。因此, 重复 ‘a’ 一次, 字符串可变为 “aa”。
示例 3:

输入:
s = “ab”
p = “.*”
输出: true
解释: “.*” 表示可匹配零个或多个(‘*’)任意字符(‘.’)。
示例 4:

输入:
s = “aab”
p = “cab”
输出: true
解释: ‘c’ 可以不被重复, ‘a’ 可以被重复一次。因此可以匹配字符串 “aab”。
示例 5:

输入:
s = “mississippi”
p = “misis*p.”
输出: false

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if p=="":
return s==""
if len(p)==1:
return len(s)==1 and (s[0]==p[0] or p[0]=='.')
if p[1]!="*":
if s=="":
return False
return (s[0]==p[0] or p[0]=='.') and self.isMatch(s[1:],p[1:])
while s and(s[0]==p[0] or p[0]=='.'):
if self.isMatch(s,p[2:]):
return True
s=s[1:]
return self.isMatch(s,p[2:])
s="test"
p="t*"
so=Solution()
S=so.isMatch(s,p)
print S

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
public class q10 {

public boolean isMatch(String s, String p) {
if(p.isEmpty()) return s.isEmpty();
boolean first_match=(!s.isEmpty()&&p.charAt(0)==s.charAt(0)||p.charAt(0)=='.');
if(p.length()>=2&&p.charAt(1)=='*') {
//看有没有可能,剩下的pattern匹配上全部的text
//看有没有可能,剩下的text匹配整个pattern
//isMatch(text, pattern.substring(2)) 指当p第二个为*时,前面的字符不影响匹配所以可以忽略,所以将*以及*之前的一个字符删除后匹配之后的字符,这就是为什么用pattern.substring(2)
//如果第一个已经匹配成功,并且第二个字符为*时,这是我们就要判断之后的需要匹配的字符串是否是多个前面的元素(*的功能),这就是first_match && isMatch(text.substring(1), pattern))的意义!
return (isMatch(s,p.substring(2)))||(first_match&&isMatch(s.substring(1), p));
}else {
//没有星星的情况下:第一个字符相等,而且剩下s,匹配上剩下的p,没有星星且第一个匹配成功,那么s和p同时向右移动一位看是否仍然能匹配成功
return first_match&&isMatch(s.substring(1),p.substring(1));
}

}


public static void main(String[] args) {
// TODO Auto-generated method stub
String s="qwe123";
String p="qwe";
boolean flag=new q10().isMatch(s,p);
System.out.println(flag);

}

}

c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<stdio.h>
bool isMatch(char *s,char *p)
{
if(p[0]=='\0')
{
return s[0]=='\0';
}
if(s[0]=='\0')
{
if(p[1]=='*')
{
return isMatch(s,p+2);
}
return false;
}
if(p[1]=='*')
{
if(s[0]==p[0]||p[0]=='.')
{
if(strlen(p)>=4 && p[0]==p[2] && p[3]=='*')
return isMatch(s,p+2);//此处总觉得是有些取巧,针对超时
return isMatch(s+1,p)||isMatch(s+1,p+2)||isMatch(s,p+2);
}
else
{
return isMatch(s,p+2);
}
}
else
{
if(s[0]==p[0]||p[0]=='.')
{
return isMatch(s+1,p+1);
}
}
return false;
}

0x11. 盛最多水的容器

给定 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明:你不能倾斜容器,且 n 的值至少为 2。

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下,容器能够容纳水(表示为蓝色部分)的最大值为 49。

示例:

输入: [1,8,6,2,5,4,8,3,7]
输出: 49
java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class q11 {
public int maxArea(int[] height) {
int len=height.length;
int area;
int max=0;
for(int i=0;i<len;i++) {
for(int j=i+1;j<len;j++) {
int hei=(height[i]>height[j])?height[j]:height[i];
area =hei*(j-i);
if(area>max) max=area;

}
}
return max;

}

public static void main(String[] args) {
// TODO Auto-generated method stub
int[] s= {1,8,6,2,5,4,8,3,7};
System.out.println(new q11().maxArea(s));


}
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
def maxArea(self, height):
"""
:type height: List[int]
:rtype: int
"""
maxArea=0
left=0
right=len(height)-1
while right >left:
maxArea=max(maxArea,min(height[left],height[right])*(right-left))
if height[right]>height[left]:
left+=1
else:
right-=1
return maxArea
s=[1,8,6,2,5,4,8,3,7]
so=Solution()
print so.maxArea(s)

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<math.h> 
#include<vector>
#include<iostream>
using namespace std;
class Solution {
public:
int maxArea(vector<int>& height)
{
int s=height.size();
//vector<vector<int> >dp(s,vector<int>(s));
int i=0,j=s-1;
int temp=0,maxarea=0;
while(i<j)
{
temp=min(height[i],height[j])*(j-i);
maxarea=maxarea>temp?maxarea:temp;
if(height[i]>height[j])
{
j--;
}
else
i++;
}
return maxarea;
}
};
int main(){
int s[]={1,8,6,2,5,4,8,3,7};
Solution so;
vector <int> s1;
for(int i=0;s[i]!='\0';i++)
s1.push_back(s[i]);
int a=so.maxArea(s1);
cout<<a;
return 0;
}

0x12 整数转罗马数字

罗马数字包含以下七种字符: I, V, X, L,C,D 和 M。

字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做 II ,即为两个并列的 1。12 写做 XII ,即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做 IIII,而是 IV。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况:

I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个整数,将其转为罗马数字。输入确保在 1 到 3999 的范围内。

示例 1:

输入: 3
输出: “III”
示例 2:

输入: 4
输出: “IV”
示例 3:

输入: 9
输出: “IX”
示例 4:

输入: 58
输出: “LVIII”
解释: L = 50, V = 5, III = 3.
示例 5:

输入: 1994
输出: “MCMXCIV”
解释: M = 1000, CM = 900, XC = 90, IV = 4.
java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  public String intToRoman(int num) {
int[] numArray = new int[] {1000,900,500,400,100,90,50,40,10,9,5,4,1};
String [] strArray = new String[] {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};
StringBuffer res=new StringBuffer();
if(num<1 &&num>3999) return null;

for(int i=0;i<numArray.length;i++) {
int tmp=num/numArray[i];
while(tmp>0) {
res.append(strArray[i]);
tmp--;
}
num=num%numArray[i];
}
return res.toString();

}

0x13 罗马数字转整数

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int romanToInt(String s) {
Map<Character,Integer> map=new HashMap<Character,Integer>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int result=map.get(s.charAt(s.length()-1));
for(int i=s.length()-2;i>=0;i--) {
if(map.get(s.charAt(i))>=map.get(s.charAt(i+1))) {
result+=map.get(s.charAt(i));
}else {
result-=map.get(s.charAt(i));
}
}

return result;

}
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):    
def romanToInt(self, s):
"""
:type s: str
:rtype: int
"""
sum=0
convert={'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1}

for i in range(len(s)-1):
if convert
展开收缩
] < convert
展开收缩
]:

sum -= convert
展开收缩
]

else:
sum += convert
展开收缩
]

sum += convert
展开收缩
]

return sum

0x14 最长公共前缀

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public String longestCommonPrefix(String[] strs) {
StringBuilder s=new StringBuilder();
if(strs.length==0) {
return "";
}
for(int i=0;i<strs[0].length();i++) {
for(int j=1;j<strs.length;j++) {
if(i>=strs[j].length()||strs[0].charAt(i)!=strs[j].charAt(i)) {
return s.toString();
}


}
s.append(strs[0].charAt(i));

}
return s.toString();

}
}

c++

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
for(int i=0;i<strs[0].size();i++){
for(int j=1;j<strs.size();j++){
if(strs[j][i]!=strs[0][i]) return strs[0].substr(0,i);
}

}
return strs[0];
}
};

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
shorest=min(strs,key=len)
for i,letter in enumerate(shorest):
for other in strs:
if other[i] != letter:
return shorest[:i]
return shorest

0x15 三数之和

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

1
2
3
4
5
6
7
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
  public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result=new ArrayList<>();
if(nums==null||nums.length<3) {
return result;
}
Arrays.sort(nums);
// 注意:只有排序数组才可以利用下面的解法
for(int i=0;i<nums.length;i++) {
// 对第一层元素去重(去重的目的是防止出现重复三元组结果.)
if(i>0&&nums[i]==nums[i-1]) {
continue;
}
int j=i+1;
int k=nums.length-1;
while(j<k) {
int sum=nums[i]+nums[j]+nums[k];
if(sum==0) {
List<Integer> list=new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
result.add(list);
// 对第二层元素去重处理
while(j<k&&nums[j]==nums[j+1]) {
j++;
}
while(j<k&&nums[k]==nums[k-1] ) {
k--;
}
j++;
k--;
}else if(sum>0) {
k--;
}else {
j++;
}
}
}
return result;

}

0x16 最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

1
2
3
例如,给定数组 nums = [-1,2,1,-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
public int threeSumClosest(int[] nums, int target) {
// 排序
// 遍历
// 寻找当前元素后面的最接近的两数之和
// 双指针算法,等于就输出,否则就向中间移动直至相遇
Arrays.sort(nums);
int closest = Integer.MAX_VALUE;
int direction = -1;
for(int i = 0; i < nums.length; ++i){
for(int j = i+1, k = nums.length-1; j < k;){
int sum = nums[i] + nums[j] + nums[k];
if(target == sum) return sum;
else if(target > sum){
if(target-sum < closest){
closest = target-sum;
direction = -1;
}
++j;
}else {
if(sum-target < closest){
closest = sum-target;
direction = 1;
}
--k;
}
}
}
return target + direction*closest;
}
}

0x17 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

1
2
3
4
5
6
示例:

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {

public List<String> letterCombinations(String digits) {
List<String> list=new ArrayList<String>();
if(digits.isEmpty()) {
return list;
}
String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
list.add("");
String temp=null;
int id=0;
for(int i=0;i<digits.length();i++) {
id=Integer.parseInt(digits.charAt(i)+"");
while(list.get(0).length()==i)
{
temp=list.remove(0);
for(int j=0;j<mapping[id].length();j++) {
list.add(temp+mapping[id].charAt(j));
}
}
}
return list;

}
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
def letterCombinations(self, digits):
"""
:type digits: str
:rtype: List[str]
"""
dic = {2: ['a', 'b', 'c'],
3: ['d', 'e', 'f'],
4: ['g', 'h', 'i'],
5: ['j', 'k', 'l'],
6: ['m', 'n', 'o'],
7: ['p', 'q', 'r', 's'],
8: ['t', 'u', 'v'],
9: ['w', 'x', 'y', 'z'],
}
ret_str=[]
if len(digits) == 0: return []
if len(digits) == 1:
return dic[int(digits[0])]
result=self.letterCombinations(digits[1:])
for r in result:
for j in dic[int(digits[0])]:
ret_str.append(j+r)
return ret_str

0x18 四数之和

给定一个包含 n 个整数的数组 nums 和一个目标值 target,判断 nums 中是否存在四个元素 a,b,c 和 d ,使得 a + b + c + d 的值与 target 相等?找出所有满足条件且不重复的四元组。

注意:

1
2
3
4
5
6
7
8
9
10
11
12
答案中不可以包含重复的四元组。

示例:

给定数组 nums = [1, 0, -1, 0, -2, 2],和 target = 0。

满足要求的四元组集合为:
[
[-1, 0, 0, 1],
[-2, -1, 1, 2],
[-2, 0, 0, 2]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n = len(nums)
if n < 4: return []
nums.sort()
res = []
for i in range(n-3):
# 防止重复 数组进入 res
if i > 0 and nums[i] == nums[i-1]:
continue
# 当数组最小值和都大于target 跳出
if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target:
break
# 当数组最大值和都小于target,说明i这个数还是太小,遍历下一个
if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target:
continue
for j in range(i+1,n-2):
# 防止重复 数组进入 res
if j - i > 1 and nums[j] == nums[j-1]:
continue
# 同理
if nums[i] + nums[j] + nums[j+1] + nums[j+2] > target:
break
# 同理
if nums[i] + nums[j] + nums[n-1] + nums[n-2] < target:
continue
# 双指针
left = j + 1
right = n - 1
while left < right:
tmp = nums[i] + nums[j] + nums[left] + nums[right]
if tmp == target:
res.append([nums[i],nums[j],nums[left],nums[right]])
while left < right and nums[left] == nums[left+1]:
left += 1
while left < right and nums[right] == nums[right-1]:
right -= 1
left += 1
right -= 1
elif tmp > target:
right -= 1
else:
left += 1
return res

数据库

shell

FROM :blog.cfyqy.com | Author:cfyqy

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:33:25
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  leetcode http://cn-sec.com/archives/721826.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: