leetcode

admin
admin
admin
102353
文章
87
评论
2022年1月6日01:33:25评论31 views字数 23629阅读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

  • 左青龙
  • 微信扫一扫
  • weinxin
  • 右白虎
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:33:25
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出)：
                   leetcodehttp://cn-sec.com/archives/721826.html

发表评论

匿名网友 填写信息