大厂面试的算法题，你学废了么？（一）

本是古典何须时尚 2023-02-27 05:37 81阅读 0赞

### 目录 ###

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

> 大家好，我是[爱做梦的鱼][Link 1]，我是东北大学大数据实验班大三的小菜鸡，非常渴望优秀，羡慕优秀的人，个人博客为：[爱做梦的鱼https://zihao.blog.csdn.net/][https_zihao.blog.csdn.net]，微信公众号、微信视频号为[【程序猿干货铺】][Link 2]，qq交流群为：[1107710098][]，  
> ![程序猿干货铺][Image 1]

> 如果你同样热爱算法，那么请**关注**我，我将每日更新力扣的每日一题的题解+代码，每周更新力扣周赛题解+代码  
> [专栏《力扣每日一题》][Link 3]  
> [专栏《力扣周赛》][Link 4]

# 一、转置矩阵 #

给定一个矩阵 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.  `1 <= A.length <= 1000`
2.  `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( n m nm nm)=O( n 2 n^2 n2)=O( m 2 m^2 m2)，其中 n 是 矩阵的行数，m为矩阵的列数
 *  空间复杂度：O( n m nm nm)=O( n 2 n^2 n2)=O( m 2 m^2 m2)

![在这里插入图片描述][20200716104009757.png]

# 二、搜索旋转排序数组 #

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

( 例如，数组 \[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)。  
    ![在这里插入图片描述][20200716111326415.png]

# 三、石子游戏 III #

> [题目地址（点击直接跳转）https://leetcode-cn.com/problems/stone-game-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.  `1 <= values.length <= 50000`
2.  `-1000 <= values[i] <= 1000`

> 建议大家直接去看官方题解  
> 作者：LeetCode-Solution  
> 链接：[https://leetcode-cn.com/problems/stone-game-iii/solution/shi-zi-you-xi-iii-by-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)。  
    ![在这里插入图片描述][20200716115810209.png]

## 方法二：动态规划，另一种状态的设计思路 ##

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)。  
    ![在这里插入图片描述][20200716114126898.png]

[Link 1]: https://blog.csdn.net/weixin_43124279
[https_zihao.blog.csdn.net]: https://zihao.blog.csdn.net/
[Link 2]: https://s1.ax1x.com/2020/06/11/tHUSvq.png
[1107710098]: https://s1.ax1x.com/2020/06/26/NroKrd.jpg
[Image 1]: 
[Link 3]: https://blog.csdn.net/weixin_43124279/category_10194088.html
[Link 4]: https://blog.csdn.net/weixin_43124279/category_10194115.html
[20200716104009757.png]: /images/20230209/4a07c113c79347358adcdbb019e343f3.png
[20200716111326415.png]: /images/20230209/2a9a5a81d4394a338933c82232eced28.png
[https_leetcode-cn.com_problems_stone-game-iii]: https://leetcode-cn.com/problems/stone-game-iii/
[https_leetcode-cn.com_problems_stone-game-iii_solution_shi-zi-you-xi-iii-by-leetcode-solution]: https://leetcode-cn.com/problems/stone-game-iii/solution/shi-zi-you-xi-iii-by-leetcode-solution/
[20200716115810209.png]: /images/20230209/f4856b31168748c6b839ec1c9d6644a4.png
[20200716114126898.png]: /images/20230209/b69e1c91bdfa459494fabf6845b4a0ce.png