001.Two Sum
题目描述：
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.
Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
(因为要返回坐标，所以不适合对于原有数组进行排序后，再处理的two pointer做法)
public int[] twoSum(int[] nums, int target) {
int[] ans = new int[2];
if(nums ==null || nums.length <2) return ans;
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<nums.length;i++) {
if(map.containsKey(target -nums[i])) {
ans[0] = map.get(target - nums[i]);
ans[1] = i;
return ans;
}else {
map.put(nums[i], i);
}
}
return ans;
}
- Add Two Numbers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry =0, sum =0;
while(l1 != null || l2 != null || carry != 0){
sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
cur.next = new ListNode(sum%10);
carry = sum/10;
cur = cur.next;
l1 = l1 == null ? l1 : l1.next;
l2 = l2 == null ? l2 : l2.next;
}
return dummy.next;
}
}
- Longest Substring Without Repeating Characters
Given a string, find the length of the longest substring without repeating characters.
Examples:
Given "abcabcbb", the answer is "abc", which the length is 3.
Given "bbbbb", the answer is "b", with the length of 1.
Given "pwwkew", 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.
Sliding window and Pruning
class LongestSubstringWithoutRepeating {
public int lengthOfLongestSubstring(String s){
if(s == null || s.length() ==0) return 0;
if(s.length() ==1) return 1;
int[] flag = new int[256];
char[] array = s.toCharArray();
Arrays.fill(flag, -1);
int left=-1;
int right;
int maxlen = 0;
for(right = 0; right < s.length(); right++){
if(flag[array[right]] >left) left = flag[array[right]];
flag[array[right]] = right;
maxlen = Math.max(maxlen, right - left);
}
return maxlen;
}
}
005.Longest Palindromic Substring
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) {
char[] sArray = s.toCharArray();
boolean[][] dp = new boolean[sArray.length][sArray.length];
int res = 0, resStart = 0, resEnd = 0;
for(int end = 0; end < sArray.length; end++) {
for(int start = 0; start <= end; start++) {
//小于2包含了aa和aba两种情况
if(sArray[start] == sArray[end] && (end - start <= 2 || dp[start + 1][end - 1])) {
dp[start][end] = true;
if(end - start + 1 > res) {
res = end - start + 1;
resStart = start;
resEnd = end;
}
}
}
}
return s.substring(resStart, resEnd + 1);
}
//这里用枚举法，中心发散，每个字母作为一个轴心，
//每两个字母之间也可作为对称中心。//这里作了一步减枝处理，只有两个连续的字母才能作为对称中心。
Sol2:enumeration with prunning
如果子串中有许多连续重复字母的话，可以进一步优化。最长回文子串的对称轴一定处在任意个连续的重复字母的中心。不然会导致回文子串短于这些连续字母。
这样可以每次扫描一段连续重复字母的左右位置，作为扩展的起始位置。
public String longestPalindrome(String s) {
if (s == null || s.length() < 2)
return s;
char[] sArray = s.toCharArray();
int max = 0, start = 0, end = 0, lPointer = 0, rPointer = 0, L = 0, R = 0;
for (lPointer = 0; lPointer < s.length(); lPointer = rPointer) {
rPointer = lPointer;
while (rPointer < s.length() && sArray[rPointer] == sArray[lPointer])
rPointer++;
// for(rPointer=lPointer; rPointer <s.length() &&
// sArray[rPointer]==sArray[lPointer]; rPointer++)
L = lPointer - 1;
R = rPointer;
while (L >= 0 && R < s.length() && sArray[L] == sArray[R]) {
L--;
R++;
}
// for(L=lPointer-1,R=rPointer; L >=0 && R<s.length() && sArray[L]
// == sArray[R]; L--,R++)
if (R - L - 1 > max) {
max = R - L - 1;
start = L + 1;
end = R;
}
}
return s.substring(start, end);
}
public String longestPalindrome(String s) {
if(s == null || s.length() <=1) return s;
char[] sArray = s.toCharArray();
boolean[][] dp = new boolean[sArray.length][sArray.length];
int res = 0, resStart = 0, resEnd = 0;
for (int end = 0; end < sArray.length; end++) {
for (int start = 0; start <= end; start++) {
// 小于2包含了aa和aba两种情况
if (sArray[start] == sArray[end] && (end - start <= 2 || dp[start + 1][end - 1])) {
dp[start][end] = true;
if (end - start + 1 > res) {
res = end - start + 1;
resStart = start;
resEnd = end;
}
}
}
}
return s.substring(resStart, resEnd + 1);
}
//这里DP填充为自上而下，占用上半三角
