A Literal) is a notation for representing a fixed value in source code.
Almost all programming languages have notations for atomic values such as integers, floating-point numbers, and strings.
eg.
int a = 1;
String s = "cat";
an integer literal is an integer whose value is directly represented in source code.
Some experienced developers don’t use protected since it cannot provide clean data hiding.
Why is that?
Remembering in the post [Java OOP] Java modifier and Access Level, we got this:
Note: Java default access setting is ‘No modifier’, which is also called ‘Package Private’.
Another note: by saying ‘subclass’, it means subclass declared in another package.
And in [Design] Composition Over Inheritance, we know that basically inheritance breaks encapsulation.
inheritance is seldom the best tool and is not as flexible
the protected members form an interface towards subclasses (which is bad)
interfaces are tricky to get right and document properly
So, it’s better not to make the class inheritable and instead make sure it’s as flexible as possible (and no more) by using other means.
A excellent answer from Sam Brand:
They tend to lead to YAGNI issues. Unless you have a descendant class that actually does stuff with the protected member, make it private.
“You aren’t gonna need it” (acronym: YAGNI) is a principle of extreme programming (XP) that states a programmer should not add functionality until deemed necessary.
They tend to lead to LSP issues. Protected variables generally have some intrinsic invariance associated with them (or else they’d be public). Inheritors then need to maintain those properties, which people can screw up or willfully violate.
Substitutability is a principle in OOP. It states that if S is a subtype of T, then objects of type T may be replaced with objects of type S without altering any of the desirable properties of that program
Liskov substitution principle (LSP) is a particular definition of a subtyping relation introduced by Barbara Liskov in 1987
They tend to violate OCP. If the base class makes too many assumptions about the protected member, or the inheritor is too flexible with the behavior of the class, it can lead to the base class' behavior being modified by that extension.
open/closed principle states “software entities (classes, modules, functions, etc.) should be open for extension, but closed for modification”.
That is, such an entity can allow its behaviour to be extended without modifying its source code.
This is especially valuable in a production environment, where changes to source code may necessitate code reviews, unit tests, and other such procedures to qualify it for use in a product
They tend to lead to inheritance for extension rather than composition. This tends to lead to tighter coupling, more violations of SRP, more difficult testing, and a slew of other things that fall within the ‘favor composition over inheritance’ discussion.
single responsibility principle states that every class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility
ClassA in packageA:
package packA;
import packB.ClassB;
public class ClassA {
protected int val = 10;
protected String getColor() {
return "colored";
}
public static void main(String[] args) {
ClassA ins = new ClassA();
System.out.println("val is " + ins.val);
System.out.println("color is " + ins.getColor());
System.out.println();
ClassB ins2 = new ClassB();
System.out.println("val is " + ins2.val);
System.out.println("color is " + ins2.getColor());
}
}
ClassB in packageB:
package packB;
import packA.ClassA;
public class ClassB extends ClassA {
public ClassB() {
val = 5;
}
public String getColor() {
return super.getColor();
}
}
Execution result:
val is 10
color is colored
val is 5
color is colored
The code shows how ClassB is able to access 1 protected variable and 1 protected method.
A UML class diagram describes the object and information structures used by your application, both internally and in communication with its users.
Taken from here.
Shape
Element
Description
1
Class
A definition of objects that share given structural or behavioral characteristics. For more information, see Properties of types on UML class diagrams.
1
Classifier
The general name for a class, interface, or enumeration. Components, use cases, and actors are also classifiers.
2
Collapse/ Expand control
If you cannot see the details of a classifier, click the expander at upper-left of the classifier. You might also have to click the [+] on each segment.
3
Attribute
A typed value attached to each instance of a classifier.
To add an attribute, click the Attributes section and then press ENTER. Type the signature of the attribute. For more information, see Properties of attributes on UML class diagrams.
4
Operation
A method or function that can be performed by instances of a classifier. To add an operation, click the Operations section and then press ENTER. Type the signature of the operation. For more information, see Properties of operations on UML class diagrams.
5
Association
A relationship between the members of two classifiers. For more information, see Properties of associations on UML class diagrams.
5a
Aggregation
An association representing a shared ownership relationship. The Aggregation property of the owner role is set to Shared.
5b
Composition
An Association representing a whole-part relationship. The Aggregation property of the owner role is set to Composite.
6
Association Name
The name of an association. The name can be left empty.
7
Role Name
The name of a role, that is, one end of an association. Can be used to refer to the associated object. In the previous illustration, for any Order O, O.ChosenMenu is its associated Menu.
Each role has its own properties, listed under the properties of the association.
8
Multiplicity
Indicates how many of the objects at this end can be linked to each object at the other. In the example, each Order must be linked to exactly one Menu.
* means that there is no upper limit to the number of links that can be made.
9
Generalization
The specific classifier inherits part of its definition from the general classifier. The general classifier is at the arrow end of the connector. Attributes, associations, and operations are inherited by the specific classifier.
Use the Inheritance tool to create a generalization between two classifiers.
For an array, we can build a SegmentTree for it, each node stores an extra attribute count to denote the number of elements in the the array which value is between interval start and end. (The array may not fully filled by elements)
Design a query method with three parameters root, start and end, find the number of elements in the in array’s interval [start, end] by the given root of value SegmentTree.
Similar.
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, count;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int count) {
* this.start = start;
* this.end = end;
* this.count = count;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param root, start, end: The root of segment tree and
* an segment / interval
*@return: The count number in the interval [start, end]
*/
public int query(SegmentTreeNode root, int start, int end) {
if (root == null || start > end) {
return 0;
} else if (root.start > end || root.end < start) {
return 0;
} else if (start <= root.start && root.end <= end) {
return root.count;
}
int mid = (root.start + root.end) / 2;
return query(root.left, start, Math.min(mid, end)) +
query(root.right, Math.max(mid + 1, start), end);
}
}
For an integer array (index from 0 to n-1, where n is the size of this array), in the corresponding SegmentTree, each node stores an extra attribute max to denote the maximum number in the interval of the array (index from start to end).
Design a query method with three parameters root, start and end, find the maximum number in the interval [start, end] by the given root of segment tree.
Slightly difficult as we need to keep in mind the following:
what’s the return condition? (start and end is large enough to cover the entire range)
how to handle overlapping case? (find min-point first and then analyse case by case)
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, max;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int max) {
* this.start = start;
* this.end = end;
* this.max = max
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param root, start, end: The root of segment tree and
* an segment / interval
*@return: The maximum number in the interval [start, end]
*/
public int query(SegmentTreeNode root, int start, int end) {
// write your code here
if (root == null || start > end) {
return -1;
} else if (root.start > end || root.end < start) {
return -1;
} else if (root.start >= start && root.end <= end) {
return root.max;
}
int mid = (root.start + root.end) / 2;
return Math.max(query(root.left, start, Math.min(mid, end)),
query(root.right, Math.max(mid + 1, start), end));
}
}
For a Maximum Segment Tree, which each node has an extra value max to store the maximum value in this node’s interval.
Implement a modify function with three parameter root, index and value to change the node’s value with [start, end] = [index, index] to the new given value. Make sure after this change, every node in segment tree still has the max attribute with the correct value.
It’s very similar to Segment Tree Modify/search.
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, max;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int max) {
* this.start = start;
* this.end = end;
* this.max = max
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param root, index, value: The root of segment tree and
*@ change the node's value with [index, index] to the new given value
*@return: void
*/
public void modify(SegmentTreeNode root, int index, int value) {
helper(root, index, value);
}
private int helper(SegmentTreeNode node, int target, int val) {
if (node.start > target || node.end < target) {
// no update, then just return max as normal
return node.max;
} else if (node.start == node.end && node.start == target) {
node.max = val;
return val;
} else {
// check left and right, and update max value accordingly
node.max = Math.max(helper(node.left, target, val),
helper(node.right, target, val));
return node.max;
}
}
}
The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interval.
start and end are both integers, they should be assigned in following rules:
The root’s start and end is given by build method. The left child of node A has start=A.left, end=(A.left + A.right) / 2. The right child of node A has start=(A.left + A.right) / 2 + 1, end=A.right. if start equals to end, there will be no children for this node.
Implement a build method with a given array, so that we can create a corresponding segment tree with every node value represent the corresponding interval max value in the array, return the root of this segment tree.
Similar.
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end, max;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end, int max) {
* this.start = start;
* this.end = end;
* this.max = max
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param A: a list of integer
*@return: The root of Segment Tree
*/
public SegmentTreeNode build(int[] A) {
if (A == null || A.length == 0) {
return null;
}
return helper(A, 0, A.length - 1);
}
private SegmentTreeNode helper(int[] A, int start, int end) {
if (start > end) {
return null;
}
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start == end) {
node.max = A[start];
return node;
} else {
node.left = helper(A, start, (start + end) / 2);
node.right = helper(A, (start + end) / 2 + 1, end);
if (node.right != null) {
node.max = Math.max(node.left.max, node.right.max);
} else {
node.max = node.left.max;
}
}
return node;
}
}
The structure of Segment Tree is a binary tree which each node has two attributes start and end denote an segment / interval.
start and end are both integers, they should be assigned in following rules:
The root’s start and end is given by build method. The left child of node A has start=A.left, end=(A.left + A.right) / 2. The right child of node A has start=(A.left + A.right) / 2 + 1, end=A.right. if start equals to end, there will be no children for this node.
Implement a build method with two parameters start and end, so that we can create a corresponding segment tree with every node has the correct start and end value, return the root of this segment tree.
A simple top-down run through.
/**
* Definition of SegmentTreeNode:
* public class SegmentTreeNode {
* public int start, end;
* public SegmentTreeNode left, right;
* public SegmentTreeNode(int start, int end) {
* this.start = start, this.end = end;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
*@param start, end: Denote an segment / interval
*@return: The root of Segment Tree
*/
public SegmentTreeNode build(int start, int end) {
// write your code here
if (start > end) {
return null;
}
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start < end) {
node.left = build(start, (start + end) / 2);
node.right = build((start + end) / 2 + 1, end);
}
return node;
}
}
Segment tree is a tree data structure for storing intervals, or segments.
Can be used to search the max/min or sum values in a range.
modify = O(log n)
query = O(log n)
build = O(n)
[LintCode] Segment Tree Build
[LintCode] Segment Tree Build II
[LintCode] Segment Tree Modify
[LintCode] Segment Tree Query
[LintCode] Segment Tree Query II
Given a matrix where every element is either ‘O’ or ‘X’, find the largest sub-square surrounded by ‘X’. (meaning that the 4 edges are filled with ‘X’)
Example Input:
{'X', 'O', 'X', 'X', 'X'},
{'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'O', 'X', 'O'},
{'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'O'},
Output: 3. The square submatrix starting at (1, 1) is the largest sub-squre.
Example Input:
{'X', 'O', 'X', 'X', 'X', 'X'},
{'X', 'O', 'X', 'X', 'O', 'X'},
{'X', 'X', 'X', 'O', 'O', 'X'},
{'X', 'X', 'X', 'X', 'X', 'X'},
{'X', 'X', 'X', 'O', 'X', 'O'},
Output: 4. The square submatrix starting at (0, 2) is the largest
Read a very similar question - [Question] Maximum Square Sub-matrix With All 1s
Typical DP question. Now the solution is to build 2 arrays to cache info. One horizontally and one, vertical.
create two auxiliary arrays hor[N][N] and ver[N][N].
hor[i][j] is the number of horizontal continuous ‘X’ characters till mat[i][j] in mat[][].
ver[i][j] is the number of vertical continuous ‘X’ characters till mat[i][j] in mat[][].
mat[6][6] = X O X X X X
X O X X O X
X X X O O X
O X X X X X
X X X O X O
O O X O O O
hor[6][6] = 1 0 1 2 3 4
1 0 1 2 0 1
1 2 3 0 0 1
0 1 2 3 4 5
1 2 3 0 1 0
0 0 1 0 0 0
ver[6][6] = 1 0 1 1 1 1
2 0 2 2 0 2
3 1 3 0 0 3
0 2 4 1 1 4
1 3 5 0 2 0
0 0 6 0 0 0
After we got these, start from the bottom-right corner row by row up… For every mat[i][j], we compare hor[i][j] with ver[i][j] and pick the smaller one.
All we need to do next, is to check the other 2 edges. This solution is O(n3).
C++ code provided by G4G:
int findSubSquare(int mat[][N])
{
int max = 1; // Initialize result
// Initialize the left-top value in hor[][] and ver[][]
int hor[N][N], ver[N][N];
hor[0][0] = ver[0][0] = (mat[0][0] == 'X');
// Fill values in hor[][] and ver[][]
for (int i=0; i<N; i++)
{
for (int j=0; j<N; j++)
{
if (mat[i][j] == 'O')
ver[i][j] = hor[i][j] = 0;
else
{
hor[i][j] = (j==0)? 1: hor[i][j-1] + 1;
ver[i][j] = (i==0)? 1: ver[i-1][j] + 1;
}
}
}
// Start from the rightmost-bottommost corner element and find
// the largest ssubsquare with the help of hor[][] and ver[][]
for (int i = N-1; i>=1; i--)
{
for (int j = N-1; j>=1; j--)
{
// Find smaller of values in hor[][] and ver[][]
// A Square can only be made by taking smaller
// value
int small = getMin(hor[i][j], ver[i][j]);
// At this point, we are sure that there is a right
// vertical line and bottom horizontal line of length
// at least 'small'.
// We found a bigger square if following conditions
// are met:
// 1)If side of square is greater than max.
// 2)There is a left vertical line of length >= 'small'
// 3)There is a top horizontal line of length >= 'small'
while (small > max)
{
if (ver[i][j-small+1] >= small &&
hor[i-small+1][j] >= small)
{
max = small;
}
small--;
}
}
}
return max;
}