- 此文用来记录自己在leetcode上的simple题集解决方案。
-
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
-
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
-
思路：两个for循环暴力
int* twoSum(int* nums, int numsSize, int target) {
static int a[2]={0};
for (int i = 0; i < numsSize - 1; i++)
{
for (int j = i+1; j < numsSize; j++)
{
if (nums[i] + nums[j] == target)
{
a[0] = i;
a[1] = j;
return a;
}
}
}
return 0;
}
-
题目描述
- 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
输入: 123 输出: 321
输入: -123 输出: -321
输入: 120 输出: 21
- 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
-
通过循环将数字x的每一位拆开，在计算新值时每一步都判断是否溢出。
-
溢出条件有两个，**一个是大于整数最大值MAX_VALUE，另一个是小于整数最小值MIN_VALUE，**设当前计算结果为ans，下一位为pop。
-
从ans * 10 + pop > MAX_VALUE这个溢出条件来看: 当出现 ans > MAX_VALUE / 10 且 还有pop需要添加 时，则一定溢出; 当出现 ans == MAX_VALUE / 10 且 pop > 7 时，则一定溢出，7是2^31 - 1的个位数;
不知道最后一位是7可以这样思考：
pop > Integer.MAX_VALUE%10 -
从ans * 10 + pop < MIN_VALUE这个溢出条件来看: 当出现 ans < MIN_VALUE / 10 且 还有pop需要添加 时，则一定溢出 当出现 ans == MIN_VALUE / 10 且 pop < -8 时，则一定溢出，8是-2^31的个位数
-
不知道最后一位是-8可以这样思考：
pop < Integer.MIN_VALUE%10
-
class Solution {
public int reverse(int x) {
int res = 0;
while(x!=0){
int pop = x%10;
if(res > Integer.MAX_VALUE/10 || (res==Integer.MAX_VALUE/10 && pop > Integer.MAX_VALUE%10))
return 0;
if(res < Integer.MIN_VALUE/10 || (res==Integer.MIN_VALUE/10 && pop < Integer.MIN_VALUE%10))
return 0;
res = res*10 + pop;
x /=10;
}
return res;
}
}- 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1: 输入: 121 输出: true
示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。
-
进阶:
你能不将整数转为字符串来解决这个问题吗？
-
代码如下：
class Solution {
public boolean isPalindrome(int x) {
int sum = 0;
int temp = x;
if(x<0){
return false;
}
if(x==0){
return true;
}
else{
while(x!=0){
int a = x%10;
sum = sum *10 + a;
x/=10;
}
return sum==temp;
}
}
}- 罗马数字包含以下七种字符:
I，V，X，L，C，D和M。
字符 数值 I 1 V 5 X 10 L 50 C 100 D 500 M 1000
-
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II
-
通常情况下，罗马数字中小的数字在大的数字的右边。但也
-
存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
- I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
- X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
- C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
-
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III" 输出: 3 示例 2:
输入: "IV" 输出: 4 示例 3:
输入: "IX" 输出: 9 示例 4:
输入: "LVIII" 输出: 58 解释: L = 50, V= 5, III = 3. 示例 5:
输入: "MCMXCIV" 输出: 1994 解释: M = 1000, CM = 900, XC = 90, IV = 4.
-
思路：
- 从一开始判断num（后面的）是否比prenum（前面的）小，如果小，证明要加prenum。
- 如果大，则要减去prenum，num和prenum移动位置。一直到最后一个数。
- 最后的prenum肯定要加上。
-
代码：
class Solution {
public int romanToInt(String s) {
int sum = 0;
int prenum = Solution.getValue(s.charAt(0));
for(int i=1; i<s.length(); i++){
int num = Solution.getValue(s.charAt(i));
if(num < prenum || num == prenum){
sum += prenum;
}
else{
sum -= prenum;
}
prenum = num;
}
sum = sum + prenum;
return sum;
}
public static int getValue(char a){
switch(a) {
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
default: return 0;
}
}
}- 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串
""。
示例 1:
输入: ["flower","flow","flight"] 输出: "fl" 示例 2:
输入: ["dog","racecar","car"] 输出: "" 解释: 输入不存在公共前缀。
-
说明: 所有输入只包含小写字母
a-z。 -
自己的思路，有点麻烦，最终结果是：
执行用时 :1 ms, 在所有 java 提交中击败了93.91%的用户
内存消耗 :37.8 MB, 在所有 java 提交中击败了71.58%的用户
- 记录一下自己的思路：
- 首先排除一些最容易想到的特例：
- 如果没有字符串，则返回空；
- 如果只有一个字符串，则返回第一个字符串；
- 遍历所有的字符串，找出最短的字符串，首先设定strs[0]是最短的，再往下依次取代；
- 遍历过程中，若发现有一个空串，则返回空；
- 找到最短字符串之后，将其余的串一个字符一个字符与之比较，找一个最短的长度。
- 一开始设定min_num很大，如果找不到j来代替这个值，说明字符串都相等。
- 最后一步就是根据上述两种情况进行截取。
- 代码：
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0){
return "";
}
if(strs.length == 1){
return strs[0];
}
int min_length = strs[0].length();
int flag = 0;//标记最短串的位置
int min_num = Integer.MAX_VALUE; //记录最短的相同串的长度
//循环遍历出最短字符串
for(int i=0; i<strs.length; i++){
if(strs[i].length()==0){
return "";
}
if(strs[i].length() < min_length){
min_length = strs[i].length();
flag = i;
}
else{
continue;
}
}
//对每个字符串与strs[flag]相比较
for(int i=0; i<strs.length; i++){
if(flag==i){
continue;
}
for(int j=0;j<min_length;j++){
if(strs[flag].charAt(j)!=strs[i].charAt(j)){
if(j<min_num){
min_num = j;
}
}
}
}
if(min_num != Integer.MAX_VALUE){
return strs[flag].substring(0,min_num);
}else{
return strs[flag];
}
}
}- 官方题解：
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}- 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
- 有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
示例 1:
输入: "()" 输出: true 示例 2:
输入: "()[]{}" 输出: true 示例 3:
输入: "(]" 输出: false 示例 4:
输入: "([)]" 输出: false 示例 5:
输入: "{[]}" 输出: true
- 思路记录：栈的典型应用
- 首先要把对应的括号进行匹配，python可用字典，java这里用的是hashmap。
- 从开始遍历字符串，将字符串转换为字符数组，对每个字符进行判断：
- 若为左边的起始括号，例如"("、"["、"{"，直接push进栈；
- 若为右边的结束括号，则要进行判断，若栈为空，则直接返回false，因为栈里面没有与之匹配的元素了
- 若栈不空，但是取出top元素，不与对应的map中的值对应，则不匹配，返回false；
- 注意上面一步，已经取出了栈顶元素，匹配则返回true，不匹配则返回false，所以在遍历完：
- 有两种情况：1.偶数，遍历完且匹配成功，栈空；2.奇数，栈不空，但是有不匹配的；
- 所以此时返回stack.isEmpty();对应上面的两种情况。
- 代码：
class Solution {
public boolean isValid(String s) {
int len = s.length();
if(len == 0){
return true;
}
//HashMap 键值对
HashMap<Character,Character> map = new HashMap();
map.put(')','(');
map.put(']','[');
map.put('}','{');
Stack<Character> stack = new Stack();
for(char ch: s.toCharArray()){
if(ch=='('||ch=='['||ch=='{'){
stack.push(ch);
}
if((ch==')'||ch==']'||ch=='}') &&(stack.isEmpty() || stack.pop()!=map.get(ch))){
return false;
}
}
return stack.isEmpty();
}
}- 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4
- 思路解析：
- 创建了一个新的结点，根据比较两个链表元素的大小进行插入到新的结点之后。
- 谁小谁就链接到后面，且新建的p结点和l1、l2结点的指针都向后移动。
- 如果有一条链表到头了，那就将新的p结点指针指向没空的另一条链表剩余元素。
- 代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode p = new ListNode(0);
ListNode head = p;//存下来p的位置，后面要移动
while(l1!=null && l2!=null){
if(l1.val<=l2.val){
p.next = l1;
p = p.next;
l1 = l1.next;
}else{
p.next = l2;
p = p.next;
l2 = l2.next;
}
}
if(l1==null){
p.next = l2;
}else{
p.next = l1;
}
return head.next;
}
}- 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。不要使用额外的数组空间，你必须在原地修改输入数组并在使用 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。
你不需要考虑数组中超出新长度后面的元素。
- 思路分析：
- 两个指针i和j，从头开始遍历，j首先固定不变，i在变化，直到找到不相等的元素；
- 因为已经是排好序的数组，所以肯定相等的元素都相邻；
- 找到不相等的元素，使i对应的该元素赋值到之前的相等的某个元素上，那个元素就是相等的第2个。
- 例如：1，1，2就将2赋给第二个1。1，1，1，2就将2赋给第二个1。
- 最后j的位置就在不重复的倒数第二个位置，所以返回j+1。
- 代码：
class Solution {
public int removeDuplicates(int[] nums) {
int j=0;
for(int i=0; i<nums.length; i++){
if(nums[i] != nums[j]){
j = j+1;
nums[j] = nums[i];
}
}
return j+1;
}
}- 给定一个数组 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，每次取出的数字变量为num，同时设置一个下标ans
- 在遍历过程中如果出现数字与需要移除的值不相同时，则进行拷贝覆盖nums[ans] = num，ans自增1
- 如果相同的时候，则跳过该数字不进行拷贝覆盖，最后ans即为新的数组长度
- 这种思路在移除元素较多时更适合使用，最极端的情况是全部元素都需要移除，遍历一遍结束
-
代码
class Solution {
public int removeElement(int[] nums, int val) {
int loc = 0;
for(int num: nums){
if(num!= val){
nums[loc] = num;
loc++;
}
}
return loc;
}
}- 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
- 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5 输出: 2 示例 2:
输入: [1,3,5,6], 2 输出: 1 示例 3:
输入: [1,3,5,6], 7 输出: 4 示例 4:
输入: [1,3,5,6], 0 输出: 0
- 思路：
- 首先排除两个边界，对极限情况进行考虑
- 其次考虑中间有大于等于，就返回该索引位置
- 代码如下：
class Solution {
public int searchInsert(int[] nums, int target) {
int loc = 0;
if(nums[0]>target){
return 0;
}
if(nums[nums.length-1]<target){
return nums.length;
}
for(int i=0; i< nums.length; i++){
if(nums[i] >= target){
loc = i;
break;
}
}
return loc;
}
}- 报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1
11
21
1211
111221
1 被读作 "one 1" ("一个一") , 即 11。 11 被读作 "two 1s" ("两个一"）, 即 21。 21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
注意：整数顺序将表示为一个字符串。
示例 1:
输入: 1 输出: "1"
示例 2:
输入: 4 输出: "1211"
- 解题思路
- 函数从str='1'开始向后求
- 使用两个循环，外层循环控制求到第几个数，内存循环求该数
- 函数中取pre和j两个元素，相当于使用两个指针来判断前面的和后面相邻的是否相等
- 相等则计数++，计算出有多少该元素，添加count+字符
- 若不相等，则直接添加1+该字符，并且挪动pre至后方元素，j也随之挪动，count恢复为1
- 外层每次结束一次循环，求得第n个数
- 代码
class Solution {
public String countAndSay(int n) {
String str = "1";
for (int i = 2; i <= n; i++) {
StringBuilder builder = new StringBuilder();
char pre = str.charAt(0);
int count = 1;
for (int j = 1; j < str.length(); j++) {
char c = str.charAt(j);
if (c == pre) {
count++;
} else {
builder.append(count).append(pre);
pre = c;
count = 1;
}
}
builder.append(count).append(pre);
str = builder.toString();
}
return str;
}
}-
给定整数数组
nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:
输入: [-2,1,-3,4,-1,2,1,-5,4], 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
-
解题思路：
- 定义一个局部临时sum，初始赋值为0，用来存储当前的局部子序和
- 定义结果res，初始赋值为nums[0]
- 因为数组中有正负数，所以要去判断临时sum的大小
- 若sum>0，说明无论后面的数正负，都要加该数
- 但是如果当前sum<0，就要舍弃sum，因为会减小后面继续加和。
- 舍弃sum，就要将当前的sum赋值循环中的num，继续从此数开始加和
-
代码
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int sum = 0;
for(int num: nums){
if(sum>0){
sum += num;
}else{
sum = num;
}
res = Math.max(res, sum);
}
return res;
}
}- 给定一个仅包含大小写字母和空格 ' ' 的字符串，返回其最后一个单词的长度。
- 如果不存在最后一个单词，请返回 0 。
- 说明：一个单词是指由字母组成，但不包含任何空格的字符串。
示例:
输入: "Hello World" 输出: 5
-
解法一思路：
- 从字符串末尾开始向前遍历，其中主要有两种情况：
- 第一种情况，以字符串"Hello World"为例，从后向前遍历直到遍历到头或者遇到空格为止，即为最后一个单词"World"的长度5；
- 第二种情况，以字符串"Hello World "为例，需要先将末尾的空格过滤掉，再进行第一种情况的操作，即认为最后一个单词为"World"，长度为5；
- 所以完整过程为先从后过滤掉空格找到单词尾部，再从尾部向前遍历，找到单词头部，最后两者相减，即为单词的长度。
- 时间复杂度：O(n)，n为结尾空格和结尾单词总体长度。
-
代码：
class Solution {
public int lengthOfLastWord(String s) {
int end = s.length() - 1;
while(end >= 0 && s.charAt(end) == ' ') end--;
if(end < 0) return 0;
int start = end;
while(start >= 0 && s.charAt(start) != ' ') start--;
return end - start;
}
}- 解法二：
- 首先使用
strim函数去除首尾空格 - 再使用Java的寻找最后一个空格位置函数，末尾-空格位置即单词长度
- 首先使用
- 代码：
class Solution {
public int lengthOfLastWord(String s) {
//空串
s=s.trim();
if(s.length()==0){
return 0;
}
int lastEmptyIndex =s.lastIndexOf(" ");
return s.length()-1-lastEmptyIndex;
}
}- 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
- 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
- 你可以假设除了整数 0 之外，这个整数不会以零开头。
示例 1:
输入: [1,2,3] 输出: [1,2,4] 解释: 输入数组表示数字 123。 示例 2:
输入: [4,3,2,1] 输出: [4,3,2,2] 解释: 输入数组表示数字 4321。
- 思路：
- 首先要判断末尾是不是9，若为9，则变为0，在此情况后还需考虑后面数字是否为9，以便连续进位。
- 若不是9，直接将末尾加1，返回该数组。
- 若产生进位，则要根据是否如99，999该数一样会多一位，返回新的数组，首尾直接置为1，其余为0.
- 代码：
class Solution {
public int[] plusOne(int[] digits) {
for(int i=digits.length-1;i>=0;i--){
if(digits[i]==9){//此位为9，需要进位
digits[i]=0;
continue;
}
if(digits[i]!=9){
digits[i]+=1;
break;
}
}
int[] ans=new int[digits.length+1];# int数组默认为0
ans[0]=1;
if(digits[0]==0)return ans;
else return digits;
}
}- 给定两个二进制字符串，返回他们的和（用二进制表示）。
- 输入为非空字符串且只包含数字
1和0。
示例 1:
输入: a = "11", b = "1" 输出: "100" 示例 2:
输入: a = "1010", b = "1011" 输出: "10101"
-
思路
- 利用enumerate枚举方法可以得到索引和数字，算出结果
- 相加求和
- 再求出二进制数
-
代码
class Solution:
def addBinary(self, a: str, b: str) -> str:
if a==b=='0':
return "0"
num1 = num2 = 0;
# enumerate方法返回索引+数字的二元组
for i,x in enumerate(a):
num1 += int(x)*(2**(len(a)-i-1))
for i,x in enumerate(b):
num2 += int(x)*(2**(len(b)-i-1))
num = num1 + num2
res = ''
while num > 1:
num_temp = num%2
res += str(num_temp)
num = num//2
res+='1'
return res[::-1] # 倒序遍历字符串- 实现 int sqrt(int x) 函数。
- 计算并返回 x 的平方根，其中 x 是非负整数。
- 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
示例 1:
输入: 4 输出: 2 示例 2:
输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
- 解题思路：
- 采用二分法无限逼近正确值
- 当max和min差1以上的情况下，m为中值
- 根据x/m大于m还是小于等于m，来挪动指针max和min
- 代码：
class Solution {
public int mySqrt(int x) {
if(x==0||x==1){
return x;
}
int min = 0;
int max = x;
while(max - min >1){
int m = (min+max)/2;
if(x/m<m){
max = m; //x/m比m小，说明除的m大了点，去左半部分逼近m
}else{
min = m;//x/m比m大,或者等于m，说明除的m小了点，去右半部分继续逼近m
}
}
return min;
}
}-
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
-
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
-
**注意：**给定 n 是一个正整数。
示例 1：
输入： 2 输出： 2 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶 示例 2：
输入： 3 输出： 3 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
-
思路：
- 此题可以采用动态规划的思想，将大问题分为子问题，爬第n阶楼梯的方法数量，等于 2 部分之和：
-
- 爬上 n-1阶楼梯的方法数量。因为再爬1阶就能到第n阶
-
- 爬上 n-2 阶楼梯的方法数量，因为再爬2阶就能到第n阶
- 所以我们得到公式
$dp[n] = dp[n-1] + dp[n-2]$ - 同时需要初始化
$dp[1]=1 和 dp[2]=2$ - 时间复杂度：$O(n)$
-
代码：
class Solution {
public int climbStairs(int n) {
int[] dp = new int[n + 2];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}- 注：使用递归，反馈超时
-
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
示例 1:
输入: 1->1->2 输出: 1->2 示例 2:
输入: 1->1->2->3->3 输出: 1->2->3
-
代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode *p = head;
ListNode *q;
while(p!=NULL&&p->next!=NULL)
{
if(p->val==p->next->val)
{
q=p->next;
p->next =q ->next;
delete q;
}
else
{
p = p->next;
}
}
return head;
}
};-
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
-
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
-
示例:
-
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
-
思路
- 从后向前数组遍历
- 因为 nums1 的空间都集中在后面，所以从后向前处理排序的数据会更好，节省空间，一边遍历一边将值填充进去
- 设置指针 len1 和 len2 分别指向 nums1 和 nums2 的有数字尾部，从尾部值开始比较遍历，同时设置指针 len 指向 nums1 的最末尾，每次遍历比较值大小之后，则进行填充
- 当 len1<0 时遍历结束，此时 nums2 中海油数据未拷贝完全，将其直接拷贝到 nums1 的前面，最后得到结果数组
- 时间复杂度：O(m+n)
-
代码
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int len1 = m - 1;
int len2 = n - 1;
int len = m + n - 1;
while(len1 >= 0 && len2 >= 0) {
// 注意--符号在后面，表示先进行计算再减1，这种缩写缩短了代码
nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
}
// 表示将nums2数组从下标0位置开始，拷贝到nums1数组中，从下标0位置开始，长度为len2+1
System.arraycopy(nums2, 0, nums1, 0, len2 + 1);
}
}- 给定两个二叉树，编写一个函数来检验它们是否相同。
- 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1:
输入: 1 1 / \ / \ 2 3 2 3 [1,2,3], [1,2,3] 输出: true示例 2:
输入: 1 1 / \ 2 2 [1,2], [1,null,2] 输出: false示例 3:
输入: 1 1 / \ / \ 2 1 1 2 [1,2,1], [1,1,2] 输出: false
- 思路：
- 判断根节点的情况
- 递归
- 代码：
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
# p,q 都为none
if not p and not q:
return True
# 一个为none
if not p or not q:
return False
# 都不为none
if p and q:
if p.val == q.val:
# 递归判断子树
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
else:
return False- 给定一个二叉树，检查它是否是镜像对称的。
- 例如，二叉树
[1,2,2,3,4,4,3]是对称的。
1 / \ 2 2 / \ / \ 3 4 4 3
- 但是下面这个
[1,2,2,null,3,null,3]则不是镜像对称的:
1 / \ 2 2 \ \ 3 3
- 思路：单独写一个函数去递归，也可在原函数中递归
- 代码：
class Solution:
def dfs(self, left: TreeNode, right: TreeNode):
if (left == None and right == None):
return True
if (left == None or right == None):
return False
if left.val!=right.val:
return False
return self.dfs(left.left,right.right) and self.dfs(left.right,right.left)
def isSymmetric(self, root: TreeNode) -> bool:
if not root:
return True
return self.dfs(root.left, root.right)- 给定一个二叉树，返回其节点值自底向上的层次遍历。
- 即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历
- 例如：给定二叉树
[3,9,20,null,null,15,7]
3 / \ 9 20 / \ 15 7
- 返回其自底向上的层次遍历为：
[ [15,7], [9,20], [3] ]
-
由于本题的输出格式，使用到了list的append、extend、insert函数
-
思路：从顶端遍历，存放结果时每次都insert到最顶端的位置，即index=0
-
代码
class Solution:
def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
queue = [] # 结果列表
cur = [root] # 接下来要循环的当前层节点，存的是节点
while cur: # 当前层存在结点时
cur_layer_val = [] # 初始化当前层结果列表为空，存的是val
next_layer_node = [] # 初始化下一层结点列表为空
for node in cur: # 遍历当前层的每一个结点
if node: # 如果该结点不为空，则进行记录
cur_layer_val.append(node.val) # 将该结点的值加入当前层结果列表的末尾
next_layer_node.extend([node.left, node.right])
# 将该结点的左右孩子结点加入到下一层结点列表
if cur_layer_val: # 只要当前层结果列表不为空
queue.insert(0, cur_layer_val) # 则把当前层结果列表插入到队列首端
cur = next_layer_node # 下一层的结点变成当前层，接着循环
return queue - 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
- 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
- 思路
- 平衡二叉搜索树需要保证俩点：
- 根节点大于左子树任意节点，小于右子树任意节点
- 左右子数高度相差不超过 1
- 由以上性质，一个可行的递归条件可以得出：
- 每次返回的根节点处于数组中间，以其左右半数组分别递归构造左右子树
- 那么就意味着左子小于根，右子大于根，且所有节点左右子树节点数相差不超过 1 （由于递归的构树方式相同，所有节点都满足高度平衡）
- 平衡二叉搜索树需要保证俩点：
- 代码
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if nums:
loc = len(nums) // 2 # 返回整数
root = TreeNode(nums[loc])
root.left = self.sortedArrayToBST(nums[:loc])
root.right = self.sortedArrayToBST(nums[loc+1:])
return root- 给定一个二叉树，判断它是否是高度平衡的二叉树。
- 本题中，一棵高度平衡二叉树定义为：
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
-
构造一个获取当前节点最大深度的方法
depth(root)，通过比较此子树的左右子树的最大高度差abs(depth(root.left) - depth(root.right))，来判断此子树是否是二叉平衡树。若树的所有子树都平衡时，此树才平衡。 -
代码
class Solution:
def isBalanced(self, root: TreeNode) -> bool:
if not root: return True
return abs(self.depth(root.left) - self.depth(root.right)) <= 1 and \
self.isBalanced(root.left) and self.isBalanced(root.right)
def depth(self, root):
if not root: return 0
return max(self.depth(root.left), self.depth(root.right)) + 1