This is the fifth day of my participation in Gwen Challenge
1. Benefits for programmers to understand data structures and algorithms:
1. The more you understand the algorithm, the more time complexity you can reduce
For example: 2, 4, 8, 16, 32, 64, 128, 256, how to determine if a number is a power of 2? Think: Is it traditional to take this number and modulo it over and over again to see if the remainder is 0? The algorithm will be much faster: 2 to binary is :0010 2 before the number of 1 binary :0001 4-- >0100 3-- >0011 8-- >1000 7-- >0111... If n & (n-1)=0, n meets the requirement.Copy the code / / test
public static void main(String[] args) {
System.out.println(1024 & 1023);
}
/ / the result
0
Process finished with exit code 0
Copy the code2. The more you understand the algorithm, the more you can reduce space complexity and save server resources
For example, calculate the age of China’s 1.6 billion people and rank them in order of smallest to largest. The server CPU has 1 core and 512 MB memory. Consider: if you initialize a 1.6 billion array and sort the large array according to a certain algorithm, the server will jump early. Using algorithm thinking: the age of people is generally between 0 and 200 years old, we initialize an array of 200, the corner of the array represents the age, the value of the array represents the number of people in this age, the simplified code is as follows
public static void main(String[] args) {
int[] peopleArr = new int[200];
// Simulate the population of different age groups
Random random = new Random();
for (int i = 0; i < peopleArr.length; i++) {
peopleArr[i] = random.nextInt(100) * 100;
}
// The population is exported according to age
System.out.println(Arrays.toString(peopleArr));
for (int i = 0; i < peopleArr.length; i++) {
System.out.println("Population is"+i+"Old.");
for (int j = 0; j < peopleArr[i]; j++) {
System.out.print(i+""); } System.out.println(); }}Copy the code3. The more you understand data structures, the better you can cope with different business scenarios.
For example: how to achieve priority queuing of VIP users without using Redis. The JDK has a built-in queue data structure, so classes that use priority queues can solve this problem:Copy the code// The value attribute is the sort weight. The larger the value is, the higher the task is ranked
class Task implements Comparable<Task>{
private int value =1;
public int getValue(a) {
return value;
}
public void setValue(int value) {
this.value = value;
}
@Override
public int compareTo(Task o) {
return this.value>o.value? -1:1;
}
@Override
public String toString(a) {
return "Task{" +
"value=" + value +
'} '; }}/ / run
public static void main(String[] args) {
PriorityBlockingQueue<Task> priorityBlockingQueue = new PriorityBlockingQueue<>();
Task task1 = new Task();
task1.setValue(1);
Task task2 = new Task();
task2.setValue(2);
priorityBlockingQueue.add(task1);
priorityBlockingQueue.add(task1);
priorityBlockingQueue.add(task2);
priorityBlockingQueue.add(task1);
Iterator<Task> iterator = priorityBlockingQueue.iterator();
while(iterator.hasNext()) { System.out.println(iterator.next()); }}// The result is as follows
Task{value=2}
Task{value=1}
Task{value=1}
Task{value=1}
Process finished with exit code 0
Copy the code2, Common data structure analysis:
1.List
// The underlying array, with subscripts, is suitable for doing a lot of query containers
List<Integer> arrayList = new ArrayList<Integer>();
// The bottom list, with Pointers, is suitable for adding and deleting containers
List<Integer> linkedList = new LinkedList<Integer>();
// Thread safe, but slow
Vector<Integer> vector =new Vector<Integer>();
Copy the code2.set
Compared with list, it has the function of de-weighting
// Remove weights out of order, different from insertion order
Set<Integer> hashSet = new HashSet<Integer>();
// Sort to de-duplicate, as opposed to insert
Set<Integer> treeSet = new TreeSet<Integer>();
// Remove weights in the same order as inserts
Set<Integer> linkedHashSet = new LinkedHashSet<Integer>();
Copy the code3.map
A HashMap is implemented using a hash table, unordered in keys and/or values. TreeMap is implemented based on red-black tree data structure and is sorted by key. LinkedHashMap Holder insertion order. Hashtable is implemented in the same way as HashMap, but Hashtable is synchronized.
4.queue
Three, common algorithm principle and code implementation:
1. Pre-knowledge of the algorithm
Calculate the time complexity of your code
// the time complexity is O(1).
int a =1; //O(1)
int b =a+1; //O(1)
for (int i = 0; i < 100; i++) { //O(1)
// It is true that the number of cycles is 100, because 100 is a constant, so the time complexity is still O(1).
}
// The linear time complexity is O(n)
int n;
for (int i = 0; i < n; i++) { //O(n)
}
// Time complexity of logarithms
while (c<n){
c=c*2;
}
/ / derived: c ^ 2 = n = = = > c = log2n (at the bottom with a 2) = = > c = logn, time complexity is O (logn)
// Add another layer of loop
for (int i = 0; i < n; i++) {
while (c<n){
c=c*2; }}// The time complexity is O(nlogn)
// Time complexity O(n^2)
for (int i = 0; i < n; i++) {
for (int i = 0; i < n; i++) {
}
}
/ / variant
for (int i = 0; i < =n; i++) {
for (int j = i; j <= n; j++) {
}
}
// Derivation: (n-1)+(n-2)+(n-3)+...... +1==>n(n-1)/2// Time is O(n^2).
Copy the code2. Another way to switch positions between two numbers
The common practice is to introduce a third number temp. In fact, two numbers can be added and subtracted to complete the position swap, for example:
int a=3,b=2;
a=a+b;
b=a-b;
a=a-b;
Copy the code3. Quicksort
public class QuicklySort {
public static void qSort(int[] arr,int left,int right){
int ll = left;
int rr = right;
int base = arr[left];
// Start from back to front
while (ll<rr && base<=arr[rr]){
rr--;
}
if (ll<rr){
int temp = base;
arr[ll] = arr[rr];
arr[rr]=temp;
// Just changed the position once, can save one calculation
ll++;
}
// If the base number is larger than the base number, switch places
while (ll<rr && base>=arr[ll]){
ll++;
}
if (ll<rr){
int temp = base;
arr[rr] =arr[ll];
arr[ll]=temp;
rr--;
}
// Recursive, residual group quick sorting
if (ll>left){
qSort(arr,left,ll-1);
}
if (rr<right){
qSort(arr,ll+1,right); }}public static void main(String[] args) {
int[] arr = new int[] {1.5.3};
qSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); }}// Run the result
[1.3.5.6.2.4.7.8.9]
Process finished with exit code 0
Copy the code4. Insert sort
public class InsertSort {
public static void main(String[] args) {
// Implement insert sort
System.out.println("Please enter how many numbers you will enter :");
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
int[] arrInput = new int[length];
for (int i = 0; i < length; i++) {
System.out.println("Please enter no."+(i+1) +"Number.");
arrInput[i] = sc.nextInt();
}
for (int i = 1; i < arrInput.length; i++) {
for (int j = i; j >0 ; j--) {
if (arrInput[j]<arrInput[j-1]){
arrInput[j] = arrInput[j]+arrInput[j-1];
arrInput[j-1]=arrInput[j]-arrInput[j-1];
arrInput[j]=arrInput[j]-arrInput[j-1];
}else {
break; } } } System.out.println(Arrays.toString(arrInput)); }}Copy the code5. Hill sort
Hill sort works similarly to insertion sort, but adds the concepts of step, step size, and 2 points
public class ShellSort {
public static void main(String[] args) {
// Implement Hill sort
System.out.println("Please enter how many numbers you will enter :");
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
int[] arrInput = new int[length];
for (int i = 0; i < length; i++) {
arrInput[i] = sc.nextInt();
}
int step = length/2;
while (step >= 1) {
for (int i = step; i < length; i++) {
for (int j = i; j-step >=0; j -= step) {
if (arrInput[j] < arrInput[j - step]) {
arrInput[j] = arrInput[j] + arrInput[j - step];
arrInput[j - step] = arrInput[j] - arrInput[j - step];
arrInput[j] = arrInput[j] - arrInput[j - step];
} else {
break;
}
}
}
step = step / 2; } System.out.println(Arrays.toString(arrInput)); }}Copy the code6. Bubble sort
Classical sort, you know
public class BubbleSort {
public static void main(String[] args) {
// Implement bubble sort
System.out.println("Please enter how many numbers you will enter :");
Scanner sc = new Scanner(System.in);
int length = sc.nextInt();
int[] arrInput = new int[length];
for (int i = 0; i < length; i++) {
System.out.println("Please enter no."+(i+1) +"Number.");
arrInput[i] = sc.nextInt();
}
System.out.println("= = = = = = = = = = = =");
for (int i = 0; i < arrInput.length; i++) {
for (int j = 0; j < arrInput.length-1-i; j++) {
if (arrInput[i]>arrInput[i+1]){
arrInput[i]=arrInput[i]+arrInput[i+1];
arrInput[i+1]=arrInput[i]-arrInput[i+1];
arrInput[i]=arrInput[i]-arrInput[i+1]; } } } System.out.println(Arrays.toString(arrInput)); }}Copy the codeThe application of greedy algorithm and dynamic programming in real life scenarios
1. Simple understanding of greedy algorithms
Greedy algorithm refers to the optimal solution in the current situation, regardless of the future influence, also known as local optimal solution. For example, Lao Wang can get 1W from company A and 2W from company B. Lao Wang went to B company, not considering the long-term development in A and B company.Copy the code2. Greedy algorithm scenario:
There are N free meals of the same grade in a pub in a day. Given the start and end times of all meals, how can you eat the most meals in a day? A. There are 24 hours in a day B. Prioritize the end times of all meals so that you can catch the next one. The start time of the next meal is greater than the end time of the meal code implementation
public class FeastSort implements Comparable<FeastSort>{
private int startTime;
private int endTime;
private int feastNum;
public FeastSort(int startTime, int endTime, int feastNum) {
this.startTime = startTime;
this.endTime = endTime;
this.feastNum = feastNum;
}
// The meal that ends earlier is first
@Override
public int compareTo(FeastSort o) {
return this.endTime>o.endTime?1: -1;
}
public int getStartTime(a) {
return startTime;
}
public void setStartTime(int startTime) {
this.startTime = startTime;
}
public int getEndTime(a) {
return endTime;
}
public void setEndTime(int endTime) {
this.endTime = endTime;
}
public int getfeastNum(a) {
return feastNum;
}
public void setfeastNum(int feastNum) {
this.feastNum = feastNum;
}
@Override
public String toString(a) {
return "FeastSort{" +
"startTime=" + startTime +
", endTime=" + endTime +
", feastNum=" + feastNum +
'} ';
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Please enter total number of meals");
int totalFeastCount = sc.nextInt();
List<FeastSort> feastSortList = new ArrayList<>();
for (int i = 0; i < totalFeastCount; i++) {
System.out.println("Please enter no"+(i+1) +"Start and end of dinner.");
FeastSort feastSort = new FeastSort(sc.nextInt(),sc.nextInt(),i+1);
feastSortList.add(feastSort);
}
// Sort using the compareTo method overridden in FeastSort
feastSortList.sort(null);
// Filter the meal. The start time of the meal must be shorter than the end time of the last meal. The end time cannot exceed 24:00
int currentTime = 0;
for (FeastSort feastSort : feastSortList) {
if (feastSort.getStartTime()>=currentTime && feastSort.getEndTime()<=24){ System.out.println(feastSort); currentTime = feastSort.getEndTime(); }}}}/ / the resultPlease enter total number of meals6Please enter the first1Start and end time of dinner1
3Please enter the first2Start and end time of dinner4
5Please enter the first3Start and end time of dinner2
5Please enter the first4Start and end time of dinner8
16Please enter the first5Start and end time of dinner8
10Please enter the first6Start and end time of dinner19
21
FeastSort{startTime=1, endTime=3, feastNum=1}
FeastSort{startTime=4, endTime=5, feastNum=2}
FeastSort{startTime=8, endTime=10, feastNum=5}
FeastSort{startTime=19, endTime=21, feastNum=6}
Process finished with exit code 0
Copy the code3. Dynamic planning scenario
We know the weight and price of all the goods in the shopping mall. The shopping cart can carry 50kg. Now Lao Wang is selected as the lucky customer and can take away the goods with the shopping cart for free. Idea 1: Divide the price of goods by weight, which is cost-effective first? Example: commodity price :80 50 120 commodity weight :30kg 20kg 40kg price performance: Disproof: the price of commodity 1 and commodity 2 is greater than that of commodity 3 only. Train of thought 1 Incorrect train of thought 2: Use dynamic programming matrix Commodity price :8 yuan 5 12 weight :3kg 2kg 4kg Divide shopping cart into a 1kg unit to make matrix abscissa, and items make ordinate according to the number
public class DynamicProgrammingAlgorithm {
public static void main(String[] args) {
// The weight and price of the goods
int[] value = {50.60.100};
int[] weight = {30.20.40};
// The total number of items and the maximum weight the backpack can carry
int goodsCount = weight.length;
int bagWeight = 50;
// The total number of goods and the weight of the backpack matrix
int[][] gb = new int[goodsCount+1][bagWeight+1];
// Loop each item
for (int i = 1; i <= goodsCount; i++) {
// Dynamically plan the load bearing capacity of the bag, in unit 1
for (int j = 1; j <= bagWeight; j++) {
// Determine that the weight of the current item is less than that of the backpack in dynamic planning
if (weight[i-1]<=j){
// Gb matrix, taking the maximum from the current value and the previous value
gb[i][j]=Math.max(value[i-1]+gb[i-1][bagWeight-weight[i-1]],gb[i][j]);
}else {
// Prove that the backpack can not hold the weight of the item, take the value of the matrix on the row
gb[i][j]=gb[i-1][j];
}
}
}
System.out.println("The maximum value of goods a backpack can carry in the range of heavy is :"+gb[goodsCount][bagWeight]+"Yuan"); }}Copy the codepublic class DynamicProgrammingAlgorithm {
public static void main(String[] args) {
// The weight and price of the goods
int[] value = {70.60.120};
int[] weight = {30.20.40};
// The total number of items and the maximum weight the backpack can carry
int goodsCount = weight.length;
int bagWeight = 50;
// The total number of goods and the weight of the backpack matrix
int[][] gb = new int[goodsCount+1][bagWeight+1];
// Loop each item
for (int i = 1; i <= goodsCount; i++) {
// Dynamically plan the load bearing capacity of the bag, in unit 1
for (int j = 1; j <= bagWeight; j++) {
// Determine that the weight of the current item is less than that of the backpack in dynamic planning
if (weight[i-1]<=j){
// Gb matrix, taking the maximum from the current value and the previous value
gb[i][j]=Math.max(value[i-1]+gb[i-1][j-weight[i-1]]// The value of the new item + the remaining space of the current matrix and the value of the previous item location matrix
,gb[i-1][j]// Take an item if it doesn't fit
);
}else {
// Prove that the backpack can not hold the weight of the item, take the value of the matrix on the row
gb[i][j]=gb[i-1][j];
}
}
}
System.out.println("The maximum value of goods a backpack can carry in the range of heavy is :"+gb[goodsCount][bagWeight]+"Yuan"); }}// Run the resultThe maximum value of goods that a shopping cart can take away within the weight range is:130Meta Process Finished with exit code0
Copy the code