题目

原题在此
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
Example 1:
Input: l1 = [1,2,4], l2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: l1 = [], l2 = []
Output: []

Example 3:
Input: l1 = [], l2 = [0]
Output: [0]

Constraints:

• The number of nodes in both lists is in the range [0, 50].
• -100 <= Node.val <= 100
• Both l1 and l2 are sorted in non-decreasing order.

分析

当l1, l2均未遍历完时,依次链接值较小的node.之后将剩余的list全部接上.
非常简单的一道题,适合拿来练手一门不熟悉的语言.

代码

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode head(INT_MIN);
        ListNode* foo = &head;
        while(l1 && l2) {
            if(l1 -> val < l2 -> val) {
                foo -> next = l1;
                foo = foo -> next;
                l1 = l1 -> next;
            } else {
                foo -> next = l2;
                foo = foo -> next;
                l2 = l2 -> next;
            }
        }
        
        if(l1) {
            foo -> next = l1;
        } else {
            foo -> next = l2;
        }
        return head.next;
        
    }
};

题目

原题在此

解析

点踩比点赞多的一道题,配不上中等难度.你可以用任意方式遍历二叉树直到找到target为止.

代码

1
2
3
4
5
6
7
8
9

class Solution {
public:
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        if(original == target || original == NULL) return cloned;
        TreeNode *t = getTargetCopy(original -> left, cloned -> left, target);
        if(t == NULL) t = getTargetCopy(original -> right, cloned -> right, target);
        return t;        
    }
};

题目

原题在此
You are given an array of distinct integers arr and an array of integer arrays pieces, where the integers in pieces are distinct. Your goal is to form arr by concatenating the arrays in pieces in any order. However, you are not allowed to reorder the integers in each array pieces[i].
Return true if it is possible to form the array arr from pieces. Otherwise, return false.

Example 1:

Input: arr = [85], pieces = [[85]]
Output: true

Example 2:

Input: arr = [15,88], pieces = [[88],[15]]
Output: true
Explanation: Concatenate [15] then [88]

Example 3:

Input: arr = [49,18,16], pieces = [[16,18,49]]
Output: false
Explanation: Even though the numbers match, we cannot reorder pieces[0].

Example 4:

Input: arr = [91,4,64,78], pieces = [[78],[4,64],[91]]
Output: true
Explanation: Concatenate [91] then [4,64] then [78]

Example 5:

Input: arr = [1,3,5,7], pieces = [[2,4,6,8]]
Output: false

Constraints:

• 1 <= pieces.length <= arr.length <= 100
• sum(pieces[i].length) == arr.length
• 1 <= pieces[i].length <= arr.length
• 1 <= arr[i], pieces[i][j] <= 100
• The integers in arr are distinct.
• The integers in pieces are distinct (i.e., If we flatten pieces in a 1D array, all the integers in this array are distinct).

分析

版本一

这一版的思路很单纯,把pieces中的每个piece以piece[0]为key存入map中以便随机访问,再无脑按照arr中出现的顺序拼起来.最后看看拼起来的和arr是否相等.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        unordered_map<int, vector<int>> mp;
        vector<int> attached;
        for(vector<int> p : pieces) mp[p[0]] = p;
        for(int i : arr)
            if (mp.find(i) != mp.end())
                attached.insert(attached.end(), mp[i].begin(), mp[i].end());
        return attached == arr;
    }
};

改进思路

1. Map中没必要存整个piece数组,存piece[0]就可以.
2. 根据题目Constraints部分的描述,外加数组元素是distinct的,可以用数组替代Map.
3. 在遍历arr的过程中,每次必须找到一个piece以arr[i]开头,且整段piece和arr的局部必须完全一致,否则即可返回false.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool canFormArray(vector<int>& arr, vector<vector<int>>& pieces) {
        // mp<"first number of a piece", "index of this piece in pieces">
        vector<int> mp(101, -1);
        for(int i = 0; i < pieces.size(); ++i) mp[pieces[i][0]] = i;
        for(int i = 0; i < arr.size();) {
            int pindex = mp[arr[i]];
            if(pindex == -1) return false; // no piece start with this number;
            int j = 0;
            while(j < pieces[pindex].size())
                if(arr[i++] != pieces[pindex][j++]) return false;
        }
        return true;
    }
};

题目

题目链接
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].

The largest rectangle is shown in the shaded area, which has area = 10 unit.
Example:

Input: [2,1,5,6,2,3]
Output: 10

分析

暴力搜索

依次取区间arr(i..j),用min(arr(i..j)) * j - i可以遍历所有可能的长方形,从中选取最大的即可.此时时间复杂度为$O(N^2)$.
观察暴力解法发现:

1. 最大面积的长方形长度必然和数组中的某个元素的值相等.即在数组中只有arr.length个候选最大长方形.此时我们要设法确定每个元素高度的长方形的宽度.
2. 暴力搜索的过程没有做任何记录,每次搜索对下一次没有任何帮助,可以设法记录有效信息简化搜索过程.即空间换时间.
3. 输入数组元素均为非负整数,在数组两侧各添加一个0不改变最终结果(哨兵,Sentinel).如此可省略处理edge case的部分,简化代码.

算法改进

在当前元素严格小于上一个元素时,便决定了此前某些元素的宽度无法再拓展了.此时以当前下标为右界,上一个元素的下标为左界,便可确定以此元素为高的矩形的宽度.
我们可以用栈存下标.就拿例题来说,左侧哨兵下标i=-1,循环前先入栈.

1. i = 0,a[i] = 2 还有继续向右拓宽的可能,下标入栈.
2. i = 1,a[i] = 1 此时:
   1. 栈尾元素a[s.back()],即下标为0的元素2大于当前元素.高度为2的长方形无法再拓宽,退栈处理.宽度为当前下标1减去退栈后的栈尾元素下标此时为哨兵-1再减去1,即width = i - s.back() - 1; area = width * height;.
   2. 再次检查栈尾,发现哨兵高度为0还有拓宽可能,不做处理(这样可能更好理解一些,实际情况是栈内只剩下哨兵,不做处理.再第四步还有一次演示).
   3. 当前下标元素也有拓宽可能,下标入栈.
3. i = 2,a[i] = 5;i = 3,a[i] = 6 还有继续向右拓宽的可能,入栈.
4. i = 4,a[i] = 2 与第二步做相似处理,先后确定了以6和以5为高度的长方形的面积.在6,5分别退栈后访问到a[1],发现当前下标元素不小于a[1].即栈内所有元素均还有拓宽可能,故不作处理.当前下标也入栈.
5. i = 5,a[i] = 3 还有继续向右拓宽的可能,入栈. 再次强调哨兵
6. i = 6,a[i] = 0 元素访问完毕,下标来到哨兵,此时栈内除了另一个哨兵外元素全部大于哨兵.对栈内元素依次退栈计算面积,直到栈内只剩下哨兵为止.

• 绿色:宽度还有可能变长,入栈. 红色:宽度无法拓展,出栈计算面积. 虚线:以此元素为高度的长方形面积已确定. (要想象首尾各有一个0)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int res = 0;
        vector<int> stack;
        heights.push_back(0);
        stack.push_back(-1);
        for(int i = 0; i < heights.size(); ++i) {
            while(stack.size() > 1 && heights[stack.back()] >= heights[i]) {
                int h = heights[stack.back()];
                stack.pop_back();
                res = max(res, h * (i - stack.back() - 1));
            }
            stack.push_back(i);
        }
        return res;
    }
};

后续

1. 在有连续个值相同的元素时,中间会有多次错误计算,但并不影响连续元素中最后一次退栈的计算成为最大值.
2. JAVA-为什么用Deque去实现Stack?

题目

原题在此
According to Wikipedia’s article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.”

The board is made up of an m x n grid of cells, where each cell has an initial state: live (represented by a 1) or dead (represented by a 0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):

Any live cell with fewer than two live neighbors dies as if caused by under-population.
Any live cell with two or three live neighbors lives on to the next generation.
Any live cell with more than three live neighbors dies, as if by over-population.
Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.
The next state is created by applying the above rules simultaneously to every cell in the current state, where births and deaths occur simultaneously. Given the current state of the m x n grid board, return the next state.

Example 1:

Input: board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
Output: [[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

Example 2:

Input: board = [[1,1],[1,0]]
Output: [[1,1],[1,1]]

Constraints:

• m == board.length
• n == board[i].length
• 1 <= m, n <= 25
• board[i][j] is 0 or 1.

Follow up:

• Could you solve it in-place? Remember that the board needs to be updated simultaneously: You cannot update some cells first and then use their updated values to update other cells.
• In this question, we represent the board using a 2D array. In principle, the board is infinite, which would cause problems when the active area encroaches upon the border of the array (i.e., live cells reach the border). How would you address these problems?

  分析

1. 题目用vector<vector<int>>做储存,而实际上每个格子只有死或生两种状态,只占用1bit. 所以可以将下一次演化的状态暂存在高位bit,待全部计算完毕后再位移回末位bit.

   代码

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   class Solution { public: void gameOfLife(vector<vector<int>>& board) { int row = board.size(), col = board[0].size(); for(int r = 0; r < row; ++r) { for(int c = 0; c < col; ++c) { int count = 0; for (int i=max(r-1, 0); i<min(r+2, row); ++i) for (int j=max(c-1, 0); j<min(c+2, col); ++j) count += board[i][j] & 1; if (count == 3 || count - board[r][c] == 3) board[r][c] |= 2; } } for (int i = 0; i < row; ++i) for (int j = 0; j < col; ++j) board[i][j] >>= 1; } };

题目

原题在此
Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.
Return the number of pseudo-palindromic paths going from the root node to leaf nodes.
Example 1:

Input: root = [2,3,1,3,1,null,1]
Output: 2
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 2:

Input: root = [2,1,1,1,3,null,null,null,null,null,1]
Output: 1
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the green path [2,1,1], the path [2,1,3,1], and the path [2,1]. Among these paths only the green path is pseudo-palindromic since [2,1,1] can be rearranged in [1,2,1] (palindrome).
Example 3:

Input: root = [9]
Output: 1

Constraints:
The given binary tree will have between 1 and 10^5 nodes.
Node values are digits from 1 to 9.

分析

1. 要判断从root到leaf的所有数字是否能组合成一个回文串,只需要判断每个数字出现的是奇数次还是偶数次.其中,如果有超过1个的奇数次则不可能组成回文串.
2. 一开始会想用map<int, int>来储存每个数字出现了奇数次还是偶数次.仔细思考发现,key的情况只有0-9的10种情况,而value我们只关心奇偶性.所以可以用一个integer来代替map,对第n位做异或操作来改变奇偶性.
3. 这时,计算integer中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

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int res = 0;    
    int pseudoPalindromicPaths (TreeNode* root) {
        dfs(root, 0);
        return res;
    }

private:
    void dfs(TreeNode* root, int odd) {
        if(!root) return;
        odd ^= (1 << root->val);
        if(!root -> left && !root -> right) {
            if(hammingWeight(odd) < 2) res++;
            return;
        }
        dfs(root->left, odd);
        dfs(root->right, odd);
    }

    int hammingWeight(uint32_t i) {
        i = (i  & 0x55555555) + ((i >> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
        i = (i + (i >> 4)) & 0x0f0f0f0f;
        i = (i + (i >> 8)) & 0x00ff00ff;
        i = i + (i >>16) & 0x0000ffff;
        return (int)i;
    }
};

题目

题目链接
You are standing at position 0 on an infinite number line. There is a goal at position target.
On each move, you can either go left or right. During the n-th move (starting from 1), you take n steps.
Return the minimum number of steps required to reach the destination.

Example 1:

Input: target = 3
Output: 2
Explanation:
On the first move we step from 0 to 1.
On the second step we step from 1 to 3.

Example 2:

Input: target = 2
Output: 3
Explanation:
On the first move we step from 0 to 1.
On the second move we step from 1 to -1.
On the third move we step from -1 to 2.
Note:
target will be a non-zero integer in the range [-10^9, 10^9].

分析

1. target的正负不影响计算结果,因为数轴是对称的target = abs(target).
2. 找到整数n,使得$(\sum_{i=1}^n i) \geq target$.
   1. $有求和公式: target = \frac{n*(n+1)}{2}$.
   2. $整形得到一元二次方程: n^2+n-2*target=0$.
   3. $公式求解: n = \frac{(-1 + \sqrt{(1 + 8*target)})}{2}$.
   4. n可能不为整,向上取整即可.
3. 取$sum = \frac{n*(n+1)}{2}$, sum 与 target 的差 diff = sum - target
4. 此时,如果 sum == target,直接返回n即可. 又或者差值diff是偶数,那么只要把$\frac{\text{diff}}{2}$取反即可得到target,所以也是n.
5. 若差值diff为奇数,则有如下两种情况:
   1. n为奇数,则n+1为偶数,需要$\sum_{i=1}^{n+2} i$ 来改变diff的奇偶.
   2. n为偶数,则n+1为奇数,$\sum_{i=1}^{n+1} i$ 来改变diff的奇偶.

代码

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int reachNumber(int target) {
        long long t = abs(target);
        long long n = ceil((-1 + sqrt(1 + 8*t)) / 2);
        long long sum = (n * (n + 1)) / 2;
        long long diff = sum - t;
        if (sum == target || !(diff % 2)) return n;
        return n + ((n % 2) ? 2 : 1);
    }
};

基本概念

• 音: 音是一种机械波,由声源产生震动,经介质传播.单位时间内震动重复发生的次数称为频率,采用国际单位制hz (1hz=1/s)
• 音色: 某周期函数(基波)频率的整数倍的波称为谐波.不同声源所产生的基波与谐波的叠加在频率和振幅上都不尽相同,这便是音色.
• 音量:
  • 分贝(dB): 分贝的定义为,测量值与参考量值之比计算基于10的对数乘以10. $L_{dB}=10\log_{10}{(\frac{P}{P_0})}$. dB是一个无量纲,或者说它只是一种处理数据的方式.
  • 声压级(Sound Pressure Level):
• 音程: 两个音之间的频率差
• 音数: 在十二平均律中, 称任两个相邻的音之间的音数为0.5

十二平均律

频率是连续的,音的个数是不可数的.十二平均律是一种产生离散的音的算法.
以某频率为$F$的单音$f_0$为基准,利用公式 $f_n=f*2^{(\frac{n}{12})}$ ,可以构造出一个等比数列.其中,$f_0$与频率为$2F$的单音$f_{12}$构成一个称为纯八度的音程.
在一个纯八度(既频率$[F,2F]$的区间)中,可构造出13个音,十二平均律系统规定任两个相邻的音之间的音数为0.5

ISO 16中规定音名为$A_4$的音其频率为440hz.音名是啥不重要,你只要知道等比数列里有一项是440就好.

矩阵消元

概述

这节主要讲如何通过消元来系统的求解方程组.并通过消元引入了些许逆矩阵的基础知识.

消元法解方程

和初中学过的东西一样,你可以把任意一行乘以某个数加到另一行,调换一整行等式的顺序并不改变你的方程.在矩阵中你仍然可以这样做.$A\vec{x}=\vec{b}$如下:

将A与b写在一个矩阵里,称作增广矩阵(Augment Matrix)

用第二行减去三倍的第一行可得

用第三行减去两倍的第二行可得

从最后一行$5x_3=-10$回代,便可求出$x_2,x_1$的值