leetcode 30-Day LeetCoding Challenge Week1

概述

这一系列文章更新4周, 题目来自LeetCode一个30天挑战。第一周的难度集中在Easy, 主要是一些常规的编程思路, 一些基础的数据结构, 我将记录每一道题的解题思路, 以及其中涉及到的技术、技巧点。同时希望，各位看官不吝指教，共同进步。

题目地址

思路分析

Single Number

给定一个数组[1,1,2,3,3], n个元素中仅有1个元素出现1次, n-1个元素出现2次, 找出这个出现一次的元素?

思路1. 对原数组进行排序, 两两遍历, 当发生nums[i] != nums[i+1]时, 分别判定

1) 若nums[i-1] == nums[i], 则nums[i+1]
2) 若nums[i-1] != nums[i], 则nums[i]
需要注意的是, 对i=0与i=n-1时单独处理.
该方式时间复杂度为O(Nlog(N)) + O(N)

思路2. 这里利用到一个抑或操作xor, 由题干给出n-1个元素均出现两次, 结合xor开关的特点, 即1 xor 1 = 0, 1 xor 0 = 1。我们可以直接for-each进行xor运算最终的结果则为该单独数字
该方式时间复杂度为O(N)

总结.

1) 关注题干中的数字信息, 如x次
2) 注意处理数组的边界, 如头、尾
3) 将信息与逻辑知识相关联, 如(x次, xor) 进一步如mod

Happy Number

给定一个整数, 判定该整数是否为HappyNumber. 对该数字进行多轮迭代, num' = sum(各位平方和), 若num'=1，则为HappyNumber, 若成环则返回false
Input: 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

思路1. 仅有一点需要注意, 对于HappyNumber进行朴素的循环即可. 对于非HappyNumber, 需要利用HashSet进行成环判定, 让循环退出。
该方法时间复杂度>.< 不会算:-(

总结.

1) HashSet/HashMap的使用场景。
2) 时间复杂度的分析 cue作者！

Maximum Subarray

给定一个数组, 返回一个连续子数组, 使得该连续子数组和最大。

思路1. 连续子数组的定义为subarray[i,j]当0 <= i < j <= n-1时, 计算[i,j]区间内的累加和。因此我们可以相对容易的写出O(N^2)的解。
该方式时间复杂度为O(N^2)

思路2. 给定数组, 数组中的所有递增的子数组，必定是不相交的, 即sub[i, j] 与 sub[p, q], 必然i < j < p < q否则将可以构成一个sub[i, q]的递增子数组。因此我们如何找到每一段这样的连续递增子数组呢。令num[j]为当前待处理元素，cur_max=j-1之前的最大值。那么对于num[j]而言, 若加上cur_max为正, 则吸入, 否则cur_max=nums[j]。写成表达式为cur_max = cur_max > 0 ? nums[j] + cur_max : nums[j]。这里强调一下, cur_max是包含num[j]后的最大值, 也就意味着是吸入num[j]，还是以num[j]为起点重新开始。
该方式时间复杂度为O(N)

PS：这里的连续递增子数组, 本质上为连续累加和递增

总结.

1) 对于思路2, 一般而言，是考虑1个元素, 考虑2个元素, 进而考虑n个元素, 结合题干发现其中的规律。

Move Zeroes

给定数组, 保证非零元素序不变的情况下, 将0放置在数组末端, 如[0,1,0,3,12]-> [1,3,12,0,0]

思路1. 一般的暴力思路, 就是类似冒泡的那种, 只要发现了0, 就将num[i]与num[i+1, n-1]进行交换。
该方法时间复杂度为O(N^2)

思路2. 我们通过观察可以发现, 如果我们是覆写操作, 只需要按顺序将非零的元素, 提前即可，并在最后补零。这里将使用第一个技巧双指针，即维护一个遍历数组元素的指针i, 再维护一个下一个可用位置的指针j。i每次加一，j只有当非零时加一。最后将[j, i]间的元素, 全部补0即可。
该方法时间复杂度为O(N)

PS：这个题在实际生产环境中是一个优化点, 即给定列表L，删除指定元素, 要求原地删除。好处为, 降低runtime期间的内存malloc开销

总结.

1) 对于思路2, 第一，需要打破通过交换这个常规概念；第二，需要考虑数据自身的特点。