剑指Offer题解(持续更新中……)
程序员文章站
2022-06-14 23:03:26
...
文章目录
- 第2️⃣章
- 03 | [数组中重复的数字](https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/)
- 04 | [二维数组中的查找](https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/)
- 09 | [用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)
- 15 | [二进制中1的个数](https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/)
- 第3️⃣章
- 第4️⃣章
- 第5️⃣章
- 第6️⃣章
- 57 | [和为s的两个数字](https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/)
- 57-II | [和为s的连续正数序列](https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/)
- 第7️⃣章
第2️⃣章
03 | 数组中重复的数字
问题描述
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
解题思路
- 把数字i放到num[i]上
- 如果num[i]上已经有i了,那么就是重复的数字了
代码
class Solution {
public int findRepeatNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
while (i != nums[i]) {
if (nums[nums[i]] != nums[i]) {
swap(nums,i,nums[i]);
} else {
return nums[i];
}
}
}
return ans;
}
private void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
其他方法分析
方法 | 时间复杂度 | 空间复杂度 | 注 |
---|---|---|---|
题解方法 | O(n) | O(1) | |
哈希表 | O(n) | O(n) | |
先排序后遍历数组 | O(nlogn) | O(1) | |
二分法 | O(nlogn) | O(1) | 不会修改原数组 |
若果不允许修改数组呢?(二分法,详情见书,时间复杂度O(nlogn))
04 | 二维数组中的查找
问题描述
在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
解题思路
- 数组右上角(或者左下角)的元素很特殊,该元素的行中它是最大的,列中它是最小的
- 所以可以将target与它比较
- 若等于,则返回true
- 若martix[右上] < target,则martix[右上]左侧比它还要小的一行就不用考虑了
- 若martix[右上] > target,则martix[右上]下侧比它还要大的一列就不用考虑了
- 一行/一列被去掉后会出现新的martix[右上],继续判断直至没有元素可以比较
代码
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix.length == 0 || matrix[0].length == 0) return false;
int i = 0, j = matrix[0].length - 1;
while (i < matrix.length && j >= 0){
if (target == matrix[i][j]) {
return true;
} else if (target > matrix[i][j]) {
i++;
} else {
j--;
}
}
return false;
}
}
09 | 用两个栈实现队列
问题描述
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1 )
解题思路
- 可以想象两个区域,排队区和进入区
- 入队的元素先进入排队区,出队的元素从进入区选择
- 当即将进如区为空时,将排队区的元素全部依次进入进入区(即先进去排队区的,先出进入区(将栈倒置即可))
代码
class CQueue {
Stack<Integer> stact1 = new Stack<>();
Stack<Integer> stact2 = new Stack<>();
public CQueue() {
}
public void appendTail(int value) {
stact1.push(value);
}
public int deleteHead() {
if (stact1.isEmpty() && stact2.isEmpty()){
return -1;
}
if (stact2.isEmpty()){
while (!stact1.isEmpty()){
stact2.push(stact1.pop());
}
}
return stact2.pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
相关题目-225. 用两个队列实现栈
15 | 二进制中1的个数
问题描述
请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。
解题思路
- 将二进制数 -1 即可将二进制数最低位的 1 置位 0 ,比该 1 位数还低的 0 置位 1,如1100 - 1 = 1011
- 将 -1 后的数与原数作 & 操作,即可将原数中最低位的 1 去除
代码
public class Solution {
// you need to treat n as an unsigned value
//《剑指Offer》书上的思路1
public int hammingWeight(int n) {
int flag = 1;
int count = 0;
while (flag != 0){ //应该是flag会爆掉变成0
if ((flag & n) == flag) {
count++;
}
flag = flag << 1;
}
return count;
}
// //《剑指Offer》书上的思路2
public int hammingWeight(int n) {
String s = Integer.toBinaryString(n);
int count = 0;
for(char c:s.toCharArray()){
if (c == '1'){
count++;
}
}
return count;
}
}
第3️⃣章
第4️⃣章
30 | 包含min函数的栈
问题描述
定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。
解题思路
- 栈顶元素为最小元素时,若进行出栈操作,则需要对栈内所有元素进行比较,复杂度:O(N)
- 使用辅助栈来存储各个时刻栈内的最小元素
代码
class MinStack {
Stack<Integer> stack = new Stack<>();
Stack<Integer> auxStack = new Stack<>();
/** initialize your data structure here. */
public MinStack() {
}
public void push(int x) {
stack.push(x);
if (auxStack.empty() || x < auxStack.peek()) {
auxStack.push(x);
} else {
auxStack.push(auxStack.peek());
}
}
public void pop() {
stack.pop();
auxStack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return auxStack.peek();
}
}
第5️⃣章
第6️⃣章
57 | 和为s的两个数字
题目描述
输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。
解题思路
- 少了就加一点,多了就减一点
代码
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
int sum = 0;
while (true) {
sum = nums[i] + nums[j];
if (sum == target) {
break;
} else if (sum < target){
i++;
} else {
j--;
}
}
return new int[]{nums[i],nums[j]};
}
}
57-II | 和为s的连续正数序列
题目描述
输入一个正整数 target ,输出所有和为 target 的连续正整数序列(至少含有两个数)。
序列内的数字由小到大排列,不同序列按照首个数字从小到大排列。
解题思路
- 少了就加一点,多了就减一点
代码
class Solution {
public int[][] findContinuousSequence(int target) {
int i = 1,j = 2;
int sum = 3;
ArrayList<int[]> ans = new ArrayList<>();
while (i <= target/2)
{
if (sum > target) {
sum -= i;
i++;
} else if (sum < target){
j++;
sum += j;
}
if (sum == target) {
int[] temp = new int[j-i+1];
for (int k = i; k <= j; k++){
temp[k-i] = k;
}
ans.add(temp);
sum -= i;
i++;
}
}
return ans.toArray(new int[ans.size()][]);
}
}
第7️⃣章
上一篇: Ubuntu更新源
下一篇: 一个简单的php图形验证码生成程序
推荐阅读
-
剑指offer JZ31 整数中1出现的次数 Python 解
-
剑指offer JZ54 字符流中第一个不重复的字符 Python 多解
-
剑指Offer积累-JZ1-二维数组中的查找
-
剑指offer之队列中的最大值(C++/Java双重实现)
-
【剑指Offer】链表中倒数第k个结点
-
剑指offer之在排序数组中查找数字 I(C++/Java双重实现)
-
剑指Offer04:二维数组中的查找(Java)
-
【剑指 Offer-python】 03. 数组中重复的数字
-
剑指 Offer 07. 重建二叉树——【前中序】和【中后序】重建二叉树的递归思路详解
-
leetcode中剑指offer的习题 C++语言实现(2)