这一道题, 在过去半年里, 如下公司采用过如许次数: Amazon (19), Facebook (11), Apple (11), Google (10), Adobe (8), Bloomberg (5), Uber (4), Microsoft (2), Goldman Saches (2), Walmart Global Tech (2), DoorDash (2), DE Shaw (2) 题目就是求字典顺序的下一个permutation. [ A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement. Given an array of integers nums, find the next permutation of nums. The replacement must be in place and use only constant extra memory. Constraints: 1 <= nums.length <= 100 0 <= nums <= 100 ] 如果你从定义出发, 先求permutation, 再来作lexicographical sorting, 再定位给定的数组, 再返回答案, 你死定了! 因为你的解会超时; 退一步说, 就算你能全对写出来, 黄花菜都凉了 ==> 能且只能用茴字的另外一种写法: "倒摸黄瓜寻香肠"之大法! /** * @param nums: an integer array, may contain duplicate elements */ public void nextPermutation(int [] nums){ // 香肠节点 := 即一个值不小于右边元素的值的元素 // 倒摸黄瓜, 寻找第一个香肠节点 int p = -1; // 第一个香肠节点的index int pVal = 0; // 第一个香肠节点的值 for(int i = nums.length -2; i >= 0; --i){ if(nums < nums[ i + 1]){ p = i; pVal = nums; break; } } // 一共也就两CASEs, 拍手拍手, 好记好记啦! if(p == -1){ // CASE 1: 没找到, 啧啧, 这是根奇物: 左边小来右边大, 一直到尾; 嘿! 把整条黄瓜横过来就完事了 reverse(nums, 0, nums.length - 1); return; } // CASE 2: 找到啦, 香肠节点左边的就不碰了, 互换香肠节点和尾巴, 把右边当作CASE1情形下的整条黄瓜, 作同样处理 for(int j = nums.length - 1; j >= 0; --j){ if(nums[j] > pVal){ swap(nums, j, p); break; } } reverse(nums, p + 1, nums.length - 1); } 这样写, 最多10分钟就能结束, 至于这解法为什么正确, 面试官大概率不好意思问的. 说白了, 厂里要的就是会茴字各种花色写法的. 还不会? 那正好呆家里带孩子乐!
这一道题, 在过去半年里, 如下公司采用过如许次数: Amazon (19), Facebook (11), Apple (11), Google (10), Adobe (8), Bloomberg (5), Uber (4), Microsoft (2), Goldman Saches (2), Walmart Global Tech (2), DoorDash (2), DE Shaw (2) 题目就是求字典顺序的下一个permutation. [ A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order). For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement. Given an array of integers nums, find the next permutation of nums. The replacement must be in place and use only constant extra memory. Constraints: 1 <= nums.length <= 100 0 <= nums <= 100 ] 如果你从定义出发, 先求permutation, 再来作lexicographical sorting, 再定位给定的数组, 再返回答案, 你死定了! 因为你的解会超时; 退一步说, 就算你能全对写出来, 黄花菜都凉了 ==> 能且只能用茴字的另外一种写法: "倒摸黄瓜寻香肠"之大法! /** * @param nums: an integer array, may contain duplicate elements */ public void nextPermutation(int [] nums){ // 香肠节点 := 即一个值不小于右边元素的值的元素 // 倒摸黄瓜, 寻找第一个香肠节点 int p = -1; // 第一个香肠节点的index int pVal = 0; // 第一个香肠节点的值 for(int i = nums.length -2; i >= 0; --i){ if(nums < nums[ i + 1]){ p = i; pVal = nums; break; } } // 一共也就两CASEs, 拍手拍手, 好记好记啦! if(p == -1){ // CASE 1: 没找到, 啧啧, 这是根奇物: 左边小来右边大, 一直到尾; 嘿! 把整条黄瓜横过来就完事了 reverse(nums, 0, nums.length - 1); return; } // CASE 2: 找到啦, 香肠节点左边的就不碰了, 互换香肠节点和尾巴, 把右边当作CASE1情形下的整条黄瓜, 作同样处理 for(int j = nums.length - 1; j >= 0; --j){ if(nums[j] > pVal){ swap(nums, j, p); break; } } reverse(nums, p + 1, nums.length - 1); } 这样写, 最多10分钟就能结束, 至于这解法为什么正确, 面试官大概率不好意思问的. 说白了, 厂里要的就是会茴字各种花色写法的. 还不会? 那正好呆家里带孩子乐!
题目就是求字典顺序的下一个permutation. [ A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2, 1, 3], [2, 3, 1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).
For example, the next permutation of arr = [1,2,3] is [1,3,2]. Similarly, the next permutation of arr = [2,3,1] is [3,1,2]. While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement. Given an array of integers nums, find the next permutation of nums.
The replacement must be in place and use only constant extra memory. Constraints: 1 <= nums.length <= 100 0 <= nums <= 100 ]
如果你从定义出发, 先求permutation, 再来作lexicographical sorting, 再定位给定的数组, 再返回答案, 你死定了! 因为你的解会超时; 退一步说, 就算你能全对写出来, 黄花菜都凉了 ==> 能且只能用茴字的另外一种写法: "倒摸黄瓜寻香肠"之大法!
/** * @param nums: an integer array, may contain duplicate elements */ public void nextPermutation(int [] nums){ // 香肠节点 := 即一个值不小于右边元素的值的元素 // 倒摸黄瓜, 寻找第一个香肠节点 int p = -1; // 第一个香肠节点的index int pVal = 0; // 第一个香肠节点的值 for(int i = nums.length -2; i >= 0; --i){ if(nums < nums[ i + 1]){ p = i; pVal = nums; break; } } // 一共也就两CASEs, 拍手拍手, 好记好记啦! if(p == -1){ // CASE 1: 没找到, 啧啧, 这是根奇物: 左边小来右边大, 一直到尾; 嘿! 把整条黄瓜横过来就完事了 reverse(nums, 0, nums.length - 1); return; } // CASE 2: 找到啦, 香肠节点左边的就不碰了, 互换香肠节点和尾巴, 把右边当作CASE1情形下的整条黄瓜, 作同样处理 for(int j = nums.length - 1; j >= 0; --j){ if(nums[j] > pVal){ swap(nums, j, p); break; } } reverse(nums, p + 1, nums.length - 1); }
这样写, 最多10分钟就能结束, 至于这解法为什么正确, 面试官大概率不好意思问的. 说白了, 厂里要的就是会茴字各种花色写法的.
还不会? 那正好呆家里带孩子乐!
并不是回字几种写法，而是对例子进行归纳推理，就能得到解题方法 我很久不刷题，但是花了几分钟想想题目中的举的举个例子，自己如果手动排的话怎么排，仔细观察规律，很快就得到解法了
无聊的题目 不如来写个FFT（快速傅里叶变换）的算法
会吗？ 另： 这题是招毕业生用的吗？ 有些好奇。
话说，有人做过一道2个相同的箱子，仍了后只会碎和不碎，碎了就不能再用了，算最高几层扔箱子不碎的题目吗？你有没有写出最优解？
我就想问一句，会刷这种题的高手们，近两万人，烧了150亿美元，明年还要再烧200亿美元，为啥还做不出正经的Metaverse产品出来呢？第一代iPhone也就用了1.5亿。Tesla Model S大概是20个亿吧，还带建厂等等
那题不算高手吧！ 就是最简单的那种。 我觉得我说的那题才有难度。是高手做的事情！ ~~~
当然从1 楼算起，慢慢往上推的不算，~~~