xiaolei565

面试题56 - I. 数组中数字出现的次数(较难，未写完)输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。 示例 1：输入：nums = [2,7,11,15], target = 9输出：[2,7] 或者 [7,2] 示例 2：输入：nums = [10,26,30,31,47,60], target = 40输出：[10,30] 或者 [30,10] 限制：1 <= nums.length <= 10^51 <= nums[i] <= 10^6 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof 思路1：二分思路，由于是有序的，可以用二分，其他解释看代码注释 代码1：12345678910111213141516class Solution { public int[] twoSum(int[] nums, int target) { ...

面试题56 - I. 数组中数字出现的次数(较难，未写完)一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。 示例 1：输入：nums = [4,1,4,6]输出：[1,6] 或 [6,1] 示例 2：输入：nums = [1,2,10,4,1,4,3,3]输出：[2,10] 或 [10,2] 限制： 2 <= nums <= 10000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof 思路1：和leetcode260一样 直接set去重，如果有两个，则将第一个也进行删除，第二个不add 思路2：这里主要是数学的位运算 代码1：123456789101112class Solution { public int[] singleNumbers(int[] nums) { //哈希 ...

面试题55 - II. 平衡二叉树/110. 平衡二叉树(简单)输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 示例 1:给定二叉树 [3,9,20,null,null,15,7] 12345 3 / \9 20 / \ 15 7 返回 true 。 示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4] 1234567 1 / \ 2 2 / \ 3 3 / \4 4 返回 false 。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-lcof 思路1：递归思想，利用求深度的过程，进行判断即可 思路2：需要写非递归版本，请于200711补上 代码1：12345678910111213141516171819202122232425/** * Definition for a bi ...

面试题54. 二叉搜索树的第k大节点(简单)给定一棵二叉搜索树，请找出其中第k大的节点。 示例 1:输入: root = [3,1,4,null,2], k = 1 12345 3 / \1 4 \ 2 输出: 4 示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3 1234567 5 / \ 3 6 / \ 2 4 /1 输出: 4 限制：1 ≤ k ≤ 二叉搜索树元素个数 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof 思路：找第k大的，如果是中序遍历，则是递增，所以逆中序遍历即可 代码：12345678910111213141516171819202122232425262728/** * Definition for a binary tree node. * public class TreeNode
...

面试题53 - II. 0～n-1中缺失的数字(简单)一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。 示例 1:输入: [0,1,3]输出: 2 示例 2:输入: [0,1,2,3,4,5,6,7,9]输出: 8 限制：1 <= 数组长度 <= 10000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof 思路：二分查找的思路，将所有数分为左右两部分，左半部分，下标和值一样，右半部分，下标和值不一样，我们要找的就是右半部分的第一个数 算法解析： 初始化： 左边界i=0 ，右边界 j = len(nums) - 1；代表闭区间 [i,j] 。 循环二分： 当 i≤j 时循环 （即当闭区间 [i, j] 为空时跳出） ； 计算中点 m = (i + j) // 2，其中 “//“ 为向下取整除法； 若 nums[m] = m ，则 “右子数组的首位元素” ...

面试题53 - I. 在排序数组中查找数字 I(一般)统计一个数字在排序数组中出现的次数。 示例 1:输入: nums = [5,7,7,8,8,10], target = 8输出: 2 示例 2:输入: nums = [5,7,7,8,8,10], target = 6输出: 0 限制： 0 <= 数组长度 <= 50000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof 思路：二分查找的变体形式，利用两次二分找到第一次出现的下标和最后一次出现的下标，计算长度即可，注意练习二分查找变体的代码 代码1：12345678910111213141516171819202122232425262728class Solution { public int search(int[] nums, int target) { int low = 0; int high = nums.le ...

面试题51. 数组中的逆序对(困难)在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 示例 1:输入: [7,5,6,4]输出: 5 限制：0 <= 数组长度 <= 50000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof 思路：归并排序，需要了解归并排序解题模板 分治思想： 分两块，左右 分别计算，左边，右边 再计算横跨左右的 代码1：1234567891011121314151617181920212223242526272829303132333435363738class Solution { public int reversePairs(int[] nums) { // int[] assist = new int[nums.length]; return mergeSort(nums,0,nums ...

面试题50. 第一个只出现一次的字符(简单)在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 示例:s = “abaccdeff”返回 “b” s = “”返回 “ “ 限制： 0 <= s 的长度 <= 50000 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof 思路1：典型哈希思想，使用数组计数，然后遍历，数组中第一个等于1的数被输出 代码1：123456789101112131415class Solution { public char firstUniqChar(String s) { char[] c_str = s.toCharArray(); int[] count = new int[26]; for(char c:c_str){ count[c-'a']++; ...

面试题47. 礼物的最大价值(简单)在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？ 示例 1:输入: 12345[ [1,3,1], [1,5,1], [4,2,1]] 输出: 12解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 提示： 0 < grid.length <= 2000 < grid[0].length <= 200 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof 思路1：明显是dp，转移方程为$$d p(i, j)=\left{\begin{array}{ll}\operatorname{grid}(i, j) & , i=0, j=0 \\operatorname{grid}(i, j)+d p(i, j-1 ...

面试题46. 把数字翻译成字符串(简单)给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。 示例 1:输入: 12258输出: 5解释: 12258有5种不同的翻译，分别是"bccfi", "bwfi", "bczi", "mcfi"和"mzi" 提示：0 <= num < 231 来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/ba-shu-zi-fan-yi-cheng-zi-fu-chuan-lcof 思路：动态规划思路 dp[i]表示以数字num[i]结尾的翻译方案数 如果i和i-1位组合可以翻译的话，也就是在10到25之间的话，dp[i]=dp[i-1]+dp[i-2]; 如果不能翻译，则就是dp[i]=dp[i-1]; 由于单 ...