image frame

XiShng Blog

既往拼搏，守护一生所爱

Android Studio踩坑日记

移动开发

Created: March 5, 2022 1:20 AM

  • 打开Android Studio就要设置代理？

    代理设置界面

    在使用代理上，可以参考下列信息：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    // 东软信息学院
    mirrors.neusoft.edu.cn:80

    // 北京化工大学
    ubuntu.buct.edu.cn/ubuntu.buct.cn:80

    // 中国科学院开源协会
    mirrors.opencas.cn:80
    mirrors.opencas.org/mirrors.opencas.ac.cn:80

    // 上海GDG镜像服务器
    sdk.gdgshanghai.com:8000

    // 电子科技大学
    mirrors.dormforce.net:80

    如果使用上面的URL链接，那么到这里就完成了。

  • 协议接受后，需要的工作

    • SDK Tools

      SDK Tools界面

      我所用的是MAC，所以这里所圈中的是必不可少的SDK工具。

    • 安卓镜像

      安卓镜像列表

      图中圈画出来的需要注意下

      • Google Play：不支持ROOT
      • Google APIs：支持ROOT
        • 通过 ~/Library/Android/sdk/platform-tools/adb root 即可开启（路径不一致请自行修改，一般来讲都在上面下单SDK Tools文件目录中）

  • 模拟器联网问题

    • 简单的解决方法

      关闭代理，然后重新创建模拟器，然后在使用的时候关闭模拟器的WIFI，仅保留移动通信功能，此时就可以正常使用了。

    • 略微复杂，这里会讲述两种方法：

      1. 「临时解决方案」首先关掉你的模拟器，同样在SDK Tools的下载目录下，通过如下命令打开你的模拟器即可解决：

        1
        $ ~/Library/Android/sdk/emulator/emulator --avd <你模拟器的名字> -dns-server 8.8.8.8,114.114.114.114

      2. 【看看就行了，没用】「网传永久有效方案」打开你的模拟器（一定要是Google APIs类型的哦），执行下面命令：

        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        # 打开root权限
        $ ~/Library/Android/sdk/platform-tools/adb root
        restarting adbd as root

        $ ~/Library/Android/sdk/platform-tools/adb shell

        emulator64_arm64:/ # getprop
        ...
        [net.dns1]: [fec0::3]
        [net.dns2]: [10.0.2.3]
        ...
        emulator64_arm64:/ # setprop net.dns1 8.8.8.8

        emulator64_arm64:/ # getprop
        ...
        [net.dns1]: [8.8.8.8]
        [net.dns2]: [10.0.2.3]
        ...

        按照网上的教程，此时重启模拟器就可以正常使用了。

分治法

原理：将大问题转换为一个或多个子问题，知道问题可以轻易解决，最后将子问题的结果进行合并

策略：对于一个规模为n的问题，若该问题可以容易的解决(比如规模n较小)则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解决这些子问题，然后将各个子问题的解合并得到原问题的解。

分治法使用场景

  1. 该问题的规模缩小到一定的程度就可以容易的解决。
  2. 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
  3. 利用该问题分解出的子问题的解可以合并为该问题的解。
  4. 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

第一条特征是绝大多数问题可以满足的，问题的复杂性一般是随着问题规模的增加而增加；第二条特征是应用分治法的前提。它是大多数问题可以满足的，此特征反映了递归思想的应用。第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条，而不具备第三条特征，则可以考虑使用贪心法或者动态规划法。第四条关系到分治法的效率，如果各个子问题是不独立的则分治法要做寻多不必要的工作，重复的解决公共的子问题，此时虽然可用分治法，但一般使用动态规划法较好。

分治法的基本步骤

  • 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
  • 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
  • 合并：将各个子问题的解合并为原问题的解

分治法的复杂性分析

一个分治法将规模为n的问题分成k个规模为n/m的子问题去解。设分解阈值
分解阈值

，且最小子解规模为1的问题消耗一个单位时间。设将原问题分解为k个子问题以及用merge将K个子问题的解合并为原问题的解需用f(n)个单位时间，用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间：
分支规模——计算时间

可以使用分治法求解的一些经典问题

  1. 二分搜索
  2. 大整数乘法
  3. Strassen矩阵乘法
  4. 棋盘覆盖
  5. 合并排序
  6. 快速排序
  7. 线性时间选择
  8. 最接近点对问题
  9. 循环赛日程表
  10. 汉诺塔

算法探究

算法

算法之途广而宽

Created: January 17, 2022 12:58 AM

Read Me

算法很难搞懂，但想下心底要努力的目标，其实一切都可以忍受的

  • 基础常用算法

  • 动态规划

    • 基本概念

      动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，而我们希望找到具有最优值的解。动态规划算法与分治法类似，基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。

      动态规划问题经分解得到的子问题往往不是互相独立的。需要保存已解决的子问题的答案，而在需要时再找出已保存的答案，这样就可以避免大量的重复计算。可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。

      动态规划有两个重要的概念：

      • 状态：解决某一问题的中间结果，它是子问题的一个抽象定义。
      • 状态转移方程：状态与状态之间的递推关系。

      动态规划解题步骤：

      1. 状态定义：找出子问题抽象定义。
      2. 确定状态转移方程：找出状态与状态之间的递推关系。
      3. 初始状态和边界情况：最简单的子问题的结果，也是程序的出口条件 。
      4. 返回值：对于简单问题，返回值可能就是最终状态；对于复杂问题可能还需对最终状态做一些额外处理。

    • 示例题目一

      题目描述：假设正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？其中 n 是一个正整数。

      示例 1：

      1
      2
      3
      4
      5
      6
      输入： 2
      输出： 2
      解释： 有两种方法可以爬到楼顶。
      1. 1 阶 + 1 阶
      2. 2 阶
      复制代码

      示例 2：

      1
      2
      3
      4
      5
      6
      7
      输入： 3
      输出： 3
      解释： 有三种方法可以爬到楼顶。
      1. 1 阶 + 1 阶 + 1 阶
      2. 1 阶 + 2 阶
      3. 2 阶 + 1 阶
      复制代码

      这道题有两个关键特征：

      • 要求给出达成某个目的的解法个数；
      • 不要求给出每一种解法对应的具体路径。

      这样的问题往往可以用动态规划进行求解。对于这个问题，每次爬楼梯只有两种情况：

      • 最后一步爬 1 级台阶，前面有 n - 1 级台阶，这种情况下共有f(n - 1)种方法；
      • 最后一步爬 2 级台阶，前面有 n - 2 级台阶，这种情况下共有f(n - 2)种方法；

      f(n) 为以上两种情况之和，即 f(n)=f(n-1)+f(n-2)，这就是本题用到的递推关系。下面就根据动态规划的四个步骤来看那一下：

      1. 状态定义：初始化一个f数组，f[i]表示爬到i级台阶的方法数量；
      2. 状态转移方程：f(n)=f(n-1)+f(n-2)；
      3. 初始状态：一级台阶时，共1种爬法；两级台阶时，可以一级一级爬，也可以一次爬两级，共有2种爬法。即f[1] = 1，f[2] = 2；
      4. 返回值：f[n] ，即 n 级台阶共有多少种爬法。

      动态规划实现代码如下：

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      /**
      * @param {number} n
      * @return {number}
      */
      const climbStairs = function(n) {
          // 初始化状态数组
          const f = [];
          // 初始化已知值
          f[1] = 1;
          f[2] = 2;
          // 动态更新每一层楼梯对应的结果
          for(let i = 3;i <= n;i++){
              f[i] = f[i-2] + f[i-1];
          }
          // 返回目标值
          return f[n];
      };

    • 分析使用场景

      上面用动态规划的思想解决了爬楼梯的问题，当然我们的目的并不是为了解决这个问题，而是通过这个问题来看动态规划，下面就来重新认识一下动态规划。

      上面说过了分支问题，它的核心思想是：把一个问题分解为相互独立的子问题，逐个解决子问题后，再组合子问题的答案，就得到了问题的最终解。

      动态规划的思想和“分治”有点相似。不同之处在于，“分治”思想中，各个子问题之间是独立的：比如说归并排序中，子数组之间的排序并不互相影响。而动态规划划分出的子问题，往往是相互依赖、相互影响的。

      那什么样的题应该用动态规划来做？要抓以下关键特征：

      • 最优子结构，它指的是问题的最优解包含着子问题的最优解——不管前面的决策如何，此后的状态必须是基于当前状态（由上次决策产生）的最优决策。就这道题来说，f(n)和f(n-1)、f(n-2)之间的关系（状态转移方程）印证了这一点。
      • 重叠子问题，在递归的过程中，出现了反复计算的情况。
      • 无后效性，无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。

      所以，只要需要解决的问题符合这三个关键特征，就可以使用动态规划来求解。

请我喝杯咖啡吧~

支付宝
微信