大一大二的时候,老师布置的编程 作业大部分都是参照别人的,看看别人的代码写法,理解就行意思就行,很少自己动手去写,导致现在编程能力特别的差,有点挺后悔的。现在确实该每天花点时间敲敲代码,刷刷编程题,提高自己的编程能力了。找个一个刷题平台,准备坚持每天刷几题,加油!
国内版: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
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
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
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
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 = “ca b” 输出: 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
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
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): if i > 0 and nums[i] == nums[i-1]: continue if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target: break if nums[i] + nums[n-1] + nums[n-2] + nums[n-3] < target: continue for j in range(i+1,n-2): 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
评论