大厂面试的算法题,你学废了么?(一)

目录一、转置矩阵方法:暴力二、搜索旋转排序数组方法:二分查找三、石子游戏 III方法一:动态规划方法二:动态规划,另一种状态的设计思路

大家好,我是爱做梦的鱼,我是东北大学大数据实验班大三的小菜鸡,非常渴望优秀,羡慕优秀的人,个人博客为:爱做梦的鱼https://zihao.blog.csdn.net/,微信公众号、微信视频号为【程序猿干货铺】,qq交流群为:1107710098,
大厂面试的算法题,你学废了么?(一)

如果你同样热爱算法,那么请关注我,我将每日更新力扣的每日一题的题解+代码,每周更新力扣周赛题解+代码
专栏《力扣每日一题》
专栏《力扣周赛》

一、转置矩阵

给定一个矩阵 A, 返回 A 的转置矩阵。
矩阵的转置是指将矩阵的主对角线翻转,交换矩阵的行索引与列索引。

示例 1:

输入:[[1,2,3],[4,5,6],[7,8,9]]
输出:[[1,4,7],[2,5,8],[3,6,9]]

示例 2:

输入:[[1,2,3],[4,5,6]]
输出:[[1,4],[2,5],[3,6]]

提示:

    1 <= A.length <= 1000
    1 <= A[0].length <= 1000

方法:暴力

public class Transpose {
public static void main(String[] args) {
int[][] A={{1,2,3},{4,5,6},{7,8,9}};
int[][] B=new Transpose().transpose(A);
for (int[] i:B){
for (int j:i){
System.out.print(j+" ");
}
System.out.println();
}

}

public int[][] transpose(int[][] A) {
int row = A.length;
int col = A[0].length;
int[][] result = new int[col][row];
for (int i = 0; i < row; i++)
for (int j = 0; j < col; j++) {
result[j][i] = A[i][j];
}
return result;
}
}

复杂度分析

时间复杂度:O(

nmnm

nm)=O(

n2n^2

n2)=O(

m2m^2

m2),其中 n 是 矩阵的行数,m为矩阵的列数
空间复杂度:O(

nmnm

nm)=O(

n2n^2

n2)=O(

m2m^2

m2)

大厂面试的算法题,你学废了么?(一)

二、搜索旋转排序数组

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

方法:二分查找

时间复杂度是 O(log n) 级别,我们可以考虑用二分查找,每次都将指定长度的一组数一分为二,
由于搜索数组是按照升序排序的数组在未知的某个点上进行了旋转,所以每次切分肯定至少有一边数组是有序的,
在每次切分后判断目标值的位置,直到找到目标值,或找不到时返回-1.

public class SearchRotation {
public static void main(String[] args) {
int[] nums = {4, 5, 6, 7, 0, 1, 2};
int target = 0;
System.out.println(new SearchRotation().search(nums, target));

}

public int search(int[] nums, int target) {
return search(nums, 0, nums.length - 1, target);
}

private int search(int[] nums, int l, int r, int target) {
if (l > r) {
return -1;
}
int mid = (l + r) / 2;
if (nums[mid] == target) {
return mid;
}
if (nums[mid] < nums[r]) {//右侧有序
if (target > nums[mid] && target <= nums[r]) {//目标值在右侧
return search(nums, mid + 1, r, target);
} else {
return search(nums, l, mid - 1, target);
}
} else {
if (target < nums[mid] && target >= nums[l]) {
return search(nums, l, mid - 1, target);
} else {
return search(nums, mid + 1, r, target);
}
}
}
}

复杂度分析

时间复杂度:O(log n),其中 n 是数组nums的长度。
空间复杂度:O(1)。
大厂面试的算法题,你学废了么?(一)

三、石子游戏 III

题目地址(点击直接跳转)https://leetcode-cn.com/problems/stone-game-iii/

Alice 和 Bob 用几堆石子在做游戏。几堆石子排成一行,每堆石子都对应一个得分,由数组 stoneValue 给出。

Alice 和 Bob 轮流取石子,Alice 总是先开始。在每个玩家的回合中,该玩家可以拿走剩下石子中的的前 1、2 或 3 堆石子 。比赛一直持续到所有石头都被拿走。

每个玩家的最终得分为他所拿到的每堆石子的对应得分之和。每个玩家的初始分数都是 0 。比赛的目标是决出最高分,得分最高的选手将会赢得比赛,比赛也可能会出现平局。

假设 Alice 和 Bob 都采取 最优策略 。如果 Alice 赢了就返回 “Alice” ,Bob 赢了就返回 “Bob”,平局(分数相同)返回 “Tie” 。

示例 1:

输入:values = [1,2,3,7]
输出:"Bob"
解释:Alice 总是会输,她的最佳选择是拿走前三堆,得分变成 6 。但是 Bob 的得分为 7,Bob 获胜。

示例 2:

输入:values = [1,2,3,-9]
输出:"Alice"
解释:Alice 要想获胜就必须在第一个回合拿走前三堆石子,给 Bob 留下负分。
如果 Alice 只拿走第一堆,那么她的得分为 1,接下来 Bob 拿走第二、三堆,得分为 5 。之后 Alice 只能拿到分数 -9 的石子堆,输掉比赛。
如果 Alice 拿走前两堆,那么她的得分为 3,接下来 Bob 拿走第三堆,得分为 3 。之后 Alice 只能拿到分数 -9 的石子堆,同样会输掉比赛。
注意,他们都应该采取 最优策略 ,所以在这里 Alice 将选择能够使她获胜的方案。

示例 3:

输入:values = [1,2,3,6]
输出:"Tie"
解释:Alice 无法赢得比赛。如果她决定选择前三堆,她可以以平局结束比赛,否则她就会输。

示例 4:

输入:values = [1,2,3,-1,-2,-3,7]
输出:"Alice"

示例 5:

输入:values = [-1,-2,-3]
输出:"Tie"

提示:

    1 <= values.length <= 50000
    -1000 <= values[i] <= 1000

建议大家直接去看官方题解
作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/stone-game-iii/solution/shi-zi-you-xi-iii-by-leetcode-solution/
来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法一:动态规划

class Solution {
public String stoneGameIII(int[] stoneValue) {
int n = stoneValue.length;
int[] suffixSum = new int[n];
suffixSum[n - 1] = stoneValue[n - 1];
for (int i = n - 2; i >= 0; --i) {
suffixSum[i] = suffixSum[i + 1] + stoneValue[i];
}
int[] f = new int[n + 1];
// 边界情况,当没有石子时,分数为 0
// 为了代码的可读性,显式声明
f[n] = 0;
for (int i = n - 1; i >= 0; --i) {
int bestj = f[i + 1];
for (int j = i + 2; j <= i + 3 && j <= n; ++j) {
bestj = Math.min(bestj, f[j]);
}
f[i] = suffixSum[i] - bestj;
}
int total = 0;
for (int value : stoneValue) {
total += value;
}
if (f[0] * 2 == total) {
return "Tie";
} else {
return f[0] * 2 > total ? "Alice" : "Bob";
}
}
}

复杂度分析

时间复杂度:O(N),其中 N 是数组values 的长度。
空间复杂度:O(N)。
大厂面试的算法题,你学废了么?(一)

方法二:动态规划,另一种状态的设计思路

class Solution {
public String stoneGameIII(int[] stoneValue) {
int n = stoneValue.length;
int[] f = new int[n + 1];
Arrays.fill(f, Integer.MIN_VALUE);
// 边界情况,当没有石子时,分数为 0
f[n] = 0;
for (int i = n - 1; i >= 0; --i) {
int pre = 0;
for (int j = i + 1; j <= i + 3 && j <= n; ++j) {
pre += stoneValue[j - 1];
f[i] = Math.max(f[i], pre - f[j]);
}
}
if (f[0] == 0) {
return "Tie";
} else {
return f[0] > 0 ? "Alice" : "Bob";
}
}
}

复杂度分析

时间复杂度:O(N),其中 N 是数组values 的长度。
空间复杂度:O(N)。
大厂面试的算法题,你学废了么?(一)

关注博主即可阅读全文


原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

大厂面试的算法题,你学废了么?(一)

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 大厂面试的算法题,你学废了么?(一)
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏