算法唯手熟尔5月

keep going keep going

2020/5/1

5/1第一天，半年又要过去了

leetcode 21. 合并两个有序链表_Go

很简单的题目

package main

import "fmt"

// ListNode Struct
type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil && l2 == nil {
		return nil
	}
	if l1 == nil || l2 == nil {
		if l1 == nil {
			return l2
		}
		return l1
	}
	head := &ListNode{}
	tail := head
	for l1 != nil && l2 != nil {
		if l1.Val < l2.Val {
			tail.Next = l1
			l1 = l1.Next
			tail = tail.Next
		} else {
			tail.Next = l2
			l2 = l2.Next
			tail = tail.Next
		}
	}
	if l1 != nil {
		tail.Next = l1
	}
	if l2 != nil {
		tail.Next = l2
	}
	return head.Next
}

func main() {
	l1 := &ListNode{1, nil}
	l1.Next = &ListNode{2, nil}
	l1.Next.Next = &ListNode{4, nil}

	l2 := &ListNode{1, nil}
	l2.Next = &ListNode{3, nil}
	l1.Next.Next = &ListNode{4, nil}

	root := mergeTwoLists(l1, l2)
	fmt.Println(root.Val)
	fmt.Println(root.Next.Val)
}

leetcode 15. 三数之和_C++

#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    if(nums.size()<3) return ans;
    sort(nums.begin(), nums.end());
    if(nums[0]>0) return ans;
    int i=0;
    while (i<nums.size()){
        if(nums[i]>0) break;
        int left=i+1;
        int right=nums.size()-1;
        while(left<right){
            long long x=nums[i];
            long long y=nums[left];
            long long z=nums[right];
            if(x+y>0-z) right--;
            else if(x+y<0-z) left++;
            else{
                vector<int> temp;
                temp.push_back(nums[i]);
                temp.push_back(nums[left]);
                temp.push_back(nums[right]);
                ans.push_back(temp);
                while(left<right&&nums[left] == nums[left+1]) left++;
                while(left<right&&nums[right] == nums[right-1]) right--;
                left++;
                right--;
            }
        } 
        while(i+1<nums.size()&&nums[i] == nums[i+1]) i++;
        i++;
    }
    return ans;
}

int main(){
    vector<int> nums={-1, 0, 1, 2, -1, -4};
    vector<vector<int>> ans=threeSum(nums);
    for(int i=0;i<ans.size();i++){
        for(int j=0;j<ans[i].size();j++){
            printf("%d ",ans[i][j]);
        }
        printf("\n");
    }
    return 0;
}

2020/5/2

leetcode 3. 无重复字符的最长字串_Go

package main

import "fmt"

// 第一反应可以用回溯
// 后来觉得边界太难确定了，就老老实实学习了滑动窗口
func lengthOfLongestSubstring(s string) int {
	ans := 0
	mp := make(map[byte]int, 10)
	if len(s) <= 1 {
		ans = len(s)
		return ans
	}
	currentLen := 0
	startIndex := 0
	for i := 0; i < len(s); i++ {
		_, ok := mp[s[i]]
		if !ok {
			mp[s[i]] = i
			currentLen++
		} else {
			if currentLen > ans {
				ans = currentLen
			}
			startIndex = max(mp[s[i]], startIndex)
			currentLen = i - startIndex
			mp[s[i]] = i
		}
	}
	if currentLen > ans {
		ans = currentLen
	}
	return ans
}

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

func main() {
	s := "abcabcbb"
	fmt.Println(lengthOfLongestSubstring(s))
}

leetcode 16. 最接近的三数之和_C++

这题和昨天的三数之和做法一样，熟悉一下就好

#include<stdio.h>
#include<algorithm>
#include<vector>

using namespace std;

// two pointers
int threeSumClosest(vector<int>& nums, int target) {   
    int ans=0;
    if(nums.size()<3) return ans;
    sort(nums.begin(),nums.end());
    ans=nums[0]+nums[1]+nums[2];
    for(int i=0;i<nums.size();i++){
        int st=i+1,ed=nums.size()-1;
        while(st<ed){
            int sum=nums[st]+nums[ed]+nums[i];
                if(abs(target-sum)<abs(target-ans)) ans = sum;
                if(sum == target) return sum;
                else if(sum < target) st++;
                else ed--;
        }
    }
    return ans;
}

int main(){
    int a[4]={-1,2,1,-4};
    vector<int> nums(a,a+4);
    int ans=threeSumClosest(nums,1);
    printf("%d\n",ans);
    return 0;
}

2020/5/3

leetcode 19. 删除链表的倒数第N个节点_C++

#include<stdio.h>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 学了一手哑结点和删除
ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* dummy=new ListNode(0);
    dummy->next=head;
    ListNode* first=dummy;
    ListNode* second=dummy;
    for(int i=0;i<=n;i++){
        first=first->next;
    }
    while (first!=nullptr)
    {
        first=first->next;
        second=second->next;
    }
    second->next=second->next->next;
    return dummy->next;
}

int main(){
    ListNode* head=new ListNode(1);
    head->next=new ListNode(2);
    head->next->next=new ListNode(3);
    head->next->next->next=new ListNode(4);
    head->next->next->next->next=new ListNode(5);
    ListNode* ans=removeNthFromEnd(head,2);
    printf("%d\n",ans->val);
    printf("%d\n",ans->next->next->next->val);
    return 0;
}

2020/5/4

leetcode 45. 跳跃游戏 II_Go

package main

import "fmt"

// 之前做过一道类似的跳跃游戏
// 原题是能否跳到尾部
// 现在改成最少跳跃几次
// 第一个反应是dp，但仔细想一下贪心也可以了

// 方法一，从末尾处贪心
func jump1(nums []int) int {
	idx := len(nums) - 1
	steps := 0
	for idx > 0 {
		for i := 0; i < idx; i++ {
			if i+nums[i] >= idx {
				idx = i
				steps++
				break
			}
		}
	}
	return steps
}

// 方法二，正向贪心，和原题差不多
func jump(nums []int) int {
	n := len(nums)
	steps := 0
	maxIdx := 0
	end := 0
	for i := 0; i < n-1; i++ {
		maxIdx = max(maxIdx, i+nums[i])
		if i == end {
			end = maxIdx
			steps++
		}
	}
	return steps
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func main() {
	nums := []int{2, 3, 1, 1, 4}
	fmt.Println(jump(nums))
}

2020/5/5

leetcode 98. 验证二叉搜索树_Go

package main

import (
	"fmt"
	"math"
)

// TreeNode struct
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 挺基本的题目，直接递归就好了
func isValidBST(root *TreeNode) bool {
	return recurse(root, math.MinInt64, math.MaxInt64)
}

func recurse(root *TreeNode, lower int, upper int) bool {
	if root == nil {
		return true
	}
	if root.Val <= lower || root.Val >= upper {
		return false
	}
	return recurse(root.Left, lower, root.Val) && recurse(root.Right, root.Val, upper)
}

// 还有很基本的一个思路，就是结合中序遍历即可
// 不通过是因为leetcode中golang全局变量的问题
var pre int = math.MinInt64

func isValidBST2(root *TreeNode) bool {
	if root == nil {
		return true
	}
	// 访问左子树
	if !isValidBST2(root.Left) {
		return false
	}
	// 访问当前节点：如果当前节点小于等于中序遍历的前一个节点，说明不满足BST，返回 false；否则继续遍历。
	if root.Val <= pre {
		return false
	}
	pre = root.Val
	// 访问右子树
	return isValidBST2(root.Right)
}

func main() {
	root := &TreeNode{
		Val:   0,
		Left:  nil,
		Right: nil,
	}
	fmt.Println(isValidBST2(root))
}

2020/5/6

leetcode 983. 最低票价_Go

package main

import "fmt"

// 第一反应就是dp
func mincostTickets(days []int, costs []int) int {
	dp := make([]int, days[len(days)-1]+1)
	idx := 0
	for i := 1; i <= days[len(days)-1]; i++ {
		if i == days[idx] {
			dp[i] = min(dp[max(0, i-1)]+costs[0], dp[max(0, i-7)]+costs[1])
			dp[i] = min(dp[max(0, i-30)]+costs[2], dp[i])
			idx++
		} else {
			dp[i] = dp[i-1]
		}
	}
	return dp[len(dp)-1]
}

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

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

func main() {
	days := []int{1, 4, 6, 7, 8, 20}
	costs := []int{2, 7, 15}
	fmt.Println(mincostTickets(days, costs))
}

2020/5/7

leetcode 572. 另一个树的子树_Go

package main

import "fmt"

// TreeNode struct
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func newNode(val int) *TreeNode {
	return &TreeNode{
		Val:   val,
		Left:  nil,
		Right: nil,
	}
}

func creatTree(a []int) *TreeNode {
	length := len(a)
	if length == 0 {
		return nil
	}
	node := newNode(a[0])
	queue := []*TreeNode{}
	queue = append(queue, node)
	num := 1
	for num < length {
		top := queue[0]
		queue = queue[1:]
		if top.Left == nil {
			if a[num] != -1 {
				top.Left = newNode(a[num])
				queue = append(queue, top.Left)
			}
			num++
		}
		if num == length {
			break
		}
		if top.Right == nil {
			if a[num] != -1 {
				top.Right = newNode(a[num])
				queue = append(queue, top.Right)
			}
			num++
		}
	}
	return node
}

// 最基础的DFS，别的方法我是想不出的
// 自己写的太丑了，可以运行，就贴了官方的，反正DFS都差不多
func isSubtree(s *TreeNode, t *TreeNode) bool {
	if s == nil {
		return false
	}
	return check(s, t) || isSubtree(s.Left, t) || isSubtree(s.Right, t)
}

func check(a, b *TreeNode) bool {
	if a == nil && b == nil {
		return true
	}
	if a == nil || b == nil {
		return false
	}
	if a.Val == b.Val {
		return check(a.Left, b.Left) && check(a.Right, b.Right)
	}
	return false
}

func main() {
	s := []int{3, 4, 5, 1, 2, -1, -1}
	t := []int{4, 1, 2}
	S := creatTree(s)
	T := creatTree(t)
	fmt.Println(isSubtree(S, T))
}

2020/5/9

昨天脑子已经不清楚了，昨天的题目自己稍微写了一下，就挂个题解吧，觉得脑子不清楚的时候，效率确实差

leetcode 211. 最大正方形_C++

bruteforce

#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.size() == 0 || matrix[0].size() == 0) {
        return 0;
    }
    int maxSide = 0;
    int rows = matrix.size(), columns = matrix[0].size();
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (matrix[i][j] == '1') {
                // 遇到一个 1 作为正方形的左上角
                maxSide = max(maxSide, 1);
                // 计算可能的最大正方形边长
                int currentMaxSide = min(rows - i, columns - j);
                for (int k = 1; k < currentMaxSide; k++) {
                    // 判断新增的一行一列是否均为 1
                    bool flag = true;
                    if (matrix[i + k][j + k] == '0') {
                        break;
                    }
                    for (int m = 0; m < k; m++) {
                        if (matrix[i + k][j + m] == '0' || matrix[i + m][j + k] == '0') {
                            flag = false;
                            break;
                        }
                    }
                    if (flag) {
                        maxSide = max(maxSide, k + 1);
                    } else {
                        break;
                    }
                }
            }
        }
    }
    int maxSquare = maxSide * maxSide;
    return maxSquare;
}

int main(){
    return 0;
}

---

dp

这题还可以dp我是真的没想到，但看了题解之后觉得想到是正常的，还是要多练练

#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

int maximalSquare(vector<vector<char>>& matrix) {
    if (matrix.size() == 0 || matrix[0].size() == 0) {
        return 0;
    }
    int maxSide = 0;
    int rows = matrix.size(), columns = matrix[0].size();
    vector<vector<int>> dp(rows, vector<int>(columns));
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (matrix[i][j] == '1') {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                maxSide = max(maxSide, dp[i][j]);
            }
        }
    }
    int maxSquare = maxSide * maxSide;
    return maxSquare;
}

int main(){
    return 0;
}

leetcode 69. x 的平方根_C++

#include<stdlib.h>
#include<stdio.h>

using namespace std;

// 这题出的有点离谱，感觉考的是数学
// 可惜，我数学拉垮了
// 我选择二分
int mySqrt(int x) {
    int low=0,high=x,ans=-1;
    while (low<=high)
    {
        int mid=low+(high-low)/2;
        if((long long)mid*(long long)mid<=x){
            low=mid+1;
            ans=mid;
        }else{
            high=mid-1;
        }
    }
    return ans;
}

int main(){
    printf("%d\n",mySqrt(4));
    return 0;
}

2020/5/10

leetcode 236. 二叉树的最近公共祖先_C++

#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;
    
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if(root==nullptr) return root;
    if(root->val==p->val||root->val==q->val) return root;
    TreeNode *left=lowestCommonAncestor(root->left,p,q);
    TreeNode *right=lowestCommonAncestor(root->right,p,q);
        
    if(left!=NULL&&right!=NULL) return root;//如果p,q刚好在左右两个子树上
    if(left==NULL) return right;//仅在右子树
    return left;//仅在左子树
}

TreeNode* CreateTree(int a[],int n){
    if (n==0){
        return NULL;
    }
    TreeNode* root=new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    int num=1;
    while(num<n){
        TreeNode* top=q.front();
        q.pop();
        if(top->left==NULL){
            if(a[num]!=-1){
                top->left=new TreeNode(a[num]);
                q.push(top->left);
            }
            num++;
        }
        if(num==n){
            break;
        }
        if(top->right==NULL){
            if(a[num]!=-1){
                top->right=new TreeNode(a[num]);
                q.push(top->right);
            }
            num++;
        }
    }
    return root;
}

int main(){
    int a[11]={3,5,1,6,2,0,8,-1,-1,7,4};
    TreeNode* root=CreateTree(a,11);
    TreeNode *p=new TreeNode(5);
    TreeNode *q=new TreeNode(1);
    TreeNode* ans=lowestCommonAncestor(root,p,q);
    printf("%d\n",ans->val);
    return 0;
}

2020/5/11

leetcode 50. Pow(x, n)_C++

算法笔记上有类似的，不过对幂次的范围没这题这么大，注意变量类型即可

#include<stdlib.h>
#include<stdio.h>
#include<vector>
#include<algorithm>

using namespace std;

double quick(double x,long long n){
    if(n==0) return 1.0;
    if(n%2==1) {
        return x*quick(x,n-1);
    }else{
        double mul=quick(x,n/2);
        return mul*mul;
    }
}

double myPow(double x, int n) {
    long long N=n;
    if(N>=0){
        return quick(x,N);
    }else{
        return 1.0/quick(x,-N); 
    }
}

int main(){
    double ans=myPow(2.0,-2147483648);
    printf("%f\n",ans);
    return 0;
}

2020/5/12

leetcode 155. 最小栈_C++

真摸鱼题

#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<algorithm>
#include<vector>

using namespace std;

class MinStack {
public:
    /** initialize your data structure here. */
    stack<int> minStack;
    stack<int> data;
    MinStack() {
        minStack.push(INT_MAX);
    }
    
    void push(int x) {
        data.push(x);
        minStack.push(min(minStack.top(), x));
    }
    
    void pop() {
        data.pop();
        minStack.pop();
    }
    
    int top() {
        int top=data.top();
        return top;
    }
    
    int getMin() {
        return minStack.top();
    }
};

int main(){
    return 0;
}

2020/5/15

leetcode 560. 和为K的子数组_C++

#include<stdio.h>
#include<stdlib.h>
#include<vector>

using namespace std;

int dp[20001];

// 前缀和
int subarraySum(vector<int>& nums, int k) {
    int ans=0;
    int n=nums.size();
    if(n==0) return ans;
    dp[0]=0;
    for(int i=1;i<=n;i++){
        dp[i]=dp[i-1]+nums[i-1];
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(dp[i]-dp[j]==k){
                //printf("%d\n",dp[i]-dp[j]);
                ans++;
            }
        }
    }
    return ans;
}

int main(){
    int k=2;
    vector<int> nums={1,1,1};
    int ans=subarraySum(nums,k);
    printf("%d\n",ans);
    return 0;
}

2020/5/16

leetcode 25. K 个一组翻转链表_C++

感觉就是之前做过的题目的一个汇总，题解写的比自己本身的代码优雅，就记录一下题解好了

#include<stdio.h>
#include<stdlib.h>
#include<utility>
#include <iostream>
#include <fstream>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
    ListNode* prev = tail->next;
    ListNode* p = head;
    while (prev != tail) {
        ListNode* nex = p->next;
        p->next = prev;
        prev = p;
        p = nex;
    }
    return {tail, head};
}

ListNode* reverseKGroup(ListNode* head, int k) {
    ListNode* hair = new ListNode(0);
    hair->next = head;
    ListNode* pre = hair;

    while (head) {
        ListNode* tail = pre;
        // 查看剩余部分长度是否大于等于 k
        for (int i = 0; i < k; ++i) {
            tail = tail->next;
            if (!tail) {
                return hair->next;
            }
        }
        ListNode* nex = tail->next;
        pair<ListNode*,ListNode*> p;
        p = myReverse(head, tail);
        head=p.first;
        tail=p.second;
        // 把子链表重新接回原链表
        pre->next = head;
        tail->next = nex;
        pre = tail;
        head = tail->next;
    }
    return hair->next;
}

int main(){
    return 0;
}

2020/5/17

leetcode 210. 课程表 II_Go

package main

import "fmt"

// 拓扑排序
func findOrder(numCourses int, prerequisites [][]int) []int {
	// build the map
	ans := []int{}
	edges := make([][]int, numCourses)
	degree := make([]int, numCourses) // 入度
	for _, value := range prerequisites {
		edges[value[1]] = append(edges[value[1]], value[0])
		degree[value[0]]++
	}
	queue := []int{}
	for i := 0; i < numCourses; i++ {
		if degree[i] == 0 {
			queue = append(queue, i)
		}
	}
	// bfs
	for len(queue) > 0 {
		top := queue[0]
		queue = queue[1:]
		ans = append(ans, top)
		for _, v := range edges[top] {
			degree[v]--
			if degree[v] == 0 {
				queue = append(queue, v)
			}
		}
	}
	if len(ans) != numCourses {
		return []int{}
	}
	return ans
}

func main() {
	pre := [][]int{{1, 0}, {2, 0}, {3, 1}, {3, 2}}
	ans := findOrder(4, pre)
	fmt.Println(ans)
}

2020/5/18

leetcode 152. 乘积最大子数组_Go

package main

import "fmt"

// dp
func maxProduct(nums []int) int {
	n := len(nums)
	if n == 0 {
		return 0
	}
	maxF, minF, ans := nums[0], nums[0], nums[0]
	for i := 1; i < n; i++ {
		mx, mn := maxF, minF
		maxF = max(mx*nums[i], max(nums[i], mn*nums[i]))
		minF = min(mn*nums[i], min(nums[i], mx*nums[i]))
		ans = max(maxF, ans)
	}
	return ans
}

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

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

func main() {
	nums := []int{-4, -3, 2}
	ans := maxProduct(nums)
	fmt.Println(ans)
}

本文作者： xiaoyuyu
本文链接： http://woaixiaoyuyu.github.io/2020/05/01/%E7%AE%97%E6%B3%95%E5%94%AF%E6%89%8B%E7%86%9F%E5%B0%945%E6%9C%88/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果