Liam's Blog


  • Home

  • Archives

  • Tags

  • Categories

  • Photos

  • About

Prolog Programming for AI - Chapter 5 Notes and Exercises (5.1 ~ 5.2)

Posted on 2018-09-28 | Post modified 2018-09-30 | In Languages , Prolog , Cut

Preventing backtracking

Prolog will automatically backtrack if this is necessary for satisfying a goal.

Now, consider a double-step function. The relation between X and Y can be specified by three rules:

Rule 1: if X < 3 then Y = 0

Rule 2: if 3 <= X and X < 6 then Y = 2

Rule 3: if 6 <= X then Y = 3

This can be written in Prolog as a binary relation f(X, Y) as follows:

1
2
3
f(X, 0) :- X < 3.         % Rule 1
f(X, 2) : 3 =< X, X < 6. % Rule 2
f(X, 3) : 6 =< X. % Rule 3

This program assumes that before f(X, Y) is executed X is already instantiated to a number as this is required by the comparison operators.

Read more »

LeetCode #108 Convert Sorted Array to Binary Search Tree

Posted on 2018-09-28 | Post modified 2018-09-28 | In Languages , LeetCode , Python , Difficulties , Algorithms , Data Structures , Easy , Divide and Conquer , Binary Search Tree

Problem

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example

1
2
3
4
5
6
7
8
9
Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

0
/ \
-3 9
/ /
-10 5
Read more »

LeetCode #106 Construct Binary Tree from Inorder and Postorder Traversal

Posted on 2018-09-28 | Post modified 2018-09-29 | In Languages , LeetCode , Python , Difficulties , Algorithms , Data Structures , Medium , Binary Tree , Divide and Conquer

Problem

Given inorder and postorder traversal of a tree, construct the binary tree.

Example

1
2
inorder = [9,3,15,20,7]
postorder = [9,15,7,20,3]

Return the following binary tree:

1
2
3
4
5
  3
/ \
9 20
/ \
15 7
Read more »

LeetCode #590 N-ary Tree Postorder Traversal

Posted on 2018-09-28 | Post modified 2018-09-28 | In Languages , LeetCode , Python , Difficulties , Data Structures , Easy , Tricks , Tree

Problem

Given an n-ary tree, return the postorder traversal of its nodes’ values.

Example

given a 3-ary tree:

img

Return its postorder traversal as: [5,6,3,2,4,1].

Read more »

LeetCode #105 Construct Binary Tree from Preorder and Inorder Traversal

Posted on 2018-09-28 | Post modified 2018-09-28 | In Languages , LeetCode , Python , Difficulties , Algorithms , Data Structures , Medium , Binary Tree , Divide and Conquer , Tricks

Problem

Given preorder and inorder traversal of a tree, construct the binary tree.

Example

1
2
preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

1
2
3
4
5
  3
/ \
9 20
/ \
15 7

Note

You may assume that duplicates do not exist in the tree.

Read more »

LeetCode #889 Construct Binary Tree from Preorder and Postorder Traversal

Posted on 2018-09-28 | Post modified 2018-09-28 | In Languages , LeetCode , Python , Difficulties , Algorithms , Data Structures , Medium , Binary Tree , Divide and Conquer

Problem

Return any binary tree that matches the given preorder and postorder traversals.

Values in the traversals pre and post are distinct positive integers.

Example

1
2
Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

Note

  • 1 <= pre.length == post.length <= 30
  • pre[] and post[] are both permutations of 1, 2, ..., pre.length.
  • It is guaranteed an answer exists. If there exists multiple answers, you can return any of them.
Read more »

LeetCode #153 Find Minimum in Rotated Sorted Array

Posted on 2018-09-27 | Post modified 2018-09-27 | In Languages , LeetCode , Python , Difficulties , Algorithms , Medium , Divide and Conquer

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Examples

Example 1:

1
2
Input: [3,4,5,1,2] 
Output: 1

Example 2:

1
2
Input: [4,5,6,7,0,1,2]
Output: 0
Read more »

Analysis of Algorithms Lecture 9

Posted on 2018-09-27 | Post modified 2018-10-02 | In Algorithms , Basic Concepts , Divide and Conquer
Read more »

LeetCode #477 Total Hamming Distance

Posted on 2018-09-27 | Post modified 2018-09-27 | In Languages , LeetCode , Python , Difficulties , Algorithms , Medium , Backtracking , Bit Manipulation

Problem

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example

1
2
3
4
5
6
7
Input: 4, 14, 2

Output: 6

Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just
showing the four bits relevant in this case). So the answer will be:
HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.
Read more »

LeetCode #559 Maximum Depth of N-ary Tree

Posted on 2018-09-27 | Post modified 2018-09-27 | In Languages , LeetCode , Python , Difficulties , Algorithms , Easy , Depth-first Search

Problem

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example

img

We should return its max depth, which is 3.

Read more »
1…8910…18
Liam Wang

Liam Wang

Liam's Personal Blog

174 posts
133 categories
64 tags
© 2019 Liam Wang
Powered by Hexo
Theme - NexT.Muse