2024-03-25发表2025-04-15更新LeetCode / 算法13 分钟读完 (大约1982个字)

LeetCode-35

518. 零钱兑换 II

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<int> dp(amount+1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = coins[i-1]; j <= amount; j++) {
                dp[j] += dp[j-coins[i-1]];
            }
        }
        return dp[amount];
    }
};

322. 零钱兑换

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = coins[i-1]; j <= amount; j++) {
                if(dp[j - coins[i-1]] != INT_MAX)
                    dp[j] = min(dp[j], dp[j - coins[i-1]] + 1);
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

25. K 个一组翻转链表

啊？真的是困难吗

2024-03-24发表2025-04-15更新Android11 分钟读完 (大约1620个字)

01-Binder

看源码的时候可以用uml图辅助理解

多进程

为什么多进程

突破内存限制：Android系统在内存不足时，会优先杀占用内存多的进程
功能稳定性：把一些功能放到独立的进程中，保证进程功能的纯粹性和稳定性
规避系统内存泄漏：独立的WebView进程阻隔内存泄漏问题
隔离风险：不稳定功能放到子进程，保证主进程的稳定性

Android中的进程间通信

Binder
- aidl
Socket
管道：handler
共享内存
- fresco，mmkv（匿名）
信号：
- ANR监控
- matrix、xcrash、友盟apm

2024-03-17发表2025-04-15更新LeetCode / 算法6 分钟读完 (大约951个字)

LeetCode-排序

复习排序算法

稳定性容易记错的是选择排序
- 选择排序是从未排序中选择最小的，直接与未排序的第一个交换，所以不稳定
- 选择排序是从未排序中选择最小的，插入到已排序的后面，就是稳定的

先手写一遍常见排序算法

比较排序
- 交换排序
  - 冒泡
  - 快排
- 插入排序
  - 简单插入
  - 希尔排序
- 选择排序
  - 简单选择
  - 堆排序
- 归并排序
  - 二路归并
  - 多路归并
非比较排序
- 计数排序
- 桶排序
- 基数排序

#include <iostream>
#include <bits/stdc++.h>
#include <random>
using namespace std;

template <typename T>
void printVec(const vector<T>& vec, function<string(const T&)> toString);

template<typename T>
void bubbleSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    for(int i = 0; i < len; i++) {
        for(int j = 0; j < len - i - 1; j++) {
            if(compare(vec[j], vec[j+1]) > 0) {
                swap(vec[j], vec[j+1]);
            }
        }
    }
}

template<typename T>
void selectSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    for(int i = 0; i < len; i++) {
        int minIndex = i;
        for(int j = i+1; j < len; j++) {
            if(compare(vec[minIndex], vec[j]) > 0) {
                minIndex = j;
            }
        }
        swap(vec[i], vec[minIndex]);
    }
}

template<typename T>
void stableSelectSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    for(int i = 0; i < len; i++) {
        int minIndex = i;
        for(int j = i+1; j < len; j++) {
            if(compare(vec[minIndex], vec[j]) > 0) {
                minIndex = j;
            }
        }
        T t = vec[minIndex];
        for(int j = minIndex; j > i; j--) {
            vec[j] = vec[j-1];
        }
        vec[i] = t;
    }
}

template<typename T>
void insertSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    for(int i = 0; i < len-1; i++) { // 下面是i+1，这里要len-1
        for(int j = i+1; j > 0; j--) {
            if(compare(vec[j], vec[j-1]) < 0) {
                swap(vec[j], vec[j-1]);
            } else {
                break;
            }
        }
    }
}


template<typename T>
void mergeSort(vector<T>& vec, function<int(const T&, const T&)> compare, int start, int end) {
    if(end - start <= 1) return;
    int mid = (end - start) / 2 + start;
    mergeSort(vec, compare, start, mid);
    mergeSort(vec, compare, mid, end);
    // merge
    vector<T> tmp(end - start);
    int cur = 0, i = start, j = mid;
    while(i < mid && j < end) {
        if(compare(vec[i], vec[j]) <= 0) { // 稳定性
            tmp[cur++] = vec[i++];
        } else {
            tmp[cur++] = vec[j++];
        }
    }
    while(i < mid) {
        tmp[cur++] = vec[i++];
    }
    while(j < end) {
        tmp[cur++] = vec[j++];
    }
    for(i = start; i < end; i++) {
        vec[i] = tmp[i - start];
    }
}

template<typename T>
void mergeSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    mergeSort(vec, compare, 0, len);
}

template<typename T>
void quickSort(vector<T>& vec, function<int(const T&, const T&)> compare, int start, int end) {
    if(end - start <= 1) return;
    int i = start, j = end - 1;
    while(i < j) {
        while(i < j && compare(vec[i], vec[j]) <= 0) j--;
        swap(vec[j], vec[i]);
        while(i < j && compare(vec[i], vec[j]) <= 0) i++;
        swap(vec[i], vec[j]);
    }
    quickSort(vec, compare, start, i);
    quickSort(vec, compare, i+1, end); // i + 1, 已排序的枢轴就不用了
}

template<typename T>
void quickSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    quickSort(vec, compare, 0, len);
}


template<typename T>
void heapAdjust(vector<T>& vec, int i, int end, function<int(const T&, const T&)> compare) {
    for(int j = i; ; ) {
        int largest = j;
        if(j*2+1 < end && compare(vec[largest], vec[j*2+1]) < 0) {
            largest = j*2+1;
        }
        if(j*2+2 < end && compare(vec[largest], vec[j*2+2]) < 0) {
            largest = j*2+2;
        }
        if(j == largest) break;
        swap(vec[j], vec[largest]);
        j = largest;
    }
}

template<typename T>
void heapSort(vector<T>& vec, function<int(const T&, const T&)> compare) {
    int len = vec.size();
    // heapAdjust
//    for(int i = len-1; i > 0; i--) {
//        if(compare(vec[i], vec[(i+1)/2-1]) > 0) {
//            swap(vec[i], vec[(i+1)/2-1]);
//        }
//    } //wrong
    for(int i = len/2; i >= 0; i--) {
        heapAdjust(vec, i, len, compare);
    }
    // sort
    for(int i = len-1; i > 0; i--) {
        swap(vec[0], vec[i]);
        heapAdjust(vec, 0, i, compare);
    }
}

const int MAX_NUMBER = 1000;
const int MIN_NUMBER = -1000;
const int MAX_LEN = 2000000;

template <typename T>
int compare(const T& a, const T& b) {
    if(a == b) return 0;
    else if(a > b) return 1;
    else return -1;
}
template <typename T>
void printVec(const vector<T>& vec, function<string(const T&)> toString) {
    cout << "[";
    if(vec.size() > 0) cout << toString(vec[0]);
    for(size_t i = 1; i < vec.size(); i++) {
        cout << ", " << toString(vec[i]);
    }
    cout << "]\n";
}
clock_t execTime(const function<void(vector<pair<int, int>> &)>& f, vector<pair<int, int>> &vec) {
    clock_t start = clock();
    f(vec);
    clock_t end = clock();
    return end - start;
}

void speedTest(decltype(bubbleSort<pair<int, int>>) sort, vector<pair<int, int>> &a, vector<pair<int, int>> b) {
    auto cmp = [](const pair<int, int>& x, const pair<int, int>& y){ return compare(x.first, y.first); };
    clock_t our = execTime([&](vector<pair<int, int>> & vec) {sort(vec, cmp);}, a);
    clock_t libc = execTime([](vector<pair<int, int>> & vec) {std::sort(vec.begin(), vec.end());}, b);
    cout << "our: " << our << ", libc: " << libc << ", promoted: " << double(libc - our) / double(libc) * 100 << "%" << endl;
}

void test(decltype(bubbleSort<pair<int, int>>) sort, bool is_stable) {
    int len = rand() % MAX_LEN;
    vector<pair<int, int>> vec;
    map<int, int> cnt;
    for(int i = 0; i < len; i++) {
        int num = rand() % (MAX_NUMBER - MIN_NUMBER) + MIN_NUMBER;
        vec.emplace_back(num, ++cnt[num]);
    }

    speedTest(sort, vec, vec);

    bool stability = true, ok = true;
    for(int i = 0; i < len - 1; i++) {
        cnt[vec[i].first]--;
        if(compare(vec[i].first, vec[i+1].first) > 0) {
            ok = false;
        } else if(compare(vec[i].first, vec[i+1].first) == 0) {
            if(vec[i].second + 1 != vec[i+1].second) {
                stability = false;
            }
        }
    }
    if(len > 0) cnt[vec[len-1].first]--;
    for(auto & ite : cnt) {
        if(ite.second != 0) {
            ok = false;
            break;
        }
    }
//    cout << "ok: " << ok << ", stable: " << stability << endl;
    if(!ok) {
        printVec<pair<int, int>>(vec, [](const pair<int, int>& item) {
            stringstream ss;
            ss << "{" << item.first << ", " << item.second << "}";
            return ss.str();
        });
        throw runtime_error("sort failed!\n");
    }
    if(is_stable && !stability) {
        throw runtime_error("stability not match");
    }
}
int main() {
    srand(time(NULL));
    test(bubbleSort, true);
    test(selectSort, false);
    test(stableSelectSort, true);
    test(insertSort, true);
    test(mergeSort, true);
    test(quickSort, false);
    test(heapSort, false);
}

2024-03-14发表2025-04-15更新LeetCode / 算法12 分钟读完 (大约1852个字)

LeetCode-34

2789. 合并后数组中的最大元素

class Solution {
public:
    long long maxArrayValue(vector<int>& nums) {
        int n = nums.size();
        long long ans = nums[n-1];
        long long curSum = nums[n-1];
        for(int i = n - 2; i >= 0; i--) {
            if(nums[i] <= curSum) {
                curSum += nums[i];
            } else {
                curSum = nums[i];
            }
            ans = max(ans, curSum);
        }
        return ans;
    }
};

2864. 最大二进制奇数

一次遍历原地算法

class Solution {
public:
    string maximumOddBinaryNumber(string& s) {
        int len = s.length();
        int index = 0;
        for(int i = 0; i < len; i++) {
            if(s[i] == '1') {
                s[i] = '0';
                s[index++] = '1';
            }
        }
        s[index-1] = '0';
        s[len-1] = '1';
        return s;
    }
};

1261. 在受污染的二叉树中查找元素

2024-03-13发表2025-04-15更新Android28 分钟读完 (大约4152个字)

00-面试查漏补缺

2024.3.13

Handler

sendMessage
post
- 有callback的message
- looper循环执行
sendMessage
- 发送自定义的message
- 可以没有callback
- 可以有what、obj去和接收者传递消息

Message源码（仅public）

Message的获取

Handler包装的runnable
new Message()

obtain() 推荐，Message中的recycle方法会回收不用的Message，obtain的时候如果消息池不空，可以服用消息池

public final class Message implements Parcelable {
    /**
     * User-defined message code so that the recipient can identify
     * what this message is about. Each {@link Handler} has its own name-space
     * for message codes, so you do not need to worry about yours conflicting
     * with other handlers.
     */
    public int what;

    /**
     * arg1 and arg2 are lower-cost alternatives to using
     * {@link #setData(Bundle) setData()} if you only need to store a
     * few integer values.
     */
    public int arg1;

    /**
     * arg1 and arg2 are lower-cost alternatives to using
     * {@link #setData(Bundle) setData()} if you only need to store a
     * few integer values.
     */
    public int arg2;

    /**
     * An arbitrary object to send to the recipient.  When using
     * {@link Messenger} to send the message across processes this can only
     * be non-null if it contains a Parcelable of a framework class (not one
     * implemented by the application).   For other data transfer use
     * {@link #setData}.
     *
     * <p>Note that Parcelable objects here are not supported prior to
     * the {@link android.os.Build.VERSION_CODES#FROYO} release.
     */
    public Object obj;
    @UnsupportedAppUsage
    /*package*/ int flags;

    /**
     * The targeted delivery time of this message. The time-base is
     * {@link SystemClock#uptimeMillis}.
     * @hide Only for use within the tests.
     */
    @UnsupportedAppUsage
    @VisibleForTesting(visibility = VisibleForTesting.Visibility.PACKAGE)
    public long when;


    /** @hide */
    public static final Object sPoolSync = new Object();

    /**
     * Return a new Message instance from the global pool. Allows us to
     * avoid allocating new objects in many cases.
     */
    public static Message obtain() {
        synchronized (sPoolSync) {
            if (sPool != null) {
                Message m = sPool;
                sPool = m.next;
                m.next = null;
                m.flags = 0; // clear in-use flag
                sPoolSize--;
                return m;
            }
        }
        return new Message();
    }

    /**
     * Same as {@link #obtain()}, but copies the values of an existing
     * message (including its target) into the new one.
     * @param orig Original message to copy.
     * @return A Message object from the global pool.
     */
    public static Message obtain(Message orig) {
        Message m = obtain();
        m.what = orig.what;
        m.arg1 = orig.arg1;
        m.arg2 = orig.arg2;
        m.obj = orig.obj;
        m.replyTo = orig.replyTo;
        m.sendingUid = orig.sendingUid;
        m.workSourceUid = orig.workSourceUid;
        if (orig.data != null) {
            m.data = new Bundle(orig.data);
        }
        m.target = orig.target;
        m.callback = orig.callback;

        return m;
    }

    /**
     * Same as {@link #obtain()}, but sets the value for the <em>target</em> member on the Message returned.
     * @param h  Handler to assign to the returned Message object's <em>target</em> member.
     * @return A Message object from the global pool.
     */
    public static Message obtain(Handler h) {
        Message m = obtain();
        m.target = h;

        return m;
    }

    /**
     * Same as {@link #obtain(Handler)}, but assigns a callback Runnable on
     * the Message that is returned.
     * @param h  Handler to assign to the returned Message object's <em>target</em> member.
     * @param callback Runnable that will execute when the message is handled.
     * @return A Message object from the global pool.
     */
    public static Message obtain(Handler h, Runnable callback) {
        Message m = obtain();
        m.target = h;
        m.callback = callback;

        return m;
    }

    /**
     * Same as {@link #obtain()}, but sets the values for both <em>target</em> and
     * <em>what</em> members on the Message.
     * @param h  Value to assign to the <em>target</em> member.
     * @param what  Value to assign to the <em>what</em> member.
     * @return A Message object from the global pool.
     */
    public static Message obtain(Handler h, int what) {
        Message m = obtain();
        m.target = h;
        m.what = what;

        return m;
    }

    /**
     * Same as {@link #obtain()}, but sets the values of the <em>target</em>, <em>what</em>, and <em>obj</em>
     * members.
     * @param h  The <em>target</em> value to set.
     * @param what  The <em>what</em> value to set.
     * @param obj  The <em>object</em> method to set.
     * @return  A Message object from the global pool.
     */
    public static Message obtain(Handler h, int what, Object obj) {
        Message m = obtain();
        m.target = h;
        m.what = what;
        m.obj = obj;

        return m;
    }

    /**
     * Same as {@link #obtain()}, but sets the values of the <em>target</em>, <em>what</em>,
     * <em>arg1</em>, and <em>arg2</em> members.
     *
     * @param h  The <em>target</em> value to set.
     * @param what  The <em>what</em> value to set.
     * @param arg1  The <em>arg1</em> value to set.
     * @param arg2  The <em>arg2</em> value to set.
     * @return  A Message object from the global pool.
     */
    public static Message obtain(Handler h, int what, int arg1, int arg2) {
        Message m = obtain();
        m.target = h;
        m.what = what;
        m.arg1 = arg1;
        m.arg2 = arg2;

        return m;
    }

    /**
     * Same as {@link #obtain()}, but sets the values of the <em>target</em>, <em>what</em>,
     * <em>arg1</em>, <em>arg2</em>, and <em>obj</em> members.
     *
     * @param h  The <em>target</em> value to set.
     * @param what  The <em>what</em> value to set.
     * @param arg1  The <em>arg1</em> value to set.
     * @param arg2  The <em>arg2</em> value to set.
     * @param obj  The <em>obj</em> value to set.
     * @return  A Message object from the global pool.
     */
    public static Message obtain(Handler h, int what,
            int arg1, int arg2, Object obj) {
        Message m = obtain();
        m.target = h;
        m.what = what;
        m.arg1 = arg1;
        m.arg2 = arg2;
        m.obj = obj;

        return m;
    }

    /** @hide */
    public static void updateCheckRecycle(int targetSdkVersion) {
        if (targetSdkVersion < Build.VERSION_CODES.LOLLIPOP) {
            gCheckRecycle = false;
        }
    }

    /**
     * Return a Message instance to the global pool.
     * <p>
     * You MUST NOT touch the Message after calling this function because it has
     * effectively been freed.  It is an error to recycle a message that is currently
     * enqueued or that is in the process of being delivered to a Handler.
     * </p>
     */
    public void recycle() {
        if (isInUse()) {
            if (gCheckRecycle) {
                throw new IllegalStateException("This message cannot be recycled because it "
                        + "is still in use.");
            }
            return;
        }
        recycleUnchecked();
    }
    /**
     * Return the targeted delivery time of this message, in milliseconds.
     */
    public long getWhen() {
        return when;
    }

    public void setTarget(Handler target) {
        this.target = target;
    }

    /**
     * Retrieve the {@link android.os.Handler Handler} implementation that
     * will receive this message. The object must implement
     * {@link android.os.Handler#handleMessage(android.os.Message)
     * Handler.handleMessage()}. Each Handler has its own name-space for
     * message codes, so you do not need to
     * worry about yours conflicting with other handlers.
     */
    public Handler getTarget() {
        return target;
    }

    /**
     * Retrieve callback object that will execute when this message is handled.
     * This object must implement Runnable. This is called by
     * the <em>target</em> {@link Handler} that is receiving this Message to
     * dispatch it.  If
     * not set, the message will be dispatched to the receiving Handler's
     * {@link Handler#handleMessage(Message)}.
     */
    public Runnable getCallback() {
        return callback;
    }

    /** @hide */
    @UnsupportedAppUsage
    public Message setCallback(Runnable r) {
        callback = r;
        return this;
    }

    /**
     * Obtains a Bundle of arbitrary data associated with this
     * event, lazily creating it if necessary. Set this value by calling
     * {@link #setData(Bundle)}.  Note that when transferring data across
     * processes via {@link Messenger}, you will need to set your ClassLoader
     * on the Bundle via {@link Bundle#setClassLoader(ClassLoader)
     * Bundle.setClassLoader()} so that it can instantiate your objects when
     * you retrieve them.
     * @see #peekData()
     * @see #setData(Bundle)
     */
    public Bundle getData() {
        if (data == null) {
            data = new Bundle();
        }

        return data;
    }

    /**
     * Like getData(), but does not lazily create the Bundle.  A null
     * is returned if the Bundle does not already exist.  See
     * {@link #getData} for further information on this.
     * @see #getData()
     * @see #setData(Bundle)
     */
    public Bundle peekData() {
        return data;
    }

    /**
     * Sets a Bundle of arbitrary data values. Use arg1 and arg2 members
     * as a lower cost way to send a few simple integer values, if you can.
     * @see #getData()
     * @see #peekData()
     */
    public void setData(Bundle data) {
        this.data = data;
    }

    /**
     * Chainable setter for {@link #what}
     *
     * @hide
     */
    public Message setWhat(int what) {
        this.what = what;
        return this;
    }

    /**
     * Sends this Message to the Handler specified by {@link #getTarget}.
     * Throws a null pointer exception if this field has not been set.
     */
    public void sendToTarget() {
        target.sendMessage(this);
    }

    /**
     * Returns true if the message is asynchronous, meaning that it is not
     * subject to {@link Looper} synchronization barriers.
     *
     * @return True if the message is asynchronous.
     *
     * @see #setAsynchronous(boolean)
     */
    public boolean isAsynchronous() {
        return (flags & FLAG_ASYNCHRONOUS) != 0;
    }

    /**
     * Sets whether the message is asynchronous, meaning that it is not
     * subject to {@link Looper} synchronization barriers.
     * <p>
     * Certain operations, such as view invalidation, may introduce synchronization
     * barriers into the {@link Looper}'s message queue to prevent subsequent messages
     * from being delivered until some condition is met.  In the case of view invalidation,
     * messages which are posted after a call to {@link android.view.View#invalidate}
     * are suspended by means of a synchronization barrier until the next frame is
     * ready to be drawn.  The synchronization barrier ensures that the invalidation
     * request is completely handled before resuming.
     * </p><p>
     * Asynchronous messages are exempt from synchronization barriers.  They typically
     * represent interrupts, input events, and other signals that must be handled independently
     * even while other work has been suspended.
     * </p><p>
     * Note that asynchronous messages may be delivered out of order with respect to
     * synchronous messages although they are always delivered in order among themselves.
     * If the relative order of these messages matters then they probably should not be
     * asynchronous in the first place.  Use with caution.
     * </p>
     *
     * @param async True if the message is asynchronous.
     *
     * @see #isAsynchronous()
     */
    public void setAsynchronous(boolean async) {
        if (async) {
            flags |= FLAG_ASYNCHRONOUS;
        } else {
            flags &= ~FLAG_ASYNCHRONOUS;
        }
    }

    /** Constructor (but the preferred way to get a Message is to call {@link #obtain() Message.obtain()}).
    */
    public Message() {
    }
}

Looper每次循环在做什么

2024-03-13发表2025-04-15更新Android12 分钟读完 (大约1727个字)

00-面试查漏补缺

View绘制流程图

起点：ViewRootImpl

在ViewRootImpl中有一个巨长的方法performTraversals，其中会依次调用三个函数

performMeasure
performLayout
performDraw

通过ViewRootImpl的setView方法，ViewRootImpl对象会拥有一个mView对象

2024-03-12发表2025-04-15更新Android4 分钟读完 (大约544个字)

19-RecyclerView

RecyclerView

flexible:
limited: 有限屏幕中显示
large: 大量内容

RecyclerView的优势

Linear, Grid, Staggered Grid三种布局
itemAnimator接口
强制实现ViewHolder
解耦设计
性能更好

listView的局限

只能纵向列表
没有动画api
api设计太个性了，和其他view设计的重复
性能不好
三个帮手
- LayoutManager: 负责布局Views
- ItemAnimator: 负责给View加动画
- Adaptor: 提供views

2024-03-11发表2025-04-15更新Android几秒读完 (大约104个字)

20-Android多线程

Thread.yield()

暂时把时间片让出去，变成可运行状态(ready)

handler

Looper

ThreadLocal的
相当于一个线程里的大循环
在大循环里循环从messageQueue中拿消息
拿到消息后执行消息

Handler

2024-03-11发表2025-04-15更新Android4 分钟读完 (大约604个字)

18-Java多线程

Thread, Runnable, callable

基础

ThreadFactory

1
2
3

public interface ThreadFactory {
    Thread newThread(Runnable r);
}

实现一个工厂，生成thread，方便对同类thread进行统一的初始化操作

Executor

2024-03-10发表2025-04-15更新Android2 分钟读完 (大约246个字)

21-RxJava

Single

`static <T> Single.just(T t)`

生成一个Single
d对象
- return onAssembly(new SingleJust(t))
- onAssembly是一个钩子函数，一般情况下不做任何操作，就是调用一个Function<T, R>.apply()

Observer

有后续的onNext
有周期的Observer.interval()每隔一段时间onNext一次

Disposable