劍指offer(四)

<h2>劍指offer(四)</h2>

<h3>面試題四十：數(shù)組中只出現(xiàn)1次的數(shù)字</h3>

<blockquote>
題目：一個整形數(shù)組里除了兩個數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次，請寫程序找出這兩個只出現(xiàn)一次的數(shù)字。要求時間復(fù)雜度是O(n)，空間復(fù)雜度是O(1);
</blockquote>

<pre><code class="java">package offer;

/**

  • Created by KiSoo on 2017/2/7.
    */
    public class Offer40 {
    public static int[] findNumbersAppearanceOnce(int[] data) {
    int[] result = {0, 0};
    if (data == null || data.length < 2) {
    return result;
    }
    int xor = 0;
    for (int i : data) {
    xor ^= i;
    }
    int indexOf1 = findFirstBit1(xor);
    for (int i : data) {
    if (isBit1(i, indexOf1)) {
    result[0] ^= i;
    } else {
    result[1] ^= i;
    }
    }
    return result;
    }

    private static int findFirstBit1(int num) {
    int index = 0;
    while ((num & 1) == 0 && index < 32) {
    num = num >> 1;
    index++;
    }
    return index;
    }

    private static boolean isBit1(int num, int indexBit) {
    num = num >> indexBit;
    return (num & 1) == 1;
    }

    public static void main(String[] args) {
    int[] data1 = {2, 4, 3, 6, 3, 2, 5, 5};
    int[] result1 = findNumbersAppearanceOnce(data1);
    System.out.println(result1[0] + " " + result1[1]);
    int[] data2 = {4, 6};
    int[] result2 = findNumbersAppearanceOnce(data2);
    System.out.println(result2[0] + " " + result2[1]);
    int[] data3 = {4, 6, 1, 1, 1, 1};
    int[] result3 = findNumbersAppearanceOnce(data3);
    System.out.println(result3[0] + " " + result3[1]);
    }
    }

</code></pre>

<h4>思路</h4>

先將數(shù)組中的所有數(shù)字異或操作。然后，拿到得出的數(shù)值的最高位數(shù)字k，判斷數(shù)字右移k后是否為0。如果為0，則為第一個數(shù)字，而將剩下的數(shù)字全部異或后就得出第二個不重復(fù)的數(shù)字啦。

<h3>面試題四十一：和為s的兩個數(shù)字VS和為s的連續(xù)正數(shù)序列</h3>

<blockquote>
題目一：輸入一個遞增排序的數(shù)組和一個數(shù)字s，在數(shù)組中查找兩個數(shù)，使得它們的和正好是s。如果有多對數(shù)字的和等于s。輸出任意一對即可。
</blockquote>

<pre><code class="java">package offer;

import java.util.Arrays;

/**

  • Created by KiSoo on 2017/2/7.
    */
    public class offer41 {

    public static void main(String... args) {
    int[] a = {1, 2, 4, 7, 11, 15};
    Utils.syso(Arrays.toString(getResult(a, 15)));
    }

    public static int[] getResult(int[] data, int target) {
    int[] result = {0, 0};
    if (data == null) {
    return result;
    }
    int index1 = data.length - 1;
    int index2 = 0;
    while (index1 > index2) {
    int curr = data[index1] + data[index2];
    if (curr == target) {
    result[0] = data[index1];
    result[1] = data[index2];
    return result;
    } else if (curr > target) {
    index1--;
    } else index2++;
    }
    return result;
    }
    }

</code></pre>

<h4>思路</h4>

兩個指針，分別指向首尾，然后逐個相加，大于的話，尾指針前移，小于則首指針后移。

<blockquote>
題目二：輸入一個正數(shù)s，打印出所有和為s的連續(xù)正數(shù)序列。
</blockquote>

<pre><code class="java">public static void findArray(int num) {
if (num < 3)
return;
int small = 1;
int big = 2;
int middle = (1 + num) / 2;
int curSum = small + big;
while (small < middle) {
if (curSum == num)
System.out.println(small + "-->" + big);
while (curSum > num && small < middle) {
curSum -= small;
small++;
if (curSum == num)
System.out.println(small + "-->" + big);
}
big++;
curSum += big;
}
}
</code></pre>

<h4>思路</h4>

遍歷(k+1)/2，不停地疊加終點，如果超過，就減去起點。起點++。直到起點大于半值。

<h3>面試題四十二：翻轉(zhuǎn)單詞順序 VS 左旋旋轉(zhuǎn)字符串</h3>

<blockquote>
題目一：輸入一個英文句子，反轉(zhuǎn)句子中單詞的順序，但單詞內(nèi)字符串的順序不變。為簡單起見，標點符號和普通字母一樣處理。例如，輸入字符串"I am a student."，則輸出“student. a am I"。
</blockquote>

<h4>思路</h4>

1.先全部反轉(zhuǎn)，再分單詞反轉(zhuǎn)。
2.使用棧，把單詞全拷貝進入，然后再分單詞讀出。

<pre><code class="java">package offer;

import java.util.Stack;

/**

  • Created by KiSoo on 2017/2/8.
    */
    public class Offer42 {
    public static void main(String... args) {
    String str = "I am a student.";
    String str1 = getReverse(str);
    Utils.syso(str1);
    }

    private static String getReverse2(String str) {
    StringBuilder temp = new StringBuilder();
    Stack<String> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
    char c = str.charAt(i);
    if (c != ' ') {
    temp.append(c);
    } else {
    stack.push(temp.toString());
    temp.delete(0, temp.length() - 1);
    }
    }
    stack.push(temp.toString());
    temp.delete(0, temp.length() - 1);
    for (String c : stack) {
    temp.append(c).append(" ");
    }
    temp.delete(temp.length() - 1, temp.length());
    return temp.toString();
    }

    private static String getReverse(String str) {
    char[] chars = str.toCharArray();
    reverse(chars, 0, chars.length - 1);
    reverseSentence(chars);
    return new String(chars);
    }

    public static void reverseSentence(char[] chars) {
    if (chars == null)
    return;
    int begin = 0, end = 0;
    while (begin < chars.length - 1) {
    if (chars[begin] == ' ') {
    begin++;
    end++;
    } else if (chars[end] == ' ' || end == chars.length - 1) {
    reverse(chars, begin, end - 1);
    begin = end;
    } else {
    end++;
    }
    }

    }

    private static char[] reverse(char[] chars, int index1, int index2) {
    while (index1 < index2) {
    char temp = chars[index1];
    chars[index1] = chars[index2];
    chars[index2] = temp;
    index1++;
    index2--;
    }
    return chars;
    }
    }

</code></pre>

<blockquote>
題目二：字符串的左旋轉(zhuǎn)操作是把字符串前面的若干個字符轉(zhuǎn)移到字符串的尾部，請定義一個函數(shù)實現(xiàn)字符串左旋轉(zhuǎn)操作的功能。比如輸入字符串a(chǎn)bcdefg和數(shù)字2，該函數(shù)將返回左旋轉(zhuǎn)2位得到的結(jié)果“cdefgab”。
</blockquote>

<pre><code> public static void leftRotate(char[] data,int n){
reverse(data,0,n-1);
reverse(data,n,data.length-1);
reverse(data,0,data.length-1);
}
</code></pre>

<h3>面試題四十三：n個骰子的點數(shù)</h3>

<pre><code>package offer;

public class Offer43 {
/**
* 基于通歸求解
*
* @param number 色子個數(shù)
* @param max 色子的最大值
/
public static void printProbability(int number, int max) {
if (number < 1 || max < 1) {
return;
}
int maxSum = number * max;
int[] probabilities = new int[maxSum - number + 1];
probability(number, probabilities, max);
double total = 1;
for (int i = 0; i < number; i++) {
total = max;
}
for (int i = number; i <= maxSum; i++) {
double ratio = probabilities[i - number] / total;
System.out.printf("%-8.4f", ratio);
}
System.out.println();
}
/
* @param number 色子個數(shù)
* @param probabilities 不同色子數(shù)出現(xiàn)次數(shù)的計數(shù)數(shù)組
* @param max 色子的最大值
/
private static void probability(int number, int[] probabilities, int max) {
for (int i = 1; i <= max; i++) {
probability(number, number, i, probabilities, max);
}
}
/*
* @param original 總的色子數(shù)
* @param current 當前處理的是第幾個
* @param sum 已經(jīng)前面的色子數(shù)和
* @param probabilities 不同色子數(shù)出現(xiàn)次數(shù)的計數(shù)數(shù)組
* @param max 色子的最大值
/
private static void probability(int original, int current, int sum, int[] probabilities, int max) {
if (current == 1) {
probabilities[sum - original]++;
} else {
for (int i = 1; i <= max; i++) {
probability(original, current - 1, i + sum, probabilities, max);
}
}
}
/*
* 基于循環(huán)求解
* @param number 色子個數(shù)
* @param max 色子的最大值
*/
public static void printProbability2(int number, int max) {
if (number < 1 || max < 1) {
return;
}
int[][] probabilities = new int[2][max * number + 1];
// 數(shù)據(jù)初始化
for (int i = 0; i < max * number + 1; i++) {
probabilities[0][i] = 0;
probabilities[1][i] = 0;
}
// 標記當前要使用的是第0個數(shù)組還是第1個數(shù)組
int flag = 0;
// 拋出一個骰子時出現(xiàn)的各種情況
for (int i = 1; i <= max; i++) {
probabilities[flag][i] = 1;
}
// 拋出其它骰子
for (int k = 2; k <= number; k++) {
// 如果拋出了k個骰子，那么和為[0, k-1]的出現(xiàn)次數(shù)為0
for (int i = 0; i < k; i++) {
probabilities[1 - flag][i] = 0;
}
// 拋出k個骰子，所有和的可能
for (int i = k; i <= max * k; i++) {
probabilities[1 - flag][i] = 0;
// 每個骰子的出現(xiàn)的所有可能的點數(shù)
for (int j = 1; j <= i && j <= max; j++) {
// 統(tǒng)計出和為i的點數(shù)出現(xiàn)的次數(shù)
probabilities[1 - flag][i] += probabilities[flag][i - j];
}
}
flag = 1 - flag;
}
double total = 1;
for (int i = 0; i < number; i++) {
total *= max;
}
int maxSum = number * max;
for (int i = number; i <= maxSum; i++) {
double ratio = probabilities[flag][i] / total;
System.out.printf("%-8.4f", ratio);
}
System.out.println();
}
public static void main(String[] args) {
test01();
test02();
}
private static void test01() {
printProbability(2, 4);
}
private static void test02() {
printProbability2(2, 4);
}
}
</code></pre>

<h3>面試題四十四：撲克牌的順子</h3>

<blockquote>
題目：從撲克牌中隨機抽5張牌，判斷是不是一個順子，即這五張牌是不是連續(xù)的，2~10為數(shù)字本身，A為1，J為11，Q為12，K為13。大小王可以看成任意數(shù)字。
</blockquote>

<h4>思路</h4>

快速排序這組數(shù)組。

<pre><code>package offer;

import static offer.SortUtils.exchangeE;

/**

  • Created by KiSoo on 2017/2/10.
    */
    public class Offer44 {
    public static void main(String... args) {
    int[] a = {7, 6, 4, 8, 2};
    Utils.syso(isContinous(a));
    }

    public static boolean isContinous(int[] numbers) {
    if (numbers == null || numbers.length < 5) {
    return false;
    }
    quickSort(numbers, 0, numbers.length - 1);
    int numOfZero = 0;
    int numOfGap = 0;
    for (int i = 0; i < numbers.length; i++) {
    if (numbers[i] == 0)
    numOfZero++;
    }
    int small = numOfZero;
    int big = small + 1;
    while (big < numbers.length) {
    if (numbers[small] == numbers[big]) {
    return false;
    }
    numOfGap += numbers[big] - numbers[small] - 1;
    small = big;
    big++;
    }
    return numOfZero >= numOfGap;
    }

    private static void quickSort(int[] numbers, int start, int end) {
    if (start > end)
    return;
    int i = sort(numbers, start, end);
    if (i == start) {
    quickSort(numbers, start + 1, end);
    } else if (i == end) {
    quickSort(numbers, start, end - 1);
    } else {
    quickSort(numbers, start, i - 1);
    quickSort(numbers, i + 1, end);
    }
    }

    private static int sort(int[] numbers, int left, int right) {
    int index = left;
    int target = numbers[right];
    for (int i = left; i < right; i++) {
    if (numbers[i] < target) {
    if (i != index) {
    exchangeE(numbers, index, i);
    }
    index++;
    }
    }
    exchangeE(numbers, index, right);
    return index;
    }
    }

</code></pre>

<h3>面試題四十五：圓圈中最后剩下的數(shù)字</h3>

<blockquote>
題目：從0,1,...,n-1這n個數(shù)字排成一個圓圈，從數(shù)字0開始每次從這個圓圈里刪除第m個數(shù)字，求出這個圓圈里剩下的最后一個數(shù)字。
</blockquote>

<h4>思路</h4>

<ol>
<li>使用一個環(huán)形鏈表，模擬圓圈。</li>
<li>推倒出公式，利用遞歸或循環(huán)。</li>
</ol>

<pre><code class="java">package offer;

import java.util.ArrayList;

/**

  • Created by KiSoo on 2017/2/10.
    */
    public class Offer45 {
    public static void main(String... args) {
    Utils.syso(lastRemaining(5, 3));
    }

    public static int lastRemaining(int n, int m) {
    ArrayList<Integer> array = new ArrayList<>();
    for (int i = 0; i < n; i++) {
    array.add(i);
    }
    int idx = 0;
    while (array.size() != 1) {
    idx = (idx + m - 1) % array.size();
    array.remove(idx);
    }
    return array.get(0);
    }

    public static int getM(int m, int size) {
    m = 3 + m;
    while (m > size) {
    m = m - size;
    }
    return m;
    }
    }

</code></pre>

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 題目十六：合并兩個排序的鏈表 題目描述：輸入兩個單調(diào)遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表...
    管弦_閱讀 175評論 0贊 0
  • 第1章 面試的流程 編程時應(yīng)注意的三點： 思考清楚再開始編碼； 良好的代碼命名和縮進對齊； 能夠單元測試； 現(xiàn)場面...
    codingXue閱讀 570評論 5贊 0
  • 1.把二元查找樹轉(zhuǎn)變成排序的雙向鏈表 題目： 輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。 要求不...
    曲終人散Li閱讀 3,491評論 0贊 19
  • 說明： 本文中出現(xiàn)的所有算法題皆來自牛客網(wǎng)-劍指Offer在線編程題，在此只是作為轉(zhuǎn)載和記錄，用于本人學習使用，不...
    秋意思寒閱讀 1,215評論 1贊 1
  • 人在成長的過程中，總會經(jīng)歷幾個重要的時刻，會恐慌害怕，會焦躁多慮，會欣喜亢奮，也會激動難奈，這些個瞬間，會讓我們突...
    叮咚的你閱讀 264評論 0贊 0

友情鏈接更多精彩內(nèi)容