发表更新Java基础9 分钟读完 (大约1279个字)

00-Java数组遍历性能对比

三种遍历方式性能对比

  1. 循环与数组的length比较
1
2
3
4
5
6
7
8
9
10
public class JavaMain {
    static Object[] objs = new Object[10000000];
    static int zero() {
        int sum = 0;
        for(int i = 0; i < objs.length; i++) {
            sum ^= objs[i].hashCode();
        }
        return sum;
    }
}
  1. 将数组length存在方法栈中
1
2
3
4
5
6
7
8
9
10
11
public class JavaMain {
    static Object[] objs = new Object[10000000];
    static int one() {
        int sum = 0;
        int len = objs.length;
        for(int i = 0; i < len; i++) {
            sum ^= objs[i].hashCode();
        }
        return sum;
    }
}
  1. for-each循环
阅读更多
发表更新LeetCode / 算法12 分钟读完 (大约1850个字)

LeetCode-38

2181. 合并零之间的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        int sum = 0;
        ListNode dummy;
        ListNode *move_dummy = &dummy;
        ListNode *move = head;
        while(move->next) {
            sum = 0;
            while(move->next && move->next->val != 0) {
                sum += move->next->val;
                move = move->next;
            }
            move->val = sum;
            move_dummy->next = move;
            move_dummy = move_dummy->next;
            move = move->next;
            move_dummy->next = nullptr;
        }
        return dummy.next;
    }
};

977. 有序数组的平方

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        vector<int> merged_array(len);
        int i = 0, j = len - 1;
        for(int k = len - 1; k >= 0; k--) {
            if(abs(nums[i]) > abs(nums[j])) {
                merged_array[k] = nums[i] * nums[i];
                i++;
            } else {
                merged_array[k] = nums[j] * nums[j];
                j--;
            }
        }
        return merged_array;
    }
};
  • 按照绝对值归并
  • 双指针，从左右两端开始移动，

3174. 清除数字

阅读更多
发表更新牛客 / 刷题11 分钟读完 (大约1638个字)

牛客刷题-2

1.小美的平衡矩阵

1.
小美的平衡矩阵
小美拿到了一个n∗nn*n的矩阵，其中每个元素是 0 或者 1。
小美认为一个矩形区域是完美的，当且仅当该区域内 0 的数量恰好等于 1 的数量。
现在，小美希望你回答有多少个i∗ii*i的完美矩形区域。你需要回答1≤i≤n1\leq i \leq n的所有答案。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M
输入描述：
第一行输入一个正整数n，代表矩阵大小。
接下来的n行，每行输入一个长度为n的 01 串，用来表示矩阵。
1\leq n \leq 200
输出描述：
输出n行，第i行输出i*i的完美矩形区域的数量。
示例1
输入例子： 
4
1010
0101
1100
0011
输出例子： 
0
7
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
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<vector<int>> preSum(n, vector<int>(n+1));
    for(int i = 0; i < n; i++) {
        string s;
        cin >> s;
        for(int j = 0; j < n; j++) {
            preSum[i][j+1] = preSum[i][j] + (s[j] - '0');
        }
    }
    for(int window = 1; window <= n; window++) {
        if(window & 1) {
            cout << "0\n";
            continue;
        }
        int perfect = 0;
        for(int j = 0; j <= n - window; j++) {
            int sum = 0;
            for(int i = 0; i < window; i++) {
                sum += preSum[i][window + j] - preSum[i][j];
            }
            if(sum * 2 == window * window) {
                perfect++;
            }
            for(int i = window; i < n; i++) {
                sum -= preSum[i - window][window + j] - preSum[i - window][j];
                sum += preSum[i][window + j] - preSum[i][j];
                if(sum * 2 == window * window) {
                    perfect++;
                }
            }
        }
        cout << perfect << "\n";
    }
}

2.小美的数组询问

2.
小美的数组询问
小美拿到了一个由正整数组成的数组，但其中有一些元素是未知的（用 0 来表示）。
现在小美想知道，如果那些未知的元素在区间[l,r][l,r]范围内随机取值的话，数组所有元素之和的最小值和最大值分别是多少？
共有qq次询问。
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 256M，其他语言512M
输入描述：
第一行输入两个正整数n,q，代表数组大小和询问次数。
第二行输入n个整数a_i，其中如果输入的a_i为 0，那么说明a_i是未知的。
接下来的q行，每行输入两个正整数 l,r，代表一次询问。
1\leq n,q \leq 10^5
0 \leq a_i \leq 10^9
1\leq l \leq r \leq 10^9
输出描述：
输出q行，每行输出两个正整数，代表所有元素之和的最小值和最大值。
示例1
输入例子： 
3 2
1 0 3
1 2
4 4
输出例子： 
5 6
8 8
例子说明： 
只有第二个元素是未知的。
第一次询问，数组最小的和是 1+1+3=5，最大的和是 1+2+3=6。
第二次询问，显然数组的元素和必然为 8。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;
    long long sum = 0;
    long long zeroCnt = 0;
    for(int i = 0; i < n; i++) {
        int ai;
        cin >> ai;
        zeroCnt += (ai == 0 ? 1 : 0);
        sum += ai;
    }
    for(int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        cout << sum + zeroCnt*l << " " << sum + zeroCnt*r << "\n";
    }
}
阅读更多
发表更新OI KIWI / 算法2 分钟读完 (大约355个字)

OI KIWI 02-二分

二分查找

左闭右闭

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int binarySearch(vector<int>& vec, int target) {
    int len = vec.size();
    int l = 0, r = len - 1; // 
    while(l <= r) {
        int mid = (r - l) / 2 + l;
        if(vec[mid] == target) {
            return mid;
        } else if(vec[mid] > target) {
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    return -1;
}

左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int len = nums.size();
        int l = 0, r = len;
        while(l < r) {
            int mid = (r - l) / 2 + l;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] > target) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
};

总结

阅读更多
发表更新LeetCode / 算法11 分钟读完 (大约1694个字)

LeetCode-37

698. 划分为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
47
48
49
50
class Solution {
    class Solve {
        vector<int>& nums;
        int k;
        int n;
        vector<int> bucket;
        int target;
        int sum;
        bool canPartition;
        bool dfs(int index) {
            if(index >= n) { // 所有数都放进来了，且没有超过target
                // 说明一定全等于target
                // 如果有桶<target, 则一定有桶>target，所以所有桶一定>=target
                // 如果有桶>target, 则一定有桶<target，所以所有桶一定<=target
                // 所以所有桶一定==target
                return true;
            }
            for(int i = 0; i < k; i++) {
                if(i>0 && bucket[i] == bucket[i-1]) continue;
                if(bucket[i] + nums[index] <= target) {
                    bucket[i] += nums[index];
                    if(dfs(index+1)) {
                        return true;
                    }
                    bucket[i] -= nums[index];
                }
            }
            return false;
        }
        public:
        Solve(vector<int>& nums, int k):nums(nums), k(k), bucket(k) {
            n = nums.size();
            sum = accumulate(nums.begin(), nums.end(), 0);
            target = sum / k;
            sort(nums.begin(), nums.end(), greater<int>());
            if(sum % k != 0) {
                canPartition = false;
                return;
            }
            canPartition = dfs(0);
        }
        bool solve() {
            return canPartition;
        }
    };
public:
    bool canPartitionKSubsets(vector<int>& nums, int k) {
        return Solve(nums, k).solve();
    }
};

硬搜

690. 员工的重要性

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int getImportance(vector<Employee*> employees, int id) {
        int len = employees.size();
        unordered_map<int, Employee*> id2Node;
        for(Employee *employee : employees) {
            id2Node[employee->id] = employee;
        }
        function<int(int)> dfs = [&](int currentId) {
            Employee *node = id2Node[currentId];
            int ans = node->importance;
            for(int child : node->subordinates) {
                ans += dfs(child);
            }
            return ans;
        };
        return dfs(id);
    }
};

699. 掉落的方块

阅读更多
发表更新OI KIWI / 算法12 分钟读完 (大约1789个字)

OI KIWI 01-倍增

OI KIWI 倍增

思想

图片来源

查找小于limit的最大数字

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maxValueInVecSmallerThenLimit(vector<int>& vec, int limit) {
    int n = vec.size();
    int l = 0;
    int p = 1;
    while(p) {
        if(l + p < n && vec[l + p] < limit) {
            l += p;
            p <<= 1;
        } else {
            p >>= 1;
        }
    }
    return vec[l];
}
阅读更多
发表更新LeetCode / 算法44 分钟读完 (大约6551个字)

LeetCode-36

551. 学生出勤记录 I

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    bool checkRecord(string s) {
        int count = 0;
        int max_seq_late = 0;
        int seq_late = 0;
        for(char c : s) {
            if(c == 'A') count++;
            if(c == 'L') {
                seq_late++;
            } else {
                max_seq_late = max(max_seq_late, seq_late);
                seq_late = 0;
            }
        }
        max_seq_late = max(max_seq_late, seq_late);
        return count < 2 && max_seq_late < 3;

    }
};
  • 连续相同的值的个数
  • 统计元素出现的次数

3137. K 周期字符串需要的最少操作次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int minimumOperationsToMakeKPeriodic(string word, int k) {
        unordered_map<string, int> subStrCount;
        int len = word.length();
        for(int i = 0; i < len; i += k) {
            subStrCount[word.substr(i, k)]++;
        }
        int minOpCnt = len / k;
        for(auto& ite : subStrCount) {
            minOpCnt = min(minOpCnt, len / k - ite.second);
        }
        return minOpCnt;
    }
};
  • 翻译一下规则，就是把长度为nk的字符串切割成n个长度为k的子串，一次操作可以把一个子串替换成另一个字串，求如何替换，将所有字串都相同。
  • 翻译好需求，就很清楚了，直接统计每个字串出现的次数，取出现次数最大的，替换次数最少，为n - cnt[i]
阅读更多
发表更新Android / 手撸Android源码1 小时读完 (大约11066个字)

基础05-Navigation

简介

NavController是中央导航 API。它会跟踪用户访问过的目的地，并允许用户在目的地之间移动。

获取NavController

  • fragment

如果是NavHostFragment

1
val navController = this.navController
阅读更多
发表更新Android / 手撸Android源码23 分钟读完 (大约3407个字)

基础04-LiveData

LiveData

LiveData的观察者

1
2
3
4
5
6
7
fun interface Observer<T> {

    /**
     * Called when the data is changed to [value].
     */
    fun onChanged(value: T)
}
  • 通过onChanged函数分派数据变化

成员

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
@SuppressWarnings("WeakerAccess") /* synthetic access */
final Object mDataLock = new Object();
static final int START_VERSION = -1;
@SuppressWarnings("WeakerAccess") /* synthetic access */
static final Object NOT_SET = new Object();

private SafeIterableMap<Observer<? super T>, ObserverWrapper> mObservers =
        new SafeIterableMap<>();

// how many observers are in active state
@SuppressWarnings("WeakerAccess") /* synthetic access */
int mActiveCount = 0;
// to handle active/inactive reentry, we guard with this boolean
private boolean mChangingActiveState;
private volatile Object mData; // 1️⃣：当前的data
// when setData is called, we set the pending data and actual data swap happens on the main
// thread
@SuppressWarnings("WeakerAccess") /* synthetic access */
volatile Object mPendingData = NOT_SET; // 2️⃣：给多线程使用的，在4️⃣mPostValueRunnable中使用
private int mVersion; // 3️⃣：mVersion是数据版本

private boolean mDispatchingValue;
@SuppressWarnings("FieldCanBeLocal")
private boolean mDispatchInvalidated;
private final Runnable mPostValueRunnable = new Runnable() {// 4️⃣mPostValueRunnable，在主线程中将mPendingData设置为当前值
    @SuppressWarnings("unchecked")
    @Override
    public void run() {
        Object newValue;
        synchronized (mDataLock) {
            newValue = mPendingData;
            mPendingData = NOT_SET;
        }
        setValue((T) newValue);
    }
};
阅读更多
发表更新Android / 手撸Android源码18 分钟读完 (大约2687个字)

基础03-Lifecycle

lifeCycle的Observer

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
public interface LifecycleObserver

public interface DefaultLifecycleObserver : LifecycleObserver {
    /**
     * Notifies that `ON_CREATE` event occurred.
     *
     *
     * This method will be called after the [LifecycleOwner]'s `onCreate`
     * method returns.
     *
     * @param owner the component, whose state was changed
     */
    public fun onCreate(owner: LifecycleOwner) {}

    /**
     * Notifies that `ON_START` event occurred.
     *
     *
     * This method will be called after the [LifecycleOwner]'s `onStart` method returns.
     *
     * @param owner the component, whose state was changed
     */
    public fun onStart(owner: LifecycleOwner) {}

    /**
     * Notifies that `ON_RESUME` event occurred.
     *
     *
     * This method will be called after the [LifecycleOwner]'s `onResume`
     * method returns.
     *
     * @param owner the component, whose state was changed
     */
    public fun onResume(owner: LifecycleOwner) {}

    /**
     * Notifies that `ON_PAUSE` event occurred.
     *
     *
     * This method will be called before the [LifecycleOwner]'s `onPause` method
     * is called.
     *
     * @param owner the component, whose state was changed
     */
    public fun onPause(owner: LifecycleOwner) {}

    /**
     * Notifies that `ON_STOP` event occurred.
     *
     *
     * This method will be called before the [LifecycleOwner]'s `onStop` method
     * is called.
     *
     * @param owner the component, whose state was changed
     */
    public fun onStop(owner: LifecycleOwner) {}

    /**
     * Notifies that `ON_DESTROY` event occurred.
     *
     *
     * This method will be called before the [LifecycleOwner]'s `onDestroy` method
     * is called.
     *
     * @param owner the component, whose state was changed
     */
    public fun onDestroy(owner: LifecycleOwner) {}
}

public fun interface LifecycleEventObserver : LifecycleObserver {
    /**
     * Called when a state transition event happens.
     *
     * @param source The source of the event
     * @param event The event
     */
    public fun onStateChanged(source: LifecycleOwner, event: Lifecycle.Event)
}
  • 可以看到，我们在使用lifecycle.addObserver()时，可以传入LifecycleEventObserver或DefaultLifecycleObserver，一个通过event获取当前状态，一个通过不同的回调函数获取当前状态

Activity树

1
2
3
4
5
6
7
8
9
10
11
Activity -- AccountAuthenticatorActivity
         |- ActivityGroup -- TabActivity
         |- ExpandableListActivity
         |- LauncherActivity
         |- ListActivity -- PreferenceActivity
         |- NativeActivity
         |- androidx.core.app.ComponentActivity -- androidx.activity.ComponentActivity -- FragmentActivity -- AppCompatActivity
                                                |- PreviewActivity
         |- BootstrapActivity
         |- EmptyActivity
         |- EmptyFloatingActivity

LifecycleOwner

阅读更多
关注我

链接

分类

最新文章

归档

标签

6.8242
Android1
Android FrameWork1
Android 高级开发瓶颈突破系列课11
Android-官方文档1
Android-官方源码5
Android面试查漏补缺2
C/C++1
Flutter1
Java基础1
Kotlin-Android21
Kotlin-Android 实习25
LeetCode45
LeetCode 1013
LeetCode周赛1
Linux/UNIX系统编程手册38
OI KIWI2
OS4
PAT-(Advanced-Level)-Practice2
PAT-(Basic-Level)-Practice44
blockchain1
fedfab13
gallery1
geth1
git1
gradle1
hexo2
linux2
misc1
projects1
shell2
刷题2
动态规划1
多线程1
排序1
数据库2
牛客2
算法43
×