5 分钟 读完 (大约 680 个字)

回溯算法

037-数字在排序数组中出现的次数（二分查找）#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
   public int GetNumberOfK(int [] array , int k) {
       int leftIndex = -1,start=0,end=array.length-1,rightIndex=-1;
       while(start <= end)
       {
           int mid = (start+end)/2;
           if(array[mid] > k)
           {
               end = mid-1;
           }else if(array[mid] < k){
               start = mid+1;
           }else{
               leftIndex = mid;
               end = mid-1;
           }
       }
       start = 0;
       end = array.length-1;
       while(start <= end)
       {
           int mid = (start+end)/2;
           if(array[mid] > k)
           {
               end = mid-1;
           }else if(array[mid] < k){
               start = mid+1;
           }else{
               rightIndex = mid;
               start = mid+1;
           }
       }
       if(array.length == 0 || rightIndex == -1)
           return 0;
       return rightIndex-leftIndex+1;
   }
}

电话号码的字母组合#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    
    Map<String, String> phone = new HashMap<String, String>() {{
        put("2", "abc");
        put("3", "def");
        put("4", "ghi");
        put("5", "jkl");
        put("6", "mno");
        put("7", "pqrs");
        put("8", "tuv");
        put("9", "wxyz");
    }};

    public List<String> letterCombinations(String digits) {
        List<String> result = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return result;
        }
        helper(digits, "", result);
        return result;
    }

    public void helper(String digits, String combination, List<String> result) {
        if ("".equals(digits)) {
            result.add(combination);
            return;
        }

        String digit = digits.substring(0, 1);
        String letters = phone.get(digit);

        for (int i = 0; i < letters.length(); i++) {
            String letter = letters.substring(i, i + 1);
            helper(digits.substring(1), combination + letter, result);
        }
    }
}

22. 有效括号#

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<String> generateParenthesis(int n) {
    List<String> ans = new ArrayList();
    if (n <= 0) {
        return ans;
    }
    backtrack(ans, "" , 0, 0, n);
    return ans;
}

public void backtrack(List<String> result, String cur, int open, int close, int max) {
    if (cur.length() == max * 2) {
        result.add(cur);
        return;
    }

    if (open < max) {
        backtrack(result, cur + "(", open + 1, close, max);
    }

    if (close < open) {
        backtrack(result, cur + ")", open, close + 1, max);
    }
}

39. 组合总和#

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public List<List<Integer>> combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList();
    List<Integer> cur = new ArrayList();
    helper(result, cur, 0, target, candidates, 0);
    return result;
}

private void helper(List<List<Integer>> result, List<Integer> cur, int sum, int target, int[] candidates, int index) {
    if (sum > target) {
        return;
    }

    if (sum == target) {
        result.add(new ArrayList(cur));
        return;
    }

    for (int i = 0;i < candidates.length; i++) {
        if (i < index) {
            continue;
        }
        cur.add(candidates[i]);
        helper(result, cur, sum + candidates[i], target, candidates, i);
        cur.remove(cur.size() - 1);
    }
}

46. 全排列#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public List<List<Integer>> permute(int[] nums) {
    List<List<Integer>> result = new ArrayList();
    helper(result, new ArrayList(), nums, new int[nums.length]);
    return result;
}

private void helper(List<List<Integer>> result, List<Integer> cur, int[] nums, int[] index) {
    if (cur.size() == nums.length) {
        result.add(new ArrayList(cur));
        return;
    }

    for (int i=0; i < nums.length; i++) {
        if (index[i] == 1) {
            continue;
        }
        index[i] = 1;
        cur.add(nums[i]);
        helper(result, cur, nums, index);
        index[i] = 0;
        cur.remove(cur.size() - 1);
    }
}

139. 单词拆分#

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean wordBreak(String s, List<String> wordDict) {
    return helper(s, new HashSet(wordDict), 0, new Boolean[s.length()]);
}

private boolean helper(String s, Set<String> wordDict, int start, Boolean[] menu) {
    if (start == s.length()) {
        return true;
    }

    if (menu[start] != null) {
        return menu[start];
    }

    for(int end = start + 1; end <= s.length(); end++) {
        String sub = s.substring(start, end);
        if (wordDict.contains(sub) && helper(s, wordDict, end, menu)) {
            return menu[start] = true;
        }
    }
    return menu[start] = false;
}
12 分钟 读完 (大约 1729 个字)

常见基础算法

- 单例模式#

DCL#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Singleton {  
    private volatile static Singleton singleton;  
    private Singleton (){}  
    public static Singleton getSingleton() {  
    if (singleton == null) {  
        synchronized (Singleton.class) {  
        if (singleton == null) {  
            singleton = new Singleton();  
        }  
        }  
    }  
    return singleton;  
    }  
}

volatile 防止指令重排序

- 排序算法，归并、快速#

归并#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class Sort {

    public static void MergeSort(int[] arr, int low, int high)
    {
        //使用递归的方式进行归并排序，所需要的空间复杂度是O（N+logN）
        int mid = (low + high)/2;
        if(low < high)
        {
            //递归地对左右两边进行排序
            MergeSort(arr, low, mid);
            MergeSort(arr, mid+1, high);
            //合并
            merge(arr, low, mid, high);
        }
    }
    
    //merge函数实际上是将两个有序数组合并成一个有序数组
    //因为数组有序，合并很简单，只要维护几个指针就可以了
    private static void merge(int[] arr, int low, int mid, int high)
    {
        //temp数组用于暂存合并的结果
        int[] temp = new int[high - low + 1];
        //左半边的指针
        int i = low;
        //右半边的指针
        int j = mid+1;
        //合并后数组的指针
        int k = 0;
        
        //将记录由小到大地放进temp数组
        for(; i <= mid && j <= high; k++)
        {
            if(arr[i] < arr[j])
                temp[k] = arr[i++];
            else
                temp[k] = arr[j++];
        }
        
        //接下来两个while循环是为了将剩余的（比另一边多出来的个数）放到temp数组中
        while(i <= mid)
            temp[k++] = arr[i++];
        
        while(j <= high)
            temp[k++] = arr[j++];
        
        //将temp数组中的元素写入到待排数组中
        for(int l = 0; l < temp.length; l++)
            arr[low + l] = temp[l];
    }
    
}

快排#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class QuickSort implements IArraySort {

    @Override
    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝，不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        return quickSort(arr, 0, arr.length - 1);
    }

    private int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }

    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

037-数字在排序数组中出现的次数（二分查找）#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public class Solution {
   public int GetNumberOfK(int [] array , int k) {
       int leftIndex = -1,start=0,end=array.length-1,rightIndex=-1;
       while(start <= end)
       {
           int mid = (start+end)/2;
           if(array[mid] > k)
           {
               end = mid-1;
           }else if(array[mid] < k){
               start = mid+1;
           }else{
               leftIndex = mid;
               end = mid-1;
           }
       }
       start = 0;
       end = array.length-1;
       while(start <= end)
       {
           int mid = (start+end)/2;
           if(array[mid] > k)
           {
               end = mid-1;
           }else if(array[mid] < k){
               start = mid+1;
           }else{
               rightIndex = mid;
               start = mid+1;
           }
       }
       if(array.length == 0 || rightIndex == -1)
           return 0;
       return rightIndex-leftIndex+1;
   }
}

029-最小的K个数(快速排序) *#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.ArrayList;
public class Solution {

    public ArrayList<Integer> GetLeastNumbers_Solution1(int [] arr, int k) {
        ArrayList<Integer> kNumbers = new ArrayList<Integer>();
        if (arr == null || k <= 0 || k > arr.length) return kNumbers;
        int left = 0;
        int right = arr.length - 1;
        int index = partition(arr, left, right);

        while(index!=k-1){
            
            if(index<k-1){
                start=index+1;
                index=partition(arr, left, right);
            }else{
                end=index-1;
                index=partition(arr, left, right);
            }
        }
        for(int i=0;i<k;i++){
            kNumbers.add(arr[i]);
        }
        return kNumbers;
    }
    
    private int partition(int[] arr, int left, int right) {
        // 设定基准值（pivot）
        int pivot = left;
        int index = pivot + 1;
        for (int i = index; i <= right; i++) {
            if (arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
        swap(arr, pivot, index - 1);
        return index - 1;
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

013-调整数组顺序使奇数位于偶数前面 *#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public void reOrderArray(int [] array) {
    if (array == null || array.length < 2) {
        return;
    }
    int n = array.length;
    for (int i = 1; i < n; i++) {
        // 当前元素是奇数，就移动到奇数序列
        if (array[i] % 2 != 0) {
            int value = array[i];
            int cur = i;
            while (cur > 0 && (array[cur - 1] % 2 == 0)) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = value;
        }
        // 当前元素是偶数，无须移动
    }
}

028-数组中出现次数超过一半的数字#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int MoreThanHalfNum_Solution(int [] array) {
    if (array == null || array.length <= 0) {
        return 0;
    }
    int num = array[0];
    int count = 1;
    
    for (int i=1; i<array.length; i++) {
        int temp = array[i];
        if (temp == num) {
            count++;
        } else {
            count--;
        }
        
        if (count == 0) {
            num = temp;
            count = 1;
        }
    }
    count = 0;
    for (int i=0; i<array.length; i++) {
        if (array[i] == num) {
            count++;
        }
    }
    int half = array.length / 2 + 1;
    if (count >= half) {
        return num;
    }
    return 0;
}

搜索旋转排序数组#

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
public int search(int[] nums, int target) {
    // 判空
    if (nums.length == 0) return -1;
    if (nums.length == 1) return nums[0] == target ? 0 : -1;

    // 得到旋转点
    int rotateIndex = getRotateIndex(nums);

    // 如果rotateIndex0, 和
    if (rotateIndex == 0) {
        return searchTarget(nums, 0, nums.length - 1, target);
    } else {
        if (target <= nums[nums.length - 1]) {
            return searchTarget(nums, rotateIndex, nums.length - 1, target);
        } else {
            return searchTarget(nums, 0, rotateIndex, target);
        }
    }
}

// 二分查找target所在位置
private int searchTarget(int[] nums, int left, int right, int target) {

    while (left <= right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            return mid;
        } else {
            if (nums[mid] > target) {
                right = mid -1;
            } else {
                left = mid + 1;
            }
        }
    }
    return -1;
}

// 获取旋转点
private int getRotateIndex(int[] nums) {
    int left = 0;
    int right = nums.length - 1;

    if (nums[left] < nums[right]) {
        return 0;
    }

    while (left <= right) {
        int mid = (left + right ) / 2;
        if (nums[mid] > nums[mid+1]) {
            return mid+1;
        } else {
            if (nums[mid] < nums[left]) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }
    return 0;
}

最长回文子串#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public String longestPalindrome(String s) {
    if (s == null || s.length() == 0) return s;
    char[] cs = s.toCharArray();
    int len = cs.length;
    String maxStr = "";

    for (int i = 0; i < len; i++) {
        String curStr = midSpreed(cs, i, i);
        String midStr = midSpreed(cs, i, i + 1);
        maxStr = curStr.length() > maxStr.length() ? curStr : maxStr;
        maxStr = midStr.length() > maxStr.length() ? midStr : maxStr;
    }
    return maxStr;
}

private String midSpreed(char[] cs, int index, int indexNext) {
    while (index >=0 && indexNext < cs.length && cs[index] == cs[indexNext]) {
        index--;
        indexNext++;
    }

    StringBuilder sb = new StringBuilder();
    for (int i = index + 1; i < indexNext; i++) {
        sb.append(cs[i]);
    }
    return sb.toString();
}

31. 下一个排列#

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public void nextPermutation(int[] nums) {
    if (nums.length <= 0) return;
    int len = nums.length;
    for (int i = len - 1; i >= 0; i--) {
        if (i == 0) {
            Arrays.sort(nums);
        } else {
            if (nums[i] > nums[i-1]) {
                // 说明有逆序存在, 则下一个是将i-1 转变成i-1 后面比它大的数字
                Arrays.sort(nums, i, len);
                for (int j=i;j<len;j++) {
                    if (nums[j]>nums[i-1]) {
                        swap(nums,i-1,j);
                        return;
                    }
                }
            }
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

34. 在排序数组中查找元素的第一个和最后一个位置#

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public int[] searchRange(int[] nums, int target) {
    if (nums.length == 0) {
        return new int[]{-1, -1};
    }

    int leftIndex = -1;
    int rightIndex = -1;
    int left = 0, right = nums.length - 1, mid = 0;

    while (left <= right) {
        mid = (left + right) / 2;
        if (nums[mid] == target && (mid == 0 || nums[mid - 1] < nums[mid])) {
            leftIndex = mid;
            break;
        } else {
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }

    left = leftIndex != -1 ? leftIndex : 0;
    right = nums.length - 1;

    while (left <= right) {
        mid = (left + right) / 2;
        if (nums[mid] == target && (mid == nums.length - 1 || nums[mid + 1] > nums[mid])) {
            rightIndex = mid;
            break;
        } else {
            if (nums[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }

    int[] result = new int[]{leftIndex, rightIndex};
    return result;
}

152. 乘积最大子序列#

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int maxProduct(int[] nums) {
    int max = nums[0];
    int min = nums[0];
    int res = nums[0];
    for(int i=1; i<nums.length;i++) {
        if (nums[i] < 0) {
            int temp = max;
            max = min;
            min = temp;
        }
        max = Integer.max(max * nums[i], nums[i]);
        min = Integer.min(min * nums[i], nums[i]);
        res = Integer.max(max, res);
    }
    return res;
}

560. 和为K的子数组#

1
2
3
4
5
6
7
8
9
10
11
12
13
public int subarraySum(int[] nums, int k) {
    int count = 0;
    for (int i=0; i< nums.length;i++) {
        int sum = 0;
        for (int j=i;j < nums.length; j++) {
            sum += nums[j];
            if (sum == k) {
                count++;
            }
        }
    }
    return count;
}

347. 前 K 个高频元素#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public List<Integer> topKFrequent(int[] nums, int k) {
    // 使用字典，统计每个元素出现的次数，元素为键，元素出现的次数为值
    HashMap<Integer,Integer> map = new HashMap();
    for(int num : nums){
        if (map.containsKey(num)) {
            map.put(num, map.get(num) + 1);
            } else {
            map.put(num, 1);
            }
    }
    // 遍历map，用最小堆保存频率最大的k个元素
    PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
        @Override
        public int compare(Integer a, Integer b) {
            return map.get(a) - map.get(b);
        }
    });
    for (Integer key : map.keySet()) {
        if (pq.size() < k) {
            pq.offer(key);
        } else if (map.get(key) > map.get(pq.peek())) {
            pq.poll();
            pq.offer(key);
        }
    }
    // 取出最小堆中的元素
    List<Integer> res = new ArrayList<>();
    while (!pq.isEmpty()) {
        res.add(pq.poll());
    }
    return res;
}

43. 字符串相乘#

两个长度分别为 n 和 m 的数相乘，长度不会超过 n + m。
因此我们可以创建一个长度为 n + m 的数组 res 存储结果。
nums[i] * nums[j] 的结果 位于 res[i+j+1], 如果 res[i+j+1] > 10, 则进位到 res[i+j]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public String multiply(String n1, String n2) {
    int n = n1.length(), m = n2.length();
    int[] res = new int[n + m];
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            int a = n1.charAt(i) - '0';
            int b = n2.charAt(j) - '0';
            int r = a * b;
            r += res[i + j + 1];
            res[i + j + 1] = r % 10;
            res[i + j] += r / 10;
        }
    }
    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < n + m; i++) {
        if (sb.length() == 0 && res[i] == 0) continue;
        sb.append(res[i]);
    }
    return sb.length() == 0 ? "0" : sb.toString();
}
生活
4 分钟 读完 (大约 617 个字)

记录租房第三个住处-天通苑东三区

上上周末8月24号搬到了新的租房，搬到了天通苑北一区，换了一居，也住了十几天了，感觉很不错，但之前的租房也很好，它有一个大大的天台，还可以上房顶，把照片记录下来。

上周末回去稍微收拾了下屋子，卖了东西，图中为美丽聪慧的对象

客厅兼卧室

很大的地方还有个落地灯

厨房以前在这个地方，这个屋在之前一段时间我们都把垫子搬过来打地铺睡，因为有一天我发现这里比较隔猫

我的电脑桌放在这个地方

大大的厕所，目前住过最大厕所

小储藏室

通往天台的门，lily最爱去的地方，总是会在这个地方站好开叫，然后看你过来了就扒扒门，lily非常渴望自由，想出去玩

出来啦！

有一圈的天台，第一次见时真的很惊喜

视野十分开阔，夕阳西下，喝酒吃肉，美滋滋

在小区里捡到了很能叫又贪吃的新家庭成员，小 jojo

开始小小的很可爱，

陪我玩电脑

写博客

要抱抱

举高高

与lily从打闹慢慢有点和谐相处

学lily睡窗台

和我们一起睡觉，四生物一张床

后来因为早上太闹，用梳妆台挡住这两个捣蛋鬼，jojo此时已显猪态

幸福生活未完待续..

rss
几秒 读完 (大约 43 个字)

rss订阅

使用 feedly 订阅 rss，实现多设备同步

教程：https://techmoon.xyz/feedly/

目前导出的我的订阅源, Feedly订阅.opml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
<?xml version="1.0" encoding="UTF-8"?>
<opml version="2.0">
<head>
<title>Feedly订阅</title>
</head>
<body>
<outline title="NBA" text="NBA">
<outline text="千年孤寂 的 Youtube 视频" title="千年孤寂 的 Youtube 视频" xmlUrl="https://rsshub.app/youtube/channel/UC6QUkl7S6AYwkpQFhmdFIoQ" type="rss" htmlUrl="https://www.youtube.com/channel/UC6QUkl7S6AYwkpQFhmdFIoQ" />
<outline htmlUrl="https://space.bilibili.com/184687394/#/article" title="听说不怕肚子疼 的 bilibili 专栏" type="rss" text="听说不怕肚子疼 的 bilibili 专栏" xmlUrl="https://rsshub.app/bilibili/user/article/184687394" />
</outline>
<outline text="产品" title="产品">
<outline title="李自然说 的 bilibili 空间" xmlUrl="https://rsshub.app/bilibili/user/video/39089748" type="rss" htmlUrl="https://space.bilibili.com/39089748" text="李自然说 的 bilibili 空间" />
<outline htmlUrl="https://post.smzdm.com/hot_7" type="rss" xmlUrl="https://rsshub.app/smzdm/haowen/7" text="周热门-什么值得买好文" title="周热门-什么值得买好文" />
<outline xmlUrl="http://fz0512.com/feed" text="最好金龟换酒" title="最好金龟换酒" htmlUrl="http://fz0512.com" type="rss" />
<outline title="少数派" text="少数派" htmlUrl="https://sspai.com" xmlUrl="http://sspai.com/feed" type="rss" />
<outline text="V2EX-最热主题" xmlUrl="https://rsshub.app/v2ex/topics/hot" title="V2EX-最热主题" type="rss" htmlUrl="https://www.v2ex.com/" />
<outline title="微信公众号 - 一本黑" text="微信公众号 - 一本黑" xmlUrl="https://rsshub.app/wechat/csm/darkinsider" type="rss" htmlUrl="https://chuansongme.com/account/darkinsider" />
</outline>
<outline text="图片" title="图片">
<outline title="国家地理每日一图" text="国家地理每日一图" type="rss" htmlUrl="https://www.nationalgeographic.com" xmlUrl="https://feedx.co/rss/nationalgeodayphoto.xml" />
</outline>
<outline title="好友" text="好友">
<outline title="大菜猫" htmlUrl="https://www.techwei.cn/" text="大菜猫" xmlUrl="https://techwei.cn/atom.xml" type="rss" />
<outline htmlUrl="https://jacobchang.cn/" text="黄小豆的博客" title="黄小豆的博客" type="rss" xmlUrl="https://jacobchang.cn/atom.xml" />
<outline xmlUrl="https://rsshub.app/bilibili/user/video/11036610" text="爱浪的黄小豆 的 bilibili 空间" type="rss" title="爱浪的黄小豆 的 bilibili 空间" htmlUrl="https://space.bilibili.com/11036610" />
<outline htmlUrl="https://www.yuanqiongqiong.cn/" title="袁琼琼的博客" xmlUrl="http://yuanqiongqiong.cn/atom.xml" text="袁琼琼的博客" type="rss" />
</outline>
<outline text="技术" title="技术">
<outline xmlUrl="https://rsshub.app/juejin/category/backend" type="rss" text="掘金后端" title="掘金后端" htmlUrl="https://juejin.im/welcome/backend" />
<outline type="rss" text="美团技术团队" htmlUrl="https://tech.meituan.com/feed/" xmlUrl="https://rsshub.app/meituan/tech/home" title="美团技术团队" />
<outline htmlUrl="http://www.ruanyifeng.com/blog/" xmlUrl="http://www.ruanyifeng.com/blog/atom.xml" title="阮一峰的网络日志" type="rss" text="阮一峰的网络日志" />
<outline htmlUrl="https://chuansongme.com/account/importnew" type="rss" xmlUrl="https://rsshub.app/wechat/csm/importnew" text="微信公众号 - ImportNew" title="微信公众号 - ImportNew" />
<outline title="微信公众号 - 一本黑" type="rss" text="微信公众号 - 一本黑" htmlUrl="https://chuansongme.com/account/darkinsider" xmlUrl="https://rsshub.app/wechat/csm/darkinsider" />
</outline>
<outline text="新闻" title="新闻">
<outline xmlUrl="https://rsshub.app/gov/zhengce/zuixin" type="rss" text="最新政策 - 中国政府网" title="最新政策 - 中国政府网" htmlUrl="http://www.gov.cn/zhengce/zuixin.htm" />
</outline>
<outline text="生活" title="生活">
<outline text="美国日记" title="美国日记" type="rss" htmlUrl="http://cn.derekyang.us" xmlUrl="http://cn.derekyang.us/?feed=rss2" />
<outline text="人生不过如此" htmlUrl="http://nana.blog.paowang.net" title="人生不过如此" xmlUrl="http://nana.blog.paowang.net/feed/" type="rss" />
</outline>
<outline title="电影" text="电影">
<outline htmlUrl="https://www.douban.com" type="rss" xmlUrl="https://feedx.co/rss/doubanmvweek.xml" text="豆瓣电影本周口碑榜" title="豆瓣电影本周口碑榜" />
<outline text="MovieTalk-电影七日谈 的 bilibili 空间" title="MovieTalk-电影七日谈 的 bilibili 空间" xmlUrl="https://rsshub.app/bilibili/user/video/10869763" htmlUrl="https://space.bilibili.com/10869763" type="rss" />
</outline>
<outline title="艺术" text="艺术">
<outline type="rss" htmlUrl="http://bing.com" text="必应今日美图" title="必应今日美图" xmlUrl="https://feedx.co/rss/bingwallpaper.xml" />
</outline>
</body>
</opml>
</opml>
读书笔记
9 分钟 读完 (大约 1404 个字)

读《自控力》

前言#

看了本周”李自然说”讨论学习方法，里面有一句话非常喜欢，人和人的差距大于人和猪的差距。

这句话夸张的表达了人和人的差距会有多大，人和人理解问题的深度、处事的态度、说话的逻辑和好听程度，有趣指数，相信大家都想做人上人，百里挑一的人，不止是为了获得更多的财富，更是让自己的生活满意，做事情处事不惊，游刃有余。 今天开始阅读《自控力》，不是说这一本书能带我走向人生巅峰，只希望是个好的开始。

01 意志力是什么，为什么至关重要#

###意志力

就是驾驭 “我不要”， “我要做”，”我想要” 这三种力量。

“我不要” : 抵制诱惑！#

抵制甜甜圈，香烟，清仓大甩卖，或一夜情等等很诱人的东西，这些东西阻碍你实现你真正想要的，比如瘦身，好的肺，幸福的家庭等，如果你一面对就会无法抵抗，那就要提升意志力，提升“我不要”的能力。

这些东西可能会带来即时的快感，但只是因为真正美好的东西暂时离你远，因为时空的距离感，让你选择了当前的选项，但如果思维清晰，目标明确，就不要为眼前的小利益而放弃大目标。

比如你想换工作、换城市，考虑清楚之后，知道换了之后的结果是好的，但过程中有困难和安逸给你选，如果选了安逸，就是当前的诱惑赢了，如果选了困难，就是意志力的体现，对当前诱惑说出 “我不要” ！

“我要做” ：今日事今日毕 ！#

“明日复明日”，拖延症晚期患者有些事情可能拖到下辈子再做，是这部分意志力薄弱，我理解不可能每天真毕，但“做” 和 “拖”的差距是很大的，是“我要做”意志力的体现。

“我想要”： 真正要的是什么！#

当我们在冲动的时候有时会觉得这就是自己想要的，想要玩游戏、想要喝酒、巧克力蛋糕、骂人等等，但一定得想清楚，你真正要的是什么样的身材，什么样的素养，什么样的生活，是否希望苗条、升职加薪、家庭美满，是否吃”巧克力蛋糕”, 吃多少，要在关键时刻遏制住一时冲动，明确自己的目标，强大的目标明确能力，是“我想要”意志力的体现。

小总结#

个人理解意志力的体现肯定不是要让我们当机器人或当狗（加班狗、奋斗狗），而是像某口号一样，集中力量办大事，只是集中的是自己的力量，办的是“我想要”的事。

两个自我#

大脑中有两个部分，一部分是控制自己，一部分是冲动的自己。冲动为原始的冲动，我们的本能; 控制自己的就是我们的前额皮质。

“两个自我发生分歧的时候，总会有一方击败另一方。决定放弃的一方并没有做错，只是双方觉得重要的东西不同而已。”

原始的本能冲动是我们必不可少的，没有欲望，人就会变得沮丧，没有恐惧，就没法保护自己，没有厌恶，就没法提高自己，我们不是要消灭冲动的自己，而是要学会利用冲动的自己，换句话就是在合适的时候冲动，合适的时候控制。

原始的冲动带着自己进步，而当冲动要带我们走向错误的时候，控制自己的能力需要体现。

自我意识#

自我意识体现在做决定的时候，意识到要做自己的选择，生活才是自己的。

这里重点是意识到自己可以做的选择。一件事，我根据自己的想法做出选择，是自我意识，而我如果没思考，下意识走了简单舒适的选择时，就是自我意识的缺失，一种随波逐流，这样选的结果不一定不好，但不会一直是自己想要的。

做一个有自我的人

冥想#

冥想通过坐着闭眼专注于”呼“ ”吸“， 锻炼自己的控制能力，注意力集中能力，意志力。

冥想我相信对应现实中的注意力集中能力，自控能力都会有一定提升。

今天进行了人生第一次冥想，虽然大部分时间都无法专注于呼吸，但我看到了挑战，当我能完全专注于呼吸的时候，那我的集中注意力的能力就会变得很强。

mark一篇完整冥想步骤文章

https://mp.weixin.qq.com/s/2nV2u66ScuLJEHEXcrHkMQ

mysql
10 分钟 读完 (大约 1531 个字)

innodb事务隔离级别、MVCC

隔离级别#

未提交读(Read Uncommitted)：允许脏读，也就是可能读取到其他会话中未提交事务修改的数据

提交读(Read Committed)：只能读取到已经提交的数据。Oracle等多数数据库默认都是该级别 (不重复读)

可重复读(Repeated Read)：可重复读。在同一个事务内的查询都是事务开始时刻一致的，InnoDB默认级别。在SQL标准中，该隔离级别消除了不可重复读，但是还存在幻象读

串行读(Serializable)：完全串行化的读，每次读都需要获得表级共享锁，读写相互都会阻塞

MVCC#

InnoDB是一个多版本的存储引擎：为了支持事务的一些特性诸如并发和回滚，它保持着被修改行的旧版本信息。这些信息被存储在一个被叫做回滚段(rollback segment)的表空间中。InnoDB在回滚段中用这些信息来执行undo操作，以此支持事务回滚。它也用这些信息来构造行的更早的版本，以此支持一致性读（快照读）。

在内部，InnoDB为数据库中存储的每一行添加三个隐藏字段。

DB_TRX_ID：表明插入或者修改这一行的最后一个事务的事务标识符。如何查看行事务ID

DB_ROLL_PTR：指向回滚段中的一个undo log记录，如果行被修改了，那么这个undo log记录包含的信息必须先于行修改被重新修改。

DB_ROW_ID：单调递增的行ID。如果InnoDB自动生成了一个聚集索引，那么这个索引包含行ID值，否则DB_ROW_ID列不会出现在任何索引中。

锁类型#

共享锁（读锁，S锁）：若事务T对数据对象A加上S锁，则事务T可以读A但不能修改A，其他事务只能再对A加S锁，而不能加X锁，直到T释放S锁。

排他锁（写锁，X锁）：若事务T对数据对象A加上X锁，则只允许T读取和修改A，其他事务不能再对A加作何类型的锁，直到T释放A上的X锁。

意向共享锁（IS锁）：事务T在对表中数据对象加S锁前，首先需要对该表加IS（或更强的IX）锁。

意向排他锁（IX锁）：事务T在对表中的数据对象加X锁前，首先需要对该表加IX锁。

意向锁补充#
  • InnoDB 支持多粒度锁，特定场景下，行级锁可以与表级锁共存。
  • 意向锁之间互不排斥，但除了 IS 与 S 兼容外，意向锁会与 共享锁 / 排他锁 互斥。
  • IX，IS是表级锁，不会和行级的X，S锁发生冲突。只会和表级的X，S发生冲突。
  • 意向锁在保证并发性的前提下，实现了行锁和表锁共存且满足事务隔离性的要求。

2pl 两阶段锁#

两段锁协议，先随便加，最后commit才能一起释放.

GAP锁有何用#

其实这个多出来的GAP锁，就是RR隔离级别，相对于RC隔离级别，不会出现幻读的关键。

确实，GAP锁锁住的位置，也不是记录本身，而是两条记录之间的GAP。

所谓幻读，就是同一个事务，连续做两次当前读 (例如：select * from t1 where id = 10 for update;)，那么这两次当前读返回的是完全相同的记录 (记录数量一致，记录本身也一致)，第二次的当前读，不会比第一次返回更多的记录 (幻象)。

如何保证两次当前读返回一致的记录，那就需要在第一次当前读与第二次当前读之间，其他的事务不会插入新的满足条件的记录并提交。为了实现这个功能，GAP锁应运而生

快照读 & 当前读#

快照读：就是select

1
select * from table ….;

当前读：特殊的读操作，插入/更新/删除操作，属于当前读，处理的都是当前的数据，需要加锁。 

1
2
3
4
5
select * from table where ? lock in share mode;
select * from table where ? for update;
insert;
update ;
delete;

聊天讨论#

全快照、全当前，不幻读， 先快照，再当前，幻读

「 球球: 其实产生幻读的原因，就是以为读走了mvcc的副本， 」

读如果也加gap锁，就真的不会幻读了，但代价太大

「 宏伟: 张三账户余额有10000元；要转账给李四9000元，转给王五5000元；这两次转账肯定有一次因余额不足转账失败；如果在 rr 下，可重复读， 两次update 张三都会成功？ 」

这个如果两个事务并发，都先读的1w元快照读，然后第1个事务直接update张三减钱， commit， 第2个事务 接着update张三减钱，都会成功，除非
1 用数据库乐观锁
2 自己搞个分布式锁，将读写操作原子化
3 用kafka让同一用户操作串行化

敏: 交易相关的就不要快照读了, 交易要算钱，select的时候就要锁，不然这条数据之后未必可用

总结#

RR级别下，通过MVCC, 解决了两个快照读的幻读问题，
通过next-key锁，解决了两个当前读的幻读问题，但是快照读后的当前读是会幻读的.

redis
几秒 读完 (大约 71 个字)

tair & redis 的选择

tair & redis 的选择#

  1. 延迟敏感程度, 延迟敏感，说什么也得redis
  2. 数据量大的话，数据量超过100GB全内存太浪费资源，延迟没有那么敏感，使用tair
  3. 使用复杂数据结构 redis
  4. 容忍数据丢失
redis
8 分钟 读完 (大约 1160 个字)

redis单线程还这么快

为什么Redis使用单线程模型会达到每秒万级别的处理能力呢？可以将其归结为三点使Redis具有很高的吞吐量?#

1. 纯内存访问#

Redis将所有数据放在内存中，内存的响应时长大约为100纳秒，这是Redis达到每秒万级别访问的重要基础。

纯内存数据库，如果只是简单的 key-value，内存不是瓶颈。一般情况下，hash 查找可以达到每秒数百万次的数量级。瓶颈在于网络 IO 上。每次请求需要通过网络把请求发送到 redis 所在的机器，然后等待 redis 返回数据。时间大部分消耗在网络传输中。如果把 redis 和客户端放在同一台机器，网络延迟会更小，一般情况下可以打到 60000 次每秒甚至更高，取决于机器性能。

2. I/O多路复用、事件驱动模型#

旨在解决IO的问题。多路I/O复用模型是非阻塞IO，内部实现采用epoll和自己实现的事件分离框架。

其利用select、poll、epoll 可以同时检测多个流的 I/O 事件的能力，在空闲的时候，会把当前线程阻塞掉，当有一个或多个流有 I/O 事件时，就从阻塞态中唤醒，于是程序就会轮询一遍所有的流（epoll 是只轮询那些真正发出了事件的流），并且只依次顺序的处理就绪的流，这种做法就避免了大量的无用操作。

“多路”指的是多个网络连接，“复用”指的是复用同一个线程。采用多路 I/O 复用技术可以让单个线程高效的处理多个连接请求（尽量减少网络 IO 的时间消耗）。

总结就是Redis使用epoll作为I/O多路复用技术的实现，再加上Redis自身的事件处理模型将epoll中的连接、读写、关闭都转换为事件，不在网络I/O上浪费过多的时间，如下图所示。

3. 单线程避免了线程切换和竞态产生的消耗。#

线程模型#

主线程#

其它#

  1. Redis会fork得到的子进程，用来处理RDB持久化以及AOF持久化等任务

  2. 一组异步任务处理线程，即Redis异步化组件——BIO组件

BIO组件目前包括三个线程，分别处理三种类型的任务：
1）文件句柄关闭任务
2）AOF持久化任务
3）空间懒释放

持久化#

Redis 提供了两种持久化策略

RDB 持久化机制，会在一段时间内生成指定时间点的数据集快照(snapshot)

AOF 持久化机制，记录 server 端收到的每一条写命令，当 server 重启时会进行重放以此来重建之前的数据集。AOF 文件中的命令全部以 Redis 协议的格式来保存，新命令会被追加(append)到文件的末尾。 Redis 还可以在后台对 AOF 文件进行重写(rewrite) ，使得 AOF 文件的体积不会超出保存数据集状态所需的实际大小。

如果你仅使用 Redis 作为缓存加速访问，你可以关闭这两个持久化设置

你也可以同时开启这两个持久化设置，但是在这种情况下，Redis 重启时会使用 AOF 文件来重建数据集，因为 AOF 文件保存的数据往往更加完整

单线程利弊#

单线程模型能带来几个好处：
第一，单线程可以简化数据结构和算法的实现。并发数据结构实现不但困难而且开发测试比较麻烦。
第二，单线程避免了线程切换和竞态产生的消耗，对于服务端开发来说，锁和线程切换通常是性能杀手。

但是单线程会有一个问题：
对于每个命令的执行时间是有要求的。如果某个命令执行过长，会造成其他命令的阻塞，对于Redis这种高性能的服务来说是致命的，所以Redis是面向快速执行场景的数据库。

设计模式
几秒 读完 (大约 0 个字)

策略模式

netty
6 分钟 读完 (大约 972 个字)

netty模型

定义#

netty是一个高性能、异步事情驱动的网络通信框架
NIO IO多路复用 、事情驱动模型

1.设置主从reactor模式
2.指定IO类型
3.指定handler
4.绑定端口

netty优点#

  1. API使用简单，开发门槛低；

  2. 功能强大，预置了多种编解码功能，支持多种主流协议；

  3. 定制能力强，可以通过ChannelHandler对通信框架进行灵活地扩展；

  4. 性能高，通过与其他业界主流的NIO框架对比，Netty的综合性能最优；

  5. 成熟、稳定，Netty修复了已经发现的所有JDK NIO BUG，业务开发人员不需要再为NIO的BUG而烦恼；

  6. 社区活跃，版本迭代周期短，发现的BUG可以被及时修复，同时，更多的新功能会加入；

  7. 经历了大规模的商业应用考验，质量得到验证。在互联网、大数据、网络游戏、企业应用、电信软件等众多行业得到成功商用，证明了它已经完全能够满足不同行业的商业应用了。

高性能三要素#

  1. reactor模型
  2. IO多路复用
  3. 协议

reactor模型#

单线程模型#

多线程模型#

主从线程模型#

组件#

Bootstrap/ServerBootstrap#

顾名思义就是启动类，分别负责启动客户端和服务器端。这个类用来配置相关参数，比如设置EventLoopGroup，IO类型，handler等等，Netty的一切都从这里开始

EventLoopGroup#

主从多线程Reactor模型，分别有两个线程池： EventLoopGroupA和EventLoopGroupB。一个用于接收请求，另一个用于处理IO操作。

一个EventLoopGroup就相当于一个线程池，而每一个EventLoop就是一个线程，当新的Channel被创建时（有新的请求进来），就会在EventLoopGroup里注册一下，同时会分配一个EventLoop给这个Channel，

从此开始直到这个Channel被销毁，这个Channel只能被它绑定的这个EventLoop执行，这也就是为什么Netty可以不用考虑并发的原因。

EventLoop是处理各个event的具体线程。除了处理IO读写等event外，EventLoop还需要进行系统任务和定时任务进行执行

Channel#

Netty的Channel接口所提供的的API，大大降低了直接使用Socket类的复杂性

ChannelPipeline & ChannelHander#

Netty采用了一种叫做数据流（data flow）的处理机制，类似于Unix中的管道。即每一个Channel都有一个自己的ChannelPipeline，每一个pipeline里会有多个ChannelHandler。数据会像水流一样依次通过每一个handler被逐一处理。
流处理是双向混合的，分为Inbound和Outbound， 分别对应request和response。

这个handler被分成两类：ChannelOutboundHandler和ChannelInboundHandler。当服务器处理进来的请求时，则只会调用实现了ChannelInboundHandler的handler；当服务器返回信息给客户端时，则只会调用实现了ChannelOutboundHandler的handler

Encoders & Decoders#

我们在解析处理请求时通常需要对数据格式进行转换，比如把字节变成对象，或者把对象转换为字节。针对这种常见的场景，Netty提供了编码和解码的接口：MessageToByteEncoder和ByteToMessageEncoder。

其实两个抽象类分别继承了ChannelInboundHandlerAdapter和ChannelOutboundHandlerAdapter，说白了，使用起来和普通的handler没什么区别。自己写的类只要重写decode()或者encode()方法对数据进行处理即可

关注我

链接

分类

标签云

List concurrenthashmap design framework git hadoop hashmap innodb java jvm kafka maven mybatis mysql netty network pcursor redis rss spring springboot storm tair vim zookeeper 并发 旅游 机器学习 生活 索引 线上问题 英语 设计模式 读书笔记 锁 面经

最新文章

归档

标签

List 1
concurrenthashmap 1
design 8
framework 1
git 1
hadoop 2
hashmap 9
innodb 2
java 15
jvm 3
kafka 1
maven 1
mybatis 3
mysql 11
netty 3
network 2
pcursor 1
redis 3
rss 1
spring 1
springboot 5
storm 1
tair 1
vim 1
zookeeper 2
并发 4
旅游 3
机器学习 1
生活 2
索引 2
线上问题 1
英语 1
设计模式 1
读书笔记 1
锁 1
面经 1

最新文章

归档

标签

List 1
concurrenthashmap 1
design 8
framework 1
git 1
hadoop 2
hashmap 9
innodb 2
java 15
jvm 3
kafka 1
maven 1
mybatis 3
mysql 11
netty 3
network 2
pcursor 1
redis 3
rss 1
spring 1
springboot 5
storm 1
tair 1
vim 1
zookeeper 2
并发 4
旅游 3
机器学习 1
生活 2
索引 2
线上问题 1
英语 1
设计模式 1
读书笔记 1
锁 1
面经 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×