算法学习

二分查找

搜索插入位置

原题：leetcode35.搜索插入位置

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

解题思路

二分法思路比较简单，难的是处理边界条件。

首先判断插入情况，分为以下几种：

• target = mid,不用插值，返回 mid。
• target > mid && target< mid+1 ,插值返回 mid+1
• target 在所有元素之前
• target 在所有元素之后

class Solution {
   public int searchInsert(int[] nums, int target) {
    int right = nums.length - 1;
    int left = 0;
    int n = 0;
    if(target > nums[right]) {
        return right + 1;
    }
    while(left < right) {
        int mid = left + (right - left) / 2;
        if(target == nums[mid]) {
            return mid;
        } else if(target > nums[mid] && target < nums[mid+1]) {
            return mid + 1;
        } else if(target > nums[mid]) {
            left = mid + 1;
        } else if(target < nums[mid]) {
            right = mid - 1;
        }
    }
    return target > nums[left] ? left + 1 : left;
}

}

Grind 75

符号匹配校验

思路：模拟栈，遍历数组，遇到左边符号压入，右边弹出上一个匹配

function isValid(s: string): boolean {
let map = new Map();
map.set('(',')');
map.set('[',']');
map.set('{','}');

let stacKArr:string[] = []



if(!map.has(s[0])||map.has(s.charAt(s.length -1))){
    return false
}

    for(let char of s){
        if(map.has(char)){
            stacKArr.push(char)
        }else{
            var last = stacKArr.pop()
            if(map.get(last)!=char){
                return false
            }
        }
    }
    return true
};

优化思路：

function isValid(s: string): boolean {
let map = new Map();
map.set('(',')');
map.set('[',']');
map.set('{','}');

let stacKArr:string[] = []



if(!map.has(s[0])||map.has(s.charAt(s.length -1))){
    return false
}

    for(let char of s){
        if(map.has(char)){
            stacKArr.push(char)
        }else{
            var last = stacKArr.pop()
            if(map.get(last)!=char){
                return false
            }
        }
    }
    return true
};

数组融合排序

模拟链表

class ListNode {
    next:ListNode|null
    val:number
    constructor(val:number,next:ListNode|null){
        this.val = val === undefined?0:val;
        this.next = (next===undefined ? null : next)
    }
}

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode|null {
    let dump = ListNode[0]
    while(list2?.next&&list1?.next){
        if(list1?.val>list2.val){
            dump.next = list2
            list2 = list2.next
        }else{
            dump.next = list1
            list1 = list1.next // 想在跳转外部
        }
    }
   return dump;
};

股票最高利润

思路： 动态更新最低价格和最高利润

function maxProfit(prices: number[]): number {
    if(prices.length<=1){
        return 0;
    }
    let minPrice:number = prices[0];
    let maxProfit:number = 0;

    for(let i = 0; i< prices.length;i++){
        if(minPrice>prices[i]){
            minPrice = prices[i];
        }
        if(maxProfit<prices[i]- minPrice){
            maxProfit = prices[i]- minPrice
        }
    }
    return maxProfit
};