指针
二进制求和
var addBinary = function(a, b) {
let i = a.length - 1 // a 的最大索引
let j = b.length - 1 // b 的最大索引
let res = ''
let c = 0 // 记录进位
while( i >= 0 || j >=0 || c ){ // 从后面往前加
let aa = +a[ i-- ] || 0
let bb = +b[ j-- ] || 0
let total = aa + bb + c
c = total / 2 | 0
total %= 2
res = total + res;
}
return res
};
合并两个有序数组
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
//从后往前 双指针 循环次数 a+b -1
for(let i = m - 1,j = n -1,k= n+m -1; j >= 0 ; --k) {
nums1[k]= i >=0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]
}
};
plan2
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
nums1.splice(m,nums1.length - m,...nums2) 拼接数组
nums1.sort((a,b)=>{
return a-b
})
};
125. 验证回文串
示例 1：
输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。
示例 2：
输入：s = "race a car"
输出：false
解释："raceacar" 不是回文串。
示例 3：
输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
由于空字符串正着反着读都一样，所以是回文串。
function isPalindrome(s: string): boolean {
s= s.toLocaleLowerCase().replace(/([^a-zA-Z0-9])/g,'')
let left=0,right = s.length-1;
while(right>=left){
if(s[left]!==s[right]) return false;
right--
left++
}
return true;
};
392. 判断子序列
示例 1：
输入：s = "abc", t = "ahbgdc"
输出：true
示例 2：
输入：s = "axc", t = "ahbgdc"
输出：false
function isSubsequence(s: string, t: string): boolean {
let l = 0;
for(let char of t){
if(s[l] === char) l++;
}
return l === s.length;
};
167. 两数之和 II - 输入有序数组
示例 1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
function twoSum(numbers: number[], target: number): number[] {
let [i,j] = [0,numbers.length-1];
while(i<j){
let sum = numbers[i] + numbers[j];
if(sum < target) i++
else if(sum > target) j--
else return [i+1,j+1]
}
};
11. 盛最多水的容器
示例 1：
function maxArea(height: number[]): number {
let [i,j,area] = [0,height.length-1,0];
while(i<j){
const newArea = Math.min(height[i],height[j]) * (j-i);
if(newArea > area) area = newArea;
if(height[i] < height[j]) i++;
else j--
}
return area;
};
15. 三数之和
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。
function threeSum(nums: number[]): number[][] {
nums.sort((a, b) => a - b);
const len = nums.length;
const ans = [];
for (let i = 0; i < len; i++) {
if (i>0 && nums[i] === nums[i - 1]) continue;
let j = i + 1, k = len - 1;
while (j < k) {
while (j>i+1 && j < len && nums[j] === nums[j - 1]) j++;
if (j >= k) break;
const sum = nums[i] + nums[j] + nums[k];
if (sum === 0) {
ans.push([nums[i], nums[j], nums[k]]);
j++;
} else if (sum > 0) {
k--;
} else {
j++
}
}
}
return ans;
};