Tag Archives: algorithm

Conversion from hexadecimal to decimal

Problem Description:
write a program that accepts a hexadecimal value string and outputs the decimal string of the value (note that there may be multiple sets of data in a test case).

Input:
0xa

Output:
10

#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
vector<char> conclude;


int CharToInt(char x){
    if (x >= '0' && x <= '9'){
        return x - '0';
    }else{
        return x - 'A' + 10;
    }
}
void Convert(string str, int x){
    int number = 0;
    for(int i = 0; i < str.size(); ++i){
        number *= x;
        number += CharToInt(str[i]);
    }
    printf("%d\n", number);
}

int main(){
    string str;
    while (cin >> str){
        str = str.substr(2);
        Convert(str, 16);
    }
    return 0;
}

High precision addition function template

string P  (string & num,string add){
    int g=0;
    if(num.length()<add.length()){
        string t=num;
        num=add;
        add=t;
    }
    string t (num.length()-add.length(),'0');
    add= t+add;
    int len1=num.length(),len2=add.length();
    for(int i=len1-1;i>=0;i--){
        int t=((num[i]-'0') +(add[i]-'0') + g);
        num[i]=t%10+'0';
        g=t/10;
    }
    if(g!=0){
        num.insert(0,string(1,(char)g+'0'));
    }
    return num;
}

 

Leetcode-234: palindrome linked list

Topic describes
Determine whether a linked list is a palindrome list.
// 1 2 nil
// 1 2 1 nil
// 1 2 2 1 nil
Thought analysis
The fast and slow pointer finds the midpoint of the linked list and splits the midpoint and reverses the tail list to compare whether the values of the head and tail list are equal in turn
Code implementation

func isPalindrome(head *ListNode) bool {
	if head == nil {
		return true
	}
	fast := head.Next
	slow := head
	for fast != nil && fast.Next != nil {
		fast = fast.Next.Next
		slow = slow.Next
	}

	tail := reverse(slow.Next)
	slow.Next = nil

	for head != nil && tail != nil {
		if head.Val != tail.Val {
			return false
		}
		head = head.Next
		tail = tail.Next
	}
	return true
}

func reverse(head *ListNode) *ListNode {
	if head == nil {
		return head
	}
	var pre *ListNode
	for head != nil {
		temp := head.Next
		head.Next = pre
		pre = head
		head = temp
	}
	return pre
}

Random forest algorithm learning

Random forest algorithm learning
When I was doing Kaggle recently, I found that the random forest algorithm had a very good effect on classification problems. In most cases, the effect was far better than that of SVM, log regression, KNN and other algorithms. So I want to think about how this algorithm works.
To learn random forest, we first briefly introduce the integrated learning method and decision tree algorithm. The following is only a brief introduction of these two methods (see Chapter 5 and Chapter 8 of statistical learning Methods for specific learning recommendations).


Bagging and Boosting concepts and differences
This part is mainly to study the: http://www.cnblogs.com/liuwu265/p/4690486.html
Random forest belongs to Bagging algorithm in Ensemble Learning. In ensemble learning, the algorithms are mainly divided into Bagging algorithm and Boosting algorithm. Let’s first look at the characteristics and differences between the two approaches.
Bagging (Bagging)
The algorithm process of Bagging is as follows:

    randomly draw n training samples from the original sample set using the Bootstraping method, conduct a total of k rounds of drawing, and obtain k training sets. (K training sets are independent of each other, and elements can be repeated.) For k training sets, we train k models (these models can be determined according to specific problems, such as decision tree, KNN, etc.) for classification problems: classification results are generated by voting; For the regression problem, the mean value of the predicted results of k models is taken as the final prediction result. (all models are equally important)

Boosting, Boosting
Boosting algorithm process is as follows:

    establishes weight wi for each sample in the training set, indicating the attention paid to each sample. When the probability of a sample being misclassified is high, it is necessary to increase the weight of the sample. Each iteration is a weak classifier during the iteration process. We need some kind of strategy to combine them as the final model. (For example, AdaBoost gives each weak classifier a weight and combines them linearly as the final classifier. The weaker classifier with smaller error has larger weight)

Bagging, Boosting the main difference

    sample selection: Bagging adopts Bootstrap randomly put back sampling; But Boosting the training set of each round is unchanged, changing only the weight of each sample. Sample weight: Bagging uses uniform sampling with equal weight for each sample. Boosting adjust the sample weight according to the error rate, the greater the error rate, the greater the sample weight. Prediction function: Bagging all prediction functions have equal weight; Boosting the prediction function with lower error has greater weight. Parallel computing: Bagging each prediction function can be generated in parallel; Boosting each prediction function must be generated iteratively in sequence.

The following is the new algorithm obtained by combining the decision tree with these algorithm frameworks:
1) Bagging + decision tree = random forest
2) AdaBoost + decision tree = lifting tree
3) Gradient Boosting + decision tree = GBDT


The decision tree
Common decision tree algorithms include ID3, C4.5 and CART. The model building ideas of the three algorithms are very similar, but different indexes are adopted. The process of building the decision tree model is roughly as follows:
ID3, Generation of C4.5 decision tree
Input: training set D, feature set A, threshold EPS output: decision tree T
If

    D in all samples belong to the same kind of Ck, it is single node tree T, the class Ck as A symbol of the class of the nodes, T if returns A null set, namely no characteristics as the basis, it is single node tree T, and D in implementing cases the largest class Ck as A symbol of the class of the node, return T otherwise, calculating the feature of D information gain in A (ID3)/information gain ratio (C4.5), choose the greatest feature of the information gain if Ag Ag information gain (than) is less than the threshold value of eps, is T for single node tree, and will be the biggest in implementing occuring D class Ck as A symbol of the class of the node, Otherwise, D is divided into several non-empty subsets Di according to the feature Ag, and the class with the largest number of real cases in Di is taken as the marker to construct the child node, and the tree T is formed by the node and its child nodes. T is returned to the ith child node, with Di as the training set and a-{Ag} as the feature set. Recursively, 1~5 is called to obtain the subtree Ti, and Ti

is returned
Generation of CART decision tree
Here is a brief introduction to the differences between CART and ID3 and C4.5.

    CART tree is a binary tree, while ID3 and C4.5 can be multi-partite trees. When generating subtrees, CART selects one feature and one value as the segmentation point. The basis for generating two subtrees is gini index, and the feature with the minimum gini index and the segmentation point are selected to generate subtrees

Pruning of a decision tree
The pruning of decision tree is mainly to prevent overfitting, but the process is not described in detail.
The main idea is to trace back upward from the leaf node and try to prune a node to compare the loss function value of the decision tree before and after pruning. Finally, we can get the global optimal pruning scheme through dynamic programming (tree DP, acMER should know).


Random Forests
Random forest is an important integrated learning method based on Bagging, which can be used for classification, regression and other problems.
Random forests have many advantages:
Has a very high accuracy the introduction of randomness, it is not easy to make random forests after fitting of the randomness of introduction, makes the random forest has a good ability to resist noise can deal with high dimension data, and don’t have to do feature selection can not only deal with discrete data, also can deal with continuous data, data set without standardized training speed, can be variable importance easy parallelization
Disadvantages of random forest:
When the number of decision trees in the random forest is large, the space and time required for training will be large. The random forest model has a lot of problems to explain. It is a black box model
Similar to Bagging process described above, the construction process of random forest is roughly as follows:

    from the original training focus Bootstraping method is used to back the sampling random select m sample, sampling conducted n_tree time, generate n_tree a training set for n_tree a training set, we respectively training n_tree a decision tree model for a single decision tree model, assuming that the number of training sample characteristics of n, so every time divided according to the information gain/information gain ratio/gini index, choose the best characteristics of split each tree has been divided like this, until all the training sample in the node belong to the same class. In the process of decision tree splitting, the random forest is composed of multiple decision trees generated without pruning. For the classification problem, the final classification result is decided by voting according to multiple tree classifiers. For regression problems, the mean of predicted values of multiple trees determines the final prediction result

[sum of code] report


personal blog: http://fuxuemingzhu.cn/


directory
Double pointer list generation loop
The date of

Title address: https://leetcode.com/problems/sum-of-square-numbers/discuss/
Topic describes
Given a non-negative integer c, your task is to decide whether there’s two integers a and b such that a2 + b2 = c.
Example 1:

Input: 5
Output: True
Explanation: 1 * 1 + 2 * 2 = 5

Example 2:

Input: 3
Output: False

Subject to
Can a number consist of the sum of squares of two Numbers?
The problem solving method
Double pointer
The two Pointers are closer to the center, so it’s easier to understand.

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        left = 0
        right = int(c ** 0.5)
        while left <= right:
            cur = left ** 2 + right ** 2
            if cur < c:
                left += 1
            elif cur > c:
                right -= 1
            else:
                return True
        return False
                      

List generation
Xrange is a spanning form, and range returns a list. Determine if the number left after removing a square is a square.

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        def is_square(N):
            return int(N ** 0.5) ** 2 == N
        
        return any(is_square(c - a ** 2) for a in xrange(int(c ** 0.5) + 1))                

cycle
Use the loop to see if there is an A, so that c minus a squared is a perfect square.
There are a lot of ways to tell if something is a perfect square, but I’m going to use the simplest way, which is to take the square root and then square it to see if it’s equal.
The Python solution is as follows:

class Solution(object):
    def judgeSquareSum(self, c):
        """
        :type c: int
        :rtype: bool
        """
        if c == 0: return True
        for a in range(1, int(math.sqrt(c) + 1)):
            b = c - a * a
            if int(math.sqrt(b)) ** 2 == b:
                return True
        return False

C++ solution is as follows:

class Solution {
public:
    bool judgeSquareSum(int c) {
        if (c == 0) return true;
        for (int a = 1; a < (int) sqrt(c) + 1; ++a){
            double b = sqrt(c - a * a);
            if (b == (int) b){
                return true;
            }
        }
        return false;
    }
};

The date of
August 24, 2017
November 24, 2018 — starting on Sunday! A week has passed

[leetcode] 926. Flip string to monotone increasing problem solving report (Python)


personal blog: http://fuxuemingzhu.cn/


directory
Prefix calculates dynamic programming. The Prefix calculates dynamic programming
Reference Date

Title address: https://leetcode.com/problems/flip-string-to-monotone-increasing/description/
Topic describes
A string of '0's and '1's is monotone increasing if it consists of some number of '0's (possibly 0), followed by some number of '1's (also possibly 0.)
We are given a string S of '0's and '1's, and we may flip any '0' to a '1' or a '1' to a '0'.
Return the minimum number of flips to make S monotone increasing.
Example 1:

Input: "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: "00011000"
Output: 2
Explanation: We flip to get 00000000.

Note:

    1 < = S.length < = 20000S only strings of ‘0’ and ‘1’ characters.

Subject to
A string has a 0 and a 1. Ask at least how many characters to flip to make the string program a monotonically increasing string.
The problem solving method
The Prefix calculation
The second problem of the week, this problem is still a little difficult to think about.
As a general rule, we use the Prefix array to store how many 1s precede each location. Because our ultimate goal is to become a string with a 0 and a 1 in front of it, so we can go through the array, and we’re going to go through all the positions that we’re going through, and we’re going to have to count how many ones we have in front of each position plus how many zeros we have after each position. Because the first 1 has to be flipped to 0, and the second 0 has to be flipped to 1.
Anyway, you just have to figure out how many ones are in front of each position, and then, again, you have to minimize the sum of the ones in front of each position and the zeros after each position.
The P array is used to hold the first 1 of each position. So the number of zeros is going to be the total number of zeros (that is, the total number minus the total number of ones) minus the number of zeros (that is, the current position index minus the number of ones).
It’s order N in time, order N in space.

class Solution(object):
    def minFlipsMonoIncr(self, S):
        """
        :type S: str
        :rtype: int
        """
        N = len(S)
        P = [0] # how many ones
        res = float('inf')
        for s in S:
            P.append(P[-1] + int(s))
        return min(P[i] + (N - P[-1]) - (i - P[i]) for i in range(len(P)))

Dynamic programming
The master on the other side of the station came up with the method, I feel inferior ah, look for a long time to consult to be able to figure it out reluctantly.
This is a bit like buying and selling stocks, both using a two-dimensional dp array that holds the minimum number of times a string ending in 0 or 1 needs to be flipped.
For convenience, I’ve added a space to the DP array, which means that I don’t have to do any flipping before the first string has even started.
So, when we traverse to the I position of the string:

    if the character in this position is '0', then:

The current dp array ending in 0 is equal to the previous DP ending in 0, that is, there is no need to do any operation, at this time, the previous dp must end in 0; The current dp array ending in 1 is equal to Min(the previous dp + 1 ending in 0, the previous DP + 1). The idea here is that there’s a situation where you end up with the previous 0 and you flip the current 0 to 1; The other case is if the previous digit ends in a 1 and the current 0 is flipped to a 1. We need to minimize these two cases. You can end it with either a 0 or a 1.

    if the character in this position is '1', then:

The current dp array ending in 0 is equal to the previous DP ending in 0 + 1, that is, the current 1 is flipped to 0, at this time, the previous one can only end in 0; The current dp array ending in 1 is equal to Min(dp ending in 0, dp ending in 1). So what that means is how many times do I have to flip this position over to end in 1?Of course, it’s the minimum number of times you can flip a 0 or a 1, because you don’t have to flip the 1, but you can flip the 1 anyway. You can end it with either a 0 or a 1.
To sum up, it is important to understand that dp array is the number of states ending in this second dimension number. For example, DP [I][0] is the number of states that need to be flipped if the ith number ends in 0. And then, the thing to understand is that if we’re traversing this character there’s no limit to whether we’re going to flip it or not, so whether we flip it or not we have to take into account how the DP is going to update when this position becomes either 1 or 0. The way to update is to look at the previous state, the previous state to the current state, what you need to do, and how many flips you have.
It’s order N in time, order N in space.

class Solution(object):
    def minFlipsMonoIncr(self, S):
        """
        :type S: str
        :rtype: int
        """
        N = len(S)
        dp = [[0] * 2 for _ in range(N + 1)]
        for i in range(1, N + 1):
            if S[i - 1] == '0':
                dp[i][0] = dp[i - 1][0]
                dp[i][1] = min(dp[i - 1][1], dp[i - 1][0]) + 1
            else:
                dp[i][0] = dp[i - 1][0] + 1
                dp[i][1] = min(dp[i - 1][1], dp[i - 1][0])
        return min(dp[N][0], dp[N][1])

Obviously, in the above approach, each DP shift is only related to the previous state, so you can optimize the spatial complexity to O(1). The code is as follows:

class Solution(object):
    def minFlipsMonoIncr(self, S):
        """
        :type S: str
        :rtype: int
        """
        N = len(S)
        dp = [0] * 2
        for i in range(1, N + 1):
            if S[i - 1] == '0':
                dp[0] = dp[0]
                dp[1] = min(dp[1], dp[0]) + 1
            else:
                dp[1] = min(dp[1], dp[0])
                dp[0] = dp[0] + 1
        return min(dp[0], dp[1])

The resources
https://leetcode.com/problems/flip-string-to-monotone-increasing/discuss/183859/Java-DP-using-O(N)-time-and-O(1)-space
The date of
October 21, 2018 — This week’s race is a bit difficult

Connection authorization failure occurred. Reason: local security service non retryable error solution

Above the exception is when connecting to my, very strange, because DB2 USES for such a long time have never seen this problem, the single from the perspective of the exception message is obviously validation fails, the DB2 connect to a user name and password problem, the problem is why such a problem, when the user name and password are correct.

Study found that after is the system differences, the password can’t be in clear text mode is stored in the system, are saved after through the corresponding encryption algorithm, DB2 USES a SHA256 encryption, and a lot of high version of the Linux the default encryption algorithm is the SHA512, such system to create DB2 user password by SHA512 stored in the system, the connection to DB2 by SHA256 password passwords in encrypted and stored in the system, the result is, of course, failure, the solution is as follows:

Open the /etc/pam.d/system-auth file, find the second line of passwd configuration, change sha512 to Sha256, and save;

Rerun the passwd DB2 user and set the password;

Success;

This will replace the system encryption method with SHA256 and then update the saved password.

Leetcode 34 finds the first and last position of an element in the sorted array (medium)

given an ascending array of integers nums, and a target value target. Find the starting and ending positions in the array for the given target value.

your algorithm’s time complexity must be O(log n).

if there is no target value in the array, return [-1, -1].

example 1 :

enter : nums =,7,7,8,8,10 [5], target = 8
output: [3, 4]

sample 2 :

enter : nums =,7,7,8,8,10 [5], target = 6
output: [1, 1]

thought and code

O(log n) is the complexity of

class Solution {
    public int[] searchRange(int[] nums, int target) {

        int[] res = new int[] {-1, -1};

        if (nums.length < 1) return res;

        int firstIndex = search(nums, target - 1);
        
        // 如果大于target-1 的第一个索引就超级界 或者 第一个索引的值不是target 那么就说明当前数组没有目标值
        if (firstIndex == nums.length || nums[firstIndex] != target) return res;
        else res[0] = firstIndex;
		
        res[1] = search(nums, target) - 1;

        return res;    
    }

    public int search(int[] nums, int target) {
        // 找到大于target值的第一个位置
        int l = 0, r = nums.length;
        while (l < r) {
            int m = l + (r - l) / 2;
            if (target >= nums[m]) l = m + 1;
            else r = m;
        }
        return l;
    }
}

JavaScript realizes the longest substring of non repeated characters

simple rough direct code

is easy to understand with console, the code is as follows:

    var lengthOfLongestSubstring = function (s) {
      var arr = [];
      var max = 0;
      for (let index = 0; index < s.length; index++) {
        var a = arr.indexOf(s[index]);
        console.log(a, s[index], 222)
        if (a != -1) {
          arr.splice(0, a + 1)
          console.log(111, arr, max)
        }
        arr.push(s.charAt(index))
        console.log(arr, 222)
        max = Math.max(arr.length, max)
      }
      return console.log(max, arr)

    };
    lengthOfLongestSubstring('abcdeasasas')

Common attributes and methods of list and map in Dar

list common properties and methods

common property

1,length gets the length of list

main() {
  var list = ['red','yellow','pink'];
  print(list.length);
}

2, judge whether it is empty

main() {
  var list = ['red','yellow','pink'];
  print(list.isEmpty);
}

3, not null

main() {
  var list = ['red','yellow','pink'];
  print(list.isNotEmpty);
}

4, the array flips

main() {
  var list = ['red','yellow','pink'];
  print(list.reversed.toList());
}
(pink, yellow, red)

common method

1, add data

main() {
  var list = ['red','yellow','pink'];
  list.add("green");
  print(list);
}
[red, yellow, pink, green]

2, find data indexOf, find return index, can’t find return -1

main() {
  var list = ['red','yellow','pink'];
  var res = list.indexOf('yellow');
  print(res);

}  

1

3, removed data (‘ value ‘),removeAt(index)

main() {
  var list = ['red','yellow','pink'];
  list.remove('yellow');
  list.removeAt(1);

  print(list);

}  
[red]

4, modify data fillRange(start,end,value) without end

main() {
  var list = ['red','yellow','pink'];
  list.fillRange(1, 2,'green');
  print(list);

}

[red, green, pink]

5, insert data insert(index,value) to the specified position. Insert

from index

main() {
  var list = ['red','yellow','pink'];
  list.insert(1, 'green');
  print(list);
}

[red, green, yellow, pink] 

main() {
  var list = ['red','yellow','pink'];
  list.insertAll(1, ['green','white']);
  print(list);
  
} 
[red, green, white, yellow, pink]

6, convert to string join(‘, ‘), instead of the original list

main() {
  var list = ['red','yellow','pink'];
  var str = list.join(',');
  print(str);

}
 
red,yellow,pink

7, convert string to array split(‘ – ‘), do not change the original string

main() {
  var str = 'red-yellow-pink';
  var list = str.split('-');
  print(list);
  print(str);
  
}  
[red, yellow, pink]
red-yellow-pink

8, for(var item in list) loop list

main() {
  var list = ['red','yellow','pink'];
  for(var item in list) {
    print(item);
  }
}

red
yellow
pink

9,map loop list

main() {
  var list = [1,2,3,4];
  var newList = list.map((value) => value * 2);
  print(newList.toList());
}

10, see if the set satisfies some condition any

main() {
  var list = ['red','yellow','pink'];
  var f = list.any((value) => value == 'red');
  print(f);
  print(list);
  
}

11, through the set can not add repeated collection, so can not get

through the index

main() {
  var set = new Set();
  set.add('red');
  set.add('yellow');
  set.add('pink');
  set.add('red');
  print(set.toList());
}  

[red, yellow, pink]

maps type common properties and methods

1, get all keys

main() {
  var person = {
    'name':'张三',
    'age':20,
  };
  print(person.keys.toList());
}

[name, age]

2, get all values

main() {
  var person = {
    'name':'张三',
    'age':20,
  };
  print(person.values.toList());
}

3, determine whether the attribute isEmpty isEmpty

main() {
  var person = {
    'name':'张三',
    'age':20,
  };
  print(person.isEmpty);
  
}
false

common method

1, remove the specified key data (key)

main() {
  var person = {
    'name':'张三',
    'age':20,
  };
  person.remove('name');
  print(person);
}
{age: 20}

2, addAll({‘ key ‘:’ value ‘})

main() {
  var person = {
    'name':'张三',
    'age':20,
  };
  person.addAll({
    'sex':'男',
  });
  print(person);
}

{name: 张三, age: 20, sex: 男}

3, check to see if the fields are in the map containsKey(key), return true/false does not change the original pair like

main() {
  var person = {
    'name':'张三',
    'age':20,
  };
  var boo = person.containsKey('name');
  print(boo);

}

true

blog address
related documents
github document address

Java foundation — printing Yang Hui triangle

problem: print out a 10-line yanghui triangle
point: two-dimensional array
idea: first analyze the law of yanghui triangle: 1. 2. Each line ends with a 1; 3. Starting from the third row, every non-first and last number is: yangHui[I][j]=yangHui[i-1][j-1]+yangHui[i-1][j]. The code is:

//        1.声明初始化二维数组
        int[][] yangHui = new int[10][];
//        2.给数组的元素赋值
        for (int i = 0; i < yangHui.length; i++) {
            yangHui[i] = new int[i+1];
//            2.1 给首末元素赋值
            yangHui[i][0] = 1;
            yangHui[i][i] = 1;
//            2.2 给每行的非首末元素赋值
            if (i>1){
                for (int j = 1; j <yangHui[i].length-1 ; j++) {
                    yangHui[i][j]=yangHui[i-1][j-1]+yangHui[i-1][j];
                }
            }
        }
        
//        3.遍历二维数组
        for (int i = 0; i < yangHui.length; i++) {
            for (int j = 0; j <yangHui[i].length ; j++) {
                System.out.print(yangHui[i][j]+"\t");
            }
            System.out.println();
        }

Output:

1 1 1 2 1 1 3 3 1

1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28日8 1
1 9 36 84 126 126 84 36 9 1