SilMOON

1. io::stdin().read_line(&xx) appends new value on the target which is “xx” in this case.
2. A tuple can have values with different types in it while an array must have the same type.
3. A tuple with explictly type annotations example:

   let x: (i32, f64, u8) = (500, 6.4, 1);
   

4. An array in Rust have a fixed length while a Vector can grow or shrink its size.
5. An array with explictly type and elements’ number annotations example:

   let a: [i32; 5] = [1, 2, 3, 4, 5];
   

6. If [6, 6, 6, 6, 6] is the desirable array, we can declare it in this way:

   let a = [6; 5];
   

7. A good way to create a new instance of a struct that uses most of an old instance’s values but changes some is using update syntax:

   let user2 = User {
    email: String::from("user2@example.com"),
    username: String::from("user2name"),
    ..user1
   };
   

8. An example of using derived traits of custom structs:

   #[derive(Debug)]
   println!("{:?}",user1);
   println!("{:#?}",user1);
   

9. If a struct tuple is defined, when a function want to call an instance of this struct, other struct tuple (even with the same form) cannot be used:

   struct Color (u32,u32,u32);
   struct Point (u32,u32,u32);
   

   In this case, if a function want to call an instance of “Color”, we cannot put an instance of “Point” in it even they have the same form.

10. An example of a struct and its method implementation: ```rust struct Rectangle { width: u32, height: u32, } impl Rectangle { fn area(&self) -> u32 { self.width * self.height }

Given a version number MAJOR.MINOR.PATCH, increment the:

1. MAJOR version when you make incompatible API changes,
2. MINOR version when you add functionality in a backwards-compatible manner, and
3. PATCH version when you make backwards-compatible bug fixes.

Additional labels for pre-release and build metadata are available as extensions to the MAJOR.MINOR.PATCH format.

Given two non-empty linked lists representing two non-negative integers in reverse order. Also, each node contains a single digit. The question is to add the two numbers and return the result in reverse order in another linked list. For instance, as the example given by LeetCode, here’s the input: (2 -> 4 -> 3) + (5 -> 6 -> 4) and the output should be 7 -> 0 -> 8 because 342 + 465 = 807.

Here’s the definition for singly-linked list:

public class ListNode {
  int val;
  ListNode next;
  ListNode(int x) { val = x; }
 }

My very beginning thought when I saw the question was that we can read the two linked lists and reversely store them in two String variables, then read those strings as integers and add them. After that, we can store the result in a new linked list. However, this approach will cause high time complexity and is not easy to implement. So we can simply simulate how numbers add. And due to the reverse order of digits, it’s easier to add numbers from the last digits of intended numbers which are safe for carrying. The code below is my solution:

class Solution {
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);            // this line is to simplify the head
        ListNode ans = head;                        // this line is creating pointer instead of normal assignment
        int tempVal = l1.val + l2.val;
        boolean isGTTen = false;
        if (tempVal >= 10) {
            isGTTen = true;
            tempVal -= 10;
        }
        ans.next = new ListNode(tempVal);
        ans = ans.next;
        while (l1.next != null || l2.next != null) {
            l1 = (l1.next != null) ? l1.next : new ListNode(0);
            l2 = (l2.next != null) ? l2.next : new ListNode(0);
            if (isGTTen) {
                l1.val += 1;
                isGTTen = false;
                if (l1.val ==10) {
                    l1.val = 0;
                    isGTTen = true;
                }
            }
            tempVal = l1.val + l2.val;
            if (tempVal >= 10) {
                isGTTen = true;
                tempVal -= 10;
            }
            ans.next = new ListNode(tempVal);
            ans = ans.next;
        }
        if (isGTTen) {
            ans.next = new ListNode(1);
        }
        return head.next;
    }
}

It’s a really interesting question and definitely help me to understand more about pointer in Java.

Today I saw a question which required us to calculate the maximum sum of the non-consecutive subsequence of a list. An important restriction of this question is that the subsequence must be non-consecutive in the original list. For example, here’s a list [3,5,6,10], all non-consecutive subsequences in this case are [3,6], [5,10] and [3,10]. Therefore the maximum sum of non-consecutive subsequence in this case is 5 + 10 = 15.

In order to solve this problem, we can use brutal method to calculate sums of all non-consecutive subsequences which is neither easy to implement nor efficient. An interesting fact of this problem is that if we go through the original list from the first element, every position has a maximum sum from the first element to this position. And let’s say the position is i which is greater than or equal to 2, so that the maximum sum here is either max(maxSum(list[i-1]), list[i]) or maxSum(list[i-2]) + list[i]. As we can see here, it’s quite easy to solve using the dynamic programming technique.

Here’s the code for this question:

class Solution {
  public static int maxNonConsecSum(int[] inputArray) {
    int[] sumList = inputArray.clone();
    sumList[1] = Math.max(sumList[0], sumList[1]); //base case
    for (int i = 2; i < sumList.length; i++){
      sumList[i] = Math.max(Math.max(sumList[i], sumList[i-1]), sumList[i] + sumList[i - 2]);
    }
    return sumList[sumList.length-1];
  }
}

Recently I found that Flutter is interesting so I decide to start learn it and put some of my notes about Flutter and Dart here.

1. Use arrow notation for one-line functions or methods. For example:

   void main() => runApp(MyApp());
   

2. A widget’s main job is to provide a build() method that describes how to display the widget in terms of other, lower level widgets.
   
   

I got a security alert of my GitPage (this one) today. It was because the dependencies of my site were out of date which might cause some security issues.

I’m not sure if my workaround is the best practice, but it worked so I just put it here.

First I installed Bundler in my computer, then I cd into the directory of my gitpage and run bundle update. I encountered some issues of lacking header files when updating dependencies so that make sure you have ruby-dev (or ruby-devel, depend on your OS) installed.

Running bundle exec jekyll serve to test your website before pushing it to GitHub is highly recommended. I encountered some issues which nested in bundle directory where I installed ruby plugins. Those “issues” are usually date format in example project or symbolic links issues of plugins themselves which don’t affect my project so we can simply add exclude: [vendor] (vendor here can be changed, depends on your directory which contains the bundle and plugins files) in _config.yml.

This post is about the “jewels and stones” problem and my attempt to it.

The purpose is to find elements of string “J” in string “S”, it’s like finding some type of jewels in a pile of stones.

For example, here’s the input: J=”aA”, S=”aAAAbB”, so the output should be 4 in this case.

This is a pretty easy one, so I just put my code below. Although the speed of my program is not the fastest, I can’t check the official answer because I don’t have a premium subscription.

class Solution {
    public int numJewelsInStones(String J, String S) {
        int num=0;
        for (int i=0, l=S.length(); i<l; i++){
            char c = S.charAt(i);
            for (int j=0, k=J.length(); j<k; j++){
                if(c==J.charAt(j)){
                    num++;
                    break;
                }
            }
        }
        return num;
    }
}

1. Check mail-lists frequently.

2. Use

   zypper dup
   

   instead of

   zypper up
   

3. Use snapper to manage snapshots for recovery

This post is about the “Majority Element” problem and my attempts to it. In this problem, you are given an array of size n with some int numbers and you need to find the “majority element” which appears more than n/2 times.

My first attempt is intuitive: use two loops to traverse the whole array and an if statement and a counter variable to find the majority element. This approach did solve the problem, but wasn’t fast enough to pass the speed test. Here’s the code:

class Solution {
    public int majorityElement(int[] nums) {
        int counter = 1;
        int answer = 0;
        if (nums.length==1){
            answer = nums[0];
        } else{
            for (int i = 0; i < nums.length-1; i++){
                for (int j = i+1; j < nums.length; j++){
                    if (nums[i]==nums[j]){
                        counter++;
                        if (counter > nums.length/2){
                            answer = nums[j];
                            break;
                        }
                    }
                }
                counter = 1;
            }            
        }

        return answer;
    }
}

I didn’t figure out a better solution so I turned to the solution tab. And I saw some good approaches:

I. Sorting
The main idea of this approach is that if an element appears more than n/2 times, if we sort it in an monotonically increasing (or decreasing) order, the element in the middle (the index is (n/2) or (n/2 + 1), depends on the length of the array is odd or even) must be this majority element. So the solution will be very simple:

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

II. HashMap
This approach uses HashMap with element and appears times to find the majority element. The code snippet below is from leetcode:

class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            }
            else {
                counts.put(num, counts.get(num)+1);
            }
        }
        return counts;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();
    }
}

I’m doing some algorithm practices recently in Leetcode. This post is about the “Single Number” problem and my attempts to it.

In this problem, you are given an array with some int numbers in pair except one single number and you need to find the single number. The tricky part I think is that you can’t delete an element from an array directly in java so you need to fine another approach to make the single element more “outstanding”.

My first attempt is quite straightforward (and stupid): use a for loop to find the maximum number in the given array and plus it by 1 to generate an invalid number, then use another 2 loops to find elements in pair and turn them into this invalid number. At last, use another loop to find the element which doesn’t equal to the invalid number to get the result. This approach did solve the problem, but the speed is pathetically slow and unsurprisingly, it failed the speed test.

My second attempt got rid of the loop for generating invalid number and the loop for finding the element which is not “invalid”. Instead, I use a variable named “counter”, the counter will become 1 when an element has a duplicate when its “duplicate checking” loop ends, and the counter will be reset to 0 before next checking loop. If an element doesn’t have a duplicate, the counter will still be 0 and the answer will be nums[i], then the program will jump out of the loop directly. Here’s this version’s solution:

class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        int counter = 0;

        for (int i = 0; i < nums.length; i++){
            for (int j = 0; j < nums.length; j++){
                if (nums[i]==nums[j] && i!=j){
                    counter++;
                }
            }
            if (counter == 1){
                counter = 0;
            } else {
                answer = nums[i];
                break;
            }
        }

        return answer;
    }
}

This solution passed the time limited test in most cases but still failed sometimes. Obviously this solution is not fast enough because the two loops for duplicate checking. But I couldn’t figure out a better solution. So I checked the discussion posts of this problem and find a much more better solution than mine:

    int ans =0;
    int len = nums.length;
    for(int i=0; i<len; i++){
        ans ^= nums[i];
    }

    return ans;

This solution uses only one loop and the way it check unduplicated element is using bitwise XOR. The main idea is that 0^N==N and N^N==0. Also, XOR is commutative which means N1^N3^N2^N1^N2 == N1^N1^N2^N2^N3. As a result, the variable ans will always be the single element and the complexity is only O(n)! Brilliant!