顯示具有 leetcode 標籤的文章。 顯示所有文章
顯示具有 leetcode 標籤的文章。 顯示所有文章

應用 XOR 特性取出相字元或數字

  1. XOR 的特性, 相同的值 XOR 會變成 0
0^0=0
1^0=1
0^1=1
1^1=0

// code
int n = 0;
for (int i = 0; i < 10000; i++) {
    n ^= i;
}
for (int i = 0; i < 10000; i++) {
    if (i == 999) continue;
    n ^= i;
}
System.out.println(n); // print 999
  1. 應用: 兩個字串只有一個字元不同的時候, 可以用來找出該不同的字元為何.
class Solution {
    // ex. s = "abc", t="ab", then ch = 'c'

    public char findTheDifference(String s, String t) {
        char ch = 0;
        for (Character c: s.toCharArray()) {
            ch ^= c;
        }
        for (Character c: t.toCharArray()) {
            ch ^= c;
        }
        return ch;
    }
}

- 沒有留言:
標籤：

Explain - LeetCode 525 Contiguous Array

題目: Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1

解法:
  1. 當遇到 0 就 -1, 遇到 1 就 +1, 計算每個陣列位置的加總
  2. 最重要的概念就是: 當遇到相同的加總數字, 表示中間經歷了相同的 1 & 0.
  3. 因此解法就是:
    1. 走過所有的陣列, 計算每個位子的 count. 遇到 0 就 -1, 遇到 1 就 +1
    2. 最重要的概念是: 當過程中出現相同的 count (不管正負) 就表示過程中有相同的 0 與 1
    3. 因此解法就是一邊算與紀錄 count, 如果遇到相同的 count 就算距離, 把最長的距離記錄下來

Code
public class Solution {

    public static void main(String[] args) {
        new Solution().findMaxLength(new int[]{0,0,1,0,0,0,1,1});
    }

    public int findMaxLength(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int maxlen = 0, count = 0;
        for (int i = 0; i < nums.length; i++) {
            count = count + (nums[i] == 1 ? 1 : -1);
            if (map.containsKey(count)) { 2. 如果以前有過跟現在相同的 count, 表示過程中經歷了相同的 0 & 1
                maxlen = Math.max(maxlen, i - map.get(count)); // 3. 以此計算距離
            } else {
                map.put(count, i); // 1. 紀錄目前的 count 的位置
            }
        }
        return maxlen;
    }
}
- 沒有留言:
標籤：

leetcode easy - Contains Duplicate

 LeetCode


Code
class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);


        for ( int i = 0; i < nums.length-1; i++ ) {
            if (nums[i] == nums[i+1]) return true;
        }


        return false;
    }
} 
- 沒有留言:
標籤： ,

leetcode easy - Pascal's Triangle

LeetCode

Code

import java.util.ArrayList;
import java.util.List;


class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        for ( int i = 0; i < numRows; i++ ) {
            List<Integer> row = new ArrayList<>();
            for ( int j = 0; j <= i; j++ ) {
                if (i == 0 || i == 1 || j == 0 || i == j) {
                    row.add(1);
                    continue;
                }


                System.out.println("(" + i + "," + j + ")");
                row.add(result.get(i-1).get(j-1) + result.get(i-1).get(j));
            }
            result.add(row);
        }
        return result;
    }


} 
- 沒有留言:
標籤： ,

leetcode medium - Number of Islands

 Leetcode


Code
class Solution {
    public int numIslands(char[][] grid) {

        int count = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    clearIsland(grid, i, j);
                }
            }
        }
        return count;
    }

    private void clearIsland(char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[i].length || grid[i][j] == '0') return;


        grid[i][j] = '0';
        clearIsland(grid, i, j-1); // up
        clearIsland(grid, i, j+1); // down
        clearIsland(grid, i-1, j); // left
        clearIsland(grid, i+1, j); // right
    }

} 
- 沒有留言:
標籤： ,

leetcode medium - LRU Cache

LeetCode

Code
It will be great to implement LinkedList by myself, I use JDK LinkedList directly

class LRUCache {

    private LinkedList<Integer> list = new LinkedList<>();
    private Map<Integer, Integer> map = new HashMap<>();
    private final int cap;


    public LRUCache(int capacity) {
        this.cap = capacity;
    }


    public int get(int key) {
        Integer result = map.get(key);
        if (result == null) {
            return -1;
        } else {
            list.remove(Integer.valueOf(key));
            list.addFirst(key);
        }
        return result;
    }


    public void put(int key, int value) {
        Integer result = map.get(key);
        if (result != null) {
            list.remove(Integer.valueOf(key));
        } else {
            if (map.size() == cap) {
                map.remove(list.removeLast());
            }
        }
        list.addFirst(key);
        map.put(key, value);
     }
} 
- 沒有留言:
標籤： ,

LeetCode - Kids With the Greatest Number of Candies

 

LeetCode

Code
class Solution {
    public List<Boolean> kidsWithCandies(int[] candies, int extraCandies) {
        int max = max(candies);
        List<Boolean> result = new ArrayList<>();
        for (int i = 0; i < candies.length; i++) {
            result.add(candies[i] + extraCandies >= max);
        }
        return result;
    }
    
    private int max(int[] candies) {
        int max = 0;
        for ( int i = 0; i < candies.length; i++ ) {
            if (max < candies[i]) {
                max = candies[i];
            }
        }
        return max;
    }
}
- 沒有留言:
標籤： ,

leetcode - Shuffle the Array

 

LeetCode

Code
class Solution {
    public int[] shuffle(int[] nums, int n) {
        int[] result = new int[nums.length];
        int currentIdx = 0;
        for (int i = 0; i < n; i++) {
            result[currentIdx] = nums[i];
            result[currentIdx+1] = nums[i+n];
            currentIdx += 2;
        }
        return result;
    }
}
- 沒有留言:
標籤： ,

leetcode - Running Sum of 1d Array

 

LeetCode

Code
class Solution {
    public int[] runningSum(int[] nums) {
        int[] result = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            if (i == 0) {
                result[i] = nums[i];
            } else {
                result[i] = result[i-1] + nums[i];
            }
        }
        return result;
    }
}
- 沒有留言:
標籤： ,
訂閱： 文章 (Atom)

別名演算法 Alias Method

 題目 每個伺服器支援不同的 TPM (transaction per minute) 當 request 來的時候, 系統需要馬上根據 TPM 的能力隨機找到一個適合的 server. 雖然稱為 "隨機", 但還是需要有 TPM 作為權重. 解法 別名演算法...