其他算法题

枫长...大约 17 分钟

1.两数之和open in new window

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

func twoSum(nums []int, target int) []int {
    m := make(map[int]int)
    for index, val := range nums {
        if preIndex, ok := m[target-val]; ok {
            return []int{preIndex, index}
        } else {
            m[val] = index
        }
    }
    return []int{}
}

146.LRU缓存open in new window

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类: LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解题思路:LRU缓存是考察数据结构能力的题目,它本质上由一个双端链表与一个hash表构成。双端链表用于存放具体的键值对,hash表的作用是能根据key以O(1)的复杂度找到相应的键值对。注意一下链表的增删,容易在这里出错。

struct node{
    int key;
    int val;
    node* pre;
    node* next;
    node(int _key, int _val): key(_key), val(_val) {

    }
};
class LRUCache {
public:
    unordered_map<int, node*> hash;
    node* begin;
    node* end;
    int capacity;
    int size = 0;
    LRUCache(int _capacity) {
        begin = new node(-1, -1);
        end = new node(-1, -1);
        begin->next = end;
        end->pre = begin;
        capacity = _capacity;
    }
    
    void add(node* pre, node* cur) {
        node* next = pre->next;
        pre->next = cur;
        cur->pre = pre;
        cur->next = next;
        next->pre = cur;
    }

    int get(int key) {
        if(!hash.count(key)) {
            return -1;
        }
        node* cur = hash[key];
        node* pre = cur->pre;
        node* next = cur->next;
        pre->next = next;
        next->pre = pre;
        add(begin, cur);
        return cur->val;
    }
    
    void put(int key, int value) {
        if(hash.count(key)) {
            hash[key]->val = value;
            get(key);
            return;
        }
        if(size >= capacity) {
            node* cur = end->pre;
            node* pre = cur->pre;
            node* next = cur->next;
            pre->next = next;
            next->pre = pre;
            hash.erase(cur->key);
            size--;
        }
        node* cur = new node(key, value);
        add(begin, cur);
        hash[key] = cur;
        size++;
    }
};

15.三数之和open in new window

给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意:答案中不可以包含重复的三元组。

解题思路

  • 双指针经典题目,比较naive的做法就是三次遍历O(n3)的复杂度,这肯定是不行的,我们可以先排序,将无序数组转成有序的,然后在第二次与第三次遍历上做文章,优化的复杂度可以达到O(n2)。
  • 对数组进行排序,使用三个指针 i、j 和 k 分别代表要找的三个数。通过枚举 i 确定第一个数,另外两个指针 j,k 分别从左边 i + 1 和右边 n - 1 往中间移动,通过比较sum与0的大小,找到满足 sum = 0的所有组合。 由于题目要求答案不能包含重复的三元组,所以在确定第一个数和第二个数的时候,要跳过数值一样的下标(在三数之和确定的情况下,确保第一个数和第二个数不会重复,即可保证三元组不重复)
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        vector<vector<int>> ans;
        vector<int> tmp(3);
        for(int i = 0; i < n; i++) {
            if(i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int target = -nums[i], r = n - 1;
            for(int l = i + 1; l < n; l++) {
                if(l != i + 1 && nums[l] == nums[l - 1]) {
                    continue;
                }
                while(l < r && nums[l] + nums[r] > target) {
                    r--;
                }
                if(l < r && nums[l] + nums[r] == target) {
                    tmp[0] = nums[i];
                    tmp[1] = nums[l];
                    tmp[2] = nums[r];
                    ans.emplace_back(tmp);
                }
            }
        }
        return ans;
    }

42.接雨水open in new window

给定 n个非负整数表示每个宽度为1的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

解题思路

  • 思路1:单调栈问题,对于每一个凹的区域,它所能接的水是要看距离它最近的比它高的位置的高度,单调栈遍历一圈,将每个位置上所能接到的水存下来即可。 时间复杂度O(n)。
  • 思路2:双指针的思路,一开始左右两个指针指向数组的两边,判断左边和右边哪边高,假设是左边高,那么此时在l指针这一格里,右边一定有人挡水,且右边的max一定比左边的max高(因为如果左边更高左边就会卡着不动),所以此时这一格接到的水就是左边的max - 当前的高度;当右边高时同理。
    int trap(vector<int>& height) {
        vector<vector<int>> st;
        int n = height.size();
        int ans = 0;
        for(int i = 0; i < n; i++) {
            while(!st.empty() && height[st.back().back()] < height[i]) {
                vector<int> t = st.back();
                st.pop_back();
                if(!st.empty()) {
                    int high = min(height[st.back().back()], height[i]) - height[t.back()];
                    ans += high*(i - st.back().back() - 1);
                }
            }
            if(st.empty() || height[st.back().back()] > height[i]) {
                vector<int> add = { i };
                st.emplace_back(add);
            }else if(height[st.back().back()] == height[i]) {
                st.back().emplace_back(i);
            }
        }
        return ans;
    }

704.二分查找open in new window

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

func search(nums []int, target int) int {
    for l, r := 0, len(nums)-1; l <= r; {
        m := l+(r-l)/2
        if nums[m] == target {
            return m
        } else if nums[m] > target {
            r = m-1
        } else {
            l = m+1
        }
    }
    return -1
}

7.整数反转open in new window

给你一个 32 位的有符号整数 x ,返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ,就返回 0。

假设环境不允许存储 64 位整数(有符号或无符号)。

func reverse(x int) int {
	res := 0
	for x != 0 {
		res = res*10 + x%10
		x = x/10
	}
	if res <= math.MinInt32 || res >= math.MaxInt32 {
		return 0
	}
	return res
}

69.x的平方根open in new window

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

// 精确到个位
func mySqrt(x int) int {
    l, r := 1, x
    for l <= r {
        mid := (l + r) >> 1
        if x < mid * mid {
            r = mid - 1
        } else {
            l = mid + 1
        }
    }
    return r
}

// 精确到3位小数
func mySqrt(x float64) float64 {
	l, r := 0.0, x
	for l <= r {
		mid := (l + r) >> 1
		if x < mid*mid {
			r = mid - 1e-3
		} else {
			l = mid + 1e-3
		}
	}
	return r
}

209.长度最小的子数组open in new window

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。

func minSubArrayLen(target int, nums []int) int { 
    i := 0
    l := len(nums)
    sum := 0    
    result := l + 1
    for j := 0; j < l; j++ {
        sum += nums[j]
        for sum >= target {
            subLength := j - i + 1
            if subLength < result {
                result = subLength
            }
            sum -= nums[i]
            i++
        }
    }
    if result == l+1 {
        return 0
    } else {
        return result
    }
}

54.螺旋矩阵open in new window

给你一个mn列的矩阵matrix,请按照顺时针螺旋顺序,返回矩阵中的所有元素。

子数组是数组中的一个连续部分。

解题思路状态机模拟题目,我们可以定义上下左右四个方向状态为1,2,3,4;一开始方向状态为右,当右碰到边界或者已经遍历过的元素了,就将状态变成下;当下走到边界或者已经遍历过的元素了,就将状态变成左,以此类推,当所有位置都遍历完了,就可以得到的答案。

    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int first=0;
        int second=0;
        int count=0;
        int direction=2;// 上右下左
        while(count<matrix.size()*matrix[0].size())
        {
            res.push_back(matrix[first][second]);
            matrix[first][second]=101;
            count++;
            switch(direction){
                case 1: 
                    if(first==0 && direction==1) direction=2;
                    else if(direction==1 && matrix[first-1][second]==101) direction=2;
                    break;
                case 2:
                    if(direction==2 && second==matrix[0].size()-1) direction=3;
                    else if(direction==2 && matrix[first][second+1]==101) direction=3;
                    break;
                case 3:
                    if(direction==3 && first==matrix.size()-1) direction=4;
                    else if(direction==3 && matrix[first+1][second]==101) direction=4;
                    break;
                case 4:
                    if(direction==4 && second==0) direction=1;
                    else if(direction==4 && matrix[first][second-1]==101) direction=1;
                    break;
            }
            switch(direction){
                case 1: first-=1; break;
                case 2: second+=1; break;
                case 3: first+=1; break;
                case 4: second-=1; break;
            }
        }
        return res;
    }

41.缺失的第一个正数open in new window

给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

func firstMissingPositive(nums []int) int {
    for i:=0;i<len(nums);i++{
        for nums[i]>=1&&nums[i]<=len(nums)&&nums[nums[i]-1]!=nums[i]{
            nums[i],nums[nums[i]-1] = nums[nums[i]-1],nums[i]
        }
    }
    for i:=0;i<len(nums);i++{
        if nums[i]!=i+1{
            return i+1
        }
    }
    return len(nums)+1
}

240.搜索二维矩阵 IIopen in new window

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性:

  • 每行的元素从左到右升序排列。
  • 每列的元素从上到下升序排列。
func searchMatrix(matrix [][]int, target int) bool {
     n,m:= 0,len(matrix[0])-1
    for n<len(matrix)&&m>=0{
        if matrix[n][m]!=target{
            if matrix[n][m]>target{
                m--
            }else{
                n++
            }
        }else{
            return true
        }
    }
    return false
}

470.用Rand7() 实现 Rand10()open in new window

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数,试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n,即你实现的函数 rand10() 在测试时将被调用的次数。请注意,这不是传递给 rand10() 的参数。

func rand10() int {
    for{
        num := (rand7()-1)*7 + rand7()
        if num <= 40 {
            return num%10+1
        }
    }
}

440.字典序的第K小数字open in new window

给定整数 nk,返回 [1, n] 中字典序第 k 小的数字。

func findKthNumber(n int, k int) int {
	p := 1
	prefix := 1
	for p < k {
		count := 0
		currentNode := prefix
		nextNode := prefix + 1
		for currentNode <= n {
			count += int(math.Min(float64(nextNode), float64(n+1))) - currentNode
			currentNode *= 10
			nextNode *= 10
		}
		if p+count > k {
			prefix *= 10
			p++
		} else {
			prefix++
			p += count
		}
	}
	return prefix
}

239.滑动窗口最大值open in new window

type MaxQueue struct{
    Queue []int
}
func Constructor()MaxQueue{
    queue := make([]int,0)
    return MaxQueue{Queue:queue}
}
func (this *MaxQueue)push(n int){
    for len(this.Queue)!=0&&this.Queue[len(this.Queue)-1]<n{
        this.Queue = this.Queue[:len(this.Queue)-1]
    }
    this.Queue = append(this.Queue,n)
}
func (this *MaxQueue)max()int{
    return this.Queue[0]
}
func (this *MaxQueue)pop(n int){
    if n==this.Queue[0]{
        this.Queue = this.Queue[1:]
    }
}
func maxSlidingWindow(nums []int, k int) []int {
    window := Constructor()
    res := make([]int,0)
    for i:=0;i<len(nums);i++{
        if i<k-1{
            window.push(nums[i])
        }else{
            window.push(nums[i])
            res = append(res,window.max())
            window.pop(nums[i - k + 1])
        }
    }
    return res
}

//  ---
func maxSlidingWindow(nums []int, k int) []int {
    var stack []int
    var res []int
    for i, v := range nums {
        for len(stack) > 0 && v >= nums[stack[len(stack)-1]] {
            stack = stack[:len(stack)-1]
        }
        stack = append(stack, i)
        if i-k+1 > stack[0] {
            stack = stack[1:]
        }
        if i+1 >= k {
            res = append(res, nums[stack[0]])
        }
    }
    return res
}

152.乘积最大子数组open in new window

给你一个整数数组 nums ,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

func maxProduct(nums []int) int {
    n := len(nums)
	if n == 0{
		return 0
	}
	if n == 1{
		return nums[0]
	}
	maxDP := make([]int, n)
    minDP := make([]int, n)
    maxDP[0], minDP[0] = nums[0], nums[0]
    maxValue := nums[0]
    for i:=1;i<n;i++{
        maxDP[i] = Max(nums[i], Max(maxDP[i-1]*nums[i], minDP[i-1]*nums[i]))
        minDP[i] = Min(nums[i], Min(maxDP[i-1]*nums[i], minDP[i-1]*nums[i]))
        maxValue = Max(maxValue, maxDP[i])
    }
    return maxValue
}


func Max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func Min(a, b int) int {
	if a < b {
		return a
	}
	return b
}