JAVA 牛牛

Home

27. 移除元素

  • 难度：简单
  • 本题涉及算法：
  • 思路： 拷贝覆盖 倒序遍历 交换移除
  • 类似题型:

题目 27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

 

示例 1:

给定 nums = [3,2,2,3], val = 3,

函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2,

函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

注意这五个元素可为任意顺序。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

方法一 倒序遍历

  • 解题思路：
    • 倒序遍历，可以解决删除数组时，不需要对数组下标做多余的判断
  • 复杂度分析：
    • 时间复杂度：$O(n)$，假设数组的长度是 $n$，最差情况是当数组中元素都不相同，则遍历 $n$
    • 空间复杂度：$O(1)$。

python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        for i in range(len(nums)-1, -1, -1):
            if(nums[i] == val):
                nums.pop(i)
        return len(nums)

方法二 拷贝覆盖

  • 解题思路：
    • 主要思路是遍历数组nums，每次取出的数字变量为num，同时设置一个下标ans
    • 在遍历过程中如果出现数字与需要移除的值不相同时，则进行拷贝覆盖nums[ans] = num，ans自增1
    • 如果相同的时候，则跳过该数字不进行拷贝覆盖，最后ans即为新的数组长度
    • 这种思路在移除元素较多时更适合使用，最极端的情况是全部元素都需要移除，遍历一遍结束即可
  • 复杂度分析：
    • 时间复杂度：$O(n)$，假设数组的长度是 $n$，最差情况是当数组中元素都不相同，则遍历 $n$
    • 空间复杂度：$O(1)$。

python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        ans = 0
        for num in nums:
            if num != val:
                nums[ans] = num
                ans += 1
        return ans

java

class Solution {
    public int removeElement(int[] nums, int val) {
        int ans = 0;
        for (int num:nums){
            if (num != val) {
                nums[ans] = num;
                ans++;
            }
        }
        return ans;

    }
}

方法三 交换移除

  • 解题思路：
    • 主要思路是遍历数组nums，遍历指针为i，总长度为ans
    • 在遍历过程中如果出现数字与需要移除的值不相同时，则i自增1，继续下一次遍历
    • 如果相同的时候，则将nums[i]与nums[ans-1]交换，即当前数字和数组最后一个数字进行交换，交换后就少了一个元素，故而ans自减1
    • 这种思路在移除元素较少时更适合使用，最极端的情况是没有元素需要移除，遍历一遍结束即可
  • 复杂度分析：
    • 时间复杂度：$O(n)$，假设数组的长度是 $n$，最差情况是当数组中元素都不相同，则遍历 $n$
    • 空间复杂度：$O(1)$。
class Solution {
    public int removeElement(int[] nums, int val) {
        int ans = nums.length;
        for (int i = 0; i < ans;) {
            if (nums[i] == val) {
                nums[i] = nums[ans - 1];
                ans--;
            } else {
                i++;
            }
        }
        return ans;
    }
}

Read more

  • Jun 03, 2020
  • 0 views

面试题64. 求1+2+…+n

  • 难度：中等
  • 本题涉及算法： 递归
  • 思路： 递归
  • 类似题型:

题目 面试题64. 求1+2+…+n

求 1+2+…+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例 1：

输入: n = 3
输出: 6

示例 2：

输入: n = 9
输出: 45

限制：

1 <= n <= 10000

方法一 递归

  • 解题思路：
    • 题目其实指明了要用 递归
  • 复杂度分析：
    • 时间复杂度：$O(n)$。递归函数递归 $n$ 次，每次递归中计算时间复杂度为 $O(1)$，因此总时间复杂度为 $O(n)$。
    • 空间复杂度：$O(n)$。递归函数的空间复杂度取决于递归调用栈的深度，这里递归函数调用栈深度为 $O(n)$，因此空间复杂度为 $O(n)$。

python

class Solution(object):
    def sumNums(self, n):
        """
        :type n: int
        :rtype: int
        """
        # and这个逻辑运算的本质是——如果A&&B，A为false，B是不计算的；只有当A为true，才会继续计算B
        return n!=0 and n + self.sumNums(n - 1)

java

class Solution {
    public int sumNums(int n) {
        if (n == 1) return n;
        n += sumNums(n - 1);
        return n;
    }
}

Read more

  • Jun 02, 2020
  • 0 views

26. 删除排序数组中的重复项

  • 难度：简单
  • 本题涉及算法：双指针法
  • 思路： 双指针法
  • 类似题型:

题目 26. 删除排序数组中的重复项

给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 $O(1)$ 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

方法一 双指针法

  • 解题思路：

    • 数组完成排序后，我们可以放置两个指针 $i$ 和 $j$，其中 $i$ 是慢指针，而 $j$ 是快指针。只要 $nums[i] = nums[j]$，我们就增加 $j$ 以跳过重复项。

    • 当我们遇到 $nums[j] \neq nums[i]$ 时，跳过重复项的运行已经结束，因此我们必须把它$（nums[j]）$的值复制到 $nums[i + 1]$。然后递增 $i$，接着我们将再次重复相同的过程，直到 $j$ 到达数组的末尾为止。

  • 复杂度分析：
    • 时间复杂度：$O(n)$，假设数组的长度是 $n$，那么 $i$ 和 $j$ 分别最多遍历 $n$ 步。
    • 空间复杂度：$O(1)$。

python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        j = 0
        for i in range(1,len(nums)):
            if nums[i] != nums[j]:
                j += 1
                nums[j] = nums[i]
        return j+1

java

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        for(int j = 1;j<nums.length;j++) {
            if(nums[j] != nums[i]) {
                i ++ ;
                nums[i] = nums[j];
            }
        }
        return i + 1;

    }
}

Read more

  • Jun 02, 2020
  • 0 views

5409. 检查一个字符串是否包含所有长度为 K 的二进制子串

  • 难度：中等
  • 本题涉及算法： 滑动窗口
  • 思路： 滑动窗口
  • 类似题型:

题目5409. 检查一个字符串是否包含所有长度为 K 的二进制子串

给你一个二进制字符串 s 和一个整数 k 。

如果所有长度为 k 的二进制字符串都是 s 的子串，请返回 True ，否则请返回 False 。

示例 1：

输入：s = "00110110", k = 2
输出：true
解释：长度为 2 的二进制串包括 "00"，"01"，"10" 和 "11"。它们分别是 s 中下标为 0，1，3，2 开始的长度为 2 的子串。

示例 2：

输入：s = "00110", k = 2
输出：true

示例 3：

输入：s = "0110", k = 1
输出：true
解释：长度为 1 的二进制串包括 "0" 和 "1"，显然它们都是 s 的子串。

示例 4：

输入：s = "0110", k = 2
输出：false
解释：长度为 2 的二进制串 "00" 没有出现在 s 中。

示例 5：

输入：s = "0000000001011100", k = 4
输出：false

提示：

1 <= s.length <= 5 * 10^5
s 中只含 0 和 1 。
1 <= k <= 20

方法一 滑动窗口

  • 解题思路：
    • 计算长度为 k 的所有字符串出现次数，计算公式 $2^ k$
    • 计算在字符串 s 中，出现长度为 k 的所有不重复子串个数
    • 当 k=1 ，s 中子串续 >=1
  • 复杂度分析：
    • 时间复杂度 $O(N)$ ，$N$ 表示字符串长度
    • 空间复杂度 $O(1)$ ，使用的变量为自然数个 
      class Solution:
  def hasAllCodes(self, s: str, k: int) -> bool:
  s_len = len(s)
  if s_len < 2 ** k:
      return False
  curr = set()
  for i in range(s_len+1-k):
      curr.add(s[i:k+i])
  if len(curr) >= 2 ** k:
      return True
  else:
      return False
  • 如果你觉得本文对你有帮助，请点赞👍支持小牛
  • 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出

Read more

  • May 30, 2020
  • 0 views

5408. 通过翻转子数组使两个数组相等

题目 5408. 通过翻转子数组使两个数组相等

给你两个长度相同的整数数组 target 和 arr 。

每一步中，你可以选择 arr 的任意 非空子数组 并将它翻转。你可以执行此过程任意次。

如果你能让 arr 变得与 target 相同，返回 True；否则，返回 False 。

示例 1：

输入：target = [1,2,3,4], arr = [2,4,1,3]
输出：true
解释：你可以按照如下步骤使 arr 变成 target：
1- 翻转子数组 [2,4,1] ，arr 变成 [1,4,2,3]
2- 翻转子数组 [4,2] ，arr 变成 [1,2,4,3]
3- 翻转子数组 [4,3] ，arr 变成 [1,2,3,4]
上述方法并不是唯一的，还存在多种将 arr 变成 target 的方法。

示例 2：

输入：target = [7], arr = [7]
输出：true
解释：arr 不需要做任何翻转已经与 target 相等。

示例 3：

输入：target = [1,12], arr = [12,1]
输出：true

示例 4：

输入：target = [3,7,9], arr = [3,7,11]
输出：false
解释：arr 没有数字 9 ，所以无论如何也无法变成 target 。

示例 5：

输入：target = [1,1,1,1,1], arr = [1,1,1,1,1]
输出：true

提示：

target.length == arr.length
1 <= target.length <= 1000
1 <= target[i] <= 1000
1 <= arr[i] <= 1000

方法一 zip合并

  • 解题思路：
    • 使用 zip 根据字符串下标合并成数组，
    • 判断合并后数组里元素是否都相同
  • 复杂度分析：
    • 时间复杂度 $O(N)$ ，$N$ 表示数组中最短字符串长度
    • 空间复杂度 $O(1)$ ，使用的变量为自然数个

      python

      class Solution:
  def canBeEqual(self, target: List[int], arr: List[int]) -> bool:
  target.sort()
  arr.sort()
  for i in zip(target,arr):
      if len(set(i)) == 1:
          continue
      else:
          return False
  return True
  • __类似题型 __
  • 如果你觉得本文对你有帮助，请点赞👍支持小牛
  • 如果有疑惑或者表达不到位的额地方 ，请在下面👇评论区指出

Read more

  • May 30, 2020
  • 0 views

17. 电话号码的字母组合

  • 难度：中等
  • 本题涉及算法： 回溯算法
  • 思路： 回溯算法
  • 类似题型:

题目 17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

pic

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

方法一 回溯法

  • 回溯法使用：
    • 对于回溯法，通常在二叉树中被使用，更广义上来说，可以处理类树状结构或树形问题
    • 如图

17. 电话号码的字母组合.gif

  • 解题思路：
    1. digits 是数字字符串
    2. s(digits) 是 digits 所能代表的字母字符串
    3. 把 s(digits) 分解 可表示为 
        s(digits[0...n-1])
 = letter(digits[0] + digits[1...n-1])
 = letter(digits[0] + letter(digits[1] + digits[2...n-1])
 = .....

python

class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone= {
            '2':['a','b','c'],
            '3':['d','e','f'],
            '4':['g','h','i'],
            '5':['j','k','l'],
            '6':['m','n','o'],
            '7':['p','q','r','s'],
            '8':['t','u','v'],
            '9':['w','x','y','z']
        }
        def backtrack(combination,next_digits):
            if len(next_digits) == 0:
                return output.append(combination)
            else:
                for letter in phone[next_digits[0]]:
                    backtrack(combination+letter,next_digits[1:])


        output = []
        if digits:
            backtrack('',digits)
        return output

java

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");
      \}\};

    List<String> output = new ArrayList<String>();

    private void backtrack(String combination, String next_digits) {
        if (next_digits.length() == 0){
            output.add(combination);
        }else {
            String digit = next_digits.substring(0, 1);
            String letters = phone.get(digit);
            for (int i = 0; i < letters.length(); i++) {
                String letter = phone.get(digit).substring(i, i + 1);
                backtrack(combination + letter, next_digits.substring(1));
            }

        }
    }

    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0)
          backtrack("", digits);
        return output;
    }
}

Read more

  • May 21, 2020
  • 0 views

风险管理

风险管理概述

  • 客观性：风险是客观存在的
  • 目的：降低负面风险，提升正面风险
  • 三要素：事件，概率，影响
  • 非事件类风险：
    • 变异风险：已规划事件，活动存在不确定性，导致变异性风险
    • 模糊性风险：对未来可能发生，存在不确定性。如知识不足造成，项目系统太复杂模糊不清，通过专家意见，最佳事件为标杆填补差距，也可以采用增量开发，原型搭建或模拟等方法来处理
  • 项目韧性：
    • 除了对已知风险列出风险预算，还要对突发性风险预算预留合理的应急预算和时间
    • 灵活的项目变更
    • 授权信赖的团队在商定时间内完成工作
    • 经常留意预警信号，以尽早识别突发性风险
    • 明确征求相关方的意见，以明确为应对突发性风险而可以调整项目范围或策略的领域

威胁应对策略

  • 上报：当项目经理觉得某威胁不在项目范围内，或超出权限，应采用上报
  • 规避：通常是改变目标或计划，使其概率下降为零，如，延长进度，改变策略，缩小范围
  • 转移：转交给第三方，这个时候涉及到钱
  • 减轻：减轻风险发生的影响，通常我们会，多招聘几个人，或者实习生
  • 接受：
    • 主动接受：这个策略是建立在应急储备，预留时间，资金和资源的基础上
    • 被动接受：只是定期对威胁进行审查，确保并未发生重大改变

机会应对策略

  • 上报：当项目经理觉得某威胁不在项目范围内，或超出权限，应采用上报
  • 开拓：将特定机会出现的概率提高到100%，比如：分配最有能力的资源非项目缩短时间，采用最小技术，或技术升级缩短时间
  • 分享：将相应的机会责任转移给第三方，使其想有机会带来的部分收益，让那些最有能力为项目抓住机会的人担任新的风险责任人，包括建立合伙关系，合作团队，特殊公司或合资企业来分享机会
  • 提高：提高机会出现的概率，如果无法提高概率，可针对其潜在收益规模的因素来提高发生机会的概率，包括为早日完成活动而增加的资源
  • 接受：
    • 主动接受：这个策略是建立在应急储备，预留时间，资金和资源的基础上
    • 被动接受：只是定期对威胁进行审查，确保并未发生重大改变

风险管理大概流程

  • 当接手的项目紧急，在不了解项目的情况下
    1. 可先从项目的背景出发，先了解项目的情况
    2. 通过头脑风暴等各种方式收集可能存在的风险
    3. 数据分析，包括 文件分析，假设条件和制约因素分析，根本原因分析
    4. 对以识别的风险，根据风险三要素，记录风险
    5. 确定风险优先级，及风险造成影响
    6. 规划风险应对，风险责任到人，根据上面的 威胁应对策略,机会应对策略
    7. 实施风险应对，并在整个过程中 监督风险，并定期审查风险

现象

  • 当你了解这些之后，你可以拒绝领导，拒绝客户，拒绝下属，方便你的管理
  • 很多公司在 风险记录和风险审查上做的不足，相应的会确实很多经验总结教训
  • 对于突发情况，没有足够的资源利用，比如人力资源，资金，或实物资源

Read more

  • May 20, 2020
  • 0 views
Search