剑指Offer简单题
03. 数组中重复的数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
解题思路：注意题目描述：一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的 范围 内，这个 范围 恰好与数组的下标可以一一对应。
所以我们可以执行某种操作，使索引与值一一对应，即索引 0 的值为 0，索引 1 的值为 1。而一旦某个索引的值不只一个，则找到了重复的数字，也即发生了哈希冲突。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
public int findRepeatNumber(int[] nums){ int i = 0; while(i<nums.length){ if (nums[i] == i){ i++; continue; } if (nums[nums[i]]==nums[i]) return nums[i]; int temp = nums[i]; nums[i] = nums[temp]; nums[temp] = temp; } return -1; } class Solution { public int findRepeatNumber(int[] nums) { //设索引初始值为 i = 0 int i = 0; //遍历整个数组 nums while(i < nums.length) { //索引 i 的值为 i,无需执行交换操作，查看下一位 if(nums[i] == i) { i++; continue; } //索引 nums[i] 处的值也为 nums[i]，即找到一组相同值，返回 nums[i] 即可 if(nums[nums[i]] == nums[i]) return nums[i]; //执行交换操作，目的是为了使索引与值一一对应，即索引 0 的值为 0，索引 1 的值为 1 int tmp = nums[i]; nums[i] = nums[tmp]; nums[tmp] = tmp; } //如果遍历整个数组都没有找到相同的值，返回 -1 return -1; } } |
05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
return s.replace(" ","%20"); //一步到位 public String replaceSpace(String s){ StringBuilder str = new StringBuilder(); for (int i = 0;i<s.length();i++){ char c = s.charAt(i); if (c==' '){ str.append("%20"); }else { str.append(c); } } return str.toString(); } |
06. 从尾到头打印链表
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
这道题目的输入是一个链表，输出是一个数组。
链表具有的特点：
事先链表的长度是不知道的，也就是说事先你是不知道链表中存在多少节点的
链表只能从头节点开始往后遍历，而不能从非头节点往前遍历
数组具有的特点：
数组初始化的时候就必须指定长度
我们不仅可以从数组的第一个元素往后遍历访问数组，而且也可以从最后一个元素往前遍历数组
所以，我们要返回一个数组，首先需要计算出这个数组的长度，实际上数组的长度就等于链表的节点的个数，那么问题就变成了求链表的节点个数了，我们可以这样求解：
先初始化一个整形变量 length
从链表的头节点往后遍历，每遇到一个节点，那么 length 就自加 1，一直到链表的空节点为止
得到了数组的长度后，我们就可以初始化一个结果数组，然后再次从链表的头节点开始往后遍历，每遇到一个节点，那么就将节点的值放到数组的后端 (这里利用了数组可以从最后一个元素往前访问的特点)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } **/ public class Solution06 { public static class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public static void main(String[] args) { ListNode listNode = new ListNode(1); listNode.next = new ListNode(3); listNode.next.next = new ListNode(2); Solution06 solution06 = new Solution06(); System.out.println(solution06.reversePrint(listNode)); } public int[] reversePrint(ListNode head){ if (head == null){ return new int[]{}; } int length = 0; ListNode curr = head; while (curr!=null){ length++; curr = curr.next; } int[] res = new int[length]; int i = length - 1; curr = head; while (curr!=null){ res[i] = curr.val; i--; curr = curr.next; } return res; } } |
这道题需要解决的问题本质上就是将链表倒序了，而由于链表只能从头节点往后遍历，所以我们可以借助栈来完成链表的倒序排列过程。
栈的特点是：后进先出，即最后压入的元素最先弹出。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
public int[] reversePrint(ListNode head){ Stack<ListNode> stack = new Stack<>(); ListNode curr = head; while (curr.next!=null){ stack.push(curr); curr = curr.next; } int[] res = new int[stack.size()]; int i = 0; while (!stack.isEmpty()){ res[i] = stack.pop().val; i++; } return res; } |
09. 用两个栈实现队列
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
栈是一种先进后出的数据结构，队列却是一种先进先出的数据结构。
题目要求我们使用两个栈来实现一个队列，首先一点我们可以确定的是一开始往队列中 append 的数据肯定是存储在一个栈中的。
也就是说先 append 的数据都是存储在栈的栈底，换句话说，队头的元素一开始肯定是存储在一个栈中的栈底
如果我们现在想删除队头的元素的话，也就是说我们要删除的是一个栈底的元素，肯定是直接删除不到的
因为我们有两个栈，所以我们可以将 append 进来的数据从栈中 pop 出来，然后 push 到另一个栈中，这样之前栈底的元素就变为另一个栈顶的元素了，然后 pop 掉栈顶元素就可以了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */ private Stack<Integer> stack1; private Stack<Integer> stack2; public CQueue(){ this.stack1 = new Stack<>(); this.stack2 = new Stack<>(); } public void appendTail(int value){ while (!stack2.isEmpty()){ stack1.push(stack2.pop()); } stack1.push(value); } public int deleteHead(){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } if (stack2.isEmpty()){ return -1; } return stack2.pop(); } |
- ### 斐波那契数列-Ⅰ
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2
输出：1
首先，我们用回溯的思想来考虑这个问题
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public int fib(int n) { return dfs(n); } // 时间复杂度：O(2^n) private int dfs(int n) { if (n == 0) return 0; if (n == 1) return 1; int leftFib = dfs(n - 1); int rightFib = dfs(n - 2); return leftFib + rightFib; } |
接下来我们使用记忆化搜索，消除重复解
可以用数组的方式存重复解，也可以用map，但是map消耗的存储空间比较大。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
public int fib(int n) { int[] memo = new int[n + 1]; Arrays.fill(memo, -1); return dfs(n, memo); } // 时间复杂度：O(n) private int dfs(int n, int[] memo) { if (n == 0) return 0; if (n == 1) return 1; if (memo[n] != -1) { return memo[n]; } int leftFib = dfs(n - 1, memo); int rightFib = dfs(n - 2, memo); memo[n] = leftFib + rightFib; return leftFib + rightFib; } |
最后的话，采用自底而上的思路，也就是动态规划的思路
难点：状态数组和状态转移方程的定义
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
// 动态规划的四个步骤 public int fib(int n) { if (n <= 1) return n; // 1. 定义状态数组，dp[i] 表示的是数字 i 的斐波那契数 int[] dp = new int[n + 1]; // 2. 状态初始化 dp[0] = 0; dp[1] = 1; // 3. 状态转移 for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } // 4. 返回最终需要的状态值 return dp[n]; } |
本题解答：计算中取模和结果取模答案一样，但是计算中取模不会超过内存限制
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { public int fib(int n) { if(n<=1) return n; int[] dp = new int[n+1]; dp[0] = 0; dp[1] = 1; for(int i=2;i<=n;i++){ dp[i] = (dp[i-1] + dp[i-2])%1000000007; } return dp[n]; } } |
- ### 斐波那契数列-Ⅱ
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 7
输出：21
当n等于1的时候，只需要跳一次即可，只有一种跳法，记f(1)=1
当n等于2的时候，可以先跳一级再跳一级，或者直接跳二级，共有2种跳法，记f(2)=2
当n等于3的时候，他可以从一级台阶上跳两步上来，也可以从二级台阶上跳一步上来，所以总共有f(3)=f(2)+f(1)；
同理当等于n的时候，总共有f(n)=f(n-1)+f(n-2)(这里n>2)种跳法。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
class Solution { public int numWays(int n) { if(n<=1) return 1; int[] dp = new int[n+1]; dp[1]=1; dp[2]=2; for(int i=3;i<=n;i++){ dp[i] = (dp[i-1] + dp[i-2])%1000000007; } return dp[n]; } } |
- ### 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
示例 1：
输入：[3,4,5,1,2]
输出：1
暴力法：初始化两个指针，向后移动，直到右指针比左指针小
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public int minArray(int[] numbers) { for (int i = 1;i < numbers.length;i++){ if (numbers[i]<numbers[i-1]){ return numbers[i]; } } return numbers[0]; } } |
二分查找：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
/** * 剑指 offer 第 11 题 * 在原来的题目之上，假设数组中的元素可以重复 * 可以使用二分查找 * 时间复杂度是： O(logn) * 空间复杂度是：O(1) * @param nums * @return */ public int findMin_4(int[] nums) { int left = 0; int right = nums.length - 1; while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { left = mid + 1; } else if (nums[mid] < nums[right]) { right = mid; } else { right--; //一次移动少一点 } } return nums[left]; } |
- ### 二进制中1的个数
请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
public class Solution { // you need to treat n as an unsigned value public int hammingWeight(int n) { int res = 0; while(n!=0){ res+=n&1; n>>>=1; } return res; } } |
- ### 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
返回删除后的链表的头节点。
注意：此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
删除值为 val 的节点可分为两步：定位节点、修改引用。
定位节点： 遍历链表，直到 head.val val 时跳出，即可定位目标节点。
修改引用： 设节点 cur 的前驱节点为 pre ，后继节点为 cur.next ；则执行 pre.next = cur.next ，即可实现删除 cur 节点。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
public ListNode deleteNode(ListNode head,int val){ if (head.val == val) return head.next; ListNode pre = head, cur = head.next; while (cur!=null && cur.val!=val){ pre = cur; cur = cur.next; } if (cur!=null) pre.next = cur.next; return head; } |
- ### 调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
示例：
输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。
考虑定义双指针 ii , jj 分列数组左右两端，循环执行：
指针 ii 从左向右寻找偶数；
指针 jj 从右向左寻找奇数；
将 偶数 nums[i]nums[i] 和 奇数 nums[j]nums[j] 交换。
可始终保证： 指针 ii 左边都是奇数，指针 jj 右边都是偶数
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
class Solution { public int[] exchange(int[] nums) { int i = 0; int j = nums.length-1; int tmp; while (i<j){ while (i<j && nums[i]%2 == 1) i++; while (i<j && nums[j]%2 == 0) j--; tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } return nums; } } |
- ### 链表中倒数第k个节点
输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
示例：
给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.
第一时间想到的解法：
先遍历统计链表长度，记为 nn ；
设置一个指针走 (n-k)步，即可找到链表倒数第 kk 个节点。
使用双指针则可以不用统计链表长度。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
// 单指针 class Solution { public ListNode getKthFromEnd(ListNode head,int k){ int l = 1; ListNode cur = head; while(cur.next!=null){ cur = cur.next; l++; } for(int i=0;i<l-k;i++){ head = head.next; } return head; } } // 快慢指针 class Solution { public ListNode getKthFromEnd(ListNode head, int k) { ListNode former = head, latter = head; for(int i = 0; i < k; i++) former = former.next; while(former != null) { former = former.next; latter = latter.next; } return latter; } } |
- ### 反转链表
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。
其实只需要改变链表的next指针的指向，直接将链表反转 ，而不用重新定义一个新的链表，如图所示:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
public ListNode reverseList(ListNode head){ ListNode tmp; ListNode cur = head; ListNode pre = null; while (cur!=null){ tmp = cur.next; cur.next = pre; pre = cur; cur = tmp; } return pre; } // 用栈写的但是有问题 class Solution { private Stack<ListNode> stack = new Stack<>(); public ListNode reverseList(ListNode head){ ListNode curr = head; while (curr!=null){ stack.push(curr); curr = curr.next; } head = stack.pop(); while (!stack.isEmpty()){ head = head.next; head = stack.pop(); } return head; } } |
- ### 合并两个排序的链表
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dum = new ListNode(0),cur = dum; while (l1!=null && l2!=null){ if (l1.val < l2.val){ cur.next = l1; l1 = l1.next; }else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dum.next; } } |
- ### 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如输入：
4
/ \
2 7
/ \ / \
1 3 6 9
镜像输出：
4
/ \
7 2
/ \ / \
9 6 3 1
示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
class Solution { public TreeNode mirrorTree(TreeNode root) { if (root == null) return null; TreeNode tmp = root.left; root.left = mirrorTree(root.right); root.right = mirrorTree(tmp); return root; } } |
- ### 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。
例如，二叉树 [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
示例 1：
输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：
输入：root = [1,2,2,null,3,null,3]
输出：false
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
class Solution { public boolean isSymmetric(TreeNode root) { return root==null?true:recur(root.left, root.right); } public boolean recur(TreeNode L,TreeNode R){ if (L==null && R==null) return true; if (L == null || R ==null || L.val != R.val) return false; return recur(L.left,R.right) && recur(L.right,R.left); } } |
- ### 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
根据题目示例 matrix = [[1,2,3],[4,5,6],[7,8,9]] 的对应输出 [1,2,3,6,9,8,7,4,5] 可以发现，顺时针打印矩阵的顺序是 “从左向右、从上向下、从右向左、从下向上” 循环。
因此，考虑设定矩阵的“左、上、右、下”四个边界，模拟以上矩阵遍历顺序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public int[] spiralOrder(int[][] matrix){ if (matrix.length == 0) return new int[0]; int l = 0, r = matrix[0].length-1,t = 0,b = matrix.length-1,x = 0; int[] res = new int[(r+1)*(b+1)]; while (true){ for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right. if(++t > b) break; for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom. if(l > --r) break; for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left. if(t > --b) break; for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top. if(++l > r) break; } return res; } |
- ### 包含min函数的栈
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2. |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
class MinStack { /** initialize your data structure here. */ Stack<Integer> A, B; public MinStack() { A = new Stack<>(); B = new Stack<>(); } public void push(int x) { A.push(x); if(B.isEmpty() || B.peek() >= x) B.push(x); } public void pop() { if(A.pop().equals(B.peek())) B.pop(); } public int top() { return A.peek(); } public int min() { return B.peek(); } } |
- ### 数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1:
输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2
利用HashMap
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
class Solution { public int majorityElement(int[] nums) { HashMap<Integer,Integer> res = new HashMap<>(); for (int i=0;i<nums.length;i++){ if (res.containsKey(nums[i])){ int tmp = res.get(nums[i]); res.put(nums[i],tmp+1); }else { res.put(nums[i],1); } } for (Integer k: res.keySet()){ if (res.get(k)*2>nums.length){ return k; } } return 0; } } |
- ### 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
示例 1：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
本题使用排序算法解决最直观，对数组 arr 执行排序，再返回前 k 个元素即可。使用任意排序算法皆可，本文采用并介绍 快速排序。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
class Solution { public int[] getLeastNumbers(int[] arr, int k) { quickSort(arr, 0, arr.length - 1); return Arrays.copyOf(arr, k); } private void quickSort(int[] arr, int l, int r) { // 子数组长度为 1 时终止递归 if (l >= r) return; // 哨兵划分操作（以 arr[l] 作为基准数） int i = l, j = r; while (i < j) { while (i < j && arr[j] >= arr[l]) j--; while (i < j && arr[i] <= arr[l]) i++; swap(arr, i, j); } swap(arr, i, l); // 递归左（右）子数组执行哨兵划分 quickSort(arr, l, i - 1); quickSort(arr, i + 1, r); } private void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } |
- ### 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母
示例:
s = "abaccdeff"
返回 "b"
s = ""
返回 " "
用hashmap存储每个字符出现的次数，注意HashMap遍历的时候不是按照插入的顺序遍历的，需要采用LinkedHashMap才可以。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
class Solution { public char firstUniqChar(String s) { LinkedHashMap<Character,Integer> res = new LinkedHashMap<>(); for (int i=0;i<s.length();i++){ if (res.containsKey(s.charAt(i))){ res.put(s.charAt(i),res.get(s.charAt(i))+1); }else { res.put(s.charAt(i),1); } } for (Character h : res.keySet()){ if (res.get(h)==1) return h; } return ' '; } } |
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
先把第一个链表的节点全部存放到集合set中，然后遍历第二个链表的每一个节点，判断在集合set中是否存在，如果存在就直接返回这个存在的结点。如果遍历完了，在集合set中还没找到，说明他们没有相交，直接返回null即可。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { Set<ListNode> set = new HashSet<>(); while (headA!=null){ set.add(headA); headA=headA.next; } while (headB!=null){ if (set.contains(headB)) return headB; headB=headB.next; } return null; } } |
- ### 第一个只出现一次的字符
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
排序数组中的问题，优化大概率是二分法，二分法就三个框架，一个是搜索确定元素的下标，一个是搜索左边界，一个是右边界。
那么这个题用二分法，我们找到它的左右边界left和right，然后元素个数就是right-left+1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
public int search(int[] nums, int target) { return getRight(nums,target) - getLeft(nums,target) + 1; } private int getLeft(int[] nums, int target){ int left = 0,right = nums.length; while (left<right){ int mid = left + (right-left)/2; if (nums[mid] == target) right = mid; else if (nums[mid] > target) right = mid; else if (nums[mid] < target) left = mid + 1; } return left; } private int getRight(int[] nums, int target){ int left = 0,right = nums.length; while (left<right){ int mid = left + (right-left)/2; if (nums[mid] == target) left = mid + 1; else if (nums[mid] > target) right = mid; else if (nums[mid] < target) left = mid + 1; } return left-1; }https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof/ |