总结:
本周完成11道习题, Link: https://github.com/speng975/LeetCode/tree/master/cpp
排序完成3道题:
leetcode 242: https://leetcode-cn.com/problems/valid-anagram/
题目:给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的一个字母异位词。
解法:通过开辟两个26字节大小的数组,分别存'a'--'z'对应字符的个数,最后比较数组存放字符及其个数,完全相等则返回TRUE。
leetcode 324:https://leetcode-cn.com/problems/wiggle-sort-ii/
题目:给定一个无序的数组 nums,将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
解法: 申请一个和nums一样的临时数组tmp,对数组tmp进行排序,找到中间位置,遍历数组nums,奇数位填入中间数,偶数位填入末尾数,指针向左移动。
leetcode 164:https://leetcode-cn.com/problems/maximum-gap/
题目:给定一个无序的数组,找出数组在排序之后,相邻元素之间最大的差值。如果数组元素个数小于 2,则返回 0。
解法:对数组进行排序,申请一个临时变量存当前遍历到的最大值,比较数组相邻元素,计算差值,决策是否更新最大值。
二分查找完成1题:
leetcode 441: https://leetcode-cn.com/problems/arranging-coins/
题目: 你总共有 n 枚硬币,你需要将它们摆成一个阶梯形状,第 k 行就必须正好有 k 枚硬币。给定一个数字 n,找出可形成完整阶梯行的总行数。
n 是一个非负整数,并且在32位有符号整型的范围内。
解法: 循环n-=k, k++, 最后计算出来就是总行数。
栈完成1题:
leetcode 20: https://leetcode-cn.com/problems/valid-parentheses/
题目:给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
解法:
- “左” 压栈
- “右” 在栈顶查找匹配的括号, 如果找到弹出栈顶字符,否则返回false
- 最终"栈" 为空, 返回true, "栈" 非空, 返回false
注意,对于第一次输入是')','}'或者']'的情况,一定要判断堆栈是否为空,否则会数组越界。
数组完成4道题:
leetcode 905: https://leetcode-cn.com/problems/sort-array-by-parity/
题目: 给定一个非负整数数组 A,返回一个由 A 的所有偶数元素组成的数组,后面跟 A 的所有奇数元素。
解法:前后指针。
leetcode 922: https://leetcode-cn.com/problems/sort-array-by-parity-ii/
题目: 给定一个非负整数数组 A,返回一个由 A 的所有偶数元素组成的数组,后面跟 A 的所有奇数元素。
解法:另外申请数组,偶数位存偶数,奇数位存奇数。
leetcode 81: https://leetcode-cn.com/problems/search-in-rotated-sorted-array-ii/
题目: 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。
解法:排序后再二分查找。
leetcode 153: https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array/
题目: 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。
请找出其中最小的元素。
你可以假设数组中不存在重复元素。。
解法:前后指针,注意边界条件。
链表2题:
leetcode 83: https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/
题目:给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
解法:两个指针,循环遍历,相同指针则移动指针跳过。
leetcode 24: https://leetcode-cn.com/problems/swap-nodes-in-pairs/
题目:给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
解法:第一个结点指向第三个结点,第二个结点指向第一个,递归调用。