98-ValidataBinarySearchTree

Posted on 2020-03-15

验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
示例 1:

输入:
    2
   / \
  1   3
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/validate-binary-search-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路1

// isValidBSTLeft 左边返回最大值
// 判断思路返回字数的左最大和右再和跟比较判断条件比较复杂
// 收集意见的方式需要大量的记录和调查比较
func isValidBSTRe (root * TreeNode) (bool,int,int){
	// 为假的情况先返回
	// 左边大于返回false
	var min,max,leftMax,rightMin int
	var left,right ,leftNil,rightNil bool
	if root.Left != nil && root.Left.Val > root.Val{
		return false,0,0
	}
	//右边小返回false
	if root.Right != nil && root.Right.Val < root.Val{
		return false,0,0
	}
	if root.Right == nil && root.Left ==nil{
		return true,root.Val,root.Val
	}
	// 判断左情况
	if root.Left == nil {
		min = root.Val
		left = true
		leftNil = true

	}else{
		left ,min,leftMax = isValidBSTRe(root.Left)
	}
	if root.Right == nil {
		max = root.Val
		rightNil = true
		right = true
	} else {
		right,rightMin,max = isValidBSTRe(root.Right)
	}
	if left && right && (leftMax < root.Val || leftNil) && (rightMin > root.Val || rightNil ){
		return true,min,max
	}
	return false,0,0
}

思路2

// _isValidBST从上到到下限制子树约束条件，简单方便
// 立规矩的方式，你就按照我的范围搞，符合条件你愿意是啥是啥！
func _isValidBST(root *TreeNode, min int, max int) bool {
	if root == nil {
		return true
	}
	if min >= root.Val || root.Val >= max {
		return false
	}

	return _isValidBST(root.Left, min, root.Val) && _isValidBST(root.Right, root.Val, max)

}

总结

可以看到两个想法实际上本质都是递归但是在处理子树最大和最小值时候是完全两种思路。
方法1:收集子树的反馈（做调查），根节点比较民主，你们报上你们的范围，我看看我跟你们匹配不不匹配我不称职好我下台。跟的父亲发现自己选的下级下台了，完了我一手提拔的下台了我也下台吧。比较民主但是实现复杂，需要记录各种状态，但是可以保存每一步子树的情况后续可以进一步扩展。
方法2:给每个子树限定范围（立规矩），跟节点“老子就这样，你们按老子标准走，不符合的滚，老子上报下是这帮儿子不行连累了我不行”。方法简单，每次只需要把根节点的值最为范围立规范。依次往下迭代就行。但是没有记录下面的状态题目变更后可能不再适用。

常用数据结构

Posted on 2020-03-14

常用数据结构

数组，字符串; 链表;栈;队列;双端队列;树

字符串：通常要分解每个字符处理
字符串反转：双指针，逼近交换
数组：方便构造，0(1)时间下表查找。连续空间，O(n)时间查找值，删除添加O（n）

调度系统设计读书笔记

Posted on 2020-02-04

调度系统设计精要

原文链接:调度系统设计

调度系统解决的就是资源和需求供给不平衡的问题。

需求调研

调研应用场景，深入调研场景中待执行的任务（work）和能用来执行任务的资源）（resource）的特性。
分析调度系统的目的，成本优先，质量优先，最大化资源利用率等等

应用场景

了解任务的特性：

任务是否有截至日期，必须在某个时间以前完成；
任务是否支持抢占，抢占的具体规则是什么；
任务是否包含前置条件；
任务是否能在制定的资源上运行；

复杂性在于资源可能不平衡，不同资源处理任务的速度可能不一致。

linux调度例子

linux的进程调度器中，待调度的就是线程，线程只会处于执行或未执行状态。资源就是cpu（除cpu外系统不会为线程分配内存），同一个cpu在同一时间只能执行一个任务（进程中的线程），分配cpu时间给进程，上下文切换

673-NumberofLongestIncreasingSubsequence

Posted on 2020-01-18

func findNumberOfLIS(nums []int) int {
	//DP[j] = max(DP[j],DP[i]+1) 0<i<j if nums[j]>nums[i]
	//numsLen[j]  以j为结尾的最长递增序列的长度
	if len(nums) == 0{
		return  0
	}
	dp := make([]int,len(nums))
	numsLen := make([]int,len(nums))
	maxLen := 0
	for i := 0 ;i <len(dp);i++{
		dp[i] = 1
		numsLen[i] = 1
	}
	for i:=0;i<len(nums);i++{
		for j:=0;j<i;j++{
			if nums[i] >nums[j] {
				// 更新最大长度，把之前的排列加起来
				if  dp[j] + 1 > dp[i] {
					numsLen[i] = numsLen[j]
					dp[i] = dp[j]+1
				}else if dp[j] +1 == dp[i]{
					numsLen[i] += numsLen[j]
				}
			}
		}
		if maxLen < dp[i] {
			maxLen = dp[i]
		}

	}
	ret := 0
	for i := 0;i<len(nums);i++{
		if maxLen == dp[i] {
			ret += numsLen[i]
		}
	}
	return ret

}

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

34SearchRange

Posted on 2020-01-17

34-SearchRange

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法1

分别找到最左端和最右端,正常二分查找找到值直接返回，这里我们只需要对=情况区分处理，
找最左的时候如果发现目标相等，移动右指针，使得左右相等（循环推出）的情况逼近最左值
找右的时候正好相反

func searchRange(nums []int, target int) []int {
	left :=binaryLeftSerach(nums,target)
	right :=binaryRightSerach(nums,target)
	return []int{left,right}
}

func binaryLeftSerach(nums[]int ,target int ) int {
	lenN := len(nums)
	if lenN ==0 {
		return -1
	}
	right,left,mid := lenN,0,0
	//开区间[0,n) 左闭右开所以左边要+1 右边不处理，相等的时候右边动往地位走，left和right一点点逼近最左值，
	// 极限条件是left=lenN才能退出循环，所以判断下极限条件 当然如果right=lenN-1可不用判断
	for left < right {
		mid = (left +right) /2
		if nums[mid] < target{
			left = mid+1
		}else{
			right = mid
		}
	}
	if left == lenN{
		return -1
	}
	if nums[left] ==target {
		return left
	}
	return  -1
}

func binaryRightSerach(nums[]int ,target int ) int {
	lenN := len(nums)
	if lenN ==0 {
		return -1
	}
	right,left,mid := lenN,0,0
	//开区间[0,n) 左闭右开所以左边要+1 右边不处理，相等的时候左边动往高位走，left和right一点点逼近最有右值，
	// 极限条件是left=lenN才能退出循环，所以判断下极限条件 当然如果right=lenN-1可不用判断
	for left < right {
		mid = (left +right) /2
		/*
		if nums[mid] == target{
			left = mid + 1
		}else if nums[mid] > target{
			right = mid
		}else if nums[mid] < target{
			left = mid + 1
		}
		*/
		if nums[mid] > target{
			right = mid
		} else{
			left = mid + 1
		}
	}
	if right - 1 < 0 {
		return -1
	}
	if nums[right-1] == target{
		return right-1
	}
	return  -1
}

放在一个函数方法

func searchRangeV2(nums []int, target int) []int {
	l, r := 0, len(nums)-1
	if r < 0 {
		return []int{-1, -1}
	}
	//找左边界，所以右边界=或>target都收缩右边界，当l=r的时候就是左边界
	for l < r {
		mid := (l + r) / 2
		if nums[mid] < target {
			l = mid + 1
		} else {
			r = mid
		}
	}
	res1 := l
	l, r = 0, len(nums)-1
	for l < r {
		mid := (l+r)/2 + 1
		if nums[mid] > target {
			r = mid - 1
		} else {
			l = mid
		}
		fmt.Println(l, r)
	}
	res2 := l
	if nums[res1] != target {
		return []int{-1, -1}
	} else {
		return []int{res1, res2}
	}
}

236-LowestCommonAncestorofaBinaryTree

Posted on 2020-01-12

236. Lowest Common Ancestor of a Binary Tree

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Given the following binary tree:  root = [3,5,1,6,2,0,8,null,null,7,4]


 

Example 1:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
Example 2:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.
 

Note:

All of the nodes' values will be unique.
p and q are different and both values will exist in the binary tree.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路如下：

要记住两个点，从跟节点到目标节点p，q 因该是root->->…(一直都是单节点)，到最近父节点分拆分别指向p，q(p,q相等除外)
所以要找的节点有以下特点：

前面都是单路径只有，只有目标节点在其自身或子树下有能左右两个正确返回
root到p，q的路径上，到最进夫节点分叉节点

如果使用中序遍历，p，q之间的结果节点应该是中序遍历中节点最浅的节点

/**
 * Definition for TreeNode.
 * type TreeNode struct {
 *     Val int
 *     Left *ListNode
 *     Right *ListNode
 * }
 */
 package main

 //初始化_ans以防未找到空指针
 var _ans *TreeNode =&TreeNode{}

 func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
	RecursionAns(root,p,q)
    return _ans
}


//递归
//由于是二叉树，只有一个节点的子节点能包含两个节点，该节点的父节点只能有左节点有或右节点有搜索节点
func RecursionAns(node,p,q *TreeNode) bool{
	ret := false
	if node ==nil {
		return false
	}
	mid ,left,right := 0,0,0
	if RecursionAns(node.Left,p,q) {
		left = 1
	}
	if RecursionAns(node.Right,p,q) {
		right = 1
	}
	if node == p||node == q{
		mid = 1
	}
	if (mid + left + right) > 1{
		 ret = true
	}
	//如果自己或者左右大于2证明找到该节点，由于是二叉树全局只有一个节点符合条件不知道能否体检结束
	if (mid + left +right) >= 2{
		_ans = node
	}
	return ret
}

221-MaximalSquare

Posted on 2020-01-11

221-MaximalSquare

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximal-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

可以想到当前节点如果能作为最大的正方形+1，那他上面一定是一个正方形，且形成的正方形，包含其上左右三个点，
所以以该点为底点的变成应该是上左右三点变长+1，dp如下

func maximalSquare(matrix [][]byte) int {
	//使用dp转移
	//dp[i][j] = min(dp[i-1,j-1],dp[i-1],[j],dp[j]) +1
	rows := len(matrix)
	if rows <= 0 {
		return 0
	}
	cols:= len(matrix[0])
	dp:= make([][]int,len(matrix))
	len := 0
	//初始化dp数组
	for i:=0;i<rows;i++{
		dp[i] = make([]int,cols)
		for j :=0 ;j<cols;j++{
			if matrix[i][j] == '1' {
				if i==0||j==0 {
					dp[i][j] = 1
				}else{
					dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) +1
				}
				}else{
				dp[i][j]=0
			}
			if dp[i][j] > len{
				len = dp[i][j]
			}
		}
	}
	return len *len
}

199-BinaryTreeRightSideView

Posted on 2020-01-11

199-BinaryTreeRightSideView

分析实际上就是，输出每层最右边的节点，
采用双数组存储当前层和上一层，交替上一层最后一个加入输出，同时弹出记录当前层，结束后当前层切换为上一层递归执行

func rightSideView(root *TreeNode) []int {
	//二叉树层次便利，返回每层最右边的
	ret := make([]int,0)
	if root == nil {
		return ret
	}
	//lastLevelList
	lastLevelList := make([]*TreeNode,0,100)
	lastLevelList = append(lastLevelList,root)
	//保证可弹出下一层
	for len(lastLevelList) != 0 {
		//addlastLevel lastnode
		ret = append(ret,lastLevelList[len(lastLevelList)-1].Val)
		nowLevelList := make([]*TreeNode,0,100)
		//便利当前层把存储下一层
		for i := range lastLevelList{
			if lastLevelList[i].Left !=nil{
				nowLevelList = append(nowLevelList,lastLevelList[i].Left)
			}
			if lastLevelList[i].Right != nil{
				nowLevelList = append(nowLevelList,lastLevelList[i].Right)
			}
		}
		//当前层变成下一层
		lastLevelList = nowLevelList
	}
	return ret
}

114-FlattenBinaryTreetoLinkedList

Posted on 2020-01-11

114-FlattenBinaryTreetoLinkedList

思路1-递归

通过观察我们可以发现原地咱开就是，把左子树变空，右子树要么接到左子树的右边要么接到当前节点的右边
递归实现如下：
bugfree 开心😄

func flattenRe(node *TreeNode) *TreeNode{
	if node == nil{
		return nil
	}
	nodeLeft := flattenRe(node.Left)
	nodeRight := flattenRe(node.Right)
	tmp := nodeLeft
	if nodeLeft != nil{
		node.Right = nodeLeft
		for tmp.Right != nil {
			tmp = tmp.Right
		}
		tmp.Right = nodeRight
	}else{
		node.Right = nodeRight
	}
	node.Left = nil
	return node
}

思路二非递归原地打开

处理完当前节点，把直接把指针知道当前节点的右节点上，由于当前节点所有子节点都被移到右节点了，所以不用盏就可以实现遍历

func flatten2 (root *TreeNode){
	if root == nil {
		return
	}
	var temp  *TreeNode
	for root != nil {
		if root.Left != nil{
			temp = root.Left
			for temp.Right != nil {
				temp = temp.Right
			}
			temp.Right = root.Right
			root.Right = root.Left
		}
		root = root.Right
	}
	return
}

62不同路径

Posted on 2020-01-11

不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。

问总共有多少条不同的路径？



例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答

本题压缩了空间，下一层的dp只依赖上一层和当层前一个元素所以不用保存，所有dp状态，只需要一层dp值和记录的当前值就好啦。

func uniquePaths(m int, n int) int {
	//动态转移方程 F(m,n) = F(m,n-1)+F(m-1,n)\
	//F(m,n) =1 (m=0||n=0)
	fn := make([][]int,1)
	fn[0]= make([]int,n)
	pre := -1
	for i :=0;i<m;i++{
		for j:=0;j<n;j++{
			if i==0|| j==0{
				fn[0][j] = 1
			}else {
				fn[0][j] +=  pre
			}
			pre = fn[0][j]
		}
	}
	return fn[0][n-1]
}

验证二叉搜索树

思路1

思路2

总结

常用数据结构

调度系统设计精要

需求调研

应用场景

linux调度例子

34-SearchRange

方法1

放在一个函数方法

236. Lowest Common Ancestor of a Binary Tree

思路如下：

221-MaximalSquare

解题思路

199-BinaryTreeRightSideView

114-FlattenBinaryTreetoLinkedList

思路1-递归

思路二 非递归原地打开

不同路径

解答

思路二非递归原地打开