change array={a1,a2,...,an,b1,b2,...,bn} to {a1,b1,a2,b2,...,an,bn} with O(n) time and O(1) space.
int j, temp = 0, n = array.length / 2;
for (int i = 1; i < array.length - 1; i++) {
temp = 0;
j = i ;
j = n + (j/((j^(j-1))+1));
while (j < i) {
j = n + (j/((j^(j-1))+1));
}
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
package com.onezero;
/**
* change array {a1,a2,...an,b1,b2,...bn}
* to {a1,b1,a2,b2,...,an,bn}
* using O(n) time and O(1) space
*
* @author andyjojo
*
*/
public class ArrayPuzzle1 {
int [] array;
public ArrayPuzzle1(int[] arr){
array = arr;
}
/**
* from 1 to array.length - 1
* calculate result array i-th location
*
*/
public void change1() {
int j, temp = 0, n = array.length / 2;
for (int i = 1; i < array.length - 1; i++) {
temp = 0;
j = i + 1;
while (j % 2 == 1)
j = (j + 1) / 2;
j = n + j / 2 - 1;
while (j < i) {
j++;
while (j % 2 == 1)
j = (j + 1) / 2;
j = n + j / 2 - 1;
}
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
/**
* The magic calculation of {@link#change1()}
*
*/
public void change2(){
int j, temp = 0, n = array.length / 2;
for (int i = 1; i < array.length - 1; i++) {
temp = 0;
j = i ;
j = n + (j/((j^(j-1))+1));
while (j < i) {
j = n + (j/((j^(j-1))+1));
}
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
/**
* find in http://discuss.techinterview.org/default.asp?interview.11.482833.2
* it not work, need to check what it work for.
*/
/*public void changeother(){
int n = array.length/2;
for(int i=0;i<n;++i)
{
array[i]^=array[n+i]^=array[i]^=array[n+i];
}
}*/
/**
* print the array
*/
public void print() {
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
/**
* compares with a array
* @param b array b
* @return true when array b is the same with array, false otherwise
*/
public boolean compare(int[] b) {
if(array.length!=b.length) return false;
for (int i = 0; i < array.length; i++) {
if (array[i] != b[i])
return false;
}
return true;
}
/**
* construct a 2n element array {array[i]=i}
* aka. ai=i, bi=n+i
* @param n the half number of array length
* @return a 2n element array {ai=i}
*/
public static int[] constructOrignal(int n) {
int[] array = new int[n * 2];
for (int i = 0; i < 2*n; i++) {
array[i] = i;
}
return array;
}
/**
* construct the result of this puzzle of array {array[i]=i}
* @param n the half number of array length
* @return the result of this puzzle of array {array[i]=i}
*/
public static int[] constructResult(int n) {
int[] array = new int[n * 2];
for (int i = 0; i < n; i++) {
array[2 * i] = i;
array[2 * i + 1] = n + i;
}
return array;
}
/**
* @param args
*/
public static void main(String[] args) {
ArrayPuzzle1 ap;
for (int i = 1; i < 9999; i++) {
ap = new ArrayPuzzle1(constructOrignal(i));
ap.change2();//the same with ap.change1()
if (!ap.compare(constructResult(i)))
System.out.println("Fail on " + i);
}
}
}
说明(一下内容反选可见,你可以看完代码再看。希望收到你的意见,谢谢):
1 和 2n 的位置不用换
j 从 2 到 2n-1
如果j是偶数,只要直接与n+j/2交换即可
如果j是奇数,那么就要放置a[(j+1)/2]即可,那么问题就是要找到a[(j+1)/2]当前的位置
因为(j+1)/2<j,所以在处理(j+1)/2时,a[(j+1)/2] 已经不在(j+1)/2了,替换到(j+1)/2位置上元素没有替换之前的位置,所以在考虑(j+1)/2即可。
比如位置5,应该是a3, 而对于3,应该是a2, 同样对于2,应该是b1, 即n+1位置,所以a3此时应该在n+1的位置。
如果按照上面的位置找到j需要替换的元素位置小于j,说明该元素在j之前又被替换了一次,就需要继续用上面的方法查找。
分享到:
相关推荐
本文档“puzzle c.pdf”主要聚焦于C语言编程中的各种问题与谜题,旨在帮助读者理解并解决C编程过程中遇到的各种难题。文档作者Gowri Kumar分享了一系列有趣的C编程题目,这些问题既包括常见的类型错误,也涵盖了一些...
本项目名为"maze-puzzle-using-two-dimensional-array",显然它使用了二维数组来表示迷宫,这是一种简单而有效的数据结构。下面我们将深入探讨这个主题。 在Java编程中,二维数组常用于模拟现实世界中的网格系统,...
《JavaScript实现WordPuzzle游戏详解》 在编程领域,JavaScript是一种广泛应用的脚本语言,尤其在Web开发中占据着核心地位。"wordPuzzle"是一个基于JavaScript实现的文字谜题游戏,旨在通过编程技术将文字游戏的...
例如,我们可以使用`String.contains`方法检查用户输入的单词是否在谜题单词列表中,`String.lowercased()`将输入转化为小写以忽略大小写差异,以及`Array(String)`将字符串分割成单词数组进行比较。 此外,为了...
Array.Copy(puzzle, temp, puzzle.Length); int[] swapRow = new int[temp.GetLength(1)]; Array.Copy(temp, i * temp.GetLength(1), swapRow, 0, temp.GetLength(1)); Array.Copy(temp, swapIndex * temp....
numpy_array = np.array(img) ``` 3. **查看图像形状**: 数组的形状可以告诉我们图像的维度和大小。例如,(width, height) 对于灰度图像,(width, height, 3) 对于RGB图像。 ```python print(numpy_array.shape) `...
完整的作业规范可以在以下位置找到: : 8-puzzle是一款经典游戏,其中将图块1-8放置在3 x 3网格上,并留出一个空白空间(如果将图块1-(N ^ 2-1)放置在N x N网格上,则游戏会变大)。 目的是通过将图块滑入空白...
在拼图游戏的实现过程中,还会涉及到一些其他关键概念,如时间轴控制(Timeline Control)、对象实例化(Object Instantiation)以及数组和对象字典(Array和Object Dictionary)的使用,这些都对于管理拼图块的状态...
本压缩包文件涵盖了四个关键概念:树(Tree)、动态数组(Dynamic Array)、哈希映射(HashMap)以及拼图算法(Puzzle Algorithm)。接下来,我们将详细探讨这些知识点。 1. **树(Tree)**: 树是一种非线性的...
此外,函数(`function`)和条件语句(`if...else`)用于控制游戏流程,数组(`array`)和循环(`for`、`while`)常用于处理游戏数据。对于初学者来说,理解变量、数据类型、作用域以及异步编程(如回调函数、...
array ( 0 , 6 , 0 , 0 , 0 , 0 , 0 , 3 , 0 ), array ( 0 , 0 , 0 , 5 , 0 , 0 , 0 , 0 , 4 ), array ( 4 , 1 , 0 , 0 , 0 , 9 , 0 , 2 , 0 ), array ( 0 , 0 , 4 , 0 , 0 , 0 , 0 , 0 , 0 ), array ( 0 , 3...
if array[i] + array[j] == target print(array[i], array[j]) ``` #### 方法二:哈希表 利用哈希表可以将时间复杂度降低到O(n)。具体做法是遍历数组,对于每个元素,计算目标值与该元素的差值,并检查差值是否...
Anne是一个用于浮点图,图像,图形和文本的声音化库。 她目前仅对文本,浮点数的数组和矩阵进行操作。...puzzle_times = np.array([12.5, 12.92, 32.08, 73.4, 25.89, 36.81, 295.22, 16.37, 225.95]) soni
Puzzle 864. Shortest Path to Get All Keys 深度优先搜索 996. Number of Squareful Arrays 拓扑排序 269. Alien Dictionary 单调栈 42. Trapping Rain Water 85. Maximal Rectangle Monotonic stack for 2d array ...
C++中的`std::vector`或`std::array`可以用来创建这样的数据结构。 2. **面向对象编程**:C++的面向对象特性可以帮助我们将游戏逻辑分解为不同的类,如`Puzzle`(拼图类)、`Tile`(拼图块类)等。每个类都有其特定...
在C#中,可以使用`Array.Equals`方法进行快速比较。 最后,对于初学者来说,理解并实现这个游戏可以帮助他们掌握C#的基础语法、面向对象编程的概念以及如何使用图形用户界面进行交互。通过这个项目,你可以学习到...
Chapter 56: Application: Cross-Browser DHTML Map Puzzle. Chapter 57: Application: Transforming XML Data Islands. Part VI: Appendixes. Appendix A: JavaScript and Browser Object Quick Reference. ...
File Input/Output C++ File I/O Conversion Routines Binary and ASCII Files The End-of-Line Puzzle Binary I/O Buffering Problems Unbuffered I/O Designing File Formats C-Style I/O Routines C-Style ...