ARTS Week 11

Algorithm

This week’s LeetCode problem is 15. 3Sum

Description: Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Solution Idea: Sort the array from small to large first, the first two numbers first and second can start from the left, and the third number k can be traversed from back to front, when third == second or nums[first] + nums When [second] + nums[third] <0, it means that the next second needs to be traversed, and the third starts from the tail again. At the same time, because the problem solution cannot contain repeated triples, when traversing first and second, you can check whether it is the same as the previous number (because it has been sorted). If they are the same, use continue to skip loop.

Accepted Code

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        int length = nums.length;
        for (int first = 0; first < length - 1; first++) {
            if (first > 0 && nums[first] == nums[first-1]) {
                continue;
            }
            for (int second = first + 1; second < length; second++) {
                if (second > first + 1 && nums[second] == nums[second-1]) {
                    continue;
                }
                int third = length - 1;
                while (second < third && nums[first] + nums[second] + nums[third] > 0) {
                    third--;
                }
                if (second == third) {
                    break;
                }
                if (nums[first] + nums[second] + nums[third] == 0) {
                    List<Integer> tmp = new ArrayList<>();
                    tmp.add(nums[first]);
                    tmp.add(nums[second]);
                    tmp.add(nums[third]);
                    ans.add(tmp);
                }
            }
        }
        return ans;
    }
}

Review

This week’s Review is for the following article: In C, how do you know if the dynamic allocation succeeded?

In C, we often use the malloc() function to allocate space on the heap, but in reality, the malloc() function allocates virtual memory and only allocates physical memory via a page-out interrupt when a real read or write to memory occurs, as in the following test program.

#include <stdio.h>
#include <stdlib.h>
int main() {
  size_t large = 1099511627776;
  char *buffer = (char *)malloc(large);
  if (buffer == NULL) {
    printf("error!\n");
    return EXIT_FAILURE;
  }
  printf("Memory allocated\n");
  for (size_t i = 0; i < large; i += 4096) {
    buffer[i] = 0;
  }
  free(buffer);
  return EXIT_SUCCESS;
}

Run the program, and perhaps you will see Memory allocated printed out, which means that memory was successfully allocated. But it is also possible that you will see error! and the memory was not allocated successfully, because when a program tries to allocate virtual memory much larger than the physical memory (a situation called overcommit), the success of the allocation depends on the operating system.

In Linux, there are three ways to handle overcommit, heuristic (default), always, and never. For more info about it, you can visit https://www.kernel.org/doc/Documentation/vm/overcommit-accounting

Tip

The difference between ArrayList and Vector in Java is mainly the following two points.

1. Vector is thread safe, ArrayList is not thread safe.
2. ArrayList expands the underlying array by 0.5 times when it is not enough, Vector expands it by 1 time.

Share

I had an interview this week and found out that there are still issues related to multithreading, but I lack experience in this area, so I need to learn multithreading systematically in the future.