Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[**0**] + nums[**1**] = 2 + 7 = 9,
return [**0**, **1**].
1 | public int[] twoSum(int[] numbers, int target) { |
使用Hashmap结构，将值存在key，数组索引序号存在value里，使用containsKey方法简易地寻找和为target的对应项，若存在则返回对应下标，不存在就加入到map中。
Given a string, find the length of the longest substring without repeating characters.
Example 1:
Input: “abcabcbb”
Output: 3
Explanation: The answer is "abc", with the length of 3.
Example 2:
Input: “bbbbb”
Output: 1 Explanation: The answer is "b", with the length of 1.
Example 3:
Input: “pwwkew”
Output: 3 Explanation: The answer is "wke", with the length of 3.
Note that the answer must be a substring, "pwke" is a subsequence and not a substring.
即寻找最长连续子串
public int lengthOfLongestSubstring(String s) {
int n=s.length();
HashSet<Character> sett=new HashSet<>();
int maxlen=0,j=0,k=0;
while (j<n&&k<n) {
if(sett.contains(s.charAt(j))) {
sett.remove(s.charAt(k));
k++;
}else {
sett.add(s.charAt(j));
j++;
maxlen=Math.max(maxlen, j-k);
}
}
return maxlen;
}
利用HashSet结构，从字符串开始处索引，当没有重复字符时，定义的一个指针j递增，并计算最长的子串长度，当遇到重复字符时，另一指针k递增，并逐个移除Set集合里的值，直到将重复的字符移出。
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
A
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m=nums1.length,n=nums2.length;
int slen=m+n;
int num[]=new int[slen];
int j=0,k=0,i=0;
while(j<m&&k<n){
num[i]=(nums1[j]>nums2[k]?nums2[k++]:nums1[j++]);
i++;
}
while(j<m){
num[i++]=nums1[j++];
}
while(k<n){
num[i++]=nums2[k++];
}
if(slen%2==1){
return num[slen/2];
}else{
return (double)(num[slen/2]+num[slen/2-1])/2;
}
}
这个算法很容易理解，就是把两个数组重新排序到一个大数组里，再算中位数就很容易。
B
1 | public double findMedianSortedArrays(int[] nums1, int[] nums2) { |
基于二分法，比较AMid和BMid保留应该保留的部分递归，直至K==1.
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
public String longestPalindrome(String s) {
if(s.length()<1) return s;
StringBuilder str=new StringBuilder(s);
StringBuilder rs=new StringBuilder(s);
rs.reverse();
int len=s.length();
String outstr="";
for(int i=0;i<=len-1;i++) {
for(int n=2;n<=len-i;n++) {
if(str.substring(i, n+i).equals(rs.substring(len-n-i, len-i))) {
if(str.substring(i, n+i).length()>outstr.length()) {
outstr=str.substring(i, n+i);
}
}
}
}
if(outstr.equals("")) {
outstr=str.substring(0, 1);
}
return outstr;
}
将原字符串反转，通过比较对应位置的子字符串
Better Solution
1 | private int lo, maxLen; |
extendPalindrome方法选定一个中心，以两个指针j和k分别向俩个方向延伸，遍历完字符串即可。
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.p could be empty and contains only lowercase letters a-z, and characters like . or *.Example 1:
Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:
Input:
s = “aa”
p = “a“
Output: true
Explanation: ‘‘ means zero or more of the precedeng element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.
Example 3:
Input:
s = “ab”
p = “.“
Output: true
Explanation: “.“ means “zero or more (*) of any character (.)”.
Example 4:
Input:
s = “aab”
p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore it matches “aab”.
Example 5:
Input:
s = “mississippi”
p = “misisp*.”
Output: false
正则表达式
public boolean isMatch(String s, String p) {
java.util.regex.Pattern pattern=java.util.regex.Pattern.compile(p);
java.util.regex.Matcher matcher=pattern.matcher(s);
if(matcher.matches()) {
return true;
}else {
return false;
}
}
1 | public boolean isMatch(String s, String p) { |