[TOC]
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]
示例 2：
输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]
限制：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^6
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while (i < j) {
int s = nums[i] + nums[j];
if (s < target) {
i++;
} else if (s > target) {
j--;
} else {
return new int[] {nums[i], nums[j]};
}
}
return new int[0];
}
}输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5
left 到 right之间的和sum
- sum < target, right++
- sum > target, left++
- sum == target, 添加结果，left++，因为从left开始只有一个符号条件。
class Solution {
public int[][] findContinuousSequence(int target) {
List<int[]> res = new ArrayList<>();
for (int left = 1, right = 2; left < right;) {
int sum = (left + right) * (right - left + 1) / 2;
if (sum == target) {
int[] tmp = new int[right - left + 1];
for (int i = left; i <= right; i++) {
tmp[i - left] = i;
}
res.add(tmp);
left++;
} else if (sum < target) {
right++;
} else {
left++;
}
}
return res.toArray(new int[res.size()][]);
}
}输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
提示：
1 <= nums.length <= 50000
1 <= nums[i] <= 10000
class Solution {
public int[] exchange(int[] nums) {
int i = 0, j = nums.length - 1;
int length = j;
while (i <= j) {
while (i <= length && nums[i] % 2 == 1) {
i++;
}
while (j >= 0 && nums[j] % 2 == 0) {
j--;
}
if (i >= j) {
break;
}
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
return nums;
}
}给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例:
输入: numbers = [2, 7, 11, 15], target = 9
输出: [1,2]
解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。x + y = target, 先设numbers[i] = x，二分查找target - y ，找到即成功
class Solution {
public:
int binsearch(vector<int>& numbers, int target)
{
int left = 0, right = numbers.size() - 1;
int ans = -1;
while(left <= right)
{
int mid = left + ((right - left) >> 1);
if(numbers[mid] < target)
left = mid + 1;
else if(numbers[mid] > target)
right = mid - 1;
else
{
ans = mid;
break;
}
}
return ans;
}
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> ans;
for(int i = 0; i < numbers.size(); ++i)
{
int y = target - numbers[i];
int j = binsearch(numbers, y);
if(j != -1 && i != j)
{
ans.push_back(min(i+1, j+1));
ans.push_back(max(i+1, j+1));
break;
}
}
return ans;
}
};由于数组是有序的，只需要双指针即可。一个left首指针，一个right尾指针，如果left + right 值大于 target 则 right左移动， 否则 left 右移。
class Solution {
public int[] twoSum(int[] numbers, int target) {
int n = numbers.length;
int left = 0, right = n - 1;
while (left < right) {
int sum = numbers[left] + numbers[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
return new int[]{++left, ++right};
}
}
return null;
}
}给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2：
输入: "cbbd" 输出: "bb"
遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。
-
奇数回文串的“中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
-
偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。
class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
String res = s.substring(0, 1);
// 中心位置枚举到 len - 2 即可
for (int i = 0; i < len - 1; i++) {
String oddStr = centerSpread(s, i, i);
String evenStr = centerSpread(s, i, i + 1);
String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
if (maxLenStr.length() > maxLen) {
maxLen = maxLenStr.length();
res = maxLenStr;
}
}
return res;
}
private String centerSpread(String s, int left, int right) {
// left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
// right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
int len = s.length();
int i = left;
int j = right;
while (i >= 0 && j < len) {
if (s.charAt(i) == s.charAt(j)) {
i--;
j++;
} else {
break;
}
}
// 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
return s.substring(i + 1, j);
}
}给你 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
首尾各一个指针，每次向内移动短板，可以得到最大值。
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while (i < j) {
res = height[i] < height[j] ? Math.max(res, (j - i) * height[i++]) : Math.max(res, (j - i) * height[j--]);
}
return res;
}
}
import java.util.*;
public class Solution {
/**
* max water
* @param arr int整型一维数组 the array
* @return long长整型
*/
public long maxWater (int[] arr) {
// write code here
int i = 0, j = arr.length - 1;
long sum = 0;
// 找出左右边界的最小值作为水位高度
int mark = Math.min(arr[i], arr[j]);
while (i < j) {
// 如果左边较低，则左边界向右遍历， 否则右边界向左移动
if (arr[i] < arr[j]) {
i++;
// 如果当前标尺小于水位，则水量累加
if (arr[i] < mark) {
sum += mark - arr[i];
} else {
mark = Math.min(arr[i], arr[j]);
}
} else {
j--;
if (arr[j] < mark) {
sum += mark - arr[j];
} else {
mark = Math.min(arr[i], arr[j]);
}
}
}
return sum;
}
}给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c。
示例1:
输入: 5
输出: True
解释: 1 * 1 + 2 * 2 = 5
示例2:
输入: 3
输出: False
首指针left = 0, 尾指针 right = sqrt(c)的整数，然后从两头遍历，left * left + right * right < c 则left++；否则，right--。防止越界特殊处理一下。
class Solution {
public boolean judgeSquareSum(int c) {
if (c == 0) {
return true;
}
int left = 0;
int right = (int)Math.sqrt(c);
double eps = 1e-8;
boolean flag = false;
while (left <= right) {
double tmp = c - left * left;
if (Math.abs(tmp / right - right) < eps) {
flag = true;
break;
} else if ((right - tmp / right) > eps) {
right--;
} else {
left++;
}
}
return flag;
}
}编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1:
输入: "hello" 输出: "holle" 示例 2:
输入: "leetcode" 输出: "leotcede" 说明: 元音字母不包含字母"y"。
双指针，一个在头，一个在尾，两个都是元音就交换，遍历一遍即可
class Solution {
boolean flag(char c) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' || c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') {
return true;
}
return false;
}
public String reverseVowels(String s) {
int left = 0, right = s.length() - 1;
char[] chars = s.toCharArray();
while (left < right) {
boolean flag1 = flag(chars[left]), flag2 = flag(chars[right]);
if (flag1 && flag2) {
char c = chars[left];
chars[left] = chars[right];
chars[right] = c;
left++;
right--;
} else if (flag1 && !flag2) {
right--;
} else if (!flag1 && flag2){
left++;
} else {
right--;
left++;
}
}
return String.valueOf(chars);
}
}判断的次数少一点
class Solution {
public:
string reverseVowels(string s) {
unordered_map<char,int> map{{ 'a', 1}, {'e', 1}, {'i', 1},{'o', 1},{'u', 1},
{'A', 1},{'E', 1},{'I', 1},{'O', 1},{'U', 1}};
int i =0;
int j = s.length()-1;
char temp;
while(i<j)
{
while(i<j&&map[s[i]]!=1) i++;
while(i<j&&map[s[j]]!=1) j--;
if(i<j)
{
temp = s[i];
s[i] = s[j];
s[j] = temp;
}
i++;j--;
}
return s;
}
};给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba" 输出: True 示例 2:
输入: "abca" 输出: True 解释: 你可以删除c字符。 注意:
字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。
如果字符串的起始字符和结束字符相同（即 s[0]==s[s.length-1]），则内部字符是否为回文（s[1], s[2], ..., s[s.length - 2]）将唯一地确定整个字符串是否为回文。
算法： 假设我们想知道 s[i],s[i+1],...,s[j] 是否形成回文。如果 i >= j，就结束判断。如果 s[i]=s[j]，那么我们可以取 i++;j--。否则，回文必须是 s[i+1], s[i+2], ..., s[j] 或 s[i], s[i+1], ..., s[j-1] 这两种情况。 见代码中注释
class Solution {
public boolean validPalindrome(String s) {
int left = 0, right = s.length() - 1;
int delIndex = -1;
while (left <= right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
// 第一次不等，先删除左边的，left++
if (delIndex == -1) {
delIndex = left;
left++;
// 第三次不等，直接返回false
} else if (delIndex == s.length()) {
return false;
// 第二次不等，left返回到第一次不等的位置，right也回到对应的位置，删除右边的
} else {
left = delIndex;
right = s.length() - left - 2;
delIndex = s.length();
}
}
}
return true;
}
}给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。 示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
从nums1中倒序找到nums2[i]的插入位置，然后插入，遍历所有nums2[i]，即合并成功。 因为两个数组都是递增的，倒序找更快。不要小看这种方法，也是非常快的，而且空间复杂度为O(1).
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = 0, j = m - 1;
int n1 = j;
while (i < n) {
while (j >= 0) {
if (nums1[j] > nums2[i]) {
j--;
} else {
break;
}
}
for (int k = n1; k >= j + 1; k--) {
nums1[k + 1] = nums1[k];
}
nums1[j + 1] = nums2[i];
i++;
n1++;
j = n1;
}
}
}class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1, p = m + n - 1;
while (p1 >= 0 && p2 >= 0) {
nums1[p--] = (nums1[p1] < nums2[p2]) ? nums2[p2--] : nums1[p1--];
}
// nums2可能有剩余，将剩余的添加到nums1中。
for (int i = 0; i <= p2; i++) {
nums1[i] = nums2[i];
}
}
}给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例：
给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
Arrays.sort(nums);
int len = nums.length;
for (int i = 0; i < len; i++) {
// 后面的元素肯定不满足要求，都是大于0的
if (nums[i] > 0) {
return res;
}
// 遇到重复的跳过
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int cur = nums[i];
int left = i + 1, right = len - 1;
while (left < right) {
int tmp = cur + nums[left] + nums[right];
if (tmp == 0) {
List<Integer> list = Arrays.asList(cur, nums[left], nums[right]);
res.add(list);
// 剔除重复的
while (left < right && nums[left + 1] == nums[left]) {
++left;
}
while (left < right && nums[right - 1] == nums[right]) {
--right;
}
// 同时移动left、right
++left;
--right;
} else if (tmp < 0) {
// 说明left太小，left前进
++left;
} else {
--right;
}
}
}
return res;
}
}给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2] 进阶：
一个直观的解决方案是使用计数排序的两趟扫描算法。 首先，迭代计算出0、1 和 2 元素的个数，然后按照0、1、2的排序，重写当前数组。 你能想出一个仅使用常数空间的一趟扫描算法吗？
class Solution {
public void sortColors(int[] nums) {
int p1 = 0, p2 = nums.length - 1, cur = 0;
while(cur <= p2){
if(nums[cur] == 1){
cur++;
}else if(nums[cur] == 0){
int tmp = nums[p1];
nums[p1++] = nums[cur];
nums[cur++] = tmp;
}else {
int tmp = nums[p2];
nums[p2--] = nums[cur];
nums[cur] = tmp;
}
}
}
}给定一个字符串和一个字符串字典，找到字典里面最长的字符串，该字符串可以通过删除给定字符串的某些字符来得到。如果答案不止一个，返回长度最长且字典顺序最小的字符串。如果答案不存在，则返回空字符串。
示例 1:
输入: s = "abpcplea", d = ["ale","apple","monkey","plea"]
输出: "apple" 示例 2:
输入: s = "abpcplea", d = ["a","b","c"]
输出: "a" 说明:
所有输入的字符串只包含小写字母。 字典的大小不会超过 1000。 所有输入的字符串长度不会超过 1000。
先对d按首字母大小排序，然后直接匹配，找到匹配成功字符串最长的那个。
class Solution {
public:
string findLongestWord(string s, vector<string>& d) {
sort(d.begin(), d.end());
int max = 0, ans = -1, i = 0;
for(i = 0; i < d.size(); ++i)
{
int j = 0, n = d[i].length(), k = 0, flag = 0;
while(j < s.length() && k < n)
{
if(s[j] == d[i][k])
j++, k++;
else
j++;
if(k == n)
flag = 1;
}
if(flag && max < n)
max = n, ans = i;
}
return ans != -1 ? d[ans] : "";
}
};不用排序，每次记录匹配成功的字符串，跟下一次比较取最长且首字母最小的那个。
class Solution {
boolean isSubString(String s1, String s2) {
int j = 0;
for (int i = 0; i < s1.length() && j < s2.length(); i++) {
if (s1.charAt(i) == s2.charAt(j)) {
j++;
}
}
return j == s2.length();
}
public String findLongestWord(String s, List<String> d) {
String max = "";
for (String s1 : d) {
if (isSubString(s, s1) && (max.length() < s1.length() || (max.length() == s1.length() && max.compareTo(s1) > 0))) {
max = s1;
}
}
return max;
}
}